Fibonacci数列问题

Fibonacci数列的解法：

1、递归算法

递归的概念，我说不清楚，语文不好。但是核心思想，我认为就是入栈出栈。比方说，你想要求得某个结果，如果一步求解不出来，那么先把最后一步的计算步骤进栈，先不考虑它。转而去想，在求解最后一步之前的那一步应该怎么去做，就好比冬天穿衣服，再最后一步穿羽绒服之前我想大部分人会先穿一个羊毛衫（要是较真的话，内衣你应该会穿的吧）。这样，我们先把羽绒服放在一边（进栈），先去准备穿羊毛衫。然后，我们又发现在穿羊毛衫之前，我得穿个保暖内衣啊。好，我们再将羊毛衫先放一边（再进栈，此时羊毛衫在羽绒服上面放着）。这时候，我们穿上了保暖内衣，ok一下个——>栈的后入先出规则表示下一个我应该穿羊毛衫，ok穿上再下一个——>羽绒服。。。（下半身的穿衣流程类似，可能多一个胖次，自行脑补思考）。

所以你看，现实当中很多时候的事情不是一下就可以完成的，而是需要一步一步的去完成，程序更是如此。你设计的代码，目的就是为了解决一个问题，在解决的过程中，会要进行很多的步骤，递归也是这样，只是它在解决问题之前一直在调用自身。

来看一下这个Fibonacci数列：

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

第一步，n是多少。按照题目意思，自己输入n。

第二步，怎么求，这里我假设有这么一个方法就叫做Fibonacci（int n），return一个int，将n传进去之后，经过这个方法后，我就得到了Fn。

第三步，分析一下，Fn=Fn-1+Fn-2=Fn-2+Fn-3+Fn-3+Fn-4=..........所以，要求Fn（羽绒服），先去求Fn-1和Fn-2（羊毛衫），要求Fn-1就要先去求Fn-2和Fn-3，以此类推，暂时求不出来的，统统依次入栈，最后发现要求F3，我得先求F2和F1（F3入栈）。OK，F1=F2=1，F3就求出来了（F3出栈），又F4=F3+F2，F4也求得出来了（F4出栈）.......之前入栈的那些步骤，再依次出栈进行计算，直到Fn被求出来，计算Fn%10007本题结束。

第四步，放代码：

import java.util.Scanner;

public class Fibonacci {
	//Fibonacci数列  递归算法
	public static int Fibonacci (int n){
		if(n==1||n==2){
			return 1;
		} else{
                        //操作入栈出栈的核心，递归调用
			n = Fibonacci (n-1)+Fibonacci (n-2);
			return n;
		}
	}

	public static void main(String[] args) {
		while(true){
			Scanner scanner = new Scanner(System.in);
			int n；
			n = scanner.nextInt();
			int k = Fibonacci (n);
			System.out.println(k%10007);	
		}

	}

}

2、整数求余

递归的算法虽然代码简洁，但是有一个比较不太好的地方，就是执行的效率很低，它是自身层层深入的调用，在时间和空间上的复杂度都很高，而且计算的重复性操作很多，在计算机内部还很有可能造成栈溢出的现象。比方说，用递归的方法计算N阶计算的时候，当N的值越来越大，很可能计算机就罢工了。

所以，本着递归和循环理论相同的原则，结合整数求余的规律，将代码改进如下：

import java.util.Scanner;

public class Fibonacci {
	//Fibonacci数列  求余算法
	public static int Fibonacci(int n){
		int[] F = new int[n+1];//n+1是为了不让数组出现越界
		F[1]=F[2]=1;
		for(int i=3;i<=n;i++){
			F[i] = (F[i-1] + F[i-2])%10007;
		}
		return F[n];
	}
	public static void main(String[] args) {
		while(true){
			Scanner scanner = new Scanner(System.in);
			int n;
			n = scanner.nextInt();
			System.out.println(Fibonacci(n));
			
		}

	}

}

在方法里面定义一个长度为n+1的int型数组，用来存储数列的值，其中n+1是为了防止数组在执行过程当中产生越界的现象。然后，方法里面的核心在于整数求余的计算，即：

F[i] = (F[i-1] + F[i-2])%10007;

为什么这样写？当代码改进成这样时，我们就不需要先求得Fn的值再去取余数，而是直接在for循环中，直接就能将取余的运算执行，当循环结束。最后得到的Fn，就是数列中第N个数取余的结果。
为什么可以这样写？这里面是有整数取余运算的规律的，举个例子，1%10取余数就是1，2%10就是2，3%10就是3，那是不是3%10=1%10+2%10？再多举几个例子来进行验证：

5%10=5；10%10=0；15%10=5=5%10+10%10；
21%10=1；32%10=2；53%10=3=21%10+32%10；
57%7=1；89%7=5；146%7=6=57%7+89%7;
......
可以看到，好像的确是这样，这当中的原理，其实你思考一下是可以理解的，但是我说不太清楚，害怕误人子弟，想要深入理解，可以百度。
附加我找的一位前辈的博客链接，记录了取余运算规则：https://blog.csdn.net/ash_zheng/article/details/38541777
暂时就写到这了，欢迎评论交流，互相学习，哈哈。

Fibonacci数列问题

相关推荐