Top | INDEX | UP

コンピュータ概論 第07回


第06回の Q & A


第06回(続)

問13: 1 から n までの間にある素数を列挙するプログラムを作ってみましょう。 n はプログラム中に書き込むことにして、とりあえず 100 とします。

# いわゆる「エラトステネス(Eratosthenes)のふるい」による計算                              
n = 100                                                                    
                                                                         
a = [false, false]     # 0,1 は素数ではない(合成数である)              
for i in 2 .. n do     # 2 から n まで順にチェックする                     
  if a[i] == nil       # a[i] が素数か合成数か未チェックである           
    a[i] = true        # i は素数である、と a[i] に記録する                 
    k = 2*i            # ↑                                                
    while k <= n do    # ↑                                                
      a[k] = false     # 素数 i の倍数 k は合成数である、と a[k] に記録する  
      k += i           # ↓                                                    
    end                # ↓                                                    
  end                                                                        
end                                                                            
                                                                           
for i in 0 .. n do     # i を 0 から n まで動かしたとき                   
  if a[i]              # もし a[i] が true である(つまり i が素数である)   
    puts i             # ならば i を表示する                                  
  end                                                                        
end                                                                        
------------------------------------------------------------------------------------------
n = 10 の場合 (N -> nil, T -> true, F -> false)

      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, N, N, N, N, N, N, N, N, N, ...]

i = 2, a[i] == nil
      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, T, N, N, N, N, N, N, N, N, ...]
a -> [F, F, T, N, F, N, F, N, F, N, F, ...]

i = 3, a[i] == nil
      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, T, T, F, N, F, N, F, N, F, ...]
a -> [F, F, T, T, F, N, F, N, F, F, F, ...]

i = 4, a[i] == false != nil
      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, T, T, F, N, F, N, F, F, F, ...]

i = 5, a[i] == nil
      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, T, T, F, T, F, N, F, F, F, ...]

i = 6, a[i] == false != nil
      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, T, T, F, T, F, N, F, F, F, ...]

i = 7, a[i] == nil
      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, T, T, F, T, F, T, F, F, F, ...]

i = 8, a[i] == false != nil
      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, T, T, F, T, F, T, F, F, F, ...]

i = 9, a[i] == false != nil
      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, T, T, F, T, F, T, F, F, F, ...]

i = 10, a[i] == false != nil
      0  1  2  3  4  5  6  7  8  9  10
a -> [F, F, T, T, F, T, F, T, F, F, F, ...]
------------------------------------------------------------------------------------------

問14: 1 から n までの間にある素数の個数を列挙するプログラムを作ってみましょう。 n はプログラム中に書き込むこととし、100,1000,10000,10000 と変更して実行してみましょう。
n = 100                # 100,1000,10000,10000 と変更してみる
a = [false, false]     # 0,1 は素数ではない(合成数である)                      
for i in 2 .. n do     # 2 から n まで順にチェックする                          
  if a[i] == nil       # a[i] が素数か合成数か未チェックである               
    a[i] = true        # i は素数である、と a[i] に記録する                  
    k = 2*i            # ↑                                                    
    while k <= n do    # ↑                                                      
      a[k] = false     # 素数 i の倍数 k は合成数である、と a[k] に記録する   
      k += i           # ↓                                                     
    end                # ↓                                                    
  end                                                                             
end                                                                            
                                                                               
counter = 0                                                                     
for i in 0 .. n do     # i を 0 から n まで動かしたとき                       
  if a[i]              # もし a[i] が true である(つまり i が素数である)    
    counter += 1       # ならば counter を1増やす                                 
  end                                                                                
end                                                                                 
                                                                                   
puts counter           # 0 から n までの間に存在する素数の数                 

問15(発展課題): 問13,14 のプログラムをより効率的にしてみましょう。
例:

問16: 配列を利用して問4の fib1 を効率化してみましょう。
ヒント: fib1 では同じ計算を何度も繰り返しています。

memory = [0,1]   # 定義より fib4(0) = 0, fib4(1) = 1 である              
                                                                            
def fib4(m, n)   # 一度計算した値は配列 m に記憶しておいて再利用する           
  if m[n] == nil                         # まだ fib4(n) が未計算であれば   
    m[n] = fib4(m, n-1) + fib4(m, n-2)   # 計算して配列 m に記憶する     
  end                                                                       
  return m[n]                            # 計算済みの値を返す              
end                                                                      
                                                                         
for n in 0 .. 5        # 上限を 10, 15, 20, 25, 30 と大きくして           
  puts fib4(memory,n)  # fib1 と計算時間を比較してみましょう                  
