小朋友学C语言（16）：斐波那契数列的非递归实现

小鱼儿 2022-06-07 12:52 112阅读 0赞

# 一、斐波那契简介 #

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……..  
这个数列从第3项开始，每一项都等于前两项之和。

# 二、非递归实现 #

动手编写程序：

#include <stdio.h>
    
    int fibonacci(int n) 
    {
        if(1 == n || 2 == n)
        {
            return 1;
        }
    
        int f1 = 1;
        int f2 = 1;
        int f3 = 0;
    
        for(int i = 3; i <= n; i++)
        {
            f3 = f1 + f2;
            f1 = f2; 
            f2 = f3;
        }
    
        return f3;
    }
    
    int main()
    {   
        int m, result;
    
        printf("input item number: ");
        scanf("%d", &m);
    
        result = fibonacci(m);
    
        printf("The result is %d", result);
    
        return 0;
    }

运行结果：

input n: 6
    The result is 8

新知识点：  
（1）这里出现了一个新的函数scanf()。scanf()的作用是读取键盘或鼠标的输入。n是你通过键盘输入的值，&是取地址符，&n就是n在内存里的地址。找到了n在内存中的地址，也就取到了n的值。  
假如你输入n 的值为 3，则&n就是3在内存里的地址，则n就是3。  
scanf()的作用与printf()的作用相反。printf()的作用是打印、输出。  
这两个函数都是在stdio.h中声明的。  
【注意】多数线上编译器不支持scanf()函数，所以这个程序要用本机编译器（比如苹果电脑的Xcode，PC的dev c++）来编译。

（2）  
if(1 == n || 2 == n)  
\{  
return 1;  
\}  
这段表示，假如你输入的n为1或2，则返回1。下面的语句都不被执行。

（3）假如你输入的值大于2，比如你输入了6，则fibonacci()函数中的for循环是这么执行的：  
第一次，i = 3, i <= 6为真，f3 = f1 + f2 = 1 + 1 = 2, f1 = f2 = 1, f2 = f3 = 2  
第二次，i = 4, i <= 6为真，f3 = f1 + f2 = 1 + 2 = 3, f1 = f2 = 2, f2 = f3 = 3  
第三次，i = 5, i <= 6为真，f3 = f1 + f2 = 2 + 3 = 5, f1 = f2 = 3, f2 = f3 = 5  
第四次，i = 6, i <= 6为真，f3 = f1 + f2 = 3 + 5 = 8, f1 = f2 = 5, f2 = f3 = 8  
第五次，i = 7, i <= 7为假，循环结束。最终返回的f3的值为8

# 三、作业 #

（1）输入n = 1，用断点查看程序的执行过程。  
（2）输入n = 2，用断点查看程序的执行过程。  
（3）输入n = 3，用断点查看程序的执行过程。  
（4）输入n = 4，用断点查看程序的执行过程。  
（5）输入n = 5，用断点查看程序的执行过程。  
（6）输入n = 6，用断点查看程序的执行过程。  
（4）在纸上默写这个程序

> 更多内容请关注微信公众号  
> ![wchat\_official.jpg][wchat_official.jpg]

[wchat_official.jpg]: /images/20220607/22e14afbfccf410b862f4e0cbd53cd93.png