 小编是一个有着6年工作经验的工程师，关于C++编程，自己有做材料的整合，一个完整的C++编程学习路线，学习资料和工具，能够进我的群10048，-83029收取，免费送给大家，希望你也能凭着自己的努力，成为下一个优秀的程序员  背景说明 Fibonacci为1200年代的欧洲数学家，在他的着作中曾经提到：「若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......。 如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例如以下： 1、1 、2、3、5、8、13、21、34、55、89...... 算法说明 仔细观察这个数列，会发现，除了第1个数和第2个数除外，从第3个数开始，第N个数等于它前面两个数之和，也就是这个数列的通项公式为f(n)=f(n-1)+f(n-2) (n>=2,n∈正整数)。 解法 这道题，就像是我们高中时的数学题，就是给一个背景，然后算第N项或者前N项和。 我们一般的步骤都是先找数列的关系，然后推导出它的通项公式，在求解。而费氏数列的通项公式就是如下： ① f(n)=n,(n<=1,n∈正整数) ② f(n)=f(n-1)+f(n-2) (n>=2,n∈正整数) 所以，根据这个通项公式，我们就可以求解了。  public class 费式数列 { /** * @author Helen * Nov 21, 2014 10:30:46 AM * @param args * void * TODO */ public static void main(String[] args) { int n; Scanner input=new Scanner(System.in); System.out.println('请输入N:'); n=input.nextInt(); input.close(); long t=System.currentTimeMillis(); cal(n); System.out.println(); System.out.println('cal耗时:'+(System.currentTimeMillis()-t)); t=System.currentTimeMillis(); for (int i = 1; i < n; i++) { System.out.print(cal2(i)+','); } System.out.println(); System.out.println('cal2耗时:'+(System.currentTimeMillis()-t)); } public static void cal(int n){ int[] Fib=new int[n]; //f(n)=n,if n=0,n=1 Fib[0]=0; Fib[1]=1; //f(n)=f(n-1)+f(n-2),if n>=2 for (int i = 2; i < Fib.length; i++) { Fib[i]=Fib[i-1]+Fib[i-2]; } for (int i : Fib) { System.out.print(i+','); } } /** * * @author Helen * Nov 21, 2014 11:13:56 AM * @param n * @return * int * TODO 递归(耗时) */ public static int cal2(int n){ if(n==0||n==1){ return n; }else{ return cal2(n-1)+cal2(n-2); } } } 第一种是常规算法，每次都将计算后的数保存到一个数组里面，这样在计算第N个数的时候就可以从数组里直接取出第N-1和第N-2的数了； 第二种递归算法是比较耗时的，可以看出第二种每次计算第N个数时，它都要从第0(或1)个开始算起。 |
|
|
