『情報科学入門 Rubyを使って学ぶ』の練習問題の解答例の他、授業スライドの練習問題の解答例や、プログラミングのポイント等を掲載します。他クラスの方の利用歓迎。改良・訂正箇所ありましたらご指摘ください。

2010/11/29

[ス]練習問題(第四章)

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

2010/11/17

[基]数列を作る(第二章)

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になる)


2次元数列(画像)を作る
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になる)


3次元数列(カラー画像)を作る
さて、今度はカラー画像を作ってみましょう。
二次元数列で、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)
だけ^^

さあ次の行に5って表示されたら成功。
違っていたらどこかでミスしてます。


☆まとめ☆

関数の定義の仕方
def [関数名]
 [関数式]
end

2010/11/14

[教]練習問題(第四章)

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




練習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

2010/11/10

[ス]練習問題(第三章)

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


  • 2次方程式ax^2+bx+c=0の実数解の個数を求めるsolutions(a,b,c). 判別式の値だけでなく、1次方程式になっている場合にも対応せよ。(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


  • 3つの異なる値x,y,zが与えられたときの中央値を求めるmedian(x,y,z). 中央値とは大きさ順に並べたときに真ん中に来る値のことである。(median.rbというファイルを作ろう)
2通り示します。
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で中身が全て0であるような1次元配列を作る関数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)を定義せよ。ただし、作られる配列の中身は全て0にせよ。
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)の距離)
             1     (d(x,y)>r)


ちょっと保留。つながりを考えると、d(x,y)の因数がxとyだけじゃダメな気がします。
まあ、[教]練習問題(第三章)の練習3.2見てください。
言ってることがわかると思います。
  • show(sphere(20))を実行して表示される画像を確かめよ。
保留