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

授業スライド「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

[基]数列を作る（第二章）

1次元数列を作る
試しに，a0=1,a1=2,a2=3,a3=4,a4=5という数列を作ってみましょう。
a = [1,2,3,4,5]↓
はい終わり。


以下簡単に
数列を参照する→　a↓
数列のある項を参照する→　a[2]↓　（これでa2を参照できる。3と表示されるはず）
数列のある項を書き換える→　a[2] = 10↓　（これでa2が10になる）


２次元数列（画像）を作る
Rubyでお絵描きをしてみましょう。まずはirbを終了して、isrbを起動します。
isrbの起動は、"isrb"と入力してReturnを押すだけ。
さて、isrbでは各項の要素を0〜1の数値にすることで、数列を黒〜白のモノトーン画像として出力することができます。
試しに作ってみましょうか。

b = [ [0,0,0],↓
         [1,1,1],↓
         [0,0,0] ]↓

数列の中に数列を突っ込んでるんですね。これで、二次元数列bが出来ました。
これを画像として出力してみましょう。isrb独自の関数showを使います。

show(b)↓

こうなりましたか？
これで0が黒になることがわかりましたね。
0.1や0.6なんかを要素にして画像出力してみましょう。グレーになりますよ。





二次元数列に対する操作は、ほとんど一次元数列と同じなのですが、二次元なので項数の表現が違います。
b[1][2]だったら、b数列の1行目の2列目の項、ということになります。（通常b2,1など横の座標→縦の座標と表現するものですが、Ruby上では逆です。）
そして注意してほしい点は、この行と列の数え方は、どちらも0から始まっているということ。つまり一番左上の項はb[0][0]になります。
そしてさきほどのb[1][2]は、真ん中の列の一番右の数字のことになります。

以下簡単に

数列を参照する→　b↓

数列のある項を参照する→　b[1][2]↓　（これでb2,1を参照できる。1と表示されるはず）

数列のある項を書き換える→　b[1][2] = 0.5↓　（これでb2,1が0.5になる）

３次元数列（カラー画像）を作る

さて、今度はカラー画像を作ってみましょう。

二次元数列で、0~1の数字を入れていたところに、さらにRGB数列を入れて、色を表現します。

RGB数列は以下の様になっています。

　[(Red値),(Green値),(Blue値)]

それぞれのカラー値は、0~1で表します。

主な色のRGB数列をのせます。

[1,0,0]…赤

[0,1,0]…緑

[0,0,1]…青

[1,1,0]…黄色

[0,1,1]…水色

[1,0,1]…紫

[0,0,0]…黒

[1,1,1]…白

少数を使って、自分の出したい色をうまく表現してみましょう！

では肝心のこのRGB数列の使い方を。

c = [ [ [1,0,0], [0.5,0.5,0], [0,1,0] ],↓

        [ [0.5,0,0.5], [0.5,0.5,0.5], [0,0.5,0] ],↓

        [ [0,0,1], [0,0,0.5], [0,0,0] ] ]↓

まあこんな感じで、数列の中に数列を突っ込んで、さらにRGB数列を突っ込むんですね。

これで3×3のカラー画像ができたので、

show(c)↓

で表示してみましょう。

以下簡単に

数列を参照する→　c↓

数列のある項を参照する→　c[1][2]↓　（これでc2,1を参照できる。[0,0.5,0]と表示されるはず）

数列のある項を書き換える→　c[1][2] = [0,1,1]↓　（これでc2,1が[0,1,1]になる）

以上でっす。

[基]関数を定義する（第一章）

rubyで関数を定義する方法を簡単に説明します。

次のような関数を定義したいとします。

2点(x,y),(u,v)の距離を求める関数

distance(x,y,u,v)={(x-u)^2+(y-v)^2}^(1/2)

distance(x,y,u,v)は，f(x)みたいなものですね。

ではさっそく入力に入ります。この文字が入力部分です。
（以下，returnキーを押すことを↓と示します）

まずは，数学関数（ここではルート）を使うことを宣言しましょう。

include(Math)↓

次の行に"Object"と表示されたら完了。

関数定義に入りましょう。

def distance(x,y,u,v)↓　　　←"def"は"definition"の事

  sqrt((x-u)**2+(y-v)**2)↓　 ←関数の内容（sqrt(〜)がルートだったのは覚えてる？）

end　　　　　　　　　　　　←定義終わり

次の行に"nil"って表示されたら完了です☆ﾐ

次に，定義した関数を使ってみましょう。

原点(0,0)と点(3,4)の距離を調べましょう。

入力は

distance(0,0,3,4)↓

だけ＾＾

さあ次の行に５って表示されたら成功。

違っていたらどこかでミスしてます。

☆まとめ☆

関数の定義の仕方

