斐波拉契数列

题目描述

斐波那契数列是一组第一位F1和第二位F2为1，从第三位开始，后一位是前两位和的一组递增数列Fn=Fn-1+Fn-2。
那么当n比较大时，Fn也非常大，现在我们想知道，第n项，Fn等于多少

如：
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn。

样例输入10 此时Fibonacc[ ] = {1,1,2,3,5,8,13,21,34,55}
样例输出55

样例输入28 此时Fibonacc[ ] = {1,1,2,3,5,8,13,21,34,55…,10946,17711}
样例输出317811

题目分析

数组前两位默认为1，那么就可以从第三位开始，或者在计算的时候实现一个判断，将前两位返回1。实现方式有许多

代码实现

`数组方式`

#include<stdio.h>
#include<stdlib.h>
int main(){
	int *num;
	int n;
	scanf("%d",&n);
	num=(int *)malloc(n*sizeof(int));//动态规划数组，长度为 n 
	for(int i=0;i<n;i++){
		if(i<2)
			num[i]=1;
		else
			num[i]=num[i-1]+num[i-2];
	}
	printf("%d\n",num[n-1]);
	free(num);
}

`递归方式`

#include <iostream>
using namespace std;
int Fibonacc(int n){
	if(n==1||n==2)
		return 1;
	else
		return Fibonacc(n-2)+Fibonacc(n-1);
}
int main(){
	int n;
	cin>>n;
	cout << Fibonacc(n)<<endl;
	return 0;
}

`非递归方式`

#include <iostream>
using namespace std;	
int Fibonacc(int n){
	int f_left=1;	//左边一个数
	int f_right=1;	//右边一个数
	int f_n=0;		//结果数
	if(n==1||n==2)
		return 1;
	else{
		for(int i=2;i<n;i++){
			f_n=f_left+f_right;	//先左数+右数得到一个新的结果
			f_left=f_right;		//此时右边的数作为新的左数
			f_right=f_n;		//刚才的结果作为新的右数
		}
	}
		return f_n;
}
int main(){
	int n;
	cin>>n;
	cout << Fibonacc(n)<<endl;
	return 0;
}

运行结果

10
55
--------------------------------
Process exited with return value 0
Press any key to continue . . .

28
317811
--------------------------------
Process exited with return value 0
Press any key to continue . . .

总结

对于此类斐波拉契数列如果是采用数组方式，则要考虑到数组的长度定义问题，那么就需要动态定义数组长度，数组分别记录数列的每一项，占用内存则会太多，如果是采用递归，则不需要那么繁琐，依次累加最终得到最后一项，但是时间则需要太多，各个方式有利有弊。