昨日再次看到 C 语言经典例题生兔子问题, 问题描述: 现有一对兔子, 出生后从第三个月开始每个月都会生一对兔子, 新生的兔子三个月后也会开始生一对兔子, 问 XX 个月后会有多少对兔子??
我发现网上大多数解法都是根据其每月数量规律 (即 费布拉契 数列) 直接输出,
此时我思考如果将生长周期改为 4 个月还会是同样的规律吗?? 显然不是, 因此我思考做一个求解此类问题的统一算法, 主要的思想是使用递归解决
通过分析, 我们得到的不确定值有四个:
1: 初始兔子的对数
2: 生长周期
3: 生育间隔期
4: 求解答的时间
因此封装如下函数:
- //star_number: 初始兔子对数 ,mature_year: 生长周期 ,birth_interval: 生育间隔时间, years: 求解年份
- long long function(int star_number,int mature_year,int birth_interval,int years){
- if(years return star_number;
- else{
- long long myson = 0;
- for(int i=mature_year;i<=years;i+=birth_interval){
- myson += function(star_number,mature_year,birth_interval,years-i);
- }
- return myson+star_number;
- }
- }
- int main(){
- for(int i = 1;i<=15;i++){
- printf("%lld",function(1,3-1,1,i-1));
- }
- return 0;
- }
可以看到算法使用的是递归求解, 递归条件是有时间发育成熟并产生后代, 否则返回自己, 递归变量是年份, 用通俗的话来说:
我们将最开始的兔子称为母体, 母体不关心自己的间接后代, 而是只关心自己的直接后代有多少, 间接后代的数量是由直接后代决定, 而每一个直接后代我们又可以看做一个母体, 唯一的变化是剩余的繁殖时间有多少, 因此这是一个典型的递归问题.
来源: http://www.bubuko.com/infodetail-3461500.html