ETH官方钱包

前往
大廳
主題

ZeroJudge - d213: 長壽的兔子 解題心得

Not In My Back Yard | 2021-08-14 00:00:08 | 巴幣 0 | 人氣 225

題目連結:


題目大意:
假設一隻兔子可以活十年。第 0 年有兩隻小兔子剛出生(因此第十年整時牠們已經逝世了),而之後的每一年出生之兔子數都是前一年出生的兩倍。

輸入有多列,每列給定一非負整數 n(0 ≦ n < 63),試問第 n 年時兔子總數為何?



範例輸入:
0
1


範例輸出:
2
6


解題思維:
定義兩個一維陣列 D 、 B,其中 D[i] 代表第 i 年的兔子總數而 B[i] 為第 i 年出生的兔子數量。

可以看到 D[0] = B[0] = 2,而根據題意 B[i] = 2 × B[i - 1]。

則此時我們可以看到對於 0 < i < 10:
D[i] = D[i - 1] + B[i]
而對於 i ≧ 10:
D[i] = D[i - 1] + B[i] - B[i - 10]

因此我們可以按照上面遞迴式從 D[1] 開始建表,一路到 D[62]。不過因為對於 C++ 等語言而言,需要將陣列 D 、 B 宣告為長整數型態(long long)以免溢位。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
追蹤 創作集

作者相關創作

更多創作