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

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




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