斐波那契数

1 1 2 3 5 8 13 21 34 55…

创新互联坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都做网站、成都网站制作、成都外贸网站建设、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的丰城网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

像这种前两个数之和=第三个数的就叫做斐波那契数。
公式:fib(n + 2) = fib(n + 1)+fib(n)
可以推导出第n个斐波那契数的公式应该是——>fib(n) = fib(n - 1)+fib(n -2)

1 递归法

可以发现，在这样一个斐波那契数列中，前两个数是1，也就是说说过求的是前面两个数，直接返回一个1就行了。
n>2时才开始进行计算：fib(n) = fib(n - 1)+fib(n -2)

#includeint fib(int n)
{if(n<= 2)
        {return 1;
        }
        else
        {return fib(n - 1) + fib(n - 2);
        }
}
int main()
{int n;
        printf("请输入一个数:");
        scanf ("%d",&n);
        printf("第%d个斐波那契数是%d\n",n,fib(n));
        return 0;
}

请输入一个数:10
第10个斐波那契数是55

递归法有个致命的缺点就是，重复度特别高，效率低下。
当输入50的时候计算机足足算了5分钟才反应过来。

请输入一个数:50
第50个斐波那契数是-298632863

50，想要求50的fib数就要先算出49和48的fib数
49 48，想算49和48的fib数又要算48 47 47 46的fib数
48 47 47 46
47 46 46 45 46 45 45 44
…
这样的算法重复度太高，效率非常低，所以其实是很挫的一种方法。

2 循环法

#includeint fib(int n)
{int a = 1,b = 1,c = 1;
        while(n >2)//2后面的数才去算
        {c = a + b;
                a = b;
                b = c;
                n--;//让算过fib数的位置再也不要去算了
        }
        if(1 == n||2 == n)
        {return c;//退出循环之后返回c，c就是算出来的结果
        }
}

int main()
{int n;
        printf("请输入一个数:");
        scanf ("%d",&n);

        printf("第%d个斐波那契数是%d\n",n,fib(n));
        return 0;
}

请输入一个数:30
第30个斐波那契数是832040

c = a + b，不停的将前两个数赋给第三个数，所有的数字就在这abc三个数里更新，不需要像递归那样每个数都要去算前面的一堆数字才能算出来。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

标题名称：C语言编程题——求第n个斐波那契数-创新互联
分享URL：http://chengdu.cdxwcx.cn/article/cspcjd.html