蟠桃記

問題描述 :

喜歡西游記的同學肯定都知道悟空偷吃蟠桃的故事，你們一定都覺得這猴子太鬧騰了，其實你們是有所不知：悟空是在研究一個數學問題！
什么問題？他研究的問題是蟠桃一共有多少個！
不過，到最后，他還是沒能解決這個難題，呵呵^-^
當時的情況是這樣的：
第一天悟空吃掉桃子總數一半多一個，第二天又將剩下的桃子吃掉一半多一個，以后每天吃掉前一天剩下的一半多一個，到第n天準備吃的時候只剩下一個桃子。聰明的你，請幫悟空算一下，他第一天開始吃的時候桃子一共有多少個呢？

輸入:

輸入數據有多組，每組占一行，包含一個正整數n（1<n<30），表示只剩下一個桃子的時候是在第n天發生的。

輸出:

輸入數據有多組，每組占一行，包含一個正整數n（1<n<30），表示只剩下一個桃子的時候是在第n天發生的。

樣例輸入:

2 4

樣例輸出:

4 22

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2013

迭代的方法很簡單，直接按題目意思來就可以了。

<span style="font-size:18px;">for (s = n = 1; n &amp;lt; 30; n++)s = (s + 1) * 2;</span>

<span style="font-size:18px;"><br /></span>

<span style="font-size:18px;"><br /></span>

計算機的鼻祖本來就是數學家，自然優化程序的最終方法還是要回歸到數學上。
本題很容易得到它的遞推方程:

f(1) = 1;f(n) = [f(n-1) + 1] × 2;

于是我們得到:

f(n) + 2 = 2 × [f(n-1) + 2] f(1) + 2 = 3=>f(n) + 2 = 3 × 2^n-1=>f(n) = 3 × 2^n-1 - 2

對于這種推斷題還有另外一種遞推方法，雖然對于本題來說很麻煩。但有時候它是無可替代的。

f(1) = 1; f(n) = 2f(n-1) + 2 = f(n-1) + 2f(n-2) + 4;=>f(n) + f(n-1) + 4 = 2 × [f(n-1) + f(n+2) + 4];設 g(n) = f(n) + f(n-1) + 4;則 g(n) = 2 × g(n-1);g(2) = f(2) + f(1) + 4 = 9;∴g(n) = 9 × 2^n-2 (n > 1)∴f(n) + f(n-1) = 9 × 2^n-2 - 4 ①f(n-1) + f(n-2) = 9 × 2^n-3 - 4 ②┋f(3) + f(2) = 9 × 2 - 4f(2) + f(1) = 9 - 4把①式減去②式得f(n) = 9 × 2^n-3 + f(n-2)f(n-2) = 9 × 2^n-5 + f(n-4)┋

這時候，我們需要分類討論了:

n為奇數

f(n) = 9 × 2^n-3 + f(n-2)f(n-2) = 9 × 2^n-5 + f(n-4)┋f(5) = 9 × 2² + f(3)f(3) = 9 + f(1)f(1) = 1從下往上迭代，得:f(n) = 9 × (2^n-3 + 2^n-5 + ... + 2² + 1) + 1 =>f(n) = 9 × (1 - 4^(n-1)/2) ÷ (1 - 4) + 1 =>f(n) = 3 × 2^{n - 1} - 2

n為偶數

f(n) = 9 × 2^n-3 + f(n-2)f(n-2) = 9 × 2^n-5 + f(n-4)┋f(4) = 9 × 2¹ + f(2)f(2) = 4從下往上迭代，得:f(n) = 9 × (2^n-3 + 2^n-5 + ... + 2¹) + 4 =>f(n) = 9 × 2 × (1 - 4^(n-2)/2) ÷ (1 - 4) + 4 =>f(n) = 3 × 2^{n - 1} - 2

世上的事往往如此，巧合的事情經常發生。不得不感嘆大自然的美妙~
現在我們就得到了這道題目的公式了: f(n) = 3 × 2^{n – 1}?– 2

01	#include <math.h>

02	#include <stdio.h>

03

?

04	int?main(void)

05

{

06	????int?n;

07

?

08	????while?(scanf("%d", &n) != EOF)

09	????????printf("%.0f\n", 3 *?pow(2, n - 1) - 2);

10

?

11	????return?0;

12

}

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的hdu 2013 蟠桃记-递推-[解题报告]C++的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。