問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, ...]
------------------------------------------------------------------------------------------
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)
整数 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])