【題目鏈接】

ybt 1312：【例3.4】昆蟲繁殖
附加條件：該題結果可以由long long類型表示

目前成都創(chuàng)新互聯(lián)已為千余家的企業(yè)提供了網(wǎng)站建設、域名、虛擬空間、網(wǎng)站托管維護、企業(yè)網(wǎng)站設計、長治網(wǎng)站維護等服務，公司將堅持客戶導向、應用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。【題目解析】

該題“每對成蟲過x個月產(chǎn)y對卵”這句有誤，實際應該為“每對成蟲過x個月每個月產(chǎn)y對卵”，一本通書第五版P215這道題就是這樣寫的。OJ抄錄時少了“每個月”三個字，導致理解困難。

【題目考點】 1. 遞推 【解題思路】

首先要理解題意
該題中指說的蟲無論是題目還是結果，都是以“對”為單位的，不涉及“一對是兩個”這種換算。
我們認為將蟲子分為三種形態(tài)：卵，幼蟲（不能產(chǎn)卵），成蟲（可以產(chǎn)卵）
題目中每對卵要過2個月長成成蟲，每對成蟲過x個月每個月產(chǎn)y對卵這句話應該這樣理解：

假設這句話中x為3，y為1，我們可以假定有以下具體場景
一對成蟲在1月初產(chǎn)了一對卵，這對卵過2個月，在3月初變?yōu)橐粚τ紫x，再過3個月（也就是x個月），在6月初變?yōu)橐粚Τ上x，這對成蟲在6月初產(chǎn)了一對卵。
這對新的卵過了2個月在8月初變?yōu)橛紫x，在11月初變?yōu)槌上x，并產(chǎn)卵。

我們把不能產(chǎn)卵的蟲稱為幼蟲，這樣更方便理解。

設數(shù)組a與b，a[i]表示第i個月有多少對蟲，b[i]表示第i個月出生的卵的數(shù)量。

• 現(xiàn)在初始狀態(tài)下只有一對剛剛從卵變成的幼蟲，要在x個月之后才能開始第一次產(chǎn)卵。

假設x是3，寫出具體例子理解一下：
1月初有一對剛剛從卵變成的幼蟲，3個月（也就是x個月后）在4月初這對幼蟲變?yōu)槌上x，并產(chǎn)卵。

幼蟲在x個月后，也就是第x+1月才能開始產(chǎn)卵。那么前x個月只有一對蟲，對所有i滿足 1 ≤ i ≤ x 1\le i\le x 1≤i≤x，有a[i]=1，b[i]=0。

• 類比兔子繁殖（斐波那契數(shù)列）問題中：當月的成年兔子可以分為上個月就已經(jīng)是成年的兔子，和這個月剛剛成年的兔子。
  考慮某個月的蟲，可以分為上個月就已經(jīng)有的蟲（成蟲或幼蟲），和這個月剛剛從卵變成的幼蟲。
  第i個月的上個月的蟲子數(shù)量為a[i-1]。
  假設蟲卵在第m月出生，那么這些卵會在第m+2月變?yōu)橛紫x。反過來想，第i個月的剛剛從卵變成的幼蟲，實際是第i-2月出生的蟲卵。第i-2月出生的蟲卵數(shù)量為b[i-2]，所以這部分幼蟲的數(shù)量為b[i-2]。
  因而有a[i] = a[i-1] + b[i-2];
• 假設第m月卵變?yōu)橛紫x，那么第m+x月幼蟲變?yōu)槌上x。反過來想：第i月的成蟲，最晚是在第i-x月從卵變?yōu)橛紫x。第i-x月后再從卵變成的幼蟲，在第i月必然是幼蟲，不是成蟲。。
  第i-x月的成蟲在第i月當然還是成蟲，第i-x月的幼蟲在第i月夜變成了成蟲，第i個月的蟲也不可能來自第i-x月之后變成的幼蟲。因此第i個月的成蟲就是第i-x月的成蟲加幼蟲，即第i-x月的總蟲數(shù)量a[i-x]。
  第i個月的產(chǎn)卵數(shù)量b[i]，為第i個月的成蟲數(shù)量乘以y，即b[i] = a[i-x]*y。
  題目從第1個月開始，求z個月后的蟲子數(shù)量，即為求a[z+1]
• 考慮結果可能的大小。假設x為1，y為20，a的遞推式為 a i = a i ? 1 + 20 ? a i ? 3 > 20 ? a i ? 3 a_i = a_{i-1}+20\cdot a_{i-3} >20*a_{i-3} ai?=ai?1?+20?ai?3?>20?ai?3?，那么當z為50時，求a[z+1]為 a 51 > 20 ? a 48 > 2 0 2 ? a 45 > . . . > 2 0 16 ? a 3 = 2 0 16 a_{51} >20\cdot a_{48} >20^2\cdot a_{45}>...>20^{16}\cdot a_{3} = 20^{16} a51?>20?a48?>202?a45?>...>2016?a3?=2016，求這個數(shù)字的位數(shù): ? 2 0 16 ? + 1 ≈ 23 \lfloor 20^{16} \rfloor + 1\approx 23 ?2016?+1≈23。無法用int或long long類型表示。
  實際上確實如此，如果輸入數(shù)據(jù)為 1 20 50，將a與b的類型設為double，會得到結果約為 1.38 ? 1 0 24 1.38*10^{24} 1.38?1024，和我們的估算是一致的。
• 只能說該題不夠嚴謹，輸入變量范圍給定的不夠準確。該題實際上如果將a與b的類型設為long long，是可以過的。

【題解代碼】 解法1：遞推

#includeusing namespace std;
int main()
{long long a[101], b[101];//a[i]:第i個月有多少對蟲  b[i]:第i個月出生的卵的數(shù)量 
    int x, y, z;
    cin >>x >>y >>z;
    for(int i = 1; i<= x; i++)//前x個月只有第一對幼年蟲 
    {a[i] = 1;
        b[i] = 0;
    }
    for(int i = x + 1; i<= z + 1; i++)//求第z個月后，即第z+1個月 
    {b[i] = a[i-x]*y; 
        a[i] = a[i-1]+b[i-2];
    }
    cout<< a[z+1]<< endl;
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文名稱：信息學奧賽一本通1312：【例3.4】昆蟲繁殖-創(chuàng)新互聯(lián)
轉載源于：http://weahome.cn/article/ddsijs.html