フィボナッチ数列で表示したい

Question

40までの表示にしたい

1,1から始まり、40までのフィボナッチ数列を求めてint型の配列に代入し、表示したい。

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

数値が40以下までで表示したいです。

該当のソースコード

public static void main(String[] args) {
		for (int n = 1; n < 10; n++) {

			System.out.println(fibonacci(n));

		}
	}

	private static int fibonacci(int n) {

		if (n == 0) {
			return 0;
		}

		if (n == 1) {
			return 1;
		}

		return fibonacci(n - 1) + fibonacci(n - 2);
	}
}

Comments

[m.ts10806]

>コードで40以下に

この「コードで」とはどういう意味でしょうか。

[aaaajj]

ご返信ありがとうございます。
数値が40以下にという意味です。

Answer 1

純粋関数型

質問の再帰関数は副作用のない純粋関数です。しかし再帰させると計算量が増えて非効率なので、同じ純粋性を保ちながらイテレートします。int[]を使うやり方は検索するとたくさんヒットします。Java 9以上でStreamのtakeWhile()がサポートされています。

static Integer[] fibonacci09(final int limit) {
  return Stream.iterate(
                 new int[] {0,1}, t -> new int[]{t[1],t[0]+t[1]})
               .map(t -> t[1])
               .takeWhile(v -> v <= limit)
               .collect(Collectors.toList())
               .toArray(new Integer[0]);
  } 

使い方は以下のとおり。

Integer[] result = fibonacci09(40);
System.out.println(Arrays.asList(result));

ついでに、状態を持つ例。

static Integer[] fibonacci(final int limit) {
  Supplier<UnaryOperator<Integer>> genfib = () -> {
    int[] prev = new int[1]; // closure
    return x -> {
      int next = prev[0] + x;
      prev[0] = x;
      return next;
    };
  };
  return Stream.iterate(1, genfib.get())
               .takeWhile(v -> v <= limit)
               .collect(Collectors.toList())
               .toArray(new Integer[0]);
}

Answer 2

class Test {
    public static void main(String[] args) {
		int[] a = new int[41];
		a[0] = 0; a[1] = 1;
		for (int i = 2; i <= 40; i++)
			a[i] = a[i-1] + a[i-2];
		for (int i = 1; i <= 40; i++)
			System.out.println("fibonacci(" + i + ") = " +a[i]);
	}
}

追記

class Test {
	static final int N = 40;

    public static void main(String[] args) {
        int[] a = new int[N + 2];
        a[1] = 1;
		int n;
        for (n = 2; n < a.length; n++) {
            a[n] = a[n-1] + a[n-2];
			if (a[n] > N) break;
		}
        for (int i = 1; i < n; i++)
            System.out.println("fibonacci(" + i + ") = " +a[i]);
    }
}

Comments

[aaaajj]

すみませんこちらの説明不足で、数値が40以下という意味でした。

Answer 3

こんな感じになります。

  int f[]=new int[41];
  for(int i=0;i<f.length;i++){
    f[i]=fibonacci(i);
    System.out.println(""+i+":"+f[i]);
  }        

Comments

[aaaajj]

すみませんこちらの説明不足で、数値が40以下という意味でした。