課題04-1 コンビネーション#
\(n\)個の中から\(k\)個を選ぶ組み合わせの数を求めるコンビネーションを計算します。 コンビネーションは以下の式で求められます。
\[ C(n, k) = \bigg\{ \begin{array}{ll} 1 & (k = 0 \lor n = k) \\ C(n - 1, k) + C(n-1, k-1) & \mathrm{otherwise} \end{array} \]
\(n\)、\(k\)が与えられたとき、以下の条件を満たした上で、組み合わせの数を出力するプログラムを作成してください。
combination(n, k)関数を定義してください。- 再帰呼び出しを用いて 実装してください。
- \(k = 0\)もしくは\(k = n\)であれば1を返し、そうでなければ、\(C(n-1, k) + C(n-1, k-1)\)を返すこと。
- もし、\(n<k\) であれば、0を返すこと。
combination.pyというファイル名で保存してください。- コマンドライン引数で 2つの数値を受け取り、それぞれ \(n\)、\(k\) とします。
import sys
def combination(n, k):
# この中を実装してください。
pass
assert combination(4, 0) == 1, "k = 0 なら 1 通り"
assert combination(4, 4) == 1, "k = n なら 1 通り"
assert combination(5, 3) == 10, "5 個から 3 個を選ぶのは 10 通り"
assert combination(18, 3) == 816, "18 個から 3 個を選ぶのは 816 通り"
assert combination(3, 5) == 0, "n < k なら 0 通り"
n = int(sys.argv[1])
k = int(sys.argv[2])
print(f'combination({n}, {k}) = {combination(n, k)}')実行例#
python3 combination.py 18 3
combination(18, 3) = 816
python3 combination.py 18 9
combination(18, 9) = 48620
python3 combination.py 5 3
combination(18, 9) = 10課題04-2 硬貨の両替#
金額 \(a\) 円を、硬貨の種類のリスト \(c\)（例えば [1, 5, 10, 50]）で支払う方法が何通りあるかを求めます。
同じ硬貨は何枚使っても構いません。例えば 10 円を 1 円、5 円、10 円で払う方法は、「10 円 1 枚」「5 円 2 枚」「5 円 1 枚と 1 円 5 枚」「1 円 10 枚」の 4 通りです。
「先頭の硬貨を使わない場合」と「先頭の硬貨を 1 枚使う場合」に分けて考えると、次の漸化式になります。 先頭の硬貨を 1 枚使った後も、同じ硬貨をまた使えることに注意してください。
\[ \mathrm{ways}(a, c) = \bigg\{ \begin{array}{ll} 1 & (a = 0) \\ 0 & (a < 0 \ \mathrm{または}\ c \ \mathrm{が空}) \\ \mathrm{ways}(a, c[1:]) + \mathrm{ways}(a - c[0], c) & \mathrm{otherwise} \end{array} \]
以下の条件を満たすプログラムを作成してください。
ways(amount, coins)関数を定義してください。- 再帰呼び出しを用いて 実装してください。
- 終了条件は 3 つあります。金額がちょうど 0 になれば 1 通り、金額が負になるか硬貨のリストの長さが0になれば 0 通りです。
coins[1:]で先頭を除いたリスト、coins[0]で先頭の硬貨が得られます（スライス）。
- コマンドライン引数で金額（複数可）を受け取り、硬貨の種類は
[1, 5, 10, 50, 100]として、それぞれの金額の支払い方が何通りあるかを出力してください。 - ファイル名は
coin_change.pyとしてください。
import sys
def ways(amount, coins):
# ここに再帰呼び出しを用いて実装してください
pass
assert ways(10, [1, 5, 10]) == 4, "10円を 1, 5, 10 円で払う方法は 4 通り"
assert ways(15, [1, 5, 10]) == 6, "15円を 1, 5, 10 円で払う方法は 6 通り"
assert ways(100, [1, 5, 10, 50]) == 158, "100円を 1, 5, 10, 50 円で払う方法は 158 通り"
assert ways(0, [1, 5]) == 1, "0円は「何も払わない」の 1 通り"
assert ways(3, [5, 10]) == 0, "3円は 5, 10 円では払えない"
for arg in sys.argv[1:]:
amount = int(arg)
print(f"{amount}円: {ways(amount, [1, 5, 10, 50, 100])} 通り")実行例#
$ python3 coin_change.py 10 100 500
10円: 4 通り
100円: 159 通り
500円: 19161 通り課題04-3 ヨセフスの問題#
\(n\) 人が円になって、1 番から順に並んでいます。 1 番から数えて \(k\) 番目の人が円から抜け、その次の人から数え直して再び \(k\) 番目の人が抜ける、ということを繰り返すと、最後に 1 人だけ残ります。 最後に残る人の番号を求めます。
例えば 5 人で 2 番目ずつ抜けるとき、抜ける順番は 2 番、4 番、1 番、5 番で、最後に 3 番の人が残ります。
人を 0 番から数えることにすると、\(n\) 人のときに最後に残る人の位置 \(J(n, k)\) は、\(n - 1\) 人のときの位置から次の漸化式で求められます（最初の 1 人が抜けた後の \(n - 1\) 人の円は、抜けた人の次を 0 番として数え直した円と同じだからです）。
\[ J(n, k) = \bigg\{ \begin{array}{ll} 0 & (n = 1) \\ (J(n - 1, k) + k) \bmod n & (n > 1) \end{array} \]
以下の条件を満たすプログラムを作成してください。
josephus(n, k)関数を定義してください。- 再帰呼び出しを用いて 実装してください。
- 返り値は 0 番から数えた位置です。表示するときは 1 を足して「何番目の人か」を出力してください。
- コマンドライン引数で \(n\) と \(k\) を受け取ってください。
- ファイル名は
josephus.pyとしてください。 - 小さい \(n\) について、紙の上で実際に人を抜いていき、プログラムの答えと合うことを確かめてみましょう。
import sys
def josephus(n, k):
# ここに再帰呼び出しを用いて実装してください（0 番から数えた位置を返す）
pass
assert josephus(1, 3) == 0, "1 人なら 0 番（1 番目）が残る"
assert josephus(5, 2) == 2, "5 人で 2 番目ずつ抜けると 0 番から数えて 2 番（3 番目）が残る"
assert josephus(7, 3) == 3, "7 人で 3 番目ずつ抜けると 3 番（4 番目）が残る"
assert josephus(6, 1) == 5, "1 番目ずつ抜ければ最後の人（6 番目）が残る"
n = int(sys.argv[1])
k = int(sys.argv[2])
print(f"{n}人で{k}番目ずつ抜けると、最後に残るのは {josephus(n, k) + 1} 番目の人です。")実行例#
$ python3 josephus.py 5 2
5人で2番目ずつ抜けると、最後に残るのは 3 番目の人です。
$ python3 josephus.py 41 3
41人で3番目ずつ抜けると、最後に残るのは 31 番目の人です。参考リンク#
課題04-4 たらい回し関数#
以下の漸化式で表されるたらい回し関数（tarai）をPythonで実装してください。
このたらい回し関数は、プログラミング言語の実行環境のベンチマークに使われることがありますが、その他の用途は特にありません。
再帰呼び出しの引数の中で、さらに再帰呼び出しをしているところが特徴です。
\[ t(x, y, z) = \bigg\{ \begin{array}{ll} y & x \leq y \\ t(t(x - 1, y, z), t(y - 1, z, x), t(z - 1, x, y)) & otherwise \end{array} \]
以下の条件を満たすプログラムを作成してください。
tarai(x, y, z)関数を 再帰呼び出しを用いて 定義してください。- ファイル名は
tarai.pyとしてください。 - 雛形では、グローバル変数
countでtaraiの呼び出し回数を数えています（グローバル変数）。引数を少し変えただけで回数が大きく変わることを確かめてください。 tarai(2, 1, 0)について、どの順に何が呼び出されるかを紙に書き出してみましょう。引数を求めるためだけに何度も再帰呼び出しが起きることが分かります。
import sys # コマンドライン引数用
import time # 時間計測用
count = 0
def tarai(x, y, z):
global count # 関数の外で定義された変数を関数内で使うために必要
count = count + 1
# ここに関数を実装してください
assert tarai(1, 2, 3) == 2, "x <= y なら y を返す"
assert tarai(3, 2, 1) == 3
assert tarai(5, 3, 1) == 5
assert tarai(10, 5, 0) == 10
def call_tarai(x, y, z):
global count # 関数の外で定義された変数を関数内で使うために必要
count = 0
start = time.time()
result = tarai(x, y, z)
end = time.time()
print(f'tarai({x}, {y}, {z}) = {result} (呼び出し回数: {count}, 経過時間: {(end - start) * 1000}ms)')
if len(sys.argv) == 1:
call_tarai(10, 5, 0)
call_tarai(10, 5, 1)
call_tarai(12, 6, 0)
else:
x = int(sys.argv[1])
y = int(sys.argv[2])
z = int(sys.argv[3])
call_tarai(x, y, z)実行例#
$ python3 tarai.py
tarai(10, 5, 0) = 10 (呼び出し回数: 343073, 経過時間: 19.308090209960938ms)
tarai(10, 5, 1) = 10 (呼び出し回数: 55229, 経過時間: 3.088235855102539ms)
tarai(12, 6, 0) = 12 (呼び出し回数: 12604861, 経過時間: 705.502986907959ms)
$ python3 tarai.py 12 9 4
tarai(12, 9, 4) = 12 (呼び出し回数: 16741, 経過時間: 0.9222030639648438ms)
$ python3 tarai.py 12 9 1
tarai(12, 9, 1) = 12 (呼び出し回数: 3455769, 経過時間: 191.81299209594727ms)
$ python3 tarai.py 11 9 1
tarai(11, 9, 1) = 11 (呼び出し回数: 663433, 経過時間: 37.43386268615723ms)参考リンク#
発展課題#
発展課題（任意） 最長共通部分列
発展課題（任意） 最長共通部分列#
難易度 ⭐⭐⭐
この課題は任意です。提出は必須ではなく、取り組まなくても不利にはなりません。余裕があれば挑戦してください。
2 つの文字列に共通して現れる部分列（順番を保ったまま文字を取り出したもの。連続していなくてもよい）のうち、最も長いものの長さを求めます。
これを最長共通部分列（LCS; Longest Common Subsequence）と呼びます。
例えば python と typhoon では y, h, o, n の 4 文字が共通しているので、答えは 4 です。
文字列の 末尾の文字 に注目すると、次の漸化式になります。
\[ \mathrm{lcs}(a, b) = \bigg\{ \begin{array}{ll} 0 & (a \ \mathrm{または}\ b \ \mathrm{が空}) \\ \mathrm{lcs}(a[:-1], b[:-1]) + 1 & (a \ \mathrm{と}\ b \ \mathrm{の末尾の文字が同じ}) \\ \max(\mathrm{lcs}(a[:-1], b), \mathrm{lcs}(a, b[:-1])) & \mathrm{otherwise} \end{array} \]
lcs(a, b)関数を 再帰呼び出しを用いて 定義してください。a[-1]で末尾の文字、a[:-1]で末尾を除いた文字列が得られます。
- コマンドライン引数で 2 つの文字列を受け取り、最長共通部分列の長さを出力してください。
- ファイル名は
lcs.pyとしてください。 - 文字列を 15 文字程度にすると、急に時間がかかるようになります。なぜ遅くなるのか、どの呼び出しが何度も繰り返されているのかを考えてみましょう。
import sys
def lcs(a, b):
# ここに再帰呼び出しを用いて実装してください
pass
assert lcs("abc", "abc") == 3, "同じ文字列なら長さそのもの"
assert lcs("abc", "xyz") == 0, "共通の文字がなければ 0"
assert lcs("python", "typhoon") == 4, "y, h, o, n の 4 文字"
assert lcs("programming", "gaming") == 6, "g, a, m, i, n, g の 6 文字"
assert lcs("ABCBDAB", "BDCABA") == 4
a = sys.argv[1]
b = sys.argv[2]
print(f"lcs({a}, {b}) = {lcs(a, b)}")実行例#
$ python3 lcs.py python typhoon
lcs(python, typhoon) = 4
$ python3 lcs.py programming gaming
lcs(programming, gaming) = 6