C++實(shí)現(xiàn)猴子吃桃的示例代碼
題目詳情
有一天，某只猴子摘了一些桃子，當(dāng)時(shí)吃了一半，又不過(guò)癮，于是就多吃了一個(gè)。以后每天如此，到第n天想吃時(shí)，發(fā)現(xiàn)就只剩下一個(gè)桃子。輸入n，表示到第n天剩下1個(gè)桃子，請(qǐng)計(jì)算第一天猴子摘的桃子數(shù)。程序運(yùn)行結(jié)果如下：
10
1534
要求
時(shí)間限制：2000ms
內(nèi)存限制：32000kb
輸入格式:
輸入一個(gè)整數(shù)n,n>0，表示到第n天剩下1個(gè)桃子。
輸出格式：
一個(gè)整數(shù)，表示第1天摘的桃子數(shù)。
輸入樣例：
10
輸出樣例：
1534
個(gè)人思路
根據(jù)題意，設(shè)想第0天是第一天剛摘桃子沒(méi)吃的時(shí)候。
其實(shí)第n天發(fā)現(xiàn)想吃的時(shí)候只有一個(gè)桃子的時(shí)候
其實(shí)是第(n-1)天吃完一半再減一個(gè)桃子，也就是就剩最后一個(gè)桃子了。
對(duì)于夾在中間的天數(shù)有這樣規(guī)律的遞推
an+1 = an/2 - 1
反過(guò)來(lái)也就是an = 2*an+1 + 2,
這樣用遞歸也就可以
從第(n-1)天倒推回第0天(第一天剛摘桃子沒(méi)吃的時(shí)候)的桃子總數(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; //其實(shí)第n天發(fā)現(xiàn)想吃的時(shí)候只有一個(gè)桃子的時(shí)候
return 0; //也就是第(n-1)天吃完后就剩最后一個(gè)桃子了
}
int Geshu(int sum, int day)
{
if(day==0) //設(shè)想第0天是第一天剛摘桃子沒(méi)吃的時(shí)候
return sum;
return Geshu(2*sum+2,day-1);
}
到此這篇關(guān)于C++實(shí)現(xiàn)猴子吃桃的示例代碼的文章就介紹到這了,更多相關(guān)C++ 猴子吃桃內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++實(shí)現(xiàn)LeetCode(95.獨(dú)一無(wú)二的二叉搜索樹(shù)之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(95.獨(dú)一無(wú)二的二叉搜索樹(shù)之二),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
C語(yǔ)言中#pragma?pack(1)的用法與注意點(diǎn)
#pragma用于指示編譯器完成一些特定的動(dòng)作,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中#pragma?pack(1)的用法與注意點(diǎn)的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-02-02
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中二分查找遞歸非遞歸實(shí)現(xiàn)并分析
這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)中二分查找遞歸非遞歸實(shí)現(xiàn)并分析的相關(guān)資料,需要的朋友可以參考下2017-03-03
變量存放在內(nèi)存中，內(nèi)存其實(shí)就是一組有序字節(jié)組成的數(shù)組，每個(gè)字節(jié)有唯一的內(nèi)存地址。CPU 通過(guò)內(nèi)存尋址對(duì)存儲(chǔ)在內(nèi)存中的某個(gè)指定數(shù)據(jù)對(duì)象的地址進(jìn)行定位。數(shù)據(jù)對(duì)象是指存儲(chǔ)在內(nèi)存中的一個(gè)指定數(shù)據(jù)類(lèi)型的數(shù)值或字符串，它們都有一個(gè)自己的地址，指針是保存這個(gè)地址的變量2021-10-10
C 與 C++ 接口函數(shù)相互調(diào)用的實(shí)現(xiàn)
這篇文章主要介紹了C 與 C++ 接口函數(shù)相互調(diào)用的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
QT中線程池QThreadPool類(lèi)概念和使用方法詳解
這篇文章主要為大家介紹了QT中線程池QThreadPool類(lèi)概念和使用方法詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-09-09
淺談C++日志系統(tǒng)log4cxx的使用小結(jié)詳解
本篇文章是對(duì)C++日志系統(tǒng)log4cxx的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++ STL priority_queue自定義排序?qū)崿F(xiàn)方法詳解
這篇文章主要介紹了C++ STL priority_queue自定義排序?qū)崿F(xiàn)方法詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
這篇文章主要介紹了C++11中的default函數(shù)使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
本篇文章是對(duì)C++中的求組合數(shù)的各種方法進(jìn)行了詳細(xì)的介紹。需要的朋友參考下2013-05-05