[ス]練習問題（第四章）

授業スライド「04関数から計算へ」の練習問題の解答例です。

• xがyで割り切れることを判定する関数 divisible(x,y) を定義せよ。

def  divisible(x,y)

  x%y==0

end

•  素数とは、1 と自分自身しか約数がないよう な数である。上で定義した関数 sod を使って n が素数のときにのみ true, そうでないときに false となるような関数 prime(n) を定義せよ。

def  prime(n)

  sod(n,n-1) ==1

end

•  n 個から k 個を選ぶ組み合わせ数 nCk を求め る combination(n,k) を定義せよ。

def  combination(n,k)
  if  k>n
    0
  else
    if  k==0
      1
    else
      combination(n-1,k-1) + combination(n-1,k)
    end
  end
end

•  関数 tnpo(n) は n が偶数なら 1/2, 奇数なら 3 倍して 1 加えた数を求めるものだった。数学 者 Collatz はどんな整数 n が与えられたときでも、この関数を使って数を変化させてゆくと、 いずれ1 になると予想した。例えば 3 から始めた場合は3⇒10⇒5⇒16⇒8⇒4⇒2⇒1 と いった具合に予想通りになっていることが確められる。そこで n から上の手順で数を変化 させて 1 になるまでの回数を collatz(n) とする。 例えば collatz(5) = 5, collatz(16) = 4 である。

A)    collatz(n) と collatz(tnpo(n)) の関係を書け。

collatz(n)=collatz(tnpo(n))+1ですね。

B)    collatz(n) を求める関数 collatz(n) を定義せよ。 

def 　collatz(n)

  if   n==1

    0

  else

    collatz(tenpo(n))+1

  end

end

• Sierpinski のカーペット   
  –n 次のカーペットは、縦横が3**n で、n-1次ののカーペットを8 枚敷き詰めて作られる。真ん中は空いている。0次のカーペットは、縦横1 の黒い正方形とする。（実際のプログラムでは、白黒が反転する。）

def  sub(a,n,x,y)
  if  n==0
    a[y][x]=1
  else
    for  i  in 0..2
      for  j  in 0..2
        if  !(i==1&&j==1)
          sub(a,n-1,x+j*3**(n-1),y+i*3**(n-1))
        end
      end
    end
  end
end


def  cantor_dust(n)
  a=make2d(3**n,3**n)
  sub(a,n,0,0)
  a
end

• Sierpinskiの三角形  –大きさn*n で、i 行j 列目がiCjを2 で割った余りになっているような配列を作る関数sierpinski(n) を定義せよ。（見易さのために白黒を逆にしている。）

def  sierpinski(n)
  a=make2d(n,n)
  a[0][0]=1
  for  i  in  1..(n-1)
    a[i][0]=1
    for  j  in  1..(n-1)
      a[i][j]=(a[i-1][j-1]+a[i-1][j])%2
    end
  end
  a
end

• match の定義ではs 中にp が必ず現われることを仮定していた。p が現われない場合に-1 と答えるmatch_safe(s,p) を定義せよ。

def  match_safe(s,p)
  i=0
  w=p.length()
  while submatch(s,i,p,w)<w && i<=s.length()-w
    i=i+1
  end
  if  i>s.length()-w
    -1
  else
    i
  end
end