C++实现猴子吃桃的示例代码
题目详情
有一天，某只猴子摘了一些桃子，当时吃了一半，又不过瘾，于是就多吃了一个。以后每天如此，到第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++ 猴子吃桃内容请搜索小牛知识库以前的文章或继续浏览下面的相关文章希望大家以后多多支持小牛知识库！
-
本文向大家介绍C语言实现的猴子偷桃之类算法，包括了C语言实现的猴子偷桃之类算法的使用技巧和注意事项，需要的朋友参考一下 C基础算法题 好多年没碰C了 很郁闷啊～ 以上所述就是本文的全部内容了，希望大家能够喜欢，再遇到这种弱智面试题能直接喷死面试官。
-
本文向大家介绍基于C语言实现的贪吃蛇游戏完整实例代码，包括了基于C语言实现的贪吃蛇游戏完整实例代码的使用技巧和注意事项，需要的朋友参考一下 本文以实例的形式讲述了基于C语言实现的贪吃蛇游戏代码，这是一个比较常见的游戏，代码备有比较详细的注释，对于读者理解有一定的帮助。 贪吃蛇完整实现代码如下：
-
本文向大家介绍php实现猴子选大王问题算法实例，包括了php实现猴子选大王问题算法实例的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了php实现猴子选大王问题算法。分享给大家供大家参考。具体分析如下： 一、问题： n只猴子围坐成一个圈，按顺时针方向从1到n编号。 然后从1号猴子开始沿顺时针方向从1开始报数，报到m的猴子出局，再从刚出局猴子的下一个位置重新开始报数， 如此重复，直至剩下一个猴
-
本文向大家介绍C语言实现的PNPoly算法代码例子，包括了C语言实现的PNPoly算法代码例子的使用技巧和注意事项，需要的朋友参考一下 写C语言的实验用到的一个算法，判断一个点是否在多边形的内部。C的代码如下： 其中nvert是多边形顶点的个数，vertx和verty分别是多边形顶点横、纵坐标的数组，textx和testy是待测点的坐标。这个算法是由W. Randolph Franklin提出的，
-
本文向大家介绍C# 实现TXT文档转Table的示例代码，包括了C# 实现TXT文档转Table的示例代码的使用技巧和注意事项，需要的朋友参考一下 代码： 以上就是C# 实现TXT文档转Table的示例代码的详细内容，更多关于c# TXT文档转Table的资料请关注呐喊教程其它相关文章！
-
本文向大家介绍详解C#实现MD5加密的示例代码，包括了详解C#实现MD5加密的示例代码的使用技巧和注意事项，需要的朋友参考一下 C#实现MD5加密，具体如下： 方法一 首先,先简单介绍一下MD5 MD5的全称是message-digest algorithm 5(信息-摘要算法，在90年代初由mit laboratory for computer science和rsa data security