Javaのフィボナッチの例
Fibonacci number
– Every
number after the first two is the sum of the two preceding.
フィボナッチ数を見つけるJavaの例はほとんどありません。
1. Java 8ストリーム
1.1 Java 8では、 `Stream.iterate`を使って次のようなフィボナッチ数を生成することができます:
Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0]+ t[1]})
.limit(10)
.forEach(x -> System.out.println("{" + x[0]+ "," + x[1]+ "}"));
出力
{0,1}
{1,1}
{1,2}
{2,3}
{3,5}
{5,8}
{8,13}
{13,21}
{21,34}
{34,55}
__P.S上記の出力を見直してください。最初の値は私たちが望むものです。
1.2最終版。
Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0]+ t[1]})
.limit(10)
.map(t -> t[0])
.forEach(x -> System.out.println(x));
出力
0 1 1 2 3 5 8 13 21 34
1.3すべてのフィボナッチ数を合計する
int sum = Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0]+ t[1]})
.limit(10)
.map(t -> t[0])
.mapToInt(Integer::intValue)
.sum();
System.out.println("Total : " + sum);
出力
Total : 88
1.4コンマで結合する。
String collect = Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0]+ t[1]})
.limit(10)
.map(t -> t[0])
.map(String::valueOf)//convert to string
.collect(Collectors.joining(", "));
System.out.println("Result : " + collect);
出力
Result : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
1.5フィボナッチ数のリストを作成する関数。
package com.mkyong.concurrency;
import java.util.List;
import java.util.stream.Stream;
import static java.util.stream.Collectors.toList;
public class Fibonacci {
public static List<Integer> getFibonacci(int series) {
return Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0]+ t[1]})
.limit(series)
.map(n -> n[0])
.collect(toList());
}
public static void main(String[]args) {
List<Integer> fibonacci = getFibonacci(10);
fibonacci.forEach(x -> System.out.println(x));
}
}
出力
0 1 1 2 3 5 8 13 21 34
1.6 int型とlong型は、より大きなフィボナッチ数を格納するには不十分です。以下は、最初の百万フィボナッチ数を見つけるための `BigInteger`の例です。
package com.mkyong.concurrency;
import java.math.BigInteger;
import java.util.stream.Stream;
public class Fibonacci {
public static BigInteger getFibonacci(int series) {
return Stream.iterate(new BigInteger[]{
BigInteger.ZERO, BigInteger.ONE}, t -> new BigInteger[]{t[1], t[0].add(t[1])})
.limit(series)
.map(n -> n[1])//find, we need n[1] .reduce((a, b) -> b).orElse(BigInteger.ZERO);
}
public static void main(String[]args) {
System.out.println(Fibonacci.getFibonacci(1__000__000));
}
}
出力
1953282128707757731632014947596256332443...//208,988 digits!!!, too long to display here
2.再帰的ループ
2.1フィボナッチ数のリストを作成するためのJava再帰的ループの例。
デモだけに良い、この再帰的ループは遅いです。
Fibonacci.java
package com.mkyong.concurrency;
public class Fibonacci {
public static int fib(int n) {
if (n <= 1) return n;
else return fib(n - 1) + fib(n - 2);
}
public static void main(String[]args) {
for (int i = 0; i < 10; i++) {
System.out.println(fib(i));
}
}
}
出力
0 1 1 2 3 5 8 13 21 34
2.2どのように動作するのですか？
fib(n) = fib(n - 1) + fib(n - 2); fib(5) = fib(4) + fib(3); fib(4) = fib(3) + fib(2); fib(3) = fib(2) + fib(1); fib(2) = fib(1) + fib(0); fib(1) = 1 fib(0) = 1
3.通常のループ
3.1フィボナッチ数を簡単かつ容易に見つけるためのJavaノーマルループ。
Fibonacci.java
package com.mkyong.concurrency;
import java.math.BigInteger;
public class Fibonacci {
public static int fib(int n) {
if (n <= 1) return n;
int previous = 0, next = 1, sum;
for (int i = 2; i <= n; i++) {
sum = previous;
previous = next;
next = sum + previous;
}
return next;
}
public static BigInteger fib2(int n) {
if (n <= 1) return BigInteger.valueOf(n);
BigInteger previous = BigInteger.ZERO, next = BigInteger.ONE, sum;
for (int i = 2; i <= n; i++) {
sum = previous;
previous = next;
next = sum.add(previous);
}
return next;
}
public static void main(String[]args) {
for (int i = 0; i < 10; i++) {
System.out.println(fib(i));
}
System.out.println("---");
for (int i = 0; i < 10; i++) {
System.out.println(fib2(i));
}
System.out.println("---");
System.out.println(fib(100));//overflow
System.out.println(fib2(100));
}
}
出力
0 1 1 2 3 5 8 13 21 34 --- 0 1 1 2 3 5 8 13 21 34 --- -980107325 354224848179261915075
