題目詳情
有一天，某只猴子摘了一些桃子，當時吃了一半，又不過癮，于是就多吃了一個。以后每天如此，到第n天想吃時，發現就只剩下一個桃子。輸入n，表示到第n天剩下1個桃子，請計算第一天猴子摘的桃子數。程序運行結果如下：
10
1534
要求
時間限制：2000ms
內存限制：32000kb
輸入格式:
輸入一個整數n,n>0，表示到第n天剩下1個桃子。
輸出格式：
一個整數，表示第1天摘的桃子數。
輸入樣例：
10
輸出樣例：
1534
個人思路
根據題意，設想第0天是第一天剛摘桃子沒吃的時候。
其實第n天發現想吃的時候只有一個桃子的時候
其實是第(n-1)天吃完一半再減一個桃子，也就是就剩最后一個桃子了。
對于夾在中間的天數有這樣規律的遞推
an+1 = an/2 - 1
反過來也就是an = 2*an+1 + 2,
這樣用遞歸也就可以
從第(n-1)天倒推回第0天(第一天剛摘桃子沒吃的時候)的桃子總數。
| 天數 | 總數 |
|---|---|
| 0 | sum |
| 1 | sum/2 + 1 |
| 2 | (sum/2-1)/2 -1 |
| 3 | ((sum/2-1)/2 -1)/2 - 1 |
| … | … |
下面代碼
#include <iostream>
using namespace std;
int main()
{
int Geshu(int day, int n);
int n;
cin>>n;
cout<<Geshu(1,n-1)<<endl; //其實第n天發現想吃的時候只有一個桃子的時候
return 0; //也就是第(n-1)天吃完后就剩最后一個桃子了
}
int Geshu(int sum, int day)
{
if(day==0) //設想第0天是第一天剛摘桃子沒吃的時候
return sum;
return Geshu(2*sum+2,day-1);
}
到此這篇關于C++實現猴子吃桃的示例代碼的文章就介紹到這了,更多相關C++ 猴子吃桃內容請搜索億速云以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持億速云！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
