第5章の練習，投票

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

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

フィボナッチ数(f₁₀₀)は

1. 偶数
2. 奇数

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

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

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

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

スピード競争

• fib.rb
• bench.rb

load "./fib.rb"
load "./bench.rb"
for k in 10..30
  run("fibr",k)
  run("fibl",k)
end
command("set logscale y")
for k in 10..35
  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",1000000*m)
end

練習

load("./fib.rb")
load("./bench.rb")
run("fibr", 30)
run("fibr", 35)
run("fibl6", 10000000)

fibr(30)...finished in 0.130000 seconds.
fibr(35)...finished in 1.480000 seconds.
fibl6(10000000)...finished in 0.770000 seconds.

B5 = 1.480000 / 0.130000

B = (1.480000 / 0.130000) ** (1.0/5)
=> 1.6265359726073092

A = 1.48 / B**35
=> 5.970808931328691e-08

C = 0.770000 / 10000000
=> 7.7e-08

進捗状況の確認

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

単純整列法

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])の結果は?

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

演習

ruby check.rb ex05.rb
を実行して動作を確認します．
merge([1,3,5],[2,4]) -> [1,2,3,4,5]
merge([1,2,4],[3,5]) -> [1,2,3,4,5]

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

1. 1
2. 2
3. 3
4. 4
5. 5

進捗状況の確認

1. simplesort も mergesort も動いたら、投票してください。
2. simplesort だけ。
3. mergesort だけ。
4. まだ

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

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

  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
  

  load("./compare_sort.rb")
  compare_sort(10000,500)
  

  ---