题目:若有一只免子每个月生一只小免子,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);
}
}
}
|
阅读(881) | 评论(0) | 转发(0) |