第4章の練習，投票

注意

第4章のチェックは配布プログラム中のcheck.rb では prime のチェックがうまくいかないようです．とりあえずは修正版のcheck.rbを ~/algo17 にダウンロードすると直るはずです．

うまくいかない時は，古いcheck.rb をゴミ箱に入れてからダウンロードしてください．

復習:真偽値を返す関数

ファイル名: divisible.rb(新規作成)

def divisible(x,y)
   x%y==0
end

次の結果は何?

irb(main):001:0> divisible(111111111,9)

true
false
0
12345679
8

繰り返しによる和の定義

def sum_loop(n)
  s = 0
  for i in 1..n
    s = s+i
  end
  s
end

条件を満たす値を探す繰り返し

ファイル名: gd_loop.rb

def gd_loop(k,n)
  while !divisible(k,n)
    n=n-1
  end
  n
end

次の結果は何?

gd_loop(1234567,1234566)

3
11
127
9721
11111

再帰による反復計算の定義 -- 再帰による和の定義

ファイル名: sum.rb

def sum(n)
  if n>=2
    sum(n-1)+n
  else
    1
  end
end

約数の和

ファイル名: sod.rb

load("./divisible.rb")
def sod(k,n)
  if n>=2
    if divisible(k,n)
      sod(k,n-1)+n
    else
      sod(k,n-1)
    end
  else
    1
  end
end

練習

素数とは、1 と自分自身しか約数がないような数である。上で定義した関数 sod を使って 2 以上の整数 n が素数のときにのみ true, そうでないときに false となるような関数 prime(n) を定義せよ。(n が 1 の場合は考えなくてよい。つまり、prime(1) の答は true でも false でもよいとする。)
n個からk個を選ぶ組み合わせ数 nCkを求める combination(n,k)を定義せよ(教科書P. 58練習4.2)
\( \begin{eqnarray} {}_n C_k = \begin{cases} 0 & (k > n のとき) \\ 1 & (k = 0 のとき) \\ {}_{n-1} C_{k-1} + {}_{n-1} C_{k} & (それ以外) \end{cases} \end{eqnarray} \)

進捗状況の確認

prime ができた時点で投票してください。 prime(2) -> true, prime(55) -> false, prime(101)->true 位は確認すること更にcombinationができたら2を投票し直してください．

combination(5,3) -> 10
combination(10,5) -> 252

条件を満たす値を探す

ファイル名: gd.rb

load("./divisible.rb")
def gd(k,n)
  if divisible(k,n)
    n
  else
    gd(k,n-1)
  end
end

配列の作成と操作

ファイル名: make1d.rb

def make1d(n)
  a = Array.new(n)
  for i in 0..(n-1)
    a[i] = 0
  end
  a
end

ファイル名: make2d.rb

load("./make1d.rb")
def make2d(height,width)
  a = Array.new(height)
  for i in 0..(height-1)
    a[i] = make1d(width)
  end
  a
end

繰り返しによる組み合わせ数の計算

ファイル名: combination_loop.rb

def combination_loop(n,k) 
  c=make2d(n+1,n+1) 
  for i in 0..n
    c[i][0] = 1 
    for j in 1..(i-1)
      c[i][j] = c[i-1][j-1] + c[i-1][j] 
    end
    c[i][i] = 1 
  end
  c[n][k] 
end

次の結果は何?

combination_loop(40,32)

40
91390
76904685
137846538820
12641060643775

言葉探し

ファイル名: match.rb

def submatch(s,i,p,w)
  j=0
  while j< w && s[(i+j)..(i+j)]==p[j..j]
    j=j+1
  end
  j
end

def match(s,p)
  i=0
  w=p.length()
  while submatch(s,i,p,w)< w
    i=i+1
  end
  i
end

練習

matchの定義ではs中にpが必ず現れることを仮定していた．pが現れない場合に-1と答えるmatch_safe(s,p)を定義せよ
ヒント
submatchの定義は変更しないでそのまま使って良い．

def match_safe(s,p)
  i=0
  w=p.length()
  while i<=s.length()-w && submatch(s,i,p,w)< w
    i=i+1
  end
  if i<=s.length()-w
    # 見つかった時には何を返す?
  else
    # 見つからなかった時には何を返す?
  end
end

進捗状況の確認

match_safe(s,p) ができた時点で投票してください。
```
match_safe("abra","ra") -> 2
match_safe("abca","ra") -> -1
```
となることを確認してください．

第1-4章まとめ課題

