第5章の練習,投票


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

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

フィボナッチ数(f100)は

  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

スピード競争

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

練習

自分の端末でfibr(k), fib16(k)の計算時間を実測し, にあてはまるA,B,Cの値を求めなさい

進捗状況の確認

  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]

演習

省略された部分を補って関数 merge を完成させよ。
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 文の内部は何回実行される?

配列 [3,1,4,1,5,9,2,6,5] に対して,n=9なので
  1. 1
  2. 2
  3. 3
  4. 4
  5. 5

進捗状況の確認

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

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