HDOJ2569 ( 彼岸 )

f1=3

f2=9

f3=21

f4=51

猜測f(n)=2*f(n-1)+f(n-2)

在紙上打草稿寫出f3的情況，然後推出f4的情況（在f3後邊加*2或*3就成）

f3    f4    f3  f4    f3  f4

111*3    222*3   333*3

112*2    221*2   331*2

113*2    223*2   332*2

121*2    212*2   313*2

131*2    232*2   323*2

211*3    122*3   133*3

311*3    322*3   233*3

有兩種思路（實質是一樣的）：

思路1：f4=2*f3+？（仔細觀察：？代表的就是*3的個數，而他們的共同特點就是末兩位數字相同。去掉他們的最後一位，觀察）

11 12 13

21 22 23

31 32 33

這不正是f2的情況嗎？好，為什麼呢？考慮下，f3末尾兩位數字相同的情況是怎麼來的？不就是把f2的末尾數字重複一遍嗎。

那麼，為什麼不是3*f2呢？因為前邊的2*f3中已經包含了2/3的3*f2了。是以隻需再加1個f2就足夠了。

即f(n)=2f(n-1)+f(n-2)：

思路2：f4=3*f3 -？（仔細觀察：？代表的就是*2的個數，而他們的共同特點就是末兩位數字不同）

Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

<code>#include &lt;stdio.h&gt;</code>

<code>int</code> <code>main()</code>

<code>{</code>

<code>    </code><code>int</code> <code>cas,n,i;</code>

<code>    </code><code>int</code> <code>seq[50];</code>

<code>    </code><code>seq[1]=3;</code>

<code>    </code><code>seq[2]=9;</code>

<code>    </code><code>seq[3]=21;</code>

<code>    </code><code>for</code> <code>(i=4;i&lt;41;i++)</code>

<code>        </code><code>seq[i]=(seq[i-1]&lt;&lt;1)+seq[i-2];</code>

<code>    </code><code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;cas);</code>

<code>    </code><code>while</code><code>(cas--)</code>

<code>    </code><code>{</code>

<code>        </code><code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;n);</code>

<code>        </code><code>printf</code><code>(</code><code>"%d\n"</code><code>,seq[n]);</code>

<code>    </code><code>}</code>

<code>    </code><code>return</code> <code>0;</code>

<code>}</code>

本文轉自ZH奶酪部落格園部落格，原文連結：http://www.cnblogs.com/CheeseZH/archive/2012/05/13/2497881.html，如需轉載請自行聯系原作者