続･フィボナッチ数列を生成するプログラム

前回のエントリーでは、再帰手続きを使って書いたのですが、これだとnが増えるごとに計算時間はどんどん遅くなってくるので実用に耐えないアルゴリズムであることは明白です。

今度は配列を使って、一度計算したフィボナッチ数を記憶させてやりました。

public class Fibonacci {
	
	private static long calcCount = 0;
	/**
	 * フィボナッチ数列を生成するプログラム
	 * @param args n項
	 */
	public static void main(String[] args) {
		try{
			int n = Integer.parseInt(args[0]);
			System.out.println("no     number of fibonacci  calc count");
			System.out.println("--------------------------------------");
			for(int i = 0; i < n + 1; i++){
				System.out.printf("%4d:%20d:%12d\n", i, fib(i), calcCount);
			}
		}catch(Exception e){
			e.printStackTrace();
		}	
	}
	
	private static long fib(int input){
		long[] value = new long[100];
		value[0] = 0;
		value[1] = 1;
		
		for(int i = 2; i <= input; i++){
			value[i] = value[i - 1] + value[i - 2];
		}
		calcCount++;
		return value[input];
	}
}

結果

no     number of fibonacci  calc count










































































-




































   0:                   0:           1

   1:                   1:           2

   2:                   1:           3

   3:                   2:           4

   4:                   3:           5

   5:                   5:           6

   6:                   8:           7

   7:                  13:           8

   8:                  21:           9

   9:                  34:          10

  10:                  55:          11

  11:                  89:          12

  12:                 144:          13

  13:                 233:          14

  14:                 377:          15

  15:                 610:          16

  16:                 987:          17

  17:                1597:          18

  18:                2584:          19

  19:                4181:          20

  20:                6765:          21

  21:               10946:          22

  22:               17711:          23

  23:               28657:          24

  24:               46368:          25

  25:               75025:          26

  26:              121393:          27

  27:              196418:          28

  28:              317811:          29

  29:              514229:          30

  30:              832040:          31

fib()を呼び出す回数が劇的に減り、計算時間も全然早くなりましたね。