end                                                                        

絶対値・整数への丸め

以前に触れておくべき項目でしたが、おそまきながら。以下で y は整数もしくは浮動小数点数です。

y.abs絶対値
y.ceil整数への丸め(天井)
y.floor整数への丸め(床)
y.round整数への丸め(四捨五入)
y.truncate整数への丸め(切り捨て)
p = -3.14
puts p.abs
puts p.ceil
puts p.floor
puts p.round
puts p.truncate
puts (-3.14).abs
puts (-3.14).ceil
puts (-3.14).floor
puts (-3.14).round
puts (-3.14).truncate
def out(i)
  printf("%f %f %f %f %f %f\n", i, i.abs, i.ceil, i.floor, i.round, i.truncate)
end

for n in [1.9, 1.1, -1.1, -1.9]
  out(n)
end

問17: 浮動小数点数 x を入力したときにその abs, ceil, floor, round, truncate を表示するプログラムを考えてみましょう。

x = gets.to_f
printf("%f %f %f %f %f\n", x.abs, x.ceil, x.floor, x.round, x.truncate)

数学関数

いくつかの数学的な関数と定数が定義済みです。詳細については オンラインマニュアル を参照してください。

acos(x)ラジアン単位での逆三角関数
asin(x)ラジアン単位での逆三角関数
atan(x)ラジアン単位での逆三角関数
cos(x)ラジアン単位での三角関数
sin(x)ラジアン単位での三角関数
tan(x)ラジアン単位での三角関数
exp(x)指数関数 ex
log(x)自然対数
log10(x)常用対数
sqrt(x)平方根 √x
E自然対数の底 2.718281828...
PI円周率 3.1415926...
include Math   # 数学関数を利用するときの「おまじない」

printf("PI=%f, E=%f\n", PI, E)
x = PI/4
printf("x=%f, sin(x)=%f, cos(x)=%f, tan(x)=%f\n", x, sin(x), cos(x), tan(x))
x = 10
printf("x=%f, exp(x)=%f, log(x)=%f, log10(x)=%f, sqrt(x)=%f\n",
       x, exp(x), log(x), log10(x), sqrt(x))              

問18: 浮動小数点数 x を入力すると sin(x) + cos(x) を表示するプログラムを考えてみましょう。

include Math

x = gets.to_f
printf("%f\n", sin(x)+cos(x))

問19: 浮動小数点数 x を入力すると log(x) + exp(x) を表示するプログラムを考えてみましょう。 x が負値のときはどうなるでしょうか?

include Math

x = gets.to_f
printf("%f\n", log(x)+exp(x))

問20: 整数 n を入力すると tan(PI/n) を表示するプログラムを考えてみましょう。

include Math

n = gets.to_i
printf("%f\n", tan(PI/n))

問21: 整数 n を入力すると tan(PI/n) と atan(tan(PI/n) を表示するプログラムを考えてみましょう。

include Math

n = gets.to_i
z = PI/n
x = tan(z)
y = atan(x)
printf("%f %f %f %f\n", z, x, y, z-y)

ユークリッド(Euclide)の互除法

整数 a, b に対して

といいます。もうすこし厳密に定義しますと
a と b の最大公約数 = max { k | k は a を割り切る かつ k は b を割り切る }
a と b の最小公倍数 = min { k | a は k を割り切る かつ b は k を割り切る かつ k > 0 }

問22: 最大公約数を計算する関数 gcd(a,b) を定義してみましょう。

...              # 必要に応じて補助関数を定義してもよい(以後とくに明記しない)

def gcd(a,b)
  ....           # ここを考える
  return c       # c は a,b の最大公約数
end

a = 1234567
b = 7654321
printf("gcd(%d,%d)=%d\n", a, b, gcd(a,b))

問23: 最小公倍数を計算する関数 lcm(a,b) を定義してみましょう。

def lcm(a,b)
  ....           # ここを考える
  return c       # c は a,b の最小公倍数
end

a = 1234567
b = 7654321
printf("lcm(%d,%d)=%d\n", a, b, lcm(a,b))

問24: 整数 a, b に対して m a + n b = gcd(a,b) となる m,n が必ず存在します。 この m,n を計算する関数 egcd を定義してみましょう。

def egcd(a,b)
  ...             # ここを考える
  return [m,n,c]   # c は a,b の最小公倍数で a*m+b*n=c となっている
end

a = 1234567
b = 7654321
v = egcd(a,b)
printf("%d*%d+%d*%d=%d)=%d\n", a, v[0], b, v[1], v[2])