1. 首页
  2. 题解列表
  3. 1131题题解

解决斐波那契数列的多种方法，若有错误可以指正。

106 阅读 1 评论
原题链接：C语言训练-斐波纳契数列

解题思路:递归的全名叫做递推和归回，它是不断的递推和归回

斐波那契数列又名叫兔子数列，f(0)=1;f(1)=1;f(2)=2......从这我们可以得出一个表格

1

1
235813213455
0123456789
我们看这个表格，前两项都是为1，所以当n<=2的时候，永远都是为一；但当n>2的时候，可以得出f（n）=f（n-1)+f(n-2),所以我们可以利用这层递推关系来得出这个结果。

注意事项:如果递归使用的不恰当会造成不必要的麻烦，而假设n的数较大，容量值则会不断上，会导致一些问题出现，而且此题如果实在想不出递归关系可以使用迭代方法，动态分配，尾递归来求解。


参考代码:

1.递归方法

#include<stdio.h>
int Fib(int n) //运用递归方法解决斐波那契数列问题
{
    if(n<=2)
    return 1;
    else
    return Fib(n-1)+Fib(n-2); //这个是指当n>2时候的结果
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",Fib(i));
    }
return 0;
}

2.迭代方法（此方法借用“教你夺冠”这位博主的方法）

#include <stdio.h>
#include <string.h>
 
long fibonacci(int n)
{
    if (n <= 2)
    {
        return 1;
    }
 
    long result;
    long pre_result;
    long pre_pre_result;
 
    pre_result = pre_pre_result = 1;
 
    while (n > 2)
    {
        result = pre_result + pre_pre_result;
        pre_pre_result = pre_result;
        pre_result = result;
        n--;
    }
 
    return result;
}
 
int main()
{
    int N;
    scanf("%d", &N);
 
    int i;
     点赞(0)
　

0.0分

0 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)
点进来你会后悔的
点进来你会后悔的
简简单单的循环
简简单单的循环
简单的回文数
简单的回文数

评论列表 共有 1 条评论

吊炸天 1年前 回复TA 
在补充一种方法，此方法叫尾递归，不存在效率问题，代码如下
#include<stdio.h>
int Fib(int n)
{
   int a=1;
   int b=1;
   int c=1;
   while(n>=3)
   {
       c=a+b;
       a=b;
       b=c;
       n--;
   }
   return c;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",Fib(i));
    }
return 0;
}