Top | INDEX | UP

コンピュータ概論 第06回


第05回の Q & A


入出力

RDE からプログラムをファイルに保存する、RDE 上でファイルからプログラムを読み込む: 実際にやってみる

コンソール入出力:

関数名 意味 備考
getsコンソールからの文字列の入力
gets.to_iコンソールからの整数の入力 本当は gets が返す文字列へ to_i メソッドを送っている
gets.to_fコンソールからの浮動小数点数の入力 本当は gets が返す文字列へ to_f メソッドを送っている
puts(obj)コンソールへの出力 ()は省略可能、最後に改行を出力
p(obj1,...) コンソールへの出力(どちらかというとデバッグ用?) ()は省略可能
print(arg1,...) コンソールへの出力 ()は省略可能
printf(format,arg,...) コンソールへのフォーマット出力 ()は省略可能、フォーマットの詳細は オンラインマニュアルを参照

演習:

s = "いろはにほへと"
i = 12345
f = 3.1415
printf("s は %s で i は %d で f は %f です。\n", s, i, f)


第05回の補足

問5(発展課題): n を大きくしていくと計算時間はどうなるでしょうか?

まず Fn の一般形を求める。 二次方程式 z2-z-1 = 0 の(異なる)2つの解を各々

とおくと という関係が成立する。したがって任意の n について Fn = (αn - βn)/√5 と表現できる。
より一般的な解法はたぶん線形代数の講義あたりで学習している(あるいはする) と思いますが、たとえば番号を1個ずらす線型写像を考えてそれを表現する行列の 冪乗の一般形を求める問題に帰着させるという方法があります。 いま考えている Fibonacci 数列の場合はその行列が
R = ( 11 )
10
ですから R の特性方程式 z2-z-1 = 0 が現れてくると。 また初期値 F0 と F1 を変更した場合も αn とβn の線形結合で Fn が表現されることも わかります。
βの絶対値は 1 未満で αは1より大きな正数であるから、n が大きくなると Fn は指数関数的に増大することになる。 また Fn と Fn-1 の比は α に「近づく」。
問4のプログラム
def fib1(n)
  if n==0
    return 0
  elsif n==1
    return 1
  else
    return fib1(n-1) + fib1(n-2)
  end
end
について fib1(n) を計算するために必要な時間を Tn とする。 大雑把に考えて Tn = Tn-1 + Tn-2 であるから、Tn は Fibinacci 数列 Fn と同様の増加傾向を辿ることになり、ほぼ αn に比例することとなる。
参考: 上図は実測値である(αn に対する比例定数 c は約 1/150000)。

問9(発展課題): fib2(n) の計算には n 回ループを廻す必要がありますが、もうちょっと 頑張ると log(n) 回程度のループで済ますことが可能です。そのような関数 fib3(n) を定義してみましょう。

Vn = ( Fn+1 )
Fn
R = ( 11 )
10
と定義したとき
( Fn+1 ) = ( 11 ) ( Fn )
Fn 10 Fn-1
すなわち Vn = R Vn-1 となる。よって
( Fn+1 ) = ( 11 ) n


( F1 )
Fn 10 F0
すなわち Vn = Rn V0 が成立する。ここで
V0 = ( F1 ) = ( 1 )
F00
さて R は対称行列であるから Rn も対称行列となる。そこで
Rn = ( anbn )
bncn
と an, bn, cn (n > 0) を定義すると a1 = 1, b1 = 1, c1 = 0 である。 さて次の式
( a2nb2n ) = R2n = Rn Rn = ( anbn )( anbn ) = ( anan+bnbn
bn(an+cn) )
b2nc2n bn cn bn cn bn(an+cn)
bnbn+cncn
を考慮すると R, R2, R4, R8, ... という R2i (i=0,1,2...)の列が次々と計算できる。 したがって n の2進数表記を nk nk-1 ... n0 (各 ni は 0 か 1 の値をとる)とすれば
Rn = R nk2k + nk-12k-1 + ... + n020 = R nk2k R nk-12k-1 … R n020
Vn = R nk2k R nk-12k-1 … R n020 V0
となる。したがって R2i (i=0,1,2...k)を次々と計算し ni が 1 だったら R2i を V0 に対して乗ずる、という操作を k 回おこなうと Vn (すなわち Fn)が求まることになる。 この「アルゴリズム」を ruby でプログラムしたものが fib3 である。
# n 回ループを廻るアルゴリズム
def fib2(n)
  a = 1; b = 0
  while n > 0
    t = a; a += b; b = t; n -= 1
  end
  return b
end

# 約 log(n) 回ループを廻るアルゴリズム
def fib3(n)
  m = n            # n をそのまま使ってよいが説明の便宜上 m という新しい変数を使う
  i = 0            # 不要な変数だが説明の便宜上用意してある
  x=1; y=0         # 初期値は V(0) の要素 F(1) と F(0)
  a=1; b=1; c=0    # R^(2^i) の要素 a,b,c が記録される変数
  while m > 0      # for i in 1 .. k と同じ     
    if m % 2 == 1  # m の2進表記の0桁目(最下位ビット)が 1 である
                   # つまり n の2進表記のi桁目が 1 である
       x2 = x; y2 = y
       x = a*x2 + b*y2
       y = b*x2 + c*y2
    end
    i += 1  # 着目する桁を1つ進める
    m /= 2  # 余りを無視し 2 で割った値で m を置き換える(右シフトする)
    # R^(2^i) の計算
    aa = a*a; bb = b*b; cc = c*c; a_c = a+c
    a = aa + bb; b *= a_c; c = bb + cc
  end
  # while ループ終了時には V(n) が計算できている
  return y
end

for i in 0 .. 15
  # i に対して幅2桁で10進表記(幅4桁で2進表記)
  # fib2(i) の値を幅4桁で10進表記
  # fib3(i) の値を幅4桁で10進表記
  printf("%2d(%4b) %4d %4d\n", i, i, fib2(i), fib3(i))
end    

第05回の続き