package j1.lesson09;
import java.io.*;
/**
* 課題0903 - 解答例.
* @author s.arakawa
* @version $Id: FibonacciOpt_java.rps,v 1.1 2006/03/06 12:56:15 java2005 Exp $
*/
public class FibonacciOpt {
/** メソッドを起動した回数を記憶する。 */
static int count;
/**
* コンソールから0以上の整数 k を入力させ、フィボナッチ数列の第 k 項を表示するプログラム。
* ただし、フィボナッチ数列の計算は通常の再帰メソッドで実装すると非常に計算量が多くなるので、
* ある程度簡単な計算方法で算出できるようにする。
* 具体的には演習の環境で、第46項を5秒以内に計算できること。
* @param args 無視される
* @throws IOException 入力時に例外が発生した場合
*/
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("0以上の整数を入力：");
int k = Integer.parseInt(reader.readLine());
if (k < 0) {
System.out.println("0以上の整数を入力してください");
}
else {
count = 0;
System.out.println("fibonacci(" + k + ") = " + fibonacci(k));
System.out.println("起動回数は" + count + "回");
}
}
/**
* 与えられた引数に対して、フィボナッチ数列の第 k 項を返す。
* フィボナッチ数列 fib(k) は次のように定義できる。
* <pre>
* fib(0) = 0
* fib(1) = 1
* fib(k) = fib(k-1) + fib(k-2) (k > 1)
* </pre>
* @param k 計算するフィボナッチ数列の項
* @return フィボナッチ数列の第 k 項
*/
public static int fibonacci(int k) {
return fastFib(k, 0, 1);
}
/**
* <b>このメソッドは課題の仕様に含まれていない</b>。
* 引数に与えられた fk0 を fib(k), fk1 を fib(k+1) として、fib(k+n)を返す。
* このメソッドは、与えられたフィボナッチ数列の n 項先の値を計算する。
* 以下のように再帰的に定義できる。
* <pre>
* fastFib(0, fib(k), fib(k+1)) = fib(k)
* fastFib(1, fib(k), fib(k+1)) = fib(k + 1)
* fastFib(n, fib(k), fib(k+1)) = fastFib(n-1, fib(k+1), fib(k+2)) (n > 1)
* = fastFib(n-1, fib(k+1), fib(k+1) + fib(k)) (n > 1)
* </pre>
* ここで、k = 0として、fib(k) = 0, fib(k+1) = 1 を代入すると、
* 以下のように与えられた n に対して高速に fib(n) が計算できる 。
* <pre>
* fastFib(0, 0, 1) = 0 = fib(0)
* fastFib(1, 0, 1) = 1 = fib(1)
* fastFib(2, 0, 1) = fastFib(1, 1, 1) = 1 = fib(2)
* fastFib(3, 0, 1) = fastFib(2, 1, 1)
* = fastFib(1, 1, 1 + 1) = 2 = fib(3)
* fastFib(4, 0, 1) = fastFib(3, 1, 1)
* = fastFib(2, 1, 1 + 1)
* = fastFib(1, 2, 1 + 2) = 3 = fib(4)
* ...
* fastFib(n, 0, 1) = ... = fib(n)
* </pre>
* ただし、n は0以上の整数である。それ以外の数が指定された場合は考慮しなくて良い。
* @param n fib(k + n) を計算するための n
* @param fk0 fib(k)
* @param fk1 fib(k+n)
* @return 与えられた fk0 を fib(k), fk1 を fib(k+1) として、fib(k+n)
*/
public static int fastFib(int n, int fk0, int fk1) {
count++;
if (n == 0) {
return fk0;
}
else if (n == 1) {
return fk1;
}
else {
return fastFib(n - 1, fk1, fk1 + fk0);
}
}
}
|