フィボナッチ数列の X0〜X49 までを表示するプログラム

Question

###実現したいこと
↓このような実行結果にしたい

発生している問題・エラーメッセージ

全てが０になってしまった。

$ javac Fibonacci.java
$ java Fibonacci
x0 = 1
x1 = 0
x2 = 0
x3 = 0
x4 = 0
x5 = 0
x6 = 0
x7 = 0
x8 = 0
x9 = 0
x10 = 0
x11 = 0
x12 = 0
x13 = 0
x14 = 0
x15 = 0
x16 = 0
x17 = 0
x18 = 0
x19 = 0
x20 = 0
x21 = 0
x22 = 0
x23 = 0
x24 = 0
x25 = 0
x26 = 0
x27 = 0
x28 = 0
x29 = 0
x30 = 0
x31 = 0
x32 = 0
x33 = 0
x34 = 0
x35 = 0
x36 = 0
x37 = 0
x38 = 0
x39 = 0
x40 = 0
x41 = 0
x42 = 0
x43 = 0
x44 = 0
x45 = 0
x46 = 0
x47 = 0
x48 = 0
x49 = 0

該当のソースコード

public class Fibonacci {
  public static void main(String[] args) {
    int[] x = new int[50];
    System.out.println("x0 = 1");

    for (int i=1; i<x.length; i=i+1) {
      int a = (int)(Math.sqrt(1/5));
      int b = 1/2 + (int)(Math.sqrt(5/4));
      int c = (int)(Math.pow(b, i));
      int d = 1/2 - (int)(Math.sqrt(5/4));
      int e = (int)(Math.pow(d, i));
      System.out.println("x" +i+ " = " +a*(c-e));
    }
  }
}

試したこと

いろいろ試したと言うと抽象的になってしまうのですが。いろいろ調べたりして実行したのですがダメでした。全くわかりません、助けてください。

補足情報（FW/ツールのバージョンなど）

PC：Mac
エディタ：Atom

Answer 1

ルートや1/2の計算をしていますが、変数はintのままで問題ないんですか？

Answer 2

普通にフィボナッチ数列の定義に従って求めればいいだけでは？

x[0] = 1;
x[1] = 1;
for (int i = 2; i < x.length; i++) {
    x[i] = x[i - 1] + x[i - 2];
    System.out.println(x[i]);
}

Answer 3

ポイントは次の２点です。

• 第50項まで求めるとintでは桁あふれする
• フィボナッチ数列を求める公式をちゃんと使う

床関数を使う公式を使いました。

static final double SQRT5 = Math.sqrt(5);
static final double GOLDEN_RATIO = (1 + SQRT5)/2.0;

static long[] fibonacci(final long limit) {
  return LongStream.rangeClosed(1,limit+1)
                   .map(i -> (long) Math.floor(Math.pow(GOLDEN_RATIO,i)/SQRT5+0.5))
                   .toArray();
}

使用例。

long[] result3 = fibonacci(49l);
System.out.println(
   LongStream.of(result3).mapToObj(String::valueOf).collect(Collectors.joining(", ","[","]"))
);

Answer 4

int の割り算の結果は int です。小数部分は切り捨てられます。
1/2 = 0.5 -> 0
1/5 = 0.2 -> 0
5/4 = 1.25 -> 1

double の割り算の結果は小数です。
1.0/2 = 0.5

int a = (int)(Math.sqrt(1.0/5))
Math.sqrt(1.0/5) は 0.4472136... です。これを (int) でキャストすると 0。
これでは正しい結果になりません。

また、int の最大値は 2147483647 なので、
x46 = 2971215073 のような値にはなりません。
int の代わりに long を使わないとだめでしょう。

すべて double で計算して、最後に (long) でキャストすると、

public class Fibonaaci {
	public static void main(String[] args) {
		for (int i = 0; i < 50; i++) {
			double a = Math.sqrt(1.0/5);
			double b = 1.0/2 + Math.sqrt(5.0/4);
			double c = Math.pow(b, i+1);
			double d = 1.0/2 - Math.sqrt(5.0/4);
			double e = Math.pow(d, i+1);
			double x = a * (c - e);
			System.out.println("x" + i + " = " + (long)x + "\t\t" + x);
		}
	}
}

double の計算は誤差が入り結果が例えば
x8 = 34 34.00000000000001 ではなく
x8 = 33 33.99999999999999 になる可能性もあります。
今回は (long)x が切り捨てでうまく行っていますが、
(long)(x + 0.1) などとしたほうが良いかもしれません。

for文の中で、sqrt や pow を何度も計算するのは無駄なので、書き直すと、

public class Fibonacci {
	public static void main(String[] args) {
		double sqrt5 = Math.sqrt(5);
		double k = 1 / sqrt5;
		double phi = (1 + sqrt5) / 2;
		double phi2 = 1 - phi;
		double powPhi = 1, powPhi2 = 1;

		for (int i = 0; i < 50; i++) {
			powPhi *= phi;
			powPhi2 *= phi2;
			double x = k * (powPhi - powPhi2);
			System.out.println("x" + i + " = " + (long)x + "\t\t" + x);
		}
	}
}