iooops 发表于 2016-3-31 01:30:25

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

本帖最后由 iooops 于 2016-3-31 20:47 编辑

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


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






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












不知道你有没有画成下面这样 - -
https://mc.dfrobot.com.cn/data/attachment/forum/201603/31/000456ezixtycuyu9111fo.jpg

呀 - - 好像有点糊 - -






【解法】
根据以上的数字：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语言来解决这个问题啦。


如下所示：
    #include <stdio.h>
    #include <stdlib.h>

    int fib(int n) {
      int Fib;
      int i;
      if(n > 0) {
            Fib = 0;
            Fib = 1;
            for(i = 2; i <= n; i++) {
                Fib = Fib + Fib;
            }
            for(i = 0; i <= n; i++){
                printf("%d ", Fib);
            }
            printf("\n");
            printf("第%d个月能生产%d只兔子\n", n, Fib);
            return 0;
      }
      else {
            return -1;
      }
    }


    int main(void) {
      int n;
      printf("请输入月数：");
      scanf("%d", &n);
      fib(n);
      return 0;
    }

论递归的重要性。



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

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

[*]https://upload.wikimedia.org/math/c/e/7/ce7bccd95db37776721a69c77d633ac3.png
[*]https://upload.wikimedia.org/math/7/f/f/7ffcdda11bda1e9dd0d12548c9e7c526.png
[*]https://upload.wikimedia.org/math/0/8/1/081e4bd34a8347f5938a7a576451f02a.png
首先构建等比数列设https://upload.wikimedia.org/math/b/e/8/be89a66a07861aba109392da9712e915.png
化简得
https://upload.wikimedia.org/math/6/7/3/67310762e7beef61b4c01b39f2e0442e.png
比较系数可得：
https://upload.wikimedia.org/math/4/e/e/4ee4698d16ae45349e6fd5252f80938a.png
不妨设https://upload.wikimedia.org/math/5/a/3/5a36a7abdb46221883e68b7dc61f9774.png0,\alpha>0" class="mwe-math-fallback-image-inline tex">
解得：

https://upload.wikimedia.org/math/b/3/3/b338861e624f259df7d7d6ae126949b0.png
所以有https://upload.wikimedia.org/math/b/e/8/be89a66a07861aba109392da9712e915.png， 即https://upload.wikimedia.org/math/0/7/a/07ae8d6e328356269fe4ce97a42eaab0.png为等比数列。
求出数列{https://upload.wikimedia.org/math/b/3/d/b3d6234339359cbd6630d537345d48af.png}由以上可得：
https://upload.wikimedia.org/math/c/3/a/c3ad4bdf9ab8a95bcc012faecbc5ea59.png

变形得： https://upload.wikimedia.org/math/2/f/8/2f856deb15da64f37f895d7f9ae5a37a.png。 令https://upload.wikimedia.org/math/c/6/4/c645522d34e2788f70abee17375f1888.png
求数列{https://upload.wikimedia.org/math/c/9/d/c9d72c24c8835176f6f1a0ee2a14167a.png}进而得到{https://upload.wikimedia.org/math/9/d/e/9ded7825070b255e7bc092cdc2c8e98a.png}https://upload.wikimedia.org/math/1/c/d/1cd09de0ce6cd57cd07c5e753bdb2922.png
设https://upload.wikimedia.org/math/3/1/4/314e78f3b6a65ec5f91b2db8bb147a1c.png，解得https://upload.wikimedia.org/math/0/e/6/0e6009bab1d4dec0e4ec2783958e3e4e.png。 故数列https://upload.wikimedia.org/math/f/e/4/fe44bffd9793b9e0d9de097668bcc296.png为等比数列
即https://upload.wikimedia.org/math/e/5/d/e5d3869932e692eebef12ee0d3771246.png。而https://upload.wikimedia.org/math/b/c/3/bc351578116e273eba47465053ca8710.png， 故有https://upload.wikimedia.org/math/d/8/3/d839d79c5416ac6658571e5662f90dcb.png
又有https://upload.wikimedia.org/math/b/3/3/b338861e624f259df7d7d6ae126949b0.png 和https://upload.wikimedia.org/math/c/6/4/c645522d34e2788f70abee17375f1888.png
可得https://upload.wikimedia.org/math/c/6/d/c6dc35b68545005b9b6fa6995c4f6d52.png
得出https://upload.wikimedia.org/math/8/6/9/8695358de7ec5abaf79b61df5750a5f8.png表达式

https://upload.wikimedia.org/math/c/6/d/c6dc35b68545005b9b6fa6995c4f6d52.png



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


C语言的实现如下：
    #include <stdio.h>
    #include <stdlib.h>


    int fib(int n)
    {
      double constant_a = (1 + sqrt(5)) / 2;
      double constant_b = (1 - sqrt(5)) / 2;
      double constant_c = sqrt(5) / 5;
      double value_1 = 0;
      int value_2 = 0;
      if(n > 0)
      {
            for (int i = 0; i <= n; i++)
            {
                value_1 = constant_c * (pow(constant_a, i) - pow(constant_b, i));
                value_2 = (int)value_1;
                printf("%d ", value_2);
            }
            int value =constant_c * (pow(constant_a, n) - pow(constant_b, n));
            printf("\n第%d个月能生产%d只兔子\n", n, value);
            return 0;
      }
      else
      {
            return -1;
      }
    }

    int main(void) {
      int n;
      printf("请输入月数：");
      scanf("%d", &n);
      
      fib(n);
      
      return 0;
    }


运行结果如下：



啊快去试试吧~


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
回想起我的大学生活

啊温故而知新 - -
页: [1]
查看完整版本: 【一天一条C语言算法2】费氏数列