兔子繁殖问题

问题描述

著名意大利数学家Fibonacci曾提出这样一个问题，说是：有一对兔子，从出生后第3个月起每月都生一对小兔子，小兔子长到第3个月后每个月又生一对小兔子，按此规律，假设兔子没有死亡，第一个月有一对刚出生的小兔子，问第n个月有多少对兔子？

问题分析

对于这类问题，如果仅凭脑子思考，想不明白的话，可以通过模拟兔子生小兔子列式子的方式来做，找出其中的规律

（编程就是通过找题目中的规律，然后抽象，使得可以用通用方式来表达，再将这种通用方式写成某种语言的形式）

第1个月：1

第2个月：1

第3个月：1+1=2（第1个数1表示原来的兔子，第2个数1表示生的小兔子）

第4个月：2+1=3（第1个数2表示上个月的兔子数，第2个数1表示一开始的兔子又生了一对小兔子）

第5个月：3+2=5（第1个数3表示上个月的兔子数，第2个数2表示一开始的老兔子又生了一对小兔子+老兔子的孩子生的一对小兔子，其实就是上上个月的兔子数，上上个月有几对兔子，就会再生几对小兔子）

第6个月：5+3=8

第7个月：8+5=13

由上面的分析可以得到一个规律，就是目前的兔子对数，就是上个月的兔子数+上上个月的兔子数

（其实这个规则，通过数字1 1 2 3 5 8 13….的规律也可以看出来，这就是著名的斐波那契数列。）

参考程序

这个程序可以采用两种方式来实现：

一是采用循环

#include <stdio.h>int main(){ int i,n,llnum=1,lnum=1,temp; scanf("%d",&n); for(i=3;i<=n;i++) { temp=lnum; //把上个月的兔子对数放到一个临时变量里面，因为这个数会成为上上个月的兔子对数 lnum=lnum+llnum;//上个月的兔子对数+上上个月的兔子对数，然后给lnum llnum=temp;//把临时变量中的兔子对数给上上个月的变量 } printf("%d\n",lnum); return 0;}

什么时候用递归？如果规律中出现可以用同一种方式来做事情的情况，就可以用递归了，这里有的同学说，循环也是用同一种方式来做事情，对了，所以递归是可以用循环来实现的。

对于兔子繁殖问题可以这样来写，假设用N(n)表示第n个月的兔子对数，那么N(n)=N(n-1)+N(n-2) ；其中N(n-1）表示 上个月的兔子数，N(n-2）表示上上个月的兔子数。

要注意的问题，递归要有递归跳出的条件，如果没有这种跳出条件，程序就会死掉，就象盗梦空间一样，死在梦里了。

对于这个题目，跳出条件是什么，也就是说是不是能够找到n满足一定条件的时候能有一个具体的值，而不是再去调用自身。这个题目中，N(1)=1,N(2)=1

#include <stdio.h>int fun(int month){ if(month==1){ return 1;//第1个月，1对兔子，递归的跳出条件 } if(month==2){ return 1;//第2个月，1对兔子，递归的跳出条件 } else return fun(month-1)+fun(month-2); //返回上个月的兔子对数+上上个月的兔子对数}int main(){ int n; scanf("%d",&n); printf("%d\n",fun(n));​ return 0;}