第4章の練習，投票

繰り返しによる和の定義

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

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

def divisible(x,y)
  x%y == 0
end
def gd_loop(k,n)
  while !divisible(k,n)
    n=n-1
  end
  n
end

次の結果は何?

gd_loop(1234567,1234566)

3
11
127
9721
11111

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

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

約数の和

def divisible(x,y)
  x%y == 0
end
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

条件を満たす値を探す

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

def gd(k,n)
  if divisible(k,n)
    n
  else
    gd(k,n-1)
  end
end

練習

素数とは、1 と自分自身しか約数がないような数である。上で定義した関数 sod を使って 2 以上の整数 n が素数のときにのみ true, そうでないときに false となるような関数 prime(n) を定義せよ。(n が 1 の場合は考えなくてよい。つまり、prime(1) の答は true でも false でもよいとする。)
n個からk個を選ぶ組み合わせ数 nCkを求める combination(n,k)を定義せよ(標準テキスト練習4.2)

進捗状況の確認

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

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

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

言葉探し

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

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

練習

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
```
となることを確認してください．

練習

自分の好きな図を描いてみてプログラムと実行結果の画面を 11/11の課題，質問に書き込みなさい．第3章の最後にある図でも良いし，自分で工夫して考えた図でも良い．
途中でiMac端末の画面を取り込んでpng形式のファイルに変換する必要がある．この方法は, はいぱーワークブック「22.4.3.3グラブ」に書いてあるので，参照すること．はいぱーワークブックにあるように，スクリーン全体をキャプチャーしたり，選択部分だけをキャプチャーする分には問題ないようだが，ウインドウを選択してキャプチャーするとうまくいかないようだ．
CFIVEの掲示板に画像を貼る方法は，FAQ「CFIVE掲示板機能」の「掲示板の本文中に画像を張り付けたいのですがどうすればよいですか？」にある(「#ref(ファイル名)のファイル名には拡張子(.png, .jpeg, .gif)はつけないことに注意)．練習のために，テスト用掲示板に書き込むと良い．
ほかに，講義で用いた練習のうちで自分が解いたプログラムとその説明，第6回の講義の感想，改善意見，それ以外の教科書の練習問題を書いても良い．
12/1(火)までに投稿された作品は12/2(水)の講義の際にコンテスト(相互評価)を開催する．

昨年度の作品

昨年度の作品が11/12の課題にある．

ヒント

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

include Math
def make1d(n)
  a=Array.new(n)
  for i in 0..n-1
    a[i]=0
  end
  a
end
def make2d(h,w)
  a=Array.new(h)
  for i in 0..h-1
    a[i]=make1d(w)
  end
  a
end
def make3d(h,w,c)
  a=Array.new(h)
  for i in 0..h-1
    a[i]=make2d(w,c)
  end
  a
end
def show_color_picture()
  a=make3d(50,50,3)
  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

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