6700浏览
查看: 6700|回复: 4

【一天一条C语言算法2】费氏数列

[复制链接]
本帖最后由 iooops 于 2016-3-31 20:47 编辑

Yeap!!第二天~~好像有点晚 - - 下次早上发。


【说明】
Fibonacci为1200年代的欧洲数学家,在他的着作中曾经提到:若有一只兔子每个月生一只小兔子,一个月后小兔子也开始生产。起初只有一只大兔子,一个月后就有两只兔子(1大1小),二个月后有三只兔子(2大1小),三个月后有五只兔子(3大2小,小兔子投入生产)......。问第30个月能生多少只小兔子?(第0个月为0只小兔子起算)






先在草稿纸上画张兔子图推算看看哦。
注意新生的小免子需一个月成长期才会投入生产。












不知道你有没有画成下面这样 - -


呀 - - 好像有点糊 - -






【解法】
根据以上的数字:0、1、1 、2、3、5、8……我们可以总结出以下规律:
fn = 0                   n = 0, 1
fn = fn-1 + fn-2      n ≥ 2
其中n代表月份,f代表当月能生产的小兔子数量。
上述的公式所代表的就是传说中的Fibonacci数列,一般习惯称之为费氏数列,例如以下: 0、1、1 、2、3、5、8、13、21、34、55、89......


但是我们发现,就算知道规律计算起来也比较麻烦有木有!!所以我们就可以用C语言来解决这个问题啦。


如下所示:
  1.     #include <stdio.h>
  2.     #include <stdlib.h>
  3.     int fib(int n) {
  4.         int Fib[n];
  5.         int i;
  6.         if(n > 0) {
  7.             Fib[0] = 0;
  8.             Fib[1] = 1;
  9.             for(i = 2; i <= n; i++) {
  10.                 Fib[i] = Fib[i-1] + Fib[i-2];
  11.             }
  12.             for(i = 0; i <= n; i++){
  13.                 printf("%d ", Fib[i]);
  14.             }
  15.             printf("\n");
  16.             printf("第%d个月能生产%d只兔子\n", n, Fib[n]);
  17.             return 0;
  18.         }
  19.         else {
  20.             return -1;
  21.         }
  22.     }
  23.     int main(void) {
  24.         int n;
  25.         printf("请输入月数:");
  26.         scanf("%d", &n);
  27.         fib(n);
  28.         return 0;
  29.     }
复制代码


递归的重要性。



但是,当n变得越来越大的时候,O(n)的递归会变得越来越慢。为什么?这要从递归的核心开始说起……(自己查资料了解去)

其实,楼主在维基百科上还找到了其他解法,比如初等代数求解、线性代数求解以及组合法求解。其实……楼主只看得懂初等代数求解……
以下选自维基百科https://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97
初等代数解法已知

首先构建等比数列
化简得

比较系数可得:

不妨设0,  \alpha>0" class="mwe-math-fallback-image-inline tex">
解得:


所以有, 即为等比数列。
求出数列{}由以上可得:


变形得: 。 令
求数列{}进而得到{}
,解得。 故数列为等比数列
。而, 故有
又有
可得
得出表达式




应用这种方法就不用那么大的递归开销了~~


C语言的实现如下:
  1.     #include <stdio.h>
  2.     #include <stdlib.h>
  3.     int fib(int n)
  4.     {
  5.         double constant_a = (1 + sqrt(5)) / 2;
  6.         double constant_b = (1 - sqrt(5)) / 2;
  7.         double constant_c = sqrt(5) / 5;
  8.         double value_1 = 0;
  9.         int value_2 = 0;
  10.         if(n > 0)
  11.         {
  12.             for (int i = 0; i <= n; i++)
  13.             {
  14.                 value_1 = constant_c * (pow(constant_a, i) - pow(constant_b, i));
  15.                 value_2 = (int)value_1;
  16.                 printf("%d ", value_2);
  17.             }
  18.             int value =constant_c * (pow(constant_a, n) - pow(constant_b, n));
  19.             printf("\n第%d个月能生产%d只兔子\n", n, value);
  20.             return 0;
  21.         }
  22.         else
  23.         {
  24.             return -1;
  25.         }
  26.     }
  27.     int main(void) {
  28.         int n;
  29.         printf("请输入月数:");
  30.         scanf("%d", &n);
  31.       
  32.         fib(n);
  33.       
  34.         return 0;
  35.     }
复制代码



运行结果如下:
【一天一条C语言算法2】费氏数列图1


啊快去试试吧~


IMG_20160330_235543.jpg

hnyzcj  版主

发表于 2016-3-31 09:39:15

回想起我的大学生活
回复

使用道具 举报

Readface  初级技师

发表于 2016-3-31 10:39:06

和沙发一样其实板凳也有同样的感受~
回复

使用道具 举报

maker_王  初级技匠

发表于 2016-3-31 11:54:31

大学里日复一日,年复一年的算法啊
回复

使用道具 举报

iooops  中级技匠
 楼主|

发表于 2016-3-31 20:43:00

hnyzcj 发表于 2016-3-31 09:39
回想起我的大学生活

啊温故而知新 - -
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

为本项目制作心愿单
购买心愿单
心愿单 编辑
[[wsData.name]]

硬件清单

  • [[d.name]]
btnicon
我也要做!
点击进入购买页面
上海智位机器人股份有限公司 沪ICP备09038501号-4

© 2013-2024 Comsenz Inc. Powered by Discuz! X3.4 Licensed

mail