Algorithm Gossip费式数列(斐波那契数列)

题目:

若有一只免子每个月生一只小免子，2个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......。

 

求一下N个月以后一共有多少只兔子(N为自然数，起初只有一只兔子)。

PHP的两中算法取得的效率结果
非递归计算60个月:
共有兔子4052739537880只
0.00011682510376=1258432594.92-1258432594.92
0.00011682510376 times
递归计算30个月:
共有兔子2178309只
4.74454188347=1258432599.67-1258432594.92
4.74454188347 times
关于效率比较,本博还有一篇文章,也是以PHP为例做的测试:递归效率比较

C语言及Python的效率,我没有去做效率比较,有兴趣的同学做好之后发我一下,谢谢

<?php
/**
  Name: Algorithm Gossip
  Copyright: 1.0
  Author: Mervin.G
  Date: 2009-11-16
  Description: 算法 费式数列（斐波那契数列）
*/
set_time_limit(0);

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

//非递归法
function rabbit($n)
{
    $bigRabbit = 1; //大兔子 可生育
    $smallRabbit = 0; //小兔子 不可生育
    
    for($i=0;$i<$n;$i++) //N个月
    {
        $smallRabbit = $bigRabbit - $temp; //每个大兔子每月产一只小兔子,所以小兔子和大兔子数相同
        #echo ($i+1)."个月之后".$smallRabbit."只小兔子 ".$bigRabbit."只大兔子
";
        if($n>($i+1))
        {
            $temp = $smallRabbit; //一个月之后,小兔子长大
            $bigRabbit = $temp + $bigRabbit; //如果当前月+1月小于总月数,说明小兔子已经长大成大兔子
        }
        else
        {
            echo "共有兔子".($smallRabbit + $bigRabbit)."只
";
        }
    }
}

$stime=microtime_float(); //获取程序开始执行的时间
rabbit(60);
$etime=microtime_float(); //获取程序执行结束的时间
$total=$etime-$stime; //计算差值
echo "$total=$etime-$stime
";
echo "{$total} times
";

//递归法
function rabbits($n,$a)
{
    if($n == 0)
    {
        $all = $a;
    }
    else
    {
        if($n == 1)
        {
            $b = $a;
            $all = $a + $b;
        }
        else
        {
            $all = rabbits($n-1,$a) + rabbits($n-2,$a); //大兔子数 小兔子数
        }
    }
    return $all;
}
$stime=microtime_float(); //获取程序开始执行的时间
echo "共有兔子".rabbits(30,1)."只
";
$etime=microtime_float(); //获取程序执行结束的时间
$total=$etime-$stime; //计算差值
echo "$total=$etime-$stime
";
echo "{$total} times
";
?>


Python:
真是不喜欢这种语言,看起来很乱,可读性比较低

def rabbit(n,a):
    if n == 0:
        all = a
    else:
        if n == 1:
            b = a
            all = a + b
        else:
            all = rabbit(n-1,a) + rabbit(n-2,a)

    //最后一个return还真是难以想象是第一个if里的内容,还是第二个if里的内容 -_-#
    return all

C:

/*
  Name: 兔子下崽
  Copyright: 1.0
  Author: Mervin.G
  Date: 2009-11-18
  Description: 计算N个月后兔子的数量
*/

#include <stdio.h>
#include <conio.h>
#include <windows.h>

void rabbit(int n)
{
     int bigRabbit = 1;
     int smallRabbit = 0;
     int temp = 0;
     int i;
     
     for(i=0;i<n;i++)
     {
         smallRabbit = bigRabbit - temp;
         
         if(n>(i+1))
         {
             temp = smallRabbit;
             bigRabbit = temp + bigRabbit;
         }
         else
         {
             printf("共有兔子%d只",smallRabbit+bigRabbit);
         }
     }
}

main()
{
    int igetch;
    rabbit(4);
    
    while (true)
    {
        igetch = getch();
        if(igetch == 27)
        {
            exit(0);
        }
        else
        {
            printf("%d\n",igetch);
        }
    }
}