【C语言】经典兔子问题

兔子问题"/>

【C语言】经典兔子问题

题目描述

古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

程序分析

首先每个月的兔子总数指的是兔子的总对数。我们来推导一下：
一月：（一对）兔子1号，因无生育能力，所以只有1对兔子
二月： 仍旧只有兔子1号，兔子总数为1对兔子
三月： 兔子1号生了兔子2号，所以共有1 + 1 = 2对兔子
四月： 兔子1号生了兔子3号，兔子2号暂时没有生育能力，所以共有2 + 1 = 3对兔子
五月： 兔子1号生了兔子4号，兔子2号生了兔子5号，3号暂时没有生育能力，共有3 + 1 + 1 = 5对兔子
六月： 兔子1号生了兔子6号，兔子2号生了兔子7号，兔子3号生了兔子8号，兔子4、5号暂时没有生育能力，共有5 + 1 + 1 + 1 = 8对兔子
七月： 兔子1号生了兔子9号，兔子2号生了兔子10号，兔子3号生了兔子11号，兔子4号生了兔子12号，兔子5号生了兔子13号，其余兔子暂无生育能力。共有8 + 1 + 1 + 1 + 1 + 1 = 13对兔子。
…依次类推

从上述推导可以看出兔子的规律为数列1，1， 2， 3， 5， 8， 13 …
是不是很眼熟？没错，该数列就是斐波那契数列！从第三项起，每一项都等于前两项之和。

源代码

//非递归
#include<stdio.h>
#include<stdlib.h>
int main()
{long f1, f2;f1 = 1;f2 = 1;int tmp = 0;for (int i = 1; i <= 12; i++){if (i < 3){printf("第%d个月兔子总数为：%d对\n", i, f1);}else{tmp = f1 + f2;f1 = f2;f2 = tmp;printf("第%d个月兔子总数为：%d对\n", i, tmp);}}system("pause");return 0;
}//递归
int fib(int n)
{if (n < 3){return 1;}else{return fib(n - 1) + fib(n - 2);}
}int main()
{int i;scanf("%d", &i);printf("%d\n", fib(i));system("pause");return 0;
}