def [関数名]

 [関数式]

end

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

教科書「第四章・関数から計算へ」の練習問題の解答例です。




練習4.1 （素数の判定）
def  prime(n)
  sod(n,n-1) ==1   ←sod(n,k)...1〜kのうちnの約数である数の和を求める関数

end
この場合、n=1のときtrueとなる

別解

def  prime(n)

  sod(n,n) == 1+n

end

この場合、n=1のときfalseとなる

練習4.2 （組み合わせ数）
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




練習4.3 （素数の判定の改良）
def  prime2(n)
  n==1 ||  gd(n,n-1)==1
end




練習4.4 （再起と繰り返しの比較)

略

練習4.5 （RNA塩基配列の探索）

実行してみるとわかりますが、このアルゴリズムにはすごい無駄があります。

でもこれ以上がみつからないので、一応掲載しておきます。

def  rna(s)

  w=s.length()

  a=Array.new(w/3)

  i=0

  j=0

  while i<=w-3

    if s[i..(i+2)]=="AUG"

      a[j]=i

      j=j+1

    end

    i=i+1

  end

  a

end




練習4.6 （繰り返しによって値を集める）
a) def  factorial_loop(n)
     f=1
     for  i  in 1..n
       f=f*i
     end
     f
   end


b) def  power2_loop(n)

     p=1
     for  i  in 1..n
       p=p*2
     end
     p
   end

c) def  power_loop(x,n)

     p=1
     for  i  in 1..n
       p=p*x
     end
     p
   end


d) def  taylor_e_loop(x,n)
     t=1
     for  i  in 1..n
       t=t+power_loop(x,i)/factorial_loop(i)

     end
     t
   end

練習4.7 （繰り返しによって条件を満たす値を求める）
a) def  nod_loop(k,n)
     d=0

     for  i  in 1..n
       if  k%i==0
         d=d+1
       end
     end
     d
   end

b) def  nop_loop(n)
     p=0

     for  i  in 1..n
       if  prime2(n)
         p=p+1
       end
     end
     p
   end

c) def  msod_loop(n)
     m=1
     for  i  in 2..n
       if  sod(i,i)>=m
         m=sod(i,i)
       end
     end
     m
   end

練習4.8 （繰り返しによって条件を満たす値を探す）

a) load("./prime.rb")    ←素数を判定する関数（練習4.1で定義）

   def np_loop(n)

     while  !prime2(n)

       n=n+1

     end

     n

   end


b) load("./prime.rb")
   def nth_prime_loop(p,n)
     j=0　　　　　　　　　　　←jはpから何番目に大きい素数かを表す局所関数
     while  j<n
       p=np_loop(p+1)　　　←pを「元のpの次に大きい素数」に書き換える
        j=j+1
     end
     p
   end


c) def  collatz_loop(n)

     j=0

     while n!=1

       n=tnpo(n)

       j=j+1

     end

     j

   end

d) def  perfect_loop(n)

     sod(n,n-1)==n

   end

   def  next_perfect_loop(n)

     while  !perfect_loop(n)

       n=n+1

     end

     n

   end

練習4.9 （再帰的に値を集める）

a) def  factorial(n)

     if  n==1

       1

     else

       factrial(n-1)*n

     end

   end

b) def  power2(n)

     if  n==0

       1

     else

       power2(n-1)*2

     end

   end

c) def  power(x,n)

     if  n==0

       1

     else

       power(x,n-1)*x

     end

   end

d) def  taylor_e(x,n)

     if  n==0

       1

     else

       taylor_e(x,n-1)+power(x,n)/factorial(n)

     end

   end

練習4.10 （再帰的に条件を満たす値を集める）

a) def  nod(k,n)
     if  n==1
       1
     else
       if  k%n==0
         nod(k,n-1)+1
       else
         nod(k,n-1)
       end
     end
   end


b) def  nop(n)
     if  n==1
       1
     else
       if  prime2(n)
         nop(n-1)+1
       else
         nop(n-1)
       end
     end
   end


c) def  msod(n)
     if  n==1
       1
     else
       if  sod(n,n)<=msod(,n-1)
         msod(n-1)
       else
         sod(n,n)
       end
     end
   end




練習4.11 （再帰的に条件を満たす値を探す）
a) def  np(n)
     if  prime2(n)
       n
     else
       np(n+1)
     end
   end


b) def nth_prime(p,n)
     if  n==1
       np(p+1)
     else
       nth_prime(np(p+1),n-1)
     end
   end


c) def 　collatz(n)
     if   n==1
       0
     else
       collatz(tenpo(n))+1
     end
   end


d) def  perfect_loop(n)

     sod(n,n-1)==n

   end

   def  next_perfect_loop(n)

     if  perfect_loop(n)

       n

     else

       next_perfect_loop(n+1)

     end

   end

