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++ 猴子吃桃内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java猴子吃桃问题

    题目:猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个 第二天早上又将剩下的桃子吃掉一半,又多吃了一个.以后每天早上都吃了前一天剩下 的一半零一个.到第10天早上想再吃时,见只剩下一个桃子了.求第一天共摘了多少. 程序分析:采取逆向思维的方法,从后往前推断. 程序设计: public class 猴子吃桃 { static int total(int day){ if(day == 10){ return 1; } else{ return (total(day+1)+

  • C语言实现的猴子吃桃问题算法解决方案

    本文实例讲述了C语言实现的猴子吃桃问题.分享给大家供大家参考,具体如下: 问题: 猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个.第二天又将剩下的桃子吃掉一半,又多吃了一个.以后每天都吃前一天剩下的一半零一个.到第10天在想吃的时候就剩一个桃子了,求第一天共摘下来多少个桃子? 解析: ① 从最后一天的x=1个,倒推出前一天的个数x,需要注意的是表达式为x=2(x+1),而不是x=2x+1,注意两者之间的区别,想清楚为什么第二种不正确. ② 将该表达式作为循环9次的循环体,并在该语

  • Java实现的猴子吃桃问题算法示例

    本文实例讲述了Java实现的猴子吃桃问题算法.分享给大家供大家参考,具体如下: 猴子吃桃问题 概述:猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个:第二天又将剩下的桃子吃掉了一半,又多吃了一个:以后每天都吃前一天身下的一半零一个,到第n天再想吃的时候就只剩下一个桃子了,求第一天共摘了多少个桃子? 思路及演算步骤(求出共摘多少桃子的函数表达式): 离现在的天数作为变量 f(1) = 1 (剩下桃子的数目) f(2) = f(3) - (吃掉了一些) =   f(3) -(f(3)/

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

    题目详情 有一天,某只猴子摘了一些桃子,当时吃了一半,又不过瘾,于是就多吃了一个.以后每天如此,到第n天想吃时,发现就只剩下一个桃子.输入n,表示到第n天剩下1个桃子,请计算第一天猴子摘的桃子数.程序运行结果如下: 10 1534 要求 时间限制:2000ms 内存限制:32000kb 输入格式: 输入一个整数n,n>0,表示到第n天剩下1个桃子. 输出格式: 一个整数,表示第1天摘的桃子数. 输入样例: 10 输出样例: 1534 个人思路 根据题意,设想第0天是第一天刚摘桃子没吃的时候. 其

  • Python递归实现猴子吃桃问题及解析

    Python递归实现猴子吃桃问题及解析

    目录 Python递归实现猴子吃桃 Python函数(闰年&猴子偷桃)问题 函数 作业 Python递归实现猴子吃桃 猴子吃桃问题:猴子第一天摘下若干个桃子,当即吃了一半,还不瘾,又多吃了一个.第二天早上又将剩下的桃子吃掉一半,又多吃了一个.以后每天早上都吃了前一天剩的一半零一个.到第10天早上想再吃时,见只剩下一个桃子了,求第一天共摘了多少桃子? 对于此性质的问题适合用递归的思想去解决,即当前问题可以转化为性质相同的子问题去解决: 要想知道第一天的桃子数量,需要知道第二天的桃子数量,然后将第二

  • C语言实现的猴子偷桃之类算法

    C基础算法题 好多年没碰C了 很郁闷啊- // // main.c // 算法题 // // Created by mac on 14-8-9. // Copyright (c) 2014年 mac. All rights reserved. // #include <stdio.h> #include <math.h> //10. /* 求S(n) = a+aa+aaa+aaaa+...+aa..a之值,其中a是一个数字,n表示a的位数例如:2+22+222+2222+22222

  • Pygame做一期吃豆子游戏的示例代码

    Pygame做一期吃豆子游戏的示例代码

    Pygame的历史 Pygame是一个利用SDL库的写就的游戏库,SDL呢,全名Simple DirectMedia Layer,是一位叫做Sam Lantinga的大牛写的,据说他为了让Loki(致力于向Linux上移植Windows的游戏的一家大好人公司,可惜已经倒闭,唉好人不长命啊--)更有效的工作,创造了这个东东. SDL是用C写的,不过它也可以使用C++进行开发,当然还有很多其它的语言,Pygame就是Python中使用它的一个库.Pygame已经存在很多时间了,许多优秀的程序员加入其

  • 用p5.js制作烟花特效的示例代码

    用p5.js制作烟花特效的示例代码

    前言 之前看过一篇文章,使用processing制作烟花特效.效果如下 fireworks 网上调查了一圈了,发现processing是一个互动编程软件,java语言发展而来.而且动画效果是跑在processing专门的模拟器上. 不过好在也有对应的web扩展语言,有processing.js和p5.js. processing.js在github上已经好几年没有人维护了,一些processing的特性支持不了.为此踩了不少坑, 本文就集中讲解如何用p5.js写烟花特效. 代码讲解 proces

  • 使用卷积神经网络（CNN）做人脸识别的示例代码

    上回书说到了对人脸的检测,这回就开始正式进入人脸识别的阶段. 关于人脸识别,目前有很多经典的算法,当我大学时代,我的老师给我推荐的第一个算法是特征脸法,原理是先将图像灰度化,然后将图像每行首尾相接拉成一个列向量,接下来为了降低运算量要用PCA降维, 最后进分类器分类,可以使用KNN.SVM.神经网络等等,甚至可以用最简单的欧氏距离来度量每个列向量之间的相似度.OpenCV中也提供了相应的EigenFaceRecognizer库来实现该算法,除此之外还有FisherFaceRecognizer.L

  • Python用类实现扑克牌发牌的示例代码

    1. 题目 编写程序, 4名牌手打牌,计算机随机将52张牌(不含大小鬼)发给4名牌手,在屏幕上显示每位牌手的牌. 提示: 设计出3个类:Card类.Hand类和Poke类. Card类代表一张牌,其中FaceNum字段指出是牌面数字1~13,Suit字段指出的是花色,值"梅"为梅花,"方"为方块,"红"为红心,"黑"为黑桃. Hand类代表一手牌,可以认为是一位牌手手里的牌,其中cards列表变量存储牌手手里的牌.可以增加牌.

随机推荐