トップC言語入門 > アルゴリズム

アルゴリズム

1. フィボナッチ数

フィボナッチ数(Fibonacci number)とは、 イタリアの数学者レオナルド・フィボナッチにちなんで名付けられた数である。 n 番目のフィボナッチ数を Fn で表すと

    F1=1
    F2=1
    Fn=Fn-1+Fn-2
で定義される。これは、2つの初期条件を持つ漸化式である。 この数列はフィボナッチ数列と呼ばれ、最初の数項は
    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …
である。

再帰プログラム

フィボナッチ数列は再帰プログラムの説明でよく取り上げられるので、 まず、再帰を使ったプログラムを示す。

fib.c

このプログラムは大変わかりやすいが、実は、この再帰プログラムは極めて効率が悪い。 例えば、fib(7) の計算がどのように行われるかを下図に示した。

  1. まず fib(7) が fib(6) + fib(5) に展開される。
  2. fib(6) が fib(5) + fib(4)、fib(5) が fib(4) + fib(3) に展開される。
  3. fib(5) が fib(4) + fib(3)、fib(4) が fib(3) + fib(2)、… に展開される。

このように、関数コールがステップを追うごとに2倍に膨れ上がる。 例えば、f(4) は三度(2行目のfib(6),fib(5)からのコールと3行目のfib(5)からのコール) も計算される。関数コールにはオーバヘッドが伴うが、 fib(N) で N の値が大きいときは、関数コールの回数が膨大となることから、 多大な計算時間がかかる。


効率的なフィボナッチ数の求め方

効率的なフィボナッチ数の求め方を下のプログラムに示す。 fib1関数はフィボナッチ数列を配列Fに格納している。 再帰プログラムと同様に分かりやすい。 あるフィボナッチ数だけを求めるには、fib2関数でよい。 ひとつ前と二つ前の数を f1 と f2 に格納しておく。

Fibonacci.c
c:\MH\www\c01\algorithm>Fibonacci
fib(30) = 832040 時間= 46.0000000ミリ秒
fib1()  = 832040 時間=  0.0003200ミリ秒
fib2(30)= 832040 時間=  0.0001600ミリ秒

このプログラムの実行例から、 fib1, fib2関数の実行時間は再帰プログラムfib関数より、 実行時間が格段に速いことが分かる。

2. 平方根

ニュートン法平方根を求めるプログラムを以下に示す。

SquareRoot.c

3. 立方根

立方根を求めるプログラムを以下に示す。

CubicRoot.c

このプログラムの実行結果を下に示す。 計算を小数点以下6桁で計算を打ち切っているので、 計算精度も小数点以下6桁程度となっている。

c:\MH\www\c01\algorithm>CubicRoot
数字を入力      7
7.000000の立方根=1.91293119
1.91293119x1.91293119x1.91293119=7.00000010

c:\MH\www\c01\algorithm>CubicRoot
数字を入力      8
8.000000の立方根=1.99999977
1.99999977x1.99999977x1.99999977=7.99999724

33行目の 0.000001 を1桁小さい 0.0000001 に変えて実行すると、次のように、 計算精度も小数点以下7桁程度に向上している。

c:\MH\www\c01\algorithm>CubicRoot2
数字を入力      7
7.000000の立方根=1.91293119
1.91293119x1.91293119x1.91293119=7.00000010

c:\MH\www\c01\algorithm>CubicRoot2
数字を入力      8
8.000000の立方根=2.00000000
2.00000000x2.00000000x2.00000000=7.99999999

4. 円周率π

円周率πは 次のような簡単なプログラムで求めることができる。

Pi2.c

πの値を指定桁求めるプログラムを下に示す。

Pi.c

下に、実行例を示す。 120桁指定で小数点以下120桁まで 正しい結果が得られている。
c:\MH\www\c01\algorithm>pi
桁数(4の倍数)=120
n=120
0003 1415 9265 3589 7932 3846 2643 3832 7950 2884 1971 6939 9375 1058 2097 4944
5923 0781 6406 2862 0899 8628 0348 2534 2117 0679 8214 8086 5132 8230 6647
正確な値=3.1415 9265 3589 7932 3846 2643 3832 7950 2884 1971
6939 9375 1058 2097 4944 5923 0781 6406 2862 0899
8628 0348 2534 2117 0679 8214 8086 5132 8230 6647

5. 素数

素数(Prime Number)とは、1とその数自身以外に正の約数がない、1 より大きな自然数のこと。 有名な素数の求め方として、"エラトステネスのふるい" がある。 たとえば、Nまでの素数を求める場合は次のようにする。

  1. 1を消去する。
  2. 残った数の中で最小のものを残し、その倍数を消去する。 これらの消去を、最大の整数まで繰り返す。
  3. 最後に残った数がNまでの素数である。

指定された数までの素数を求めるプログラムを下に示す。 例えば 100000 までの素数を求めるとしても、瞬時に求まる。 ただし、その結果を全部表示するには時間がかかる。

prime01.c

下に、10000までの素数を求めた結果を示す。

c:\www\mcc>prime01 10000
10000までの素数:
       2       3       5       7      11      13      17      19      23      29
      31      37      41      43      47      53      59      61      67      71
      73      79      83      89      97     101     103     107     109     113
     [中略]
    9739    9743    9749    9767    9769    9781    9787    9791    9803    9811
    9817    9829    9833    9839    9851    9857    9859    9871    9883    9887
    9901    9907    9923    9929    9931    9941    9949    9967    9973