Java Coding 9 - 输出给定长度的斐波那契系列Fibonacci
2021/7/17 12:35:30
本文主要是介绍Java Coding 9 - 输出给定长度的斐波那契系列Fibonacci,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
什么是斐波那契数?
Wikipedia 的定义比较详细,大家可以参考一下。
斐波那契数是一系列连续顺序排列的整型数。主要特征就是当前数是前两位数之和。
例如:
1 1 2 3 5 8 13 21 34 55 89 144 。。。
或则以0为初始值:
0 1 1 2 3 5 8 13 21 34 55 89 144 。。。
思路:
- 利用集合的特性,将数列依次存在集合中再输出
- 循环动态计算,边计算边输出(最佳)
- 利用递归调用
实现:
用ArrayList存储Fibonacci数列
public static void printFibonacciUsingCollection(int len) { ArrayList<Integer> fi = new ArrayList<>(); fi.add(0); fi.add(1); for (int i = 2; i <= len - 1; i++) { fi.add(fi.get(i - 2) + fi.get(i - 1)); } if (len < 1) { System.out.println("the length is invalid"); } else if (len == 1) { System.out.println("Fibonacci series of length " + len + " are here:"); System.out.println("[" + fi.get(0) + "]"); } else if (len == 2) { System.out.println("Fibonacci series of length " + len + " are here:"); System.out.println("[" + fi.get(0) + ", " + fi.get(1) + "]"); } else { System.out.println("Fibonacci series of length " + len + " are here:"); System.out.println(fi); } }
动态计算:
当前fn = fn-2 + fn-1
下一轮fn-2,fn-1的值将这样变换:
fn-2 = fn-1
fn-1 = fn
public static void printFibonacciWithoutCollection(int len) { int f0 = 0; int f1 = 1; int fi; if (len <= 0) { System.out.println("the length is invalid"); } else { System.out.println("the fibonacci series of length " + len + " are here"); if (len == 1) { System.out.println(f0); } else if (len == 2) { System.out.println(f0 + " " + f1); } else { System.out.print(f0 + " " + f1 + " "); for (int i = 3; i <= len; i++) { fi = f0 + f1; System.out.print(fi + " "); f0 = f1; f1 = fi; } System.out.println(); } } }
递归调用:
f(n) = f(n-1) + f(n-2)
例如:计算f(4)
f0 = 0
f1 = 1
f(4) = f(2) + f(3) 转换成先计算f(2)和f(3)
f(2) = f(0) + f(1) = 1
f(3) = f(2) + f(1) = 2
再将计算出的结果返回
f(4) = f(2) + f(3) = 1 + 2 = 3
每次分解递归调用再回归
public static int findFibonacciUsingRecursion(int len) { int f0 = 0; int f1 = 1; int fn; if (len == 1) { return f0; } else if (len == 2) { return f1; } else { fn = findFibonacciUsingRecursion(len - 2) + findFibonacciUsingRecursion(len - 1); return fn; } }
完整代码
递归:
import java.util.*; public class Test { public static void main(String[] args) { testPrintFibonacciUsingRecursion(); } public static void testPrintFibonacciUsingRecursion() { System.out.println("Please enter a length greater than 0, -1 means to quit"); Scanner in = new Scanner(System.in); int len = in.nextInt(); while (len != -1) { if (len <= 0) { System.out.println("the length is invalid"); } else { System.out.println("the fibonacci series of length " + len + " are here:"); for (int i = 1; i <= len; i++) { System.out.print(findFibonacciUsingRecursion(i) + " "); } System.out.println(); } System.out.println("Please enter a length greater than 0 again, -1 means to quit"); len = in.nextInt(); } } public static int findFibonacciUsingRecursion(int len) { int f0 = 0; int f1 = 1; int fn; if (len == 1) { return f0; } else if (len == 2) { return f1; } else { fn = findFibonacciUsingRecursion(len - 2) + findFibonacciUsingRecursion(len - 1); return fn; } } }
非递归:
import java.util.*; public class Test { public static void main(String[] args) { testPrintFibonacci(); } public static void testPrintFibonacci() { System.out.println("Please enter a length greater than 0, -1 means to quit"); Scanner in = new Scanner(System.in); int len = in.nextInt(); while (len != -1) { printFibonacciWithoutCollection(len); // printFibonacciWithoutCollection(len); len = in.nextInt(); } } public static void printFibonacciUsingCollection(int len) { ArrayList<Integer> fi = new ArrayList<>(); fi.add(0); fi.add(1); for (int i = 2; i <= len - 1; i++) { fi.add(fi.get(i - 2) + fi.get(i - 1)); } if (len < 1) { System.out.println("the length is invalid"); } else if (len == 1) { System.out.println("Fibonacci series of length " + len + " are here:"); System.out.println("[" + fi.get(0) + "]"); } else if (len == 2) { System.out.println("Fibonacci series of length " + len + " are here:"); System.out.println("[" + fi.get(0) + ", " + fi.get(1) + "]"); } else { System.out.println("Fibonacci series of length " + len + " are here:"); System.out.println(fi); } } public static void printFibonacciWithoutCollection(int len) { int f0 = 0; int f1 = 1; int fi; if (len <= 0) { System.out.println("the length is invalid"); } else { System.out.println("the fibonacci series of length " + len + " are here"); if (len == 1) { System.out.println(f0); } else if (len == 2) { System.out.println(f0 + " " + f1); } else { System.out.print(f0 + " " + f1 + " "); for (int i = 3; i <= len; i++) { fi = f0 + f1; System.out.print(fi + " "); f0 = f1; f1 = fi; } System.out.println(); } } } }
输出结果:
Please enter a length greater than 0, -1 means to quit 0 the length is invalid 1 the fibonacci series of length 1 are here 0 2 the fibonacci series of length 2 are here 0 1 3 the fibonacci series of length 3 are here 0 1 1 8 the fibonacci series of length 8 are here 0 1 1 2 3 5 8 13 -1 Process finished with exit code 0
这篇关于Java Coding 9 - 输出给定长度的斐波那契系列Fibonacci的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求