詳解C語言解決經典問題之兔子產子

2022-03-19 13:00:41

1. 問題描述

有一對兔子，從出生後的第 3 個月起每個月都生一對兔子。

小兔子長到第 3 個月後每個月又生一對兔子，假設所有的兔子都不死，問 30 個月內每個月的兔子總數為多少？

2. 題目分析

這是一個有趣的古典數學問題，我們畫一張表來找一下兔子數的規律吧

Tip：不滿 1 個月的兔子為小兔子，滿 1 個月不滿 2 個月的為中兔子，滿3個月以上的為老兔子。

可以看出，每個月的兔子總數依次為 1，1，2，3，5，8，13…這就是 Fibonacci數列。

總結數列規律：即從前兩個月的兔子數可以推出第 3 個月的兔子數。

3. 演演算法設計

該題目是典型的迭代迴圈，即是一個不斷用新值取代變數的舊值，然後由變數舊值遞推出變數新值的過程。

這種迭代與如下因素有關：初值、迭代公式、迭代次數。經過問題分析，演演算法可以描述為：

用C語言來描述選代公式即為fib=fibl+fib2。

其中 fib 為當前新求出的兔子數。

fib1 為前一個月的兔子數。

fib2 中存放的是前兩個月的兔子數，然後為下一次選代做準備。

進行如下的賦值fib2=fib1，fib1=fib，要注意賦值的次序，選代次數由迴圈變數控制，表示所求的月數。

4. 程式碼實現

完整程式碼

#include <stdio.h>

int main()
{
    long fib1 = 1;
    long fib2 = 1;
    long fib = 0;
    int i = 0;
    
    printf("%12d%12d", fib1, fib2); 

    for (i = 3; i <= 30; i++)
    {
        fib = fib1 + fib2; 
        printf("%12d", fib); 
        if (i % 4 == 0)
        {
            printf("n"); 
        }
        fib2 = fib1; 
        fib1 = fib; 
    }
    printf("n");
    return 0;
}

執行結果

程式碼解釋

5. 演演算法升級

這個程式雖然是正確的，但可以進行改進。

目前用 3 個變數來求下一個月的兔子數，其實可以在迴圈體中一次求出下兩個月的兔子數，就可以只用兩個變數來實現。

這裡將fib1+fib2 的結果不放在 fib 中，而是放在 fib1 中，此時 fib1 不再代表前一個月的兔子數，而是代表最新一個月的免子數。

再執行fib2=fib1+fib2，由於此時 fib1 中已經是第 3 個月的兔子數了，因此 fib2 中就是第 4 個月的兔子數了。

可以看出，此時 fib1 和 fib2 均為最近兩個月的兔子數，迴圈可以推出下兩個月的兔子數。

改程序式如下

#include <stdio.h>

int main()
{
	long fib1 = 1, fib2 = 1;
	int i = 0;
	for (i = 1; i <= 15; i++)
	{
		printf("%12d%12d", fib1, fib2);
		if (i % 2 == 0)
		{
			printf("n");
		}
		fib1 = fib1 + fib2;
		fib2 = fib1 + fib2;
	}
	return 0;
}