問4: (この授業では) Fibonacci 数列の定義は以下のとおりです。
def fib1(n)
if n==0
return 0
elsif n==1
return 1
else
return fib1(n-1) + fib1(n-2)
end
end
for n in 0 .. 5
puts fib1(n)
end
---------------------------------------------------------------------- fib1(5) fib1(4) + fib1(3) fib1(3) + fib1(2) + fib1(2) + fib1(1) fib1(2) + fib1(1) + fib1(1) + fib1(0) + fib1(1) + fib1(0) + fib1(1) fib1(1) + fib1(0) + fib1(1) + fib1(1) + fib1(0) + fib1(1) + fib1(0) + fib1(1) 1 + 0 + 1 + 1 + 0 + 1 + 0 +1 5 ----------------------------------------------------------------------
問5(発展課題): n を大きくしていくと計算時間はどうなるでしょうか？
問6: もっと「効率良く」Fibonacci 数列を計算する関数は定義できるでしょうか？
def fib2(n)
a = 1 # F(1)
b = 0 # F(0)
while n > 0 # n 回ループする
t = a
a += b
b = t
n -= 1
end
return b
end
for n in 0 .. 5
puts fib2(n)
end
# コメント: Ruby では a, b = a+b, a という多重代入も可能だがここでは触れない
問7: for n in 0 .. 25 くらいで fib1 と fib2 の計算時間を比較してみましょう。
問8: fib2(n) で Fn が計算できることの証明をしてみましょう。
| Vn = ( | Fn+1 | ) |
| Fn |
| R = | ( | 1 | 1 | ) |
| 1 | 0 |
| ( | Fn+1 | ) | = | ( | 1 | 1 | ) ( | Fn | ) |
| Fn | 1 | 0 | Fn-1 |
| ( | Fn+1 | ) | = | ( | 1 | 1 | ) | n |
( | F1 | ) |
| Fn | 1 | 0 | F0 |
| V0 = | ( | F1 | ) | = | ( | 1 | ) |
| F0 | 0 |
a = 1 b = 0と変数 a, b の値を代入後に a, b を(同時に) a+b, a で置き換える 計算を n 回くりかえすと a = Fn+1 , b = Fn となっている(証明終り)。
このように「アルゴリズム」が異なると計算時間などが大幅に違ってくることがあります。 したがって、ある問題を解くときにより効率的なアルゴリズムを適用するのが賢い方法です。
問9(発展課題): fib2(n) の計算には n 回ループを廻す必要がありますが、もうちょっと 頑張ると log(n) 回程度のループで済ますことが可能です。そのような関数 fib3(n) を定義してみましょう。
配列の各要素を ',' で区切り、'[' と ']' で括ると配列が生成できます。
[]
要素がゼロ個の空な配列です。
a = [3, 1, 4] puts a[0] puts a[1] puts a[2]
配列要素がすべて整数である配列 a を定義しています。
b = ['apple', 'banana', 'orange'] puts b[0] puts b[1] puts b[2]
配列要素がすべて文字列である配列 b を定義しています。
c = ['apple', 12345, 2.71828] puts c[0] puts c[1] puts c[2]
配列要素に文字列・整数・浮動小数点数が混ざっている配列 c を定義しています。
d = ["apple", [["banana", "orange"], "melon"], "kiwi"] puts d[0] # "apple" puts d[1][0][0] # "banana" puts d[1][0][1] # "orange" puts d[1][1] # "melon" puts d[2] # "kiwi" puts d[-1] # 負値は末尾から数えたインデックスと解釈されます puts d[1024] # 定義されていないインデックスに対応する配列要素は nil
配列の配列を定義しています。
オンラインマニュアル には配列についての様々なメソッドが記載されていますが、ここでは最小限に 留めます(最初から便利なメソッドを使ってしまうと勉強にならない、という 観点も含んでいます)。
| a[i] | i番目の要素 |
|---|---|
| a[i..j] | i番目からj番目までの要素(からなる配列) |
| a[i, n] | i番目からn個の要素(からなる配列)、つまり a[i, i+n-1] |
| a[i] = x | i番目に x を代入 |
| a[i..j] = b | i番目からj番目までに配列 b を代入、つまり a[i] = b[0], … a[j] = b[j-i] |
| a[i, n] = b | i番目からn個の要素に配列 b を代入、つまり a[i] = b[0], … a[i+n-1] = b[n-1] |
| a.length | 配列 a のサイズ(インデックスの最大値 + 1) |
| a.size | 配列 a のサイズ、a.length と同等 |
| a.pop | 末尾の要素の取り出し |
| a.push(x) | x を末尾に追加 |
| a.shift | 先頭の要素の取り出し |
| a.unshift(x) | x を先頭に追加 |
a = ["apple", "orange"]
puts a[0] # apple
puts a.length # 2
a[0] = "banana"
puts a[0] # banana
a.push("melon")
puts a[-1] # melon
puts a.length # 3
puts a.pop # melon
puts a.length # 2
puts a.pop # orange
puts a.length # 1
puts a.pop # banana
puts a.length # 0
問10: 月(1から12)を入力すると、その月の日数を表示するプログラムを作ってみましょう(うるう年は考えないことにします)。
# 0 1 2 3 4 5 6 7 8 9 10 11 12 a = [nil, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] m = gets.to_i puts a[m]
問11: 与えられた(要素が整数の)配列から2乗の最大値を探す関数を定義しましょう。
def m(a)
... # ここを考える
end
puts m([3, 7, 8, 1, -5, 9, 0]) # 81 が表示される
# 配列のインデックスを使って計算する
def m1(a)
m = 0 # 最大値を記録しておく変数
for i in 0 ... a.size # i を 0 から a.size - 1 まで動かす
v = a[i]*a[i]
if v > m
m = v # a[i]**2 がいままでの最大値より大きければ m の値を更新
end
end
return m
end
puts m1([3, 7, 8, 1, -5, 9, 0])
# 配列の要素を使って計算する
def m2(a)
m = 0 # 最大値を記録しておく変数
for v in a # 配列 a の各要素を変数 v に代入していく
vv = v*v
if vv > m
m = vv # vv がいままでの最大値より大きければ m の値を更新
end
end
return m
end
puts m2([3, 7, 8, 1, -5, 9, 0])
問12: 与えられた(要素が整数でサイズが等しい)配列 a, b に対して、各要素の積の和(Σa[i]b[i]) を計算する関数を定義しましょう。
def s(a,b) ... # ここを考える end a = [1,2,3,4,5] b = [5,4,3,2,1] puts s(a,b) # 35 が表示される
def s1(a,b)
sum = 0 # 総和を記録しておく変数
for i in 0 ... a.size # インデックス i を配列 a,b の全体に動かす
sum += a[i]*b[i] # 配列 a,b のi番目の要素の積を計算して sum に加える
end
return sum
end
def s2(a,b)
if a.size == 0 # a,b が空の配列であれば s2(a,b) は 0 となる
return 0
else
v = a.shift * b.shift # 配列 a,b から先頭要素(つまり a[0] と b[0])を取り出して積を計算
return v + s2(a,b) # (先頭要素を取り除いた) a,b について s2(a,b) を計算して加える
end
end
a = [1,2,3,4,5]
b = [5,4,3,2,1]
puts s1(a,b)
puts s2(a,b)
問13: 1 から n までの間にある素数を列挙するプログラムを作ってみましょう。 n はプログラム中に書き込むことにして、とりあえず 100 とします。
# いわゆる「Eratosthenes のふるい」による計算
n = 100
a = [false, false] # 0,1 は素数ではない(合成数である)
for i in 2 .. n do # 2 から n まで順にチェックする
if a[i] == nil # a[i] が素数か合成数か未チェックである
a[i] = true # i は素数である、と a[i] に記録する
k = 2*i # ↑
while k <= n do # ↑
a[k] = false # 素数 i の倍数 k は合成数である、と a[k] に記録する
k += i # ↓
end # ↓
end
end
for i in 0 .. n do # i を 0 から n まで動かしたとき
if a[i] # もし a[i] が true である(つまり i が素数である)
puts i # ならば i を表示する
end
end
------------------------------------------------------------------------------------------
n = 10 の場合 (N -> nil, T -> true, F -> false)
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, N, N, N, N, N, N, N, N, N, ...]
i = 2 == nil
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, T, N, N, N, N, N, N, N, N, ...]
a -> [F, F, T, N, F, N, F, N, F, N, F, ...]
i = 3 == nil
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, T, T, F, N, F, N, F, N, F, ...]
a -> [F, F, T, T, F, N, F, N, F, T, F, ...]
i = 4 == false != nil
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, T, T, F, N, F, N, F, T, F, ...]
i = 5 == nil
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, T, T, F, T, F, N, F, T, F, ...]
i = 6 == false != nil
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, T, T, F, T, F, N, F, T, F, ...]
i = 7 == nil
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, T, T, F, T, F, F, F, T, F, ...]
i = 8 == false != nil
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, T, T, F, T, F, F, F, T, F, ...]
i = 9 == false != nil
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, T, T, F, T, F, F, F, T, F, ...]
i = 10 == false != nil
0 1 2 3 4 5 6 7 8 9 10
a -> [F, F, T, T, F, T, F, F, F, T, F, ...]
------------------------------------------------------------------------------------------
# いわゆる「Eratosthenes のふるい」による計算
n = 100
a = [false, false] # 0,1 は素数ではない(合成数である)
for i in 2 .. n do # 2 から n まで順にチェックする
if a[i] == nil # a[i] が素数か合成数か未チェックである
a[i] = true # i は素数である、と a[i] に記録する
k = 2*i # ↑
while k <= n do # ↑
a[k] = false # 素数 i の倍数 k は合成数である、と a[k] に記録する
k += i # ↓
end # ↓
end
end
counter = 0
for i in 0 .. n do # i を 0 から n まで動かしたとき
if a[i] # もし a[i] が true である(つまり i が素数である)
counter += 1 # ならば counter を1増やす
end
end
puts counter # 0 から n までの間に存在する素数の数
問15(発展課題): 問13,14 のプログラムをより効率的にしてみましょう。
問16: 配列を利用して問4の fib1 を効率化してみましょう。
ヒント: fib1 では同じ計算を何度も繰り返しています。
memory = [0,1] # 定義より fib4(0) = 0, fib4(1) = 1 である
def fib4(m, n) # 一度計算した値は配列 m に記憶しておいて再利用する
if m[n] == nil # まだ fib4(n) が未計算であれば
m[n] = fib4(m, n-1) + fib4(m, n-2) # 計算して配列 m に記憶する
end
return m[n] # 計算済みの値を返す
end
for n in 0 .. 5 # 上限を 10, 15, 20, 25, 30 と大きくして
puts fib4(memory,n) # fib1 と計算時間を比較してみましょう
end