11/8 アルゴリズムと計算量
前回までの補足
- 講義のスライド(PDF形式)は，cfiveの「情報科学(水4)」のコースの「教材」のところからダウンロード可能にしてある．講義受講者以外への再配布は許可されないので注意すること．
- cfive掲示板に，前回のスライドの練習問題に対応するプログラムがいくつか投稿されているので，参考にして欲しい．
10/25の課題について
- 締切は，11/22. 11/8 14:00 時点で提出者は2名．コメントを付けておいたので今後の参考にするように．
スライドの補足
スライドに使われたプログラム
数え上げによる平方根の計算
def square(x)
x * x
end
def sqrt1(x,delta)
n=0
while square(n * delta) < x
n = n + 1
end
n * delta
end
二分法による平方根の計算
def good(guess,x,delta)
(square(guess)-x).abs < delta
end
def sqrt2(x,delta)
low=0.0; high=x;
mid=(low+high)/2
while !good(mid,x,delta)
if square(mid) < x then
low=mid
else
high=mid
end
mid=(low+high)/2
end
mid
end
ニュートン法による平方根の計算
def f(r,x)
(r + x/r) / 2
end
def sqrt3(x,delta)
guess = x*1.0
while !good(guess,x,delta)
guess = f(guess,x)
end
guess
end
定義通りに計算するフィボナッチ数
def fib1(x)
if x==0 || x==1 then
1
else
fib1(x-1)+fib1(x-2)
end
end
0から計算するフィボナッチ数の計算
def fib2(x)
i=0; fi=1; fi1=1
while i < x
i = i+1
f2 = fi+fi1
fi = fi1
fi1 = f2
end
fi
end
0から計算するフィボナッチ数の計算
def fib2(x)
i,fi,fi1=0,1,1
while i < x
i,fi,fi1 = i+1,fi1,fi+fi1
end
fi
end
行列を用いるフィボナッチ数の計算法(3)
# 行列を用いるフィボナッチ数の計算
# ここでは行列は2次元配列で表わすことにする。
def is_even(n)
n%2 == 0
end
# 行列a,bの積
def mat_x_mat(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], a[1][0]*b[0][1] + a[1][1]*b[1][1]]]
end
# 単位行列
$unit = [[1,0],
[0,1]]
# 行列の自乗
def square(m)
mat_x_mat(m,m)
end
# 行列mのn乗
def power(m,n)
if n==0 then
$unit
elsif is_even(n) then
square(power(m, n/2))
else
mat_x_mat(power(m, n-1), m)
end
end
# フィボナッチ数のQ行列
$q_matrix = [[1,1],
[1,0]]
def fib3(n)
power($q_matrix, n)[0][0]
end
単純な最大公約数の計算
# 単純な最大公約数の計算
# y が xで割り切れるとき true
def divisible(y,x)
y % x == 0
end
# nがxとyの約のときtrue
def common_divisor(n,x,y)
divisible(x,n) && divisible(y,n)
end
# xとyの最大公約数
def gcd_simple(x,y)
n = x
while !common_divisor(n,x,y)
n = n - 1
end
n
end
ユークリッドの互助法
def euclid(x,y)
if x == 0 then
y
else
euclid(y % x, x)
end
end
単純整列法
# aのi番目とj番目を交換
def swap(a,i,j)
ai = a[i]; aj = a[j]
a[i] = aj; a[j] = ai
end
# aのi番目以降の最小の要素を見つけ、
# その添字を返す
def find_minimum(a,i)
min_value = a[i] # 暫定最小値
min_index = i # その添字
for j in (i+1)..(a.size-1)
if a[j] < min_value then
min_value = a[j] # 新たな最小値
min_index = j # を発見した
end # 場合
end
min_index # 添字を返す
end
# 本体: 先頭から順に最小要素を移動
def sort(a)
for i in 0..(a.size-1)
min_index = find_minimum(a,i)
swap(a, i, min_index)
end
a
end
単純整列法
# aのi番目とj番目を交換
def swap(a,i,j)
a[i], a[j] = a[j], a[i]
end
# aのi番目以降の最小の要素を見つけ、
# その添字を返す
def find_minimum(a,i)
# 暫定最小値とその添字
min_value, min_index = a[i],i
for j in (i+1)..(a.size-1)
if a[j] < min_value then
# 新たな最小値を発見した場合
min_value, min_index = a[j],j
end
end
min_index # 添字を返す
end
# 本体: 先頭から順に最小要素を移動
def sort(a)
for i in 0..(a.size-1)
min_index = find_minimum(a,i)
swap(a, i, min_index)
end
a
end
併合整列法
# 整列: 併合法
Tree = Struct.new(:left, :right)
def divide(a,i_min,i_max)
if i_min == i_max then
a[i_min]
else
mid = (i_min+i_max)/2
Tree.new(divide(a,i_min,mid), divide(a,mid+1,i_max))
end
end
def merge(left,right) # leftとrightを併合した配列を作る
merged = Array.new() # 結果の配列を作る
while left.size > 0 || right.size > 0 # leftかrightに要素が残っている間
merged.push( # 結果の配列の最後に
if right.size == 0 then # 右が空なら
left.shift # 左の先頭を
elsif left.size == 0 then # 左が空なら
right.shift # 右の先頭を
elsif left[0] < right[0] then # 左の先が小さければ
left.shift # 左の先頭を
else # それ以外は
right.shift # 右の先頭を
end # 追加する
)
end
merged # 結果の配列を返す
end
def merge_tree(node_or_number)
if node_or_number.instance_of?(Tree) then
merge(merge_tree(node_or_number.left),
merge_tree(node_or_number.right))
else
[node_or_number]
end
end
def merge_sort(a)
merge_tree(divide(a,0,a.size-1))
end
ビン整列法
# ビン整列法
$max = 1000
def count_occurences(a) # 値の出現回数から成る配列を作る
counts = Array.new($max, 0) # 結果を格納する配列
for i in 0..(a.size-1) # aの全要素について
counts[a[i]] = counts[a[i]]+1 # a[i]の出現回数を増やす
end
counts
end
def rebuild(a,counts) # 出現回数から配列を再構成する
i=0 # iは再構成さ出る配列の添字
for v in 0..($max-1) # 全ての値について小さい順に
for k in 0..(counts[v]-1) # 出現回数だけ
a[i] = v # aに書き込んでゆく
i = i+1
end
end
end
def bin_sort(a) # 配列aの整列は
rebuild(a, count_occurences(a)) # aをaの出現回数で再構成すること
a
end