Java Fibonacci示例

ゝ一纸荒年。 2023-02-15 05:05 7阅读 0赞

![format_png][]![format_png][]

> [斐波那契数][Link 1] –前两个数字后的每个数字都是前两个数字的和。

很少有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}

*PS查看上面的输出，第一个值是我们想要的。*

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

> **注意**  
> 请使用`BigInteger`存储斐波那契数字，以避免出现溢出问题。

## 参考文献 ##

1.  [斐波那契数][Link 1]

标签： [斐波那契][Link 2] [Java][] [Java 8][] [流][Link 3]

> 翻译自: [https://mkyong.com/java/java-fibonacci-examples/][https_mkyong.com_java_java-fibonacci-examples]

[format_png]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly93d3cubWt5b25nLmNvbS93cC1jb250ZW50L3VwbG9hZHMvMjAxOC8xMS9maWJvbmFjY2lfbnVtYmVyLnBuZw?x-oss-process=image/format,png
[Link 1]: https://en.wikipedia.org/wiki/Fibonacci_number
[Link 2]: https://mkyong.com/tag/fibonacci/
[Java]: https://mkyong.com/tag/java/
[Java 8]: https://mkyong.com/tag/java-8/
[Link 3]: https://mkyong.com/tag/stream/
[https_mkyong.com_java_java-fibonacci-examples]: https://mkyong.com/java/java-fibonacci-examples/