这个题目看着眼熟吧猴子吃桃问题——但凡在学校里学过 Java、C 语言或者刷过一点算法题的人八成都在书里或者卷子上见过它。题目本身不长猴子第一天摘了若干个桃子当场吃了一半觉得不过瘾又多吃了一个第二天早上又把剩下的桃子吃掉一半再加一个之后每天早上都重复这个操作。等到了第 10 天早上猴子准备吃桃子的时候一看——只剩 1 个了。题目问第一天到底摘了多少个桃子很多人第一反应是拿个变量顺着天数往下算结果发现算到一半就卡住了因为顺着推根本不知道第一天摘了多少。实际上这题的破局点只有一个逆推。从第 10 天剩下的 1 个桃子出发反推第 9 天、第 8 天一直到第 1 天。很多初学者栽在这里不是因为不会写 Java而是没把“递推关系”反过来想清楚。这篇文章我打算把这题掰开揉碎讲一遍包括数学建模、Java 的循环解法、递归解法、正向验证以及一些容易踩的坑。既照顾刚接触 Java 的同学也聊点对刷题和面试有帮助的思路。1. 题目到底怎么读先建模而不是先写代码1.1 一个经典的“逆推型”递推问题先把题目完整地复述一遍因为很多网上流传的版本缺了最后一句。完整条件是这样的猴子第一天摘下若干个桃子当即吃了一半觉得不够又多吃了一个。第二天早上它又把剩下的桃子吃掉一半再多加一个。以后每天早上的吃法都和前一天的规则一样吃前一天剩下的一半再多吃一个。直到第 10 天早上猴子想吃桃子时发现只剩下 1 个桃子。每天都不吃坏桃子也没有别的动物偷吃的前提下问猴子第一天一共摘了多少个桃子。这道题在数学上属于典型的递推问题而且是从“末状态”向“初状态”反推的类型。它不像斐波那契数列那样正着推顺手也不像排序那样去模拟一个过程它需要你先把第 n 天和第 n1 天的关系写出来再决定用循环还是递归。从第 n 天到第 n1 天的变化规律是吃了“当天总数的一半再多一个”。用公式表达就是第 n1 天早上剩下的桃子数 第 n 天早上剩下的桃子数 - (第 n 天早上剩下的桃子数 / 2 1)把这个式子整理一下第 n1 天的剩余量 第 n 天的剩余量 ÷ 2 - 1这个式子看着很清楚但有个问题我们是知道最后一天反过来求第一天。所以更常用的是它的逆向形式。把上面的式子做代数变换第 n 天的剩余量 (第 n1 天的剩余量 1) × 2什么意思呢就是如果你知道某一天早上剩下的桃子数那么前一天的桃子数一定是“这一天的剩余量加 1 之后乘以 2”。为什么是这个关系因为猴子每天吃“一半加一个”剩下的恰好就是“原来的一半减一个”。那么原来的一半就等于“剩下的加一个”原来的总数自然就是“剩下的 1× 2”。这个关系是整个题目的核心不管用循环、递归还是公式法都要反复用到它。写代码之前先在草稿纸上把这个公式写明白。1.2 可验证的初始条件和最终条件先把已知条件列出来第 10 天早上剩余的桃子数 1。第 9 天早上剩余的桃子数 (1 1) × 2 4。第 8 天早上剩余的桃子数 (4 1) × 2 10。第 7 天早上剩余的桃子数 (10 1) × 2 22。第 6 天早上剩余的桃子数 (22 1) × 2 46。第 5 天早上剩余的桃子数 (46 1) × 2 94。第 4 天早上剩余的桃子数 (94 1) × 2 190。第 3 天早上剩余的桃子数 (190 1) × 2 382。第 2 天早上剩余的桃子数 (382 1) × 2 766。第 1 天早上剩余的桃子数 (766 1) × 2 1534。所以第一天摘了 1534 个桃子。注意1534 是“第 1 天早上”的总数不是“第一天吃剩下的”。它指的是猴子摘下来、还没有开始吃时的完整数量恰好也是猴子在第一天早上看到的桃子数。这里有个容易混淆的地方很多同学第一步就加错会把第 10 天的 1 直接代入公式算出来第 9 天是 4这个没问题但有人会把第 10 天当成“吃了之后剩 1”于是把第 9 天当成 1这就大错特错了。正向验证一遍第 1 天1534 ÷ 2 1 768剩下 1534 - 768 766第 2 天766 ÷ 2 1 384剩下 382第 3 天382 ÷ 2 1 192剩下 190第 4 天190 ÷ 2 1 96剩下 94第 5 天94 ÷ 2 1 48剩下 46第 6 天46 ÷ 2 1 24剩下 22第 7 天22 ÷ 2 1 12剩下 10第 8 天10 ÷ 2 1 6剩下 4第 9 天4 ÷ 2 1 3剩下 1。第 10 天早上正好剩 1 个。数字对得上说明模型没问题。2. 用 Java 实现的几种思路循环、递归和公式法2.1 最憨但最稳的写法倒序循环既然已经明确了逆向递推公式那就直接用一个循环从第 10 天倒着推回第 1 天。这种写法不烧脑适合所有阶段的开发者。public class MonkeyPeachLoop { public static void main(String[] args) { int peach 1; // 第10天早上的剩余数量 for (int day 9; day 1; day--) { peach (peach 1) * 2; System.out.println(第 day 天早上的桃子数 peach); } System.out.println(第一天摘的桃子数 peach); } }输出结果第9天早上的桃子数 4 第8天早上的桃子数 10 第7天早上的桃子数 22 第6天早上的桃子数 46 第5天早上的桃子数 94 第4天早上的桃子数 190 第3天早上的桃子数 382 第2天早上的桃子数 766 第1天早上的桃子数 1534 第一天摘的桃子数 1534这里最关键的地方是循环变量的边界。peach初始化为 1代表第 10 天早上的剩余量。循环从day 9开始用第 10 天的数据反推第 9 天一直做到day 1就反推出了第 1 天的数量。循环结束之后peach里存的就是第一天的总数。这段代码会在控制台打印每一天的中间结果方便核对。如果不想打印那么多去掉System.out.println那一行即可。从性能上看这个循环只执行 9 次时间复杂度是 O(n)n 是天数空间复杂度是 O(1)只有一个整型变量。这种解法在实际开发里是首选因为它逻辑清晰、不依赖方法调用栈、不会栈溢出调试也简单。2.2 面试官喜欢的写法递归递归在数据结构与算法里占有特殊地位。很多人觉得递归难其实递归就做两件事找到递推关系找准终止条件。拿猴子吃桃来说递推关系已经有了终止条件就是第 10 天剩 1 个。如果定义f(day)表示“第 day 天早上还没吃之前的桃子数”则有f(10) 1f(n) (f(n 1) 1) × 2对应的 Java 代码public class MonkeyPeachRecursion { public static int f(int day) { if (day 10) { return 1; } return (f(day 1) 1) * 2; } public static void main(String[] args) { int result f(1); System.out.println(第一天摘的桃子数 result); } }这个写法里调用f(1)之后会发生连环调用f(1)调用f(2)f(2)调用f(3)……一直调用到f(10)然后f(10)返回 1再一层层往回带值最后算出f(1) 1534。很多初学者会写错终止条件常见错误是写成if (day 1) return 1;。这就完全反了因为题目说的是第 10 天剩 1 个不是第 1 天剩 1 个。这样一写递归会一路算到f(10)甚至更远结果全乱。另一个常见错误是递推公式写反写成return 2 * f(day 1) - 1。这个式子看着稍微有点像算出来结果差之千里。正确写法必须是(f(day 1) 1) * 2这是由“吃一半加一个”反推得到的不要凭感觉乱改。递归的优点是代码短、逻辑与数学定义一致、可读性强。缺点是如果天数很多会占用大量 Java 虚拟机栈空间导致StackOverflowError。本题目只有 10 天递归深度很浅完全没问题。但如果把 10 改成 10000那递归基本上必挂循环解法却毫发无损。所以我在实际工作中倾向于用循环打底递归负责呈现思路。2.3 逼格更高的写法数学公式直接求解用数学方法把递推公式展开可以直接写出通项公式。设第 n 天早上剩余的桃子数为 T(n)已知T(n1) T(n) / 2 - 1做代数变换两边同时加 2T(n1) 2 (T(n) 2) / 2所以T(n) 2构成一个公比为 1/2 的等比数列。于是T(n) 2 (T(10) 2) / 2^(10-n)T(10) 1则T(n) 3 / 2^(10-n) - 2当 n 1 时T(1) 3 / 2^9 - 2 3 × 512 - 2 1534如果你愿意一行代码也能算public class MonkeyPeachFormula { public static void main(String[] args) { int day 10; int result (int) (3 * Math.pow(2, day - 1) - 2); System.out.println(第一天摘的桃子数 result); } }Math.pow(2, 9)等于 512乘 3 减 2 得 1534。公式法的最大优势是时间复杂度 O(1)不管天数多少一次就算出来。但它也有局限需要对递推式做比较熟练的数学变换。如果只是解这道题循环和递归已经完全够用。公式法更适合作为一种“额外视角”去理解题目的本质也能帮你更清晰地看到为什么是 1534 而不是别的数。3. 正向验算、工具函数和边界问题3.1 用正向模拟验证逆向推出来的结果代码写完了数字也输出 1534 了但心里总有点不踏实。怎么确认这个答案是对的最直接的办法是写一段正向模拟假设第一天有 1534 个桃子按题目规则每天吃“一半加一个”连续吃 9 天看看第 10 天早上是不是剩 1 个。public class MonkeyPeachVerify { public static void main(String[] args) { int peach 1534; for (int day 1; day 9; day) { int eaten peach / 2 1; peach peach - eaten; System.out.println(第 day 天吃了 eaten 个剩余 peach 个); } System.out.println(第10天早上剩余 peach); } }输出第1天吃了768个剩余766个 第2天吃了384个剩余382个 第3天吃了192个剩余190个 第4天吃了96个剩余94个 第5天吃了48个剩余46个 第6天吃了24个剩余22个 第7天吃了12个剩余10个 第8天吃了6个剩余4个 第9天吃了3个剩余1个 第10天早上剩余1这个验证过程相当重要。首先它能在做题时帮你排除“公式方向写反”“循环边界搞错”“递归终止条件写错”这类问题。其次它也是一种很通用的编码习惯——任何逆推出来的结果都值得用正向逻辑再走一遍。在真实业务开发里这种思想对应的就是“用另一条路径交叉验证计算结果”排查脏数据时特别好用。3.2 数据类型的隐患int 够用吗猴子吃桃问题里第一天摘了 1534 个int 完全够用。但如果你把题目的参数改一改比如第 20 天早上剩 1 个那第一天摘的桃子就会变成 3×2^19 - 2也就是 1572862int 还能扛得住。可一旦变成第 30 天剩 1 个结果就是 3×2^29 - 2约 16 亿已经接近 int 的上限。如果变成第 31 天结果直接超过 21 亿int 就溢出了。所以写代码时不要默认 int 永远安全。建议根据参数范围选择类型必要时用longpublic class MonkeyPeachLong { public static void main(String[] args) { long peach 1L; for (int day 29; day 1; day--) { peach (peach 1L) * 2L; } System.out.println(第1天桃子数 peach); } }第 31 天用 long 也能算出 6442450942仍然在范围内。要是天数再往上加就得考虑用BigInteger了。虽然这个题目本身不会触发这种极端场景但作为程序员心里要有一根弦所有递推乘法都要警惕溢出。尤其是面试时如果面试官追加一句“如果第 100 天呢”你能立刻答出“需要用 BigInteger 或者用字符串处理”会显得经验很足。如果在循环里加上打印语句还能直观地看到“第 n 天剩余量”增长的速度有多快——第 1 天到第 10 天是指数增长翻倍速度惊人。这也是为什么猴子摘桃这类问题被用来讲解递归和递推时特别合适的缘故数字增长趋势能验证公式还能加深对指数爆炸的直观感受。3.3 方法抽取把“逆推逻辑”和“主流程”分开在实际工程里不建议把所有逻辑都堆在main方法里。哪怕只是一个小算法题也值得把核心逻辑抽成一个方法。这样便于单元测试、便于复用也更接近真实开发的写法。下面这段代码把循环逆推封装成一个静态方法public class MonkeyPeachUtils { /** * 计算第1天早上的桃子总数 * * param lastDay 最后观察的那一天例如第10天 * param lastRemain 最后观察那天早上的剩余桃子数例如1 * return 第1天早上的桃子数 */ public static long calcFirstDayPeach(int lastDay, long lastRemain) { long peach lastRemain; for (int day lastDay - 1; day 1; day--) { peach (peach 1) * 2; } return peach; } public static void main(String[] args) { long result calcFirstDayPeach(10, 1); System.out.println(第一天摘的桃子数 result); } }写成方法之后你还可以加一些防御性参数校验lastDay必须大于等于 2lastRemain必须大于等于 0。如果以后题目改成“第 15 天早上剩 3 个”直接传参进去就行不用改内部逻辑。这是编程习惯的问题但很多人就是在这个小细节上拉开差距的。4. 常见错误和踩坑实录帮你提前排雷4.1 错误一把“第 10 天剩 1 个”当成“第 10 天吃了剩 1 个”这种错误不止一次出现在初学者身上。把题意理解成“猴子在第 10 天吃完之后还剩下 1 个”然后会把第 10 天当成一个被吃过的状态导致反推时多推一步算出来结果变成了 3070。其实题目意思是“第 10 天早上还没吃的时候就剩下 1 个了”。所以第 10 天是观察终点不需要对它再执行一次“吃一半加一个”的规则。怎么避免最简单的办法是读题之后先用手算验证几个数。根据“第 9 天早上 4 个、第 10 天早上 1 个”这个关系你会发现 4 ÷ 2 - 1 1正好符合题意。如果按“第 10 天吃完剩 1 个”理解那第 10 天早上的原始数量应该满足“x ÷ 2 - 1 1”x 4这会让第 9 天变成另一个值和已知递推明显矛盾。多做一步手算比直接写代码更容易发现问题。4.2 错误二循环边界写错循环写法里常见错误是把day从 9 循环到 0或者从 10 循环到 1。这两种都会导致计算结果偏差。正确思路是peach代表“当前已知道的那一天的剩余量”每执行一次循环体就反推前一天。所以第一次进循环计算出来的是第 9 天最后一次进循环计算出来的必须是第 1 天。循环变量应该从lastDay - 1开始到 1 结束。如果你不确定边界建议打印每一天的中间值然后用第 2 节里的正向模拟去验证。代码能跑通不代表结果对输出结果和手算结果一致才算真的对。4.3 错误三递归方向写反递归写法里f(day)依赖f(day 1)而不是f(day - 1)。因为题目给的是末状态反推初状态。一部分同学受“从第 1 天开始推”的思维惯性影响会写出public static int f(int day) { if (day 10) { return 1; } return f(day - 1) / 2 - 1; }这个写法问题很大当day 10时虽然返回 1但f(1)会调用f(0)、f(-1)……根本没完没了最终栈溢出。正确的递归必须保证子问题朝“已经知道答案的边界”靠近。本题的边界是第 10 天所以参数应该增大而不是减小。注意递归递归关键就在“递”和“归”两个方向。末状态已知就朝末状态递归初状态已知就朝初状态递归。写之前先想清楚哪一头是不需要计算的。4.4 错误四直接使用short或byte如果拿byte peach 1来写循环第 3 次就爆了因为(10 1) * 2已经等于 22还是安全的可一旦到第 6、7 次就超过 127byte 溢出变成负数。同理short也不太安全。虽然这个题用 int 就够但把数据类型意识培养起来以后处理其他算法题会有好处。那我会怎么做默认使用int并且在乘法之后回顾一下数字的量级。如果题目参数可能调整或者天数本身是用户输入那我直接上long。代码多写一个L后缀不丢人反而显得严谨。5. 变体训练从一道经典题理解递推思维5.1 换个问法问第 n 天剩余量如果题目变成“已知第一天摘 1534 个求第 n 天早上剩余多少个”这就是正向推导问题了。递推公式T(n1) T(n) / 2 - 1循环可以正着写int peach 1534; for (int day 1; day 9; day) { peach peach / 2 - 1; System.out.println(第 (day 1) 天早上剩余 peach); }这个变体很简单但能帮你理解正推和逆推的本质区别正推是“已知起点求过程”逆推是“已知终点求起点”。平时刷题时判断题目类型是正推还是逆推比急着找公式更重要。5.2 换成“每次吃三分之一加两个”再进一步把条件改成“猴子每天吃剩下桃子的三分之一再多吃两个到第 10 天早上剩 1 个”。那递推关系变成第 n1 天剩余 第 n 天剩余 × (1 - 1/3) - 2 第 n 天剩余 × 2/3 - 2反推公式第 n 天剩余 (第 n1 天剩余 2) × 3 / 2这个变体考的不是死记硬背而是你能不能灵活地从“吃了多少”推出“原来有多少”。如果你只是把这道题当作“背答案”来刷遇到这种微调就会露怯。我建议每个准备面试的朋友把这种递推题的通用模板记牢设 f(n) 表示第 n 天早上的数量根据“吃法”建立 f(n) 和 f(n1) 的关系式确认哪一天是边界用循环或递归实现正向验算。这套模板几乎能覆盖所有“猴子吃桃类”问题。题目怎么变骨架都不变。5.3 在 LeetCode 风格场景里的定位严格来说猴子吃桃不是一道高频算法面试题考链表、二叉树、动态规划的频率远高于它。但它在初学者阶段出现的频率很高因为它是理解“递归”和“递推”的最佳入门素材之一。它比阶乘多了一点弯弯绕比斐波那契多了一点逆推思想又没有复杂的数据结构和边界条件非常适合用来检验一个初学者能不能把数学语言翻译成程序语言。面试时如果真遇到这道题建议的做法是先说思路“我打算从第 10 天逆推到第 1 天”然后写循环版本再补充递归版本最后提一下时间复杂度和溢出风险。一套组合拳打下来基本不会扣分。6. 我在实际处理这类题时的一些写码习惯最后聊点我的个人习惯。每次写这种递推题我一般不会只写一种解法。先把循环版本写出来跑一遍再把递归版本写出来跑一遍最后必然补一个正向验证函数。不要嫌麻烦正向验证代码往往只有几行但对“确认思路没跑偏”特别有用。就像写业务代码时我会对关键计算函数做一层交叉校验用两种不同方式算出同一个指标确保结果一致再入库。这种习惯放在算法题里就是验算。另外如果是教学场景我非常推荐在代码里保留打印语句。看到第 9 天是 4、第 8 天是 10、第 7 天是 22……这些数呈指数增长的时候对“递推公式”的理解会一下子深很多。如果一股脑只输出最终结果虽然简洁但对初学者来说少了很多直观感受。还有一个容易被忽略的点变量命名。很多人写算法题喜欢用x、n、p这样的名字这不是不行但代码可读性会差一些。我倾向于用peach、remain、eaten这类能表达含义的名字。哪怕题目只写 20 行一个好名字也能帮你在调试时少浪费几分钟。尤其在团队协作里同事看你的代码不会盯着你的数学推导过程看只会看变量名和函数名是否表意清晰。如果你打算在博客里复现这道题我建议配一个“天数-剩余数”的表格或者保留中间输出。比如列出从第 1 天到第 10 天的剩余桃子数1534、766、382、190、94、46、22、10、4、1。这张表本身就是递推关系的最好证明。你会发现倒着看是“乘以 2 再加 2”正着看是“除以 2 再减 1”两个方向都在验证同一套逻辑。猴子吃桃这道题本身不难但它是一块很好的试金石。能独立把它写对说明你对递归、循环、递推公式和边界条件已经有了基本感觉。在这基础上再去学动态规划、回溯算法底层思维是相通的。下次再遇到类似题目别急着开 IDE先在草稿纸上把“第 n 天和第 n1 天的关系”写出来。写清楚了代码基本就出来一半了。
