課題06-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
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
課題06-2 フィボナッチ数列 #
以下の漸化式で定義されるフィボナッチ数列の第 \(n\) 項を求める関数 fibonacci(n) を 再帰呼び出しを用いて 実装してください（\(n\geq1\)）．
\[ \mathrm{fibonacci}(n) = \bigg\{ \begin{array}{ll} 1 & (n = 1, 2) \\ \mathrm{fibonacci}(n-1) + \mathrm{fibonacci}(n-2) & (n > 2) \end{array} \]
import sys
def fibonacci(n):
# この中を実装してください．
pass
for arg in sys.argv[1:]:
n = int(arg)
print(f'fibonacci({n}) = {fibonacci(n)}')
実行例 #
$ python3 fibonacci.py 5 10 20 30
fibonacci(5) = 5
fibonacci(10) = 55
fibonacci(20) = 6765
fibonacci(30) = 832040
課題06-3 たらい回し関数 #
以下の漸化式で表されるたらい回し関数（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} \]
import sys # コマンドライン引数用
import time # 時間計測用
count = 0
def tarai(x, y, z):
global count # 関数の外で定義された変数を関数内で使うために必要
count = count + 1
# ここに関数を実装してください
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)
参考リンク #
課題06-4 Collatzの予想 #
以下の漸化式で定義されるCollatzの予想を検証する関数 collatz(n) を 再帰呼び出しを用いて 実装してください．
ファイル名は collatz.py としてください．
\[ \mathrm{collatz}(x_{n+1}) = \bigg\{ \begin{array}{ll} x_n / 2 & (x_n \mod 2 = 0) \\ 3 x_n + 1 & (x_n \mod 2 = 1) \end{array} \]
Collatz の予想は，任意の正の整数 \(n\) に対して，この式を繰り返すと（\(n\)をどんどん大きくすると）， 有限回の操作のうちに必ず \(1\) に到達するという予想です． 証明はされておらず，いまだに未解決の問題です．
以下のcollatz関数では，引数 x に対して，Collatz の予想に従って，x が \(1\) に到達するまでの数列をリストに格納して返します．
xが1でなければ，上の式に従って \(collatz(x_{n+1})\)を計算します．
import sys
def collatz(x, list):
list.append(x)
if x != 1:
# 以下の pass の代わりに x が奇数のとき，偶数のときそれぞれの
# 処理（x / 2, 3 * x + 1）を実装して，x + 1 を求めてください
pass
for value in sys.argv[1:]:
n = int(value)
list = []
collatz(n, list)
print(f'collatz({n}) = {list} ({len(list)} steps)')
実行例 #
$ python3 collatz.py 10 15 7 30
collatz(10) = [10, 5, 16, 8, 4, 2, 1] (7 steps)
collatz(15) = [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1] (18 steps)
collatz(7) = [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] (17 steps)
collatz(30) = [30, 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1] (19 steps)