自分の好きな図を描くプログラムを書いて，プログラムと実行結果の画面を第1-4章まとめ課題に投稿して下さい．第3章の最後にある図でも良いし，自分で工夫して考えた図でも良いです．
途中でiMac端末の画面を取り込んでpng形式のファイルに変換する必要があります．これには，Finderを使って，「アプリケーション」-> 「プレビュー.app」を起動して，「ファイル」->「スクリーンショットを撮る」->「選択部分」で取り込む部分を選んでから，「ファイル」->「別名で保存」でフォーマット「PNG」を選んで，適当なフォルダに保存してください．

ITC-LMSのマニュアルによると，画像ファイルの登録可能な拡張子は以下のようになっているようです．

.ai, .ani, .anim, .apng, .art, .bef, .bmf, .bmp, .bsave, .cal, .cdf, .cdr, .cgm, .cgm, .ciff, .cin, .cpc, .djvu, .dng, . dpx, .dxf, .ecw, .emf, .eps, .eva, .exr, .fits, .flic, .fpx, .gerber, .gif, .hdri, .hvif, .icer, .icns, .ico, .ics, .iges, .iges pgml, .ilbm, .jbig, .jbig2, .jng, .jpeg, .jpeg 2000, .jpeg
xr, .jpeg-hdr, .jpeg-ls, .miff, .mng, .pbm, .pcx, .pdf, .pgf, .pgm, .pict, .pict, .pictor,
.pixel, .png, .postscript, .ppm, .psd, .psp, .rad, .rgbe, .sgi, .svg, .swf, .tga, .tiff, .vml, .wbmp, .webp, .wmf, .x aml, .xar, .xar, .xbm, .xcf, .xpm

掲示板で画像を表示する方法がうまくいくかを試すには，テスト用掲示板を使ってください．こちらにだけ投稿して提出したつもりにならないようにしてください．
11/20(月)までに投稿された作品は11/22(水)の講義の際にコンテスト(相互評価)を開催します．

昨年度の作品

昨年度の作品が第1-4章まとめ課題にあります．

ヒント

一から作るのが面倒な人は，以下のプログラムの(1)の部分の穴を埋めて a[y][x]に点(x,y)でのR,G,B値からなる大きさ3の配列を入れるコードを書くので良い．

include Math
load("./make2d.rb")
def show_color_picture()
  a=make2d(50,50)
  for y in 0..49
    for x in 0..49
# 穴を埋める．
#a[y][x]にRGB値からなる大きさ3の配列(要素は0から1までの実数)を入れる
       (1)
    end 
  end
  show(a)
end

たとえば，(1)のところに

      a[y][x]=[x/49.0,1.0-y/49.0,1.0]

と入れると，

左上(x=0, y=0)の色が[Red,Blue,Green]=[0,1,1]で水色，
右上(x=49,y=0)の色が，[Red,Blue,Green]=[1,1,1]で白，
左下(x=0,y=49)の色が，[Red,Blue,Green]=[0,1,0]で青，
右下(x=49,y=49)の色が，[Red,Blue,Green]=[1,1,0]でマゼンタ

になり，その間を補間した

のような図が得られる．

ヒント

乱数を使いたい人はrand(n)で0以上n-1以下の整数が返る．

irb(main):014:0> rand(3)
=> 1
irb(main):015:0> rand(3)
=> 2
irb(main):016:0> rand(3)
=> 0

実数の乱数は rand() で0.0以上1.0以下の一様乱数が返る．

irb(main):017:0> rand()
=> 0.65583344076718
irb(main):018:0> rand()
=> 0.336235732920702
irb(main):019:0> rand()
=> 0.324077367496

実数値を整数値に変換するには，「式」の後に .to_i() をつける．

irb(main):020:0> x=2.9
=> 2.9
irb(main):021:0> x.to_i()
=> 2
irb(main):022:0> x=-2.9
=> -2.9
irb(main):023:0> x.to_i()
=> -2

四捨五入ではないので，注意が必要．

ヒント

画像ファイルをrubyの配列にするには，一旦 convertコマンドを使って，テキストエディタで見える形式にするのが楽だろう．

というPNG形式の画像ファイルがある時，

convert globe.png -compress none globe.ppm

を実行すると，以下のようなテキスト形式のファイル globe.ppm が作られる．

P3
34 42
255
246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 246 
....
246 246 246 246 246 246 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245 245

このファイル形式はPNM(Wikipedia) のように扱いやすいので，これをテキストエディタで編集して，rubyの配列の初期化の形に修正すると楽と思われる．