订阅其实程序员还不如小学生
2011 9 22 02:09 PM 5036次查看
分类：编程 标签：无
说实话，当我看到这题时，我第一个想到的解法是极限。
假设每次都能整除，那么这题实际上相当于一个等比数列求和：第一次能喝的汽水数量是1000，公比是1/3，因此结果就是(1000 - 1000 * (1 / 3)n) / (1 - 1 / 3)。当n趋向于正无穷大时，1000 * (1 / 3)n的极限为0，因此结果是1500。考虑到可能会剩下空瓶，所以应该是≤1500。
接着看到程序员的解法，自己也动手写了个：
# -*- coding: utf-8 -*-
def calculate(drinks):
total = 0
times = 0
bottles = 0
while drinks > 0:
times += 1
total += drinks
bottles += drinks
exchanged = bottles / 3
left = bottles % 3
bottles = left
print u'第%d次兑换，喝了%d瓶，兑换了%d瓶，剩%d个空瓶，共喝了%d瓶' % (times, drinks, exchanged, left, total)
drinks = exchanged
calculate(1000)第1次兑换，喝了1000瓶，兑换了333瓶，剩1个空瓶，共喝了1000瓶
第2次兑换，喝了333瓶，兑换了111瓶，剩1个空瓶，共喝了1333瓶
第3次兑换，喝了111瓶，兑换了37瓶，剩1个空瓶，共喝了1444瓶
第4次兑换，喝了37瓶，兑换了12瓶，剩2个空瓶，共喝了1481瓶
第5次兑换，喝了12瓶，兑换了4瓶，剩2个空瓶，共喝了1493瓶
第6次兑换，喝了4瓶，兑换了2瓶，剩0个空瓶，共喝了1497瓶
第7次兑换，喝了2瓶，兑换了0瓶，剩2个空瓶，共喝了1499瓶
最后看到小学生的写法，发现果然简单，而且小学时我确实就是那样解题的…
不过现在又有个新问题了：小学生算出来的结果是1500瓶，比程序员多了一瓶，这难道是整除的原因么？
想了一下后我发现，按照正常情况，空瓶最后总会剩下的：如果剩1～2瓶，自然无法兑换；如果剩3瓶，最后换1瓶，还是会剩1个空瓶——这就是程序员得出1499的原因。
小学生的漏洞在于那个等式其实应该是不等式：x - 1000 ≤ x / 3。
不过现实是最后会剩下2个空瓶，小学生可以先借一瓶，喝完后剩3个空瓶，兑换一瓶还回去，于是就1500瓶了。但傻兮兮的程序员还抱着2个空瓶，自以为是最佳解了…
向下滚动可载入更多评论，或者点这里禁止自动加载。