CS 入門 4b クラス第11回資料 (2014.12.18)

CS 入門 4b クラス第 11 回資料 (2014.12.18)
担当: 伊知地宏
前回の問題の解答
1
[別解]
[問題 9.1]
def power_r_bench(n, k)
if k == 0
1
1. べき乗計算を時間計算量 O(log2 k) で解く再帰
関数 power r(n, k) を作りなさい．
elsif k % 2 == 0
1 + power_r_bench(n * n, k / 2)
2. 関数 power r(n, k) の呼び出し回数を計測す
る関数 power r bench(n, k) を作りなさい．
else
1 + power_r_bench(n, k - 1)
end
[解答]
end
def power_r(n, k)
if k == 0
1
elsif k % 2 == 0
power_r(n * n, k / 2)
else
power_r(n, k - 1) * n
end
end
def power_r_bench(n, k)
power_r_b_sub(n, k, 1)
ende
def power_r_b_sub(n, k, count)
if k == 0
count
elsif k % 2 == 0
power_r_b_sub(n * n, k / 2, count + 1)
else
power_r_b_sub(n, k - 1, count + 1)
end
end
1
[問題 9.2]
def e
[ [ 1, 0 ],
1. ユークリッドの互除法で最大公約数を求める再
[ 0, 1 ] ]
帰関数 gcd r(x, y) を作りなさい．
end
[解答]
def q
[ [ 1, 1 ],
def gcd_r(x, y)
if y == 0
[ 1, 0 ] ]
x
else
gcd_r(y, x%y)
end
def v0
[ 1, 1 ]
end
end
end
def is_even(x)
[問題 9.3]
x%2 == 0
end
1. フィボナッチ数を時間計算量 O(n) で解く再帰
関数 fib r(n) をファイル fib tr.rb に作りな
さい．
def matxmat(a,b)
[ [ a[0][0]*b[0][0] + a[0][1]*b[1][0],
[解答]
a[0][0]*b[0][1] + a[0][1]*b[1][1] ],
[ a[1][0]*b[0][0] + a[1][1]*b[1][0],
def fib_r(n)
a[1][0]*b[0][1] + a[1][1]*b[1][1] ] ]
fib_r_sub(n, 1, 1)
end
end
def fib_r_sub(n, fib, prev)
if n < 2
def matxvec(a,v)
[ a[0][0]*v[0] + a[0][1]*v[1] ,
a[1][0]*v[0] + a[1][1]*v[1] ]
fib
else
end
fib_r_sub(n - 1, fib + prev, fib)
end
end
def matpower(a,n)
if n==0
e
else
if is_even(n)
matsquare(matpower(a,n/2))
else
matxmat(a,matpower(a,n-1))
end
end
end
def matsquare(a)
matxmat(a,a)
2
れるので，matxmat(a,b) が呼び出されるのは k+
end
1 回となる．
def fib3(k)
qk = matpower(q,k)
vk = matxvec(qk, v0)
2k < n < 2k+1 のとき，matpower(a,n) の呼び
出し系列で matsquare(matpower(a,n/2)) が k
回呼び出され，matpower(a,n) の第 2 引数が連続
vk[1]
end
して奇数になることはないので，matxmat(a,b)
が呼び出されるのは最大で k + 1 回となり，した
がって matxmat(a,b) が呼び出されるのは最大で
行列を用いた上記のフィボナッチ数の計算アルゴリ
2k + 1 回である．
以上より，fib3(n) が示すアルゴリズムの時間計
ズムの時間計算量を求めなさい．
算量は O(k)，すなわち O(log n) となる．
[問題 9.4]
[解答]
上記アルゴリズムでは，行列の積をとる所が計算
2
今日の授業項目
量の決め手になる．再帰関数 matpower(a,n) は，
再帰呼び出しをして得た行列を関数 matxmat(a,b)
1. 再帰
で計算して関数の値を得ている．matpower(a,n)
2. ソート
が呼び出された回数より 1 回少なく matxmat(a,b)
が呼び出される．
関数
matxmat(a,b)
次回の予告
の関数定義の最初に
print(“*”) を入れて実験を行うと，* が出力される
回数は，fib3(1) で 1 回，fib3(2) で 2 回，fib3(4)
で 3 回，fib3(8) で 4 回，fib3(16) で 5 回となる．
次回の授業は第 2 演習室で行います．
1. 再帰プログラムの演習
fib3(n) の n の値が 2 倍になると * の出力される
回数が 1 つ増えるので，時間計算量は O(log n) が
予想される．
再帰関数 matpower(a,n) で，再帰呼び出しにお
いて第 2 引数の変化に注目すれば，matxmat(a,b)
の計算回数が分かる．n が偶数のときには再帰呼び
出しで n が 2 で割られ，n が奇数のときには再帰
呼び出しで n − 1 となる．
n = 2k のときには，再帰関数 matpower(a,n)
の呼び出し系列は，
matpower(a, 2k )
→ matpower(a, 2k−1 )
..
.
→ matpower(a, 2)
→ matpower(a, 1)
→ matpower(a, 0)
となり，matsquare(matpower(a,n/2)) が k 回，
matxmat(a,matpower(a,n-1)) が 1 回呼び出さ
3

Download Report