亲宝软件园·资讯

展开

C++ 猴子吃桃 C++实现猴子吃桃的代码实例

Rage Your Dream.DS 人气:2

题目详情
有一天,某只猴子摘了一些桃子,当时吃了一半,又不过瘾,于是就多吃了一个。以后每天如此,到第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);
}

加载全部内容

相关教程
猜你喜欢
用户评论