Question

[C语言]用递归算法编写一个程序求Fibonacci数列的第n项值

小弟在自学C语言，函数一章的课后作业有道题一直让我摸不着头脑，只好来这请教高人啦。大虾们帮个忙吧？列出程序的同时最好能帮我解释一下，谢谢！
题目如下：
用递归算法编写求Fibonacci数列第n项值的函数fib(int n),并用主函数输出它的前20项来验证该函数。

Answer 1

代码：

#include<iostream>

#include<vector>

using namespace std;

vector<int>a,b,c;

void jisuan(int n){

if(n<=1)cout<<1<<endl;

else{

a.push_back(1);

b.push_back(1);

for(int i=2;i<=n;++i){

c=b;//存一下b的值

for(int j=b.size()-1,k=a.size()-1;k>=0;k--,j--){

b[j]+=a[k];

if(b[j]>=10){

if(k==0&&j==0){

b.insert(b.begin(),1);

j++;//插入之后需要%10的那个数往后移动一位

}

else{

b[j-1]++;//如果b前面还有数，前一个数+1

}

b[j]%=10;//把数%10，变成小于10的数因为前面已经进位

}

}

a=c;

}

for(int i=0;i<b.size();i++){

cout<<b<i>;

}

cout<<endl;

}

}

int main(){

int n;

cin>>n;

jisuan(n);

return 0;

}

扩展资料：

在做c/c++编程的对#include指令都不会陌生，绝大多数人也都知道如何使用，相信仍有人对此是一知半解的，

C:

#include<stdio.h>

C++:

#include<iostream>

表示包含C/C++标准输入输出头文件。包含指令不仅仅限于.h头文件，可以包含任何编译器能识别的C/C++代码文件，包括.c、.hpp、.cpp、.hxx、.cxx等，甚至.txt、.abc等等都可以。

预处理器发现#include指令后，就会寻找指令后面<>中的文件名，并把这个文件的内容包含到当前文件中。被包含文件中的文本将替换源代码文件中的#include指令，就像你把被包含文件中的全部内容键入到源文件中的这个位置一样。

参考资料：

百度百科——include（计算机专业术语）

Answer 2

#include <stdio.h>
unsigned int Fibonacci(int n);
int main( void )
{
int i;
for(i = 1 ;i <= 20;i ++)
{
printf("%d\n",Fibonacci(i));
}
return 0;
}
unsigned int Fibonacci(int n)
{
if( n == 1 || n == 2) // 递归结束的条件，求前两项
return 1;
else
return Fibonacci(n-1)+Fibonacci(n-2); // 如果是求其它项，先要求出它前面两项，然后做和。
}
这种算法效率比较低
哪里不清楚可以Hi我

Answer 3

int fib(){
int a[]= new int [60];
a[0]=a[1]=1;int j=0;
for(int i=2;i<60;i++){

a[i]=a[i-1]+a[i-2];
}
}
其他的罗嗦的部分你自己写啊，这个是那个递归函数了，最后输出a[]值就可以了，这种写法就是递归的方式，代码简单，运行效率不是很高

Answer 4

int Fib(int n)
{if(n==0)
return(0);
else if(n==1)
return(1);
else
return(Fib(n-1)+Fib(n-2));
}
int main()
{int n;
printf("Input n:");
scanf("%d",&n);
printf("Fib(%d)=%d\n",n,(Fib(n-1)+Fib(n-2)));
return 0;
}

Answer 5

#include <iostream.h>
int fib(int i)
{
if( i == 1 || i == 2) return i;
else return fib(i-1)+fib(i-2);
}
void main()
{
int s,i;
for(i = 0 ;i <= 20;i ++)
{ s=f(i);
cout<<“f(i)="<<s<<'\t';
}
}