練習4.12 （配列を作る）

a) def  make3d(a,b,c)

     v=Array.new(a)
  for  i  in 0..(a-1)
    v[i]=make2d(b,c)
  end
end

b) def  makend(n,m)

     a=Array.new(m)

     if  n==1

       for  i  in 0..(m-1)

         a[i]=0

       end

     else

       for  i  in 0..(m-1)

         a[i]=makend(n-1,m)

       end

     end

     a

   end

c) def sub(d,i)

     if  i==0

       a=make1d(d[0])
     else
       a=Array.new(d[i])
       for j in 0..(d[i]-1)
         a[j]=sub(d,i-1)
       end
      end
      a
    end

   def  makearray(d)
     sub(d,(d.length()-1))
   end
 


練習4.13 （配列の並べ替え）
a) def  sub_ascending(a)　　　←補助関数。昇順になってないとこを数える
       j=0
       for  i  in 0..(a.length()-2)
         if  a[i]>a[i+1]
           j=j+1
         end
       end
       j
     end


     def  is_ascending(a)
       sub_is_ascending(a)==0
     end

b)  def swap_ascending(a,i)
　　 if a[i]>a[i+1]
　　　swap(a,i,i+1)

　 　end
　 end

c) def  swap_ascending_all(a)

      for  i  in 0..(a.length()-2)

        swap_ascending(a,i)

      end
      a

    end

d) def  swapsort(a)

      while  !is_ascending(a)

         a=swap_ascending_all(a)

      end
      a

    end




練習4.14 （Eratosthenesのなんとか）
load("./make1d.rb")
def  eratosthenes(n)
  a=make1d(n-1)
  for  i  in 0..(n-2)
    if  a[i]==0
      for  j  in (i+1)..(n-2)
        if  (j+2)%(i+2)==0
          a[j]=1
        end
      end
    end
  end
  a
end


練習4.15 （Sierpinskiの三角形）
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

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

授業スライド「03条件分岐」の練習問題の解答例です。

• ２次方程式ax^2+bx+c=0の実数解の個数を求めるsolutions(a,b,c).　判別式の値だけでなく、１次方程式になっている場合にも対応せよ。（solutions.rbというファイルを作ろう。）

def  det(a,b,c)　　　←補助関数として、判別式Dを定義
  b**2-4*a*c
end
def  solutions(a,b,c)
  if  a==0 || det(a,b,c)==0　　←"||"は「または」
    1
  else
    if  det(a,b,c)>0
      2
    else
      0
    end
  end
end

• ３つの異なる値x,y,zが与えられたときの中央値を求めるmedian(x,y,z). 中央値とは大きさ順に並べたときに真ん中に来る値のことである。（median.rbというファイルを作ろう）

２通り示します。
1)補助関数を使う
def  max(x,y)　　　　←二つの大きいほうを出す
  if x>y
    x
  else
    y
  end
end
def  min(x,y)　　  　←二つの小さいほうを出す
  if  x>y
    y
  else
    x
  end
end
def  median(x,y,z)  ←やっと本題
  if  max(x,y)<z
    max(x,y)
  else
    if  min(x,y)>z
      min(x,y)
    else
      z
    end
  end
end


2)条件式をがんばる
def  median(x,y)
  if  (y<x && x<z) || (z<x && x<y)　　　←"&&"は「かつ」
    x
  else
    if  (x<y && y<z) || (z<y && y<x)
      y
    else
      z
    end
  end
end

• 大きさnで中身が全て０であるような１次元配列を作る関数make1d(n)を定義せよ。

def  make1d(n)
  a=Array.new(n)　　←これで長さnの数列が出来る
  for  i  in 0..(n-1)
    a[i]=0
  end
end

• h行w列の配列を作るmake2d(h,w)を定義せよ。ただし、作られる配列の中身は全て０にせよ。

load("./make1d.rb")　　←make1d(n)を定義してあるファイル
def  make2d(h,w)
  a=Array.new(h)
  for  i  in 0..h-1
    a[i]=make1d(w)
  end
end

• 次の計算をする関数b(r,x,y)を定義せよ。(x,y)だけでなくrも因数となっていることに注意せよ。

　　　　　　b(x,y) =  {r-d(x,y)}/r （d(x,y)≦r）　　（d(x,y)は、原点と点(x,y)の距離）
　　　　　　　　　　　　 １　　　　　（d(x,y)＞r）


ちょっと保留。つながりを考えると、d(x,y)の因数がxとyだけじゃダメな気がします。
まあ、[教]練習問題（第三章）の練習3.2見てください。
言ってることがわかると思います。

• show(sphere(20))を実行して表示される画像を確かめよ。

保留