第5章の練習，投票

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

整数を素因数分解する。
一般の方程式の整数解を求める
将棋の必勝手を求める
数独パズルを解く
路線図の最短経路を求める

100番目のフィボナッチ数 fib(100)は?

偶数
奇数

スピード競争

load("./bench.rb")
load("./fib.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

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

進捗状態の確認

fibl6の表示までできた時点で投票してください．
Y軸を対数スケールにしてfibrの表示ができた
fibrとfiblの表示ができた
まだ

行列の固有値は

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

手計算で答えることを想定していますが，Mathematicaが使える人は，

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

で計算することもできます．

国語辞典で先にくるのは?

しょうほう
しようほう
じょうほ
じょうほう
ショー

単純整列法

simplesort.rb

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 index_to_x(i)
  i * 30 + 60
end

def index_to_y(i)
  400
end

def person16()
  a = Array.new(16)
  for i in 0..15
    a[i] = Person.new()
    a[i].x = index_to_x(i)
    a[i].y = index_to_y(i)
    a[i].height = rand(60) + 40
  end
  a
end

tmp = a[i]
a[i] = a[k]
a[k].move(index_to_x(i), index_to_y(i)) 
a[k] = tmp
tmp.move(index_to_x(k), index_to_y(k))

単純整列法のアニメーション

animated_simplesort.rb


include(Komaba::MiniStar)

def min_index(a, i)
  min = i 
  for j in i..(a.length()-1)
    if a[j] < a[min]
      min = j
    end
  end
  min
end

def simplesort(a)
  for i in 0..(a.length()-1)
    k = min_index(a, i)
    a[k].flash(0.5)
    tmp = a[i]
    a[i] = a[k]
    a[k].move(index_to_x(i), index_to_y(i)) 
    a[k] = tmp
    tmp.move(index_to_x(k), index_to_y(k)) 
  end
  a
end

def index_to_x(i)
  i * 30 + 60
end

def index_to_y(i)
  400
end

def person16()
  a = Array.new(16)
  for i in 0..15
    a[i] = Person.new()
    a[i].x = index_to_x(i)
    a[i].y = index_to_y(i)
    a[i].height = rand(60) + 40
  end
  a
end

実行

a=person16()
simplesort(a)

消す　

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

併合並列法

def is_even(x)
  x%2 == 0
end
def merge(a,b)
  c = Array.new(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
  if ia < a.length()
    for i in ia..(a.length() - 1)
      c[ic] = a[i]
      ic = ic + 1
    end
  else
    if ib < b.length()
      for i in ib..(b.length() - 1)
        c[ic] = b[i]
        ic = ic + 1
      end
    end
  end
  c
end

def mergesort(a)
  n = a.length()
  from = Array.new(n)
  for i in 0..(n-1)
    from[i] = [ (a[i]) ]
  end
  while n > 1
    to = Array.new((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

併合並列法(アニメーション)

animated_mergesort.rb

include(Komaba::MiniStar)

def mergesort(a)
  n = a.length()
  from = Array.new(n)
  for i in 0..(n-1)
    from[i] = [a[i]]
  end
  while n > 1
    to = Array.new((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

def merge(a, b)
  for i in 0..(a.length() - 1)
    a[i].flash(0.5, [1, 0, 0])
  end
  for i in 0..(b.length() - 1)
    b[i].flash(0.5, [0, 0, 1])
  end
  c = Array.new(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]
      move_smaller(c[ic], ic - ia)
      ia = ia + 1
      ic = ic + 1
    else
      c[ic] = b[ib]
      move_smaller(c[ic], ic - (a.length() + ib))
      ib = ib + 1
      ic = ic + 1
    end
  end
  if ia < a.length()
    for i in ia..(a.length() - 1)
      c[ic] = a[i]
      move_smaller(c[ic], ic - i)
      ic = ic + 1
    end
  else
    if ib < b.length()
      for i in ib..(b.length() - 1)
        c[ic] = b[i]
        move_smaller(c[ic], ic - (a.length() + i))
        ic = ic + 1
      end
    end
  end
  c
end

def is_even(n)
  n % 2 == 0
end

def index_to_x(i)
  i * 30 + 60
end

def next_y(person)
  if person.y == 400
    200
  else
    400
  end
end

def move_smaller(person, dx)
  person.move(person.x + dx * 30, next_y(person))
end

def person16()
  a = Array.new(16)
  for i in 0..15
    a[i] = Person.new()
    a[i].x = index_to_x(i)
    a[i].y = 400
    a[i].height = rand(60) + 40
  end
  a
end

実行

a=person16()
mergesort(a)

消す　

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

併合整列法(再帰)

mergesort_rec.rb

def mergesort(a)
  submergesort(a,0,a.length())
end

def submergesort(a,i,n)
  if n<2
    if n==0
      [ ]
    else
      [ (a[i]) ]
    end
  else
    merge(submergesort(a,i,n/2),submergesort(a,i+n/2,n-n/2))
  end
end

併合整列法(再帰)アニメーション

animated_mergesort_rec.rb

include(Komaba::MiniStar)

def merge(a, b)
  for i in 0..(a.length() - 1)
    a[i].flash(0.5, [1, 0, 0])
  end
  for i in 0..(b.length() - 1)
    b[i].flash(0.5, [0, 0, 1])
  end
  c = Array.new(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]
      move_smaller(c[ic], ic - ia)
      ia = ia + 1
      ic = ic + 1
    else
      c[ic] = b[ib]
      move_smaller(c[ic], ic - (a.length() + ib))
      ib = ib + 1
      ic = ic + 1
    end
  end
  if ia < a.length()
    for i in ia..(a.length() - 1)
      c[ic] = a[i]
      move_smaller(c[ic], ic - i)
      ic = ic + 1
    end
  else
    if ib < b.length()
      for i in ib..(b.length() - 1)
        c[ic] = b[i]
        move_smaller(c[ic], ic - (a.length() + i))
        ic = ic + 1
      end
    end
  end
  c
end

def mergesort(a)
  submergesort(a,0,a.length())
end

def submergesort(a,i,n)
  if n<2
    if n==0
      []
    else
      [a[i]]
    end
  else
    merge(submergesort(a,i,n/2),submergesort(a,i+n/2,n-n/2))
  end
end

def index_to_x(i)
  i * 30 + 60
end

def next_y(person)
  if person.y == 400
    200
  else
    400
  end
end

def move_smaller(person, dx)
  person.move(person.x + dx * 30, next_y(person))
end

def person16()
  a = Array.new(16)
  for i in 0..15
    a[i] = Person.new()
    a[i].x = index_to_x(i)
    a[i].y = 400
    a[i].height = rand(60) + 40
  end
  a
end

実行

a=person16()
mergesort(a)

消す　

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

クイックソート

qsort.rb

def quick_sort(a)
  qsort(a, 0, a.length()-1)
end

def qsort(a, from, to)  
  if from < to
    pivot = (from + to) / 2
    med = a[pivot]
    l = from
    r = to  
    while l <= r do
      while a[l] < med
        l = l + 1
      end
      while a[r] > med
        r = r - 1
      end
      if l <= r
        tmp = a[l]
        a[l] = a[r]
        a[r] = tmp
        l = l + 1
        r = r - 1
      end
    end
    qsort(a, from, r)
    qsort(a, l, to)
  end
  a
end

クイックソート(アニメーション)

include(Komaba::MiniStar)

def quick_sort(a)
  qsort(a, 0, a.length()-1)
end

def qsort(a, from, to)  
  if from < to
    pivot = (from + to) / 2
    med = a[pivot]
    med.flash(1.5)
    l = from
    r = to  
while l <= r do
      while a[l] < med
        l = l + 1
      end
      while a[r] > med
        r = r - 1
      end
      if l <= r
        tmp = a[l]
        a[l] = a[r]
        a[r].move(index_to_x(l), index_to_y(l)) 
        a[r] = tmp
        tmp.move(index_to_x(r), index_to_y(r))
        l = l + 1
        r = r - 1
      end
    end
    qsort(a, from, r)
    qsort(a, l, to)
  end
  a
end
def index_to_x(i)
  i * 30 + 60
end

def index_to_y(j)
  400
end

def person16()
  a = Array.new(16)
  for i in 0..15
    a[i] = Person.new()
    a[i].x = index_to_x(i)
    a[i].y = index_to_y(i)
    a[i].height = rand(60) + 40
  end
  a
end

実行

a=person16()
quick_sort(a)

消す　

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

◆アニメはわかりやすかったか？

わかりやすかった
何とか理解できた
全然わからなかった

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

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

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 min_index(a, i)
  min = i 
  for j in i..(a.length()-1)
    if a[j] < a[min]
      min = j
    end
  end
  min
end

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(10000,100)