汽水瓶兑换问题的三种解法：模拟、递归与公式法及C++实现

1. 题目复述与关键信息拆解我在大学期间刷各类OJ的时候遇到过很多“看似简单、实则藏坑”的基础题这道“汽水瓶”就是其中之一。它常出现在某高校OJ的基础题列表第25题题目本身只有一句话三个空汽水瓶可以换一瓶汽水手里有n个空瓶时最多能喝多少瓶特别的是如果你手里恰好只有2个空瓶可以先向商店借1个空瓶凑成3个换一瓶喝完后把空瓶还给商店。输入多组数据n0结束每组输出对应答案。拿到题的第一反应是“这还不简单循环减2就完了”但真上手写代码后才发现版本差异、边界条件、借瓶规则的理解都可能是扣分点。这道题非常适合用来练习“先建模、再编码”的思维。它不像算法题那样需要复杂的数据结构但很考验你把一个生活中的兑换过程抽象成数学表达式的能力。如果你能把这道题吃透后面遇到“瓶盖换饮料”“空瓶换啤酒”等变体都能很快套用同一套分析框架。这篇文章我会从题目原意开始拆解给出三种不同层次的解法把我调试过程中踩过的坑和总结的经验都写出来最后附上可以直接提交的C代码和自测用例。不管你是刚接触OJ的新手还是想帮别人讲题的老手相信都能从中看到一些有价值的东西。1.1 题目到底在问什么先把手上的空瓶数记为n目标是计算最多可以喝到的汽水瓶数。这里有两个关键词一个是“最多”一个是“可以喝”。很多人只盯着“换”这个动作忘记了换来的汽水喝完之后空瓶还会继续参与兑换。也就是说这是一个动态过程初始有n个空瓶每用3个空瓶换1瓶汽水喝掉后空瓶数要加1手里剩下的空瓶会重新变成下一轮的兑换资本。整个过程会一直持续到手里的空瓶不够3个为止。第二个关键点是“借瓶规则”。常见版本里如果最后手里剩2个空瓶允许先向老板借1个空瓶凑成3个换一瓶汽水喝完新汽水得到1个空瓶再把空瓶还给老板。这样就等价于2个空瓶也能“变”出最后一瓶汽水。题目如果明确写了这个规则那么答案就会比“不借瓶”的模拟结果多出不少。很多第一次做这道题的人都会在这里被卡住。需要特别注意的是只有“2个空瓶”时可以借如果最后只剩1个空瓶借1个也凑不够3个也就无法再换。换句话讲在可借瓶的规则下偶数个空瓶能喝到n/2瓶奇数个空瓶能喝到(n-1)/2瓶。输入输出格式也是容易丢分的地方。题目要求多组输入每行一个正整数n读到0结束。每组输出一个整数占一行。这里的0只是结束标记不是有效数据不能把它当成“0个空瓶”去计算。同时要确保每一行输出都有换行符OJ判题对空白符通常不敏感但漏换行在某些老式OJ上还是可能被判格式错误。1.2 三个隐藏的规则陷阱第一个陷阱是“喝掉后产生的空瓶”必须被纳入计算。举个例子初始有9个空瓶如果只用9除以3等于3答案就是3瓶那就错了。实际过程是9个空瓶换3瓶喝掉后有3个空瓶又可以换1瓶喝掉后剩1个空瓶最终一共喝到4瓶。所以简单整除只在恰好每一步没有剩余空瓶时成立更通用的关系是“剩余空瓶 旧空瓶 % 3 换到的瓶数”。第二个陷阱是“借瓶规则”触发条件很隐蔽。很多人写模拟循环时只在n大于等于3的时候循环然后忽略掉n等于2的情况导致输出比正确答案少1。对于n2正确答案是1。如果你在纸上推一下向老板借1个空瓶凑3个换1瓶喝掉后得到1个空瓶正好还给老板净效果就是喝了1瓶手头最终空瓶为0。所以代码里必须单独处理“剩余空瓶2”的情况或者用公式法直接从根上避免这个坑。第三个陷阱是“多组数据的终止条件”。有些题目用EOF结束有些用0结束这道题明确是0结束。我见过有人用while(cin n)读入所有数然后对每行输出答案导致读到0时也输出了一个0被判WA。虽然这只是一个很小的格式问题但OJ判题只认结果这种细节往往最让人头疼。2. 三种解法从暴力模拟到一行公式这道题很适合用“一题多解”的方式来做因为你会发现模拟法、递归法、公式法得出的答案完全一致但代码量、思维深度和运行效率逐层递进。在实际比赛中用公式法当然最快但理解模拟法和递归法能帮你应对题目规则的变动。下面我分别展开讲。2.1 模拟法跟着规则一步步走模拟法最贴近生活直觉就是“按题目说的规则一瓶一瓶换”。代码思路如下设置答案变量ans初始为0。当前空瓶数cur初始为n。只要cur大于等于3就不断执行本次可以换到的瓶数t cur / 3ans tcur cur % 3 t。因为换到的t瓶汽水喝完后又会变成t个空瓶所以新一轮的空瓶数是“上次没换出去的余数”加上“刚喝出来的空瓶”。循环结束后如果cur等于2说明可以借1个空瓶再喝最后一瓶ans加1。输出ans。这个过程和“人工拿着瓶子去换”完全一致。我在这里写一个完整可运行的C版本#include iostream using namespace std; int simulate(int n) { int ans 0; int cur n; while (cur 3) { int t cur / 3; ans t; cur cur % 3 t; } if (cur 2) { ans; } return ans; } int main() { int n; while (cin n n ! 0) { cout simulate(n) endl; } return 0; }这段代码的优点是容易读懂也容易根据题目规则修改。比如如果不允许借瓶只需要把最后的if语句去掉如果规则改成“4个空瓶换1瓶”只需要把所有的3改成4。缺点是稍微啰嗦而且当n特别大时虽然实际循环次数是O(log n)但堆了一堆临时变量看起来不够简洁。对这道题的数据范围来说模拟法完全够用我甚至推荐新手第一版就写模拟法因为它能帮你验证自己对题意的理解是否正确。2.2 递归法把换瓶过程抽象成递推关系观察模拟过程我们可以将其转化为一个递归关系。设f(n)表示初始有n个空瓶时最多能喝到的汽水瓶数。当n小于3时如果n等于2答案就是1因为可以借1个如果n等于1或0答案就是0。当n大于等于3时我们可以先换n/3瓶喝掉后剩下n % 3 n / 3个空瓶然后继续这个过程于是得到f(n) n / 3 f(n % 3 n / 3)边界条件f(0) 0f(1) 0f(2) 1我写一个递归版本的代码#include iostream using namespace std; int drink(int n) { if (n 2) return 0; if (n 2) return 1; return n / 3 drink(n % 3 n / 3); } int main() { int n; while (cin n n ! 0) { cout drink(n) endl; } return 0; }这个递归形式很优雅但它暴露了一个问题递归深度取决于n被3整除的轮数虽然仍然很小但如果题目把n扩大到10的9次方甚至更大递归函数调用本身会有一定开销。更重要的是这种递推关系还没有显式揭示答案就是n/2它更像是一种“用函数表达过程”的思路。如果你只想知道答案不建议用它来提交但它非常适合做纸面推导。顺便提一个递推的另一种写法。从“净消耗”的角度看每喝一瓶汽水需要消耗3个空瓶但喝完后又得到1个空瓶所以净消耗2个空瓶。于是f(n) f(n - 2) 1。边界是f(0)0f(1)0f(2)1。这样能直接推出f(n)等于n/2向下取整。这种思路我放在下一节详细说明它是解决这道题最漂亮的方法。2.3 公式法为什么答案等于 n/2先直接说结论在“3个空瓶换1瓶且最后2个空瓶可以借瓶再喝一瓶”的规则下n个空瓶最多能喝的汽水瓶数就是n / 2的整数除法结果也就是floor(n/2)。这个结论可以用“净消耗”模型来证明。想象每一次成功喝到一瓶汽水从空瓶数量的角度发生了什么变化首先你支付了3个空瓶换到一瓶未开封的汽水你喝掉它手里多出1个空瓶。所以整个周期结束后你的空瓶数量净减少了2个。如果中间使用了借瓶也不改变净消耗借来的空瓶最终也要用喝出来的空瓶还回去本质上只是让你在“差一个瓶子”的时候提前完成一次交易。设初始空瓶数为n最后喝了x瓶。因为每喝一瓶净减少2个空瓶整个过程至少要消耗2x个空瓶。空瓶数不能变成负数所以必须满足2x ≤ n也就是x ≤ n/2。另一方面只要n≥2你总能通过“凑3个换1瓶”的操作一步一步喝到目标瓶数最多会剩下1个空瓶无法使用当n为奇数时。换句话说上限可以达到所以答案就是n/2向下取整。这个推导还可以解释一个常见的反直觉现象为什么9个空瓶能喝4瓶而不是3瓶因为整个过程等效于每2个空瓶换1瓶汽水9个空瓶能负担4次净消耗剩下1个空瓶用不掉。有了这个公式代码就简化成一行#include iostream using namespace std; int main() { int n; while (cin n n ! 0) { cout n / 2 endl; } return 0; }如果题目明确禁止借瓶答案就不能直接用n/2了。不给借瓶时n2的答案是0n3是1n4是13个换1瓶喝后剩2个不够3个不能再换n5是1n6是2n7是2n8是2n9是3不9个换3瓶喝后3个再换1瓶喝后1个共4瓶这里规则是不借但允许继续换。所以禁止借瓶时需要用模拟法。公式法只有在允许借瓶或题目特别说明空瓶可以赊欠时才成立。3. 我的踩坑记录与调试心得这段我要分享一些实际运行代码时踩过的坑很多不是算法问题而是对题目细节、输入输出和C特性的疏忽。这些坑单独拎出来都很小组合在一起却能把人搞到怀疑人生。3.1 读入循环里的“0”陷阱初版代码我写的是while (cin n) { cout n / 2 endl; }我自信满满地提交结果最后一个测试点超时因为n0时程序没有退出而是输出了一个0然后继续等待输入。OJ的测试数据里0是终止符不是合法数据。后来我改成while (cin n n ! 0) { cout n / 2 endl; }问题就解决了。这里的判断顺序很关键先读n再判断n是否为0如果读入失败或n为0都会跳出循环。如果你想更严谨一点也可以写成while (cin n) { if (n 0) break; cout n / 2 endl; }两种写法都可以但我建议养成“读入后立即判断终止条件”的习惯可以避免很多OJ题里“遇到0停止”的误判。3.2 借瓶规则理解错导致答案差一我第一次做这道题时以为“借瓶”是每换一瓶都可以先欠一个瓶子于是把代码写成了这样int ans 0; while (n 1) { n - 2; ans; }这个代码的答案也是n/2但它不是按照三个瓶子换一瓶的过程来模拟的而是直接套“净消耗2个瓶子”的模型。虽然答案对但我觉得不踏实万一测试数据里n2我的确能输出1万一规则稍有变化比如“不借瓶”这个代码就会错。所以后来我在写题解时都会强调答案公式和过程模拟是两回事只有理解了“净消耗”才能真正理解为什么能这么算。奇怪的是我发现有些同学的代码里先按普通兑换模拟最后再加了一个“if (n 2) ans”却把答案加重复了。举个例子初始n7模拟过程7个空瓶换2瓶剩余1个空瓶喝掉2瓶后得到2个空瓶此时手里一共3个空瓶再换1瓶喝掉后剩1个空瓶。所以正确答案是3。如果有人在循环结束后发现n剩下2就再加1可能会重复计算。写代码前最好在纸上先完整跑一遍流程不要凭感觉。3.3 整数除法与数据类型的选择这道题的数据范围通常不超过1000所以用int完全足够。但如果你在做衍生题n很大比如10的18次方那么直接用int乘2或除2可能会溢出。这时就要用long long。C里整数除法向下取整对非负数没有四舍五入的困扰。但我见过有人为了求“n/2向上取整”写出n / 2 1结果当n为偶数时多算了1。在这道题里答案要求向下取整所以n / 2是安全且准确的。还有一个隐蔽的问题如果题目读入的是字符串需要手动转换可能会遇到前导空格或换行残留。这道题直接用cin n就能跳过空白字符不需要额外处理。如果你用scanf要注意格式符是%d。其实用cin更省心。我个人建议在本地调试时多加几个特殊用例。比如输入1应该输出0输入2应该输出1输入3应该输出1输入6应该输出3。不要只测n10这种常规数据边界值往往是WA的重灾区。4. 题目背后的能力考查与延伸思考很多人刷OJ只是为了AC但我觉得更值得做的是“透过题目看考查点”。一道基础题背后往往藏着三类能力阅读理解、数学建模、代码细节。搞懂这些你以后遇到类似的题会轻松很多。4.1 OJ题目想要训练什么这道题首先考查了“题意提取能力”。题目没有直接告诉你“每瓶汽水相当于2个空瓶”而是用一段生活化描述包装了数学本质。你需要把“3个空瓶换1瓶喝完又多1个空瓶”翻译成“每次净消耗2个空瓶”。这种翻译能力在做算法题时至关重要尤其是面试题里经常出现这种“包装过的简单数学题”。其次它考查了“循环与终止条件控制”。多组输入、遇到0结束是非常常见的输入格式很多学生都会在这里翻车。一个合格的程序员应该能一眼看出这类输入框架并形成肌肉记忆读入数据判断终止条件处理单组逻辑输出结果。最后它考查了“极端边界意识”。n2时能不能借瓶n1时答案是不是0如果题目没有特别说明许多人会默认“只有n3才处理”从而漏掉n2的情况。OJ的测试数据总会包含边界你的算法如果只满足一般规律而不满足边界就会在看不到的地方被扣分。4.2 从汽水瓶到更一般的“兑换”问题如果我们把规则推广为“每m个空瓶换1瓶汽水且允许最后借瓶”那么答案会变成多少用同样的“净消耗”模型分析每喝一瓶汽水支付m个空瓶得到1个空瓶净消耗m-1个空瓶。所以最多能喝到的瓶数就是n / (m - 1)向下取整。比如4个空瓶换1瓶则n个空瓶最多喝n/3瓶5个空瓶换1瓶最多喝n/4瓶。如果不允许借瓶问题变得稍微复杂。这时不能直接套用n/(m-1)的公式因为最后剩余的空瓶可能不足以凑成m个但仍然可能通过分批兑换来最大化瓶数。最稳妥的办法还是模拟法不断用cur / m换新瓶ans累计cur更新为cur % m cur / m直到cur m为止。没有借瓶规则时这个循环结束后的剩余空瓶就彻底用不上了。你会发现在m3、不允许借瓶时答案不再是n/2。我在测试n4时答案是13个换1瓶喝后剩2个无法借所以喝不到第二瓶而允许借瓶时答案是2。所以题目中那一条“借瓶”规则直接改变了结果。再推广一层如果规则变成“瓶子和瓶盖都能换”比如“3个瓶盖换1瓶2个空瓶换1瓶”这就是另一道经典编程题。这时需要同时维护空瓶数和瓶盖数两个变量状态转移会更复杂但核心思想仍然是“喝掉一瓶会同时产生一个空瓶和一个瓶盖”。理解了基础模型你就能把这些变体题当作“同一种套路”来处理。4.3 用数学建模重新看待这类题目我想强调一个思维方式把现实操作转换成“守恒量”。汽水瓶问题中真正守恒的是“总瓶子数 喝掉瓶数 剩余空瓶数 借入空瓶数”只是这个等式写起来有点绕。更实用的做法是找到“每瓶汽水的净成本”。一旦你想明白“净成本是2个空瓶”所有模拟过程都可以被一个简单除法替代。这种思维在更复杂的题目里也是通用的。例如“买啤酒问题”某啤酒2元一瓶2个空瓶可换1瓶啤酒4个瓶盖可换1瓶啤酒问10元最多能喝多少瓶。如果你执着于递归模拟代码会比较长如果你学会寻找“每瓶酒的净价格”或“空瓶、瓶盖折算成钱”就能构造更简洁的解法。虽然这道东华OJ基础题只是一个小小的起点但方法论是可以迁移的。当然数学建模也有局限。当规则中出现“兑换需要附加条件”或“兑换所得不能再次参与兑换”时公式就不再可靠必须回到模拟法。所以我的建议是先建模再验证最后用代码做交叉检查。像我写这篇文章就是用模拟法、递归法、公式法三种方式同时跑确保答案一致。如果你在写代码时对答案没把握可以在本地写两个版本的函数对拍一个模拟一个公式随机生成n对比输出。这是排查隐藏bug非常有效的办法。5. 完整参考代码与自测用例这一部分我直接给出可以提交到OJ的完整代码并整理一份自测数据。你不需要改任何东西复制到编辑器里编译运行输入测试数据就能看到结果。不过在提交之前我还是建议你自己动手写一遍哪怕写得笨一点也比抄答案强。5.1 可直接提交的C代码这是最简洁的公式法版本也是我最终提交的版本#include iostream using namespace std; int main() { int n; while (cin n n ! 0) { cout n / 2 endl; } return 0; }如果你对“为什么直接除2”还有疑虑或者题目版本不允许借瓶那就用下面的模拟法提交原理更通用#include iostream using namespace std; int main() { int n; while (cin n n ! 0) { int ans 0; int cur n; while (cur 3) { int t cur / 3; ans t; cur cur % 3 t; } if (cur 2) { ans; } cout ans endl; } return 0; }两种代码的复杂度都很低。公式法是O(1)模拟法是O(log n)对于这道题的数据范围来说没有任何性能问题。在实际OJ中内存占用几乎可以忽略所以选择哪种完全取决于你对题目的理解是否通透。5.2 自测数据与预期输出我建议你在本地跑这几组数据确认输出和下面表格完全一致输入n预期输出解释10只有1个空瓶无法兑换也无法借21借1个空瓶凑3个换1瓶喝完还瓶313个空瓶换1瓶喝掉剩1个空瓶423个换1瓶后剩2个空瓶借1个再换1瓶52先换1瓶剩2个空瓶加喝后产生的1个共3个再换1瓶636个换2瓶喝后剩2个借1个再换1瓶737个换2瓶余1喝后共3个再换1瓶余1848个换2瓶余2喝后共4个再换1瓶余1喝后共2个借1个再换1瓶949个换3瓶喝后换1瓶喝后剩1个10510个换3瓶余1喝后共4个再换1瓶余1喝后共2个借1个再换1瓶0结束不输出我特别建议你手推一遍n8的过程因为它的轮次比较多容易算错。整个过程是8空瓶 → 换2瓶剩2个空瓶喝掉2瓶后新增2个空瓶手里共4个空瓶4个空瓶换1瓶剩1个空瓶喝掉后新增1个空瓶手里共2个借1个凑3个换1瓶喝掉后还瓶最终喝了2114瓶。你会发现n/24完美吻合。5.3 后续扩展建议做完这道题我建议你继续尝试下面几个变体用来检验自己是否真的理解了模型把“3个空瓶换1瓶”改成“4个空瓶换1瓶”并保留最后的借瓶规则推导答案公式并写代码验证。去掉借瓶规则只允许在空瓶数达到兑换条件时兑换这时n4的答案变成1验证你的模拟法是否还能正确处理。把输入方式改成“读取全部测试数据一次输出全部结果”和“逐个读入逐个输出”两种版本体验一下OJ对输出的宽容度。尝试把模拟法改造成一个函数并在主程序里用一段随机数据对拍“模拟函数”和“公式函数”体会自动化测试的乐趣。我个人在实际练习中的体会是基础题的最大价值不在于“AC”本身而在于你能不能用多种方式解释它。如果某天你能向别人讲清楚“为什么答案是n/2而不是n/3”那你就算真正掌握了这道题。最后再分享一个小习惯每做完一道OJ题我都会把代码保存到本地一个文件夹里并在代码注释中写上题目要求和我的思考过程。这样过几个月回来看能快速回忆起当时的思路也能看到自己进步了多少。这道汽水瓶题虽然简单但如果你愿意深挖它完全可以成为你理解“数学建模 模拟验证”的第一块跳板。