斐波那契数列(Fibonacci sequence),又称黄金分割数列,是一个非常经典的递归问题。斐波那契数列的算法描述:
斐波那契数列,一个令人着迷而又充满神秘色彩的数字序列,它以0和1作为起始,后续的每一个数字都是前两个数字的和。这个看似简单的数列,却蕴藏着自然界中无数令人惊叹的奥秘。
在自然界中,斐波那契数列无处不在,它像是一个隐形的脉络,贯穿于万物生长的每一个细节之中。你是否注意到,菠萝的果鳞排列呈现出一种特定的规律?那就是斐波那契数列!再看向日葵的种子排列,同样是斐波那契数列的完美展现。这种数列不仅在植物中有所体现,动物界也同样留下了它的足迹。比如,鹦鹉螺的螺旋生长模式,就是斐波那契数列在三维空间中的绝佳例证。下图左边图形是斐波那契数列互相镜像的螺旋线。
好了言归正传,上一篇博客我们已经介绍了不少斐波拉契数列的算法,本文我们再来补充一些。
- 算法7:利用集合框架中的Map实现斐波拉契数列的算法。
这个算法版本利用 Map 的 computeIfAbsent() 方法高效计算斐波那契数列。避免对较小的序列的重复计算。这个算法版本的思想其实与上一篇博客中【算法4: 借助一个数组列表ArrayList,前两项是0和1,从n=2项起,每一项是之前两项之和。实际上也是一种迭代算法】相似。所谓的高效是针对于上篇博客【算法1: 斐波那契数列的递归算法版本】而言的,因为这个算法在计算数列后面的项时需要多次重复计算前面所有的项。
上一篇博客:java编程 斐波拉契数列算法集锦【斐波拉契数列】【上】
package fibonacci;
/**** @author QiuGen* @description 斐波那契数列的递归算法* *** 使用 Map 的 computeIfAbsent() 方法高效计算* *** 斐波那契数列。避免对较小的序列的重复计算。* @date 2024/8/20* ***/
import java.util.HashMap;
import java.util.Map;
/*** 使用 Map 的 computeIfAbsent() 方法高效计算* 斐波那契数列。避免对较小的序列的重复计算。***/
public class FibonacciMap {private final Map<Integer,Long> map;public FibonacciMap() {map = new HashMap<>();map.put(0, 0L);map.put(1, 1L);} public long addValue(int x) {return map.computeIfAbsent(x, k -> addValue(k-1) + addValue(k-2));} public void printMap() {map.forEach((k,v)->System.out.println(v));}public static void main(String[] args) {System.out.println("***利用集合computeIfAbsent方法的递归算法***");FibonacciMap fibonacci = new FibonacciMap();for (int i = 0; i < 20; i++) {fibonacci.addValue(i);}fibonacci.printMap();}
}
例程测试结果。例程的前20项结果,也是一样的:
- 算法8:函数式编程实现斐波拉契数列算法
首先迭代生成一个包含斐波拉契数列的两项元素Stream<long[]>流
/***迭代生成斐波那契数列的无限流***/public static Stream<long[]> fibStream( ) {Stream<long[]> fibStream = Stream.iterate(new long[]{0, 1},fib -> new long[]{fib[1], fib[0] + fib[1]});return fibStream;}
用Collect收集结果,结果保存在List列表中,然后遍历打印结果。
/**用Collect收集结果**/public static void fibStreamA( ) {List<Long> lst = fibStream().map(fib -> fib[0]).limit(30) //前30项.collect(ArrayList::new, ArrayList::add,ArrayList::addAll);lst.forEach(System.out::println);}
- 算法9:函数式编程转换为LongStream用forEach打印结果的算法
前面部分产生Stream<long[]>流与算法8相同。
然后,转换为LongStream用forEach打印结果。
/**转换为LongStream用forEach打印结果**/public static void fibStreamB( ) {LongStream fibLongStream = fibStream().map(fib -> fib[0]).mapToLong(k->k).limit(30); //前30项fibLongStream.forEach(System.out::println);}
最后,是算法8和算法9,函数式编程实现斐波拉契数列算法的测试程序的完整源码:
package fibonacci;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.LongStream;
import java.util.stream.Stream;/**** @author QiuGen* @description 斐波那契数列的函数式编程的算法* @date 2024/8/20* ***/
public class FibonacciStream {/***迭代生成斐波那契数列的无限流***/public static Stream<long[]> fibStream( ) {Stream<long[]> fibStream = Stream.iterate(new long[]{0, 1},fib -> new long[]{fib[1], fib[0] + fib[1]});return fibStream;}/**用Collect收集结果**/public static void fibStreamA( ) {List<Long> lst = fibStream().map(fib -> fib[0]).limit(30) //前30项.collect(ArrayList::new, ArrayList::add,ArrayList::addAll);lst.forEach(System.out::println);}/**转换为LongStream用forEach打印结果**/public static void fibStreamB( ) {LongStream fibLongStream = fibStream().map(fib -> fib[0]).mapToLong(k->k).limit(30); //前30项fibLongStream.forEach(System.out::println);}public static void main(String[] args) {fibStreamA();fibStreamB();}
}