【C语言】经典兔子问题

ゞ浴缸里的玫瑰 2023-07-11 11:18 2阅读 0赞

## 题目描述 ##

古典问题：有一对兔子，从出生后第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;
    }