C++實現(xiàn)猴子吃桃的示例代碼
題目詳情
有一天,某只猴子摘了一些桃子,當時吃了一半,又不過癮,于是就多吃了一個。以后每天如此,到第n天想吃時,發(fā)現(xiàn)就只剩下一個桃子。輸入n,表示到第n天剩下1個桃子,請計算第一天猴子摘的桃子數(shù)。程序運行結(jié)果如下:
10
1534
要求
時間限制:2000ms
內(nèi)存限制:32000kb
輸入格式:
輸入一個整數(shù)n,n>0,表示到第n天剩下1個桃子。
輸出格式:
一個整數(shù),表示第1天摘的桃子數(shù)。
輸入樣例:
10
輸出樣例:
1534
個人思路
根據(jù)題意,設想第0天是第一天剛摘桃子沒吃的時候。
其實第n天發(fā)現(xiàn)想吃的時候只有一個桃子的時候
其實是第(n-1)天吃完一半再減一個桃子,也就是就剩最后一個桃子了。
對于夾在中間的天數(shù)有這樣規(guī)律的遞推
an+1 = an/2 - 1
反過來也就是an = 2*an+1 + 2,
這樣用遞歸也就可以
從第(n-1)天倒推回第0天(第一天剛摘桃子沒吃的時候)的桃子總數(shù)。
天數(shù) | 總數(shù) |
---|---|
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天發(fā)現(xià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++實現(xiàn)猴子吃桃的示例代碼的文章就介紹到這了,更多相關C++ 猴子吃桃內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
c語言實現(xiàn)輸入一組數(shù)自動從大到小排列的實例代碼
下面小編就為大家?guī)硪黄猚語言實現(xiàn)輸入一組數(shù)自動從大到小排列的實例代碼。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2016-09-09Opencv基于CamShift算法實現(xiàn)目標跟蹤
這篇文章主要為大家詳細介紹了Opencv基于CamShift算法實現(xiàn)目標跟蹤,具有一定的參考價值,感興趣的小伙伴們可以參考一下2018-01-01