第5章の練習，投票

アルゴリズムのない問題は?(難問)

整数を素因数分解する。
一般の方程式(整係数多変数高次不定方程式)の整数解を求める
将棋の必勝手を求める
数独パズルを解く
路線図の最短経路を求める

定義通りに計算するフィボナッチ数

def fibr(k)
  if k==0 || k==1
    1
  else
    fibr(k-1)+fibr(k-2)
  end
end

再帰的アルゴリズムの使用(練習5.1)

fibrを使って，fib(k)>100,000となる最小のkを見つけなさい． ([Control]+[C]を押すと計算を中止できる).

再帰的アルゴリズムの使用

fibrを使って，fib(k)>10,000,000となる最小のkを見つけなさい． ([Control]+[C]を押すと計算を中止できる).

配列に要素を入れていくフィボナッチ数の計算

def fibi(k)
  f=make1d(k+1)
  f[0]=1
  f[1]=1
  for i in 2..k
    f[i]=f[i-1]+f[i-2]
  end
  f[k]
end

0から順に数え上げるフィボナッチ数の計算

def fibl(k)
  f=1
  p1=1
  for i in 2..k
    p2 = p1     #fib(i-2)
    p1 = f      #fib(i-1)
    f = p1 + p2 #fib(i)
  end
  f             #fib(k)
end

フィボナッチ数を計算する近似式

include Math
def fiba(k)
  phi=(1.0+sqrt(5))/2.0
  phi**(k+1)/sqrt(5)
end

近似式の誤差

e=|fibl(40)-fiba(40)|の大きさは? ただし，

10**(-n) = 1.0e-n

10 <= e

1 <= e < 10

0.1 <= e < 1

0.01 <= e < 0.1

e < 0.01

スピード競争

load "./fib.rb"
load "./bench.rb"
for k in 10..24
  run("fibr",k)
  run("fibl",k)
end
command("set logscale y")
for k in 10..32
  run("fibr",k)
end

実行時間から計算時間を見積もる(2)

def fibl6(k)
  f=1
  p1=1
  for i in 2..k
    p2 = p1
    p1 = f
    f = (p1 + p2)%1000000
  end
  f
end

reset()
command("unset logscale")
for m in 1..10
  run("fibl6",100000*m)
end

練習

進捗状況の確認

fibl6 の表示までできた時点で、投票してください。
Y 軸を対数スケールにして fibr の表示ができた。
A,B,Cの値を求めることができた．　
まだ

行列の固有値は

0
±1
±√2
(1±√3)/2
(1±√5)/2

A ={{1,1},{1,0}};
MatrixForm[%]
Eigenvalues[A]

単純整列法

def min_index(a,i)
  min_j=i
  for j in (i+1)..(a.length()-1)
    if a[j]< a[min_j]
      min_j=j
    end
  end
  min_j
end
def simplesort(a) 
  for i in 0..(a.length()-1)
    k = min_index(a,i) 
    v = a[i] 
    a[i] = a[k] 
   a[k] = v
  end
  a 
end

併合整列法

def merge(a,b) 
 c = make1d(a.length()+b.length()) 
 ia =0 
 ib =0 
 ic =0 
 while ia < a.length() && ib < b.length()
   if a[ia] < b[ib] 
     c[ic] = a[ia] 
     ia = ia + 1 
     ic = ic + 1
   else 
     c[ic] = b[ib] 
     ib = ib + 1 
     ic = ic + 1
   end 
  end
  while ia< a.length()
    # ここ
    # を
    # うめる
  end
  while ib< b.length()
    # ここ
    # を
    # うめる
  end
  c 
end
def is_even(x)
  x%2 == 0
end
def mergesort(a) 
  n = a.length() 
  from = make2d(n,1)
  for i in 0..(n-1)
    from[i] = [ (a[i]) ] 
  end
  while n > 1 
    to = make1d((n+1)/2) 
    for i in 0..(n/2-1)
      to[i] = merge(from[i*2], from[i*2+1]) 
    end
    if !is_even(n) 
      to[(n+1)/2-1]=from[n-1]
    end 
    from=to 
    n=(n+1)/2
  end
  from[0] 
end

merge([3,5,7], [2,4])の結果は?

[2,3,4,5,7]
[3,5,7,4,2]
[4,2,3,5,7]
[3,4,2,5,7]
[3,5,4,2,7]

演習

チェック
merge([1,3,5],[2,4]) -> [1,2,3,4,5]
merge([1,2,4],[3,5]) -> [1,2,3,4,5]

while 文の内部は何回実行される？

進捗状況の確認

simplesort も mergesort も動いたら、投票してください。
simplesort だけ。
mergesort だけ。
まだ

練習: アルゴリズムによる速度差の実測

整列の複数のアルゴリズムに対応したプログラムを作り，速度の違いを調べる
ランダムな列を作り，それを整列させてみよ．
列の長さで時間がどう変化するかをグラフを描いてみよ

グラフから，実行時間を予測する式を推定せよ

load("./randoms.rb")    # randoms(id,size,max)
load("./bench.rb")      # run(function_name, x, v)
load("./simplesort.rb") # simplesort(a)
load("./mergesort.rb")  # mergesort(a)

def compare_sort(max, step)
  for i in 1..(max/step)
    x=i*step
    a=randoms(i,x,1)
    run("simplesort", x, a)
    a=randoms(i,x,1)
    run("mergesort", x, a)
  end
end

compare_sort(2000,100)

ソートの可視化(isrbで実行)

a=person16()
simplesort(a)

for i in 0..(a.length()-1)
  a[i].hide()
end

a=person16()
mergesort(a)

for i in 0..(a.length()-1)
  a[i].hide()
end

a=person16()
quicksort(a)