舍罕王赏麦

来自计算思维百科
跳转至: 导航搜索
舍罕王赏麦.png

传说,舍罕王打算重赏象棋的发明人宰相西萨班达依尔。国王问他有何要求,这位聪明的大臣“胃口”看来并不大,他跪着说:“陛下,请您在这个棋盘的第一个小格内,赏我一粒麦子,在第二个小格内给两粒,第三个格内给四粒,按照这样的比例关系,摆满棋盘上所有64格的麦粒,就把这些麦粒都赏给您的仆人罢。”国王听,认为这区区赏金,微不足道,于是满口答应说:“爱卿,你所要求的并不多啊。你当然会如愿偿的。”说着,便令人把一袋麦子拿到宝座前。结果出乎国王的预料,按宰相的方法放,还没有放到20格,一袋麦子就已经用完了。一袋又一袋的麦子被扛到了国王面前。结果,国王发现,如果按此方法摆下去,摆到第64格,即使拿来全国的粮食也兑现不了国王许下的诺言。请你来算算舍罕王到底需要赏出多少麦子。

涉及的计算思维

我们可以看出解决该问题需要循环叠加,所以可以用递归法来解决,体现了计算思维的递归思想。

解决方案

方案一——递归法

第i个棋盘需要放2i个麦粒,这个问题就是要求1+21+22+…+263的和。于是我们可以使用递归法来求解,这里用到的递推公式为:f(n)=f(n-1)+2n-1,其中f(n)表示前n个棋盘覆盖的麦粒之和,f(1)=1是初始值,然后递推求解就可以了。

这个问题也反映了计算复杂度的问题,如果一个问题求解的代价以2i的速度增长,这个增长速度是非常惊人的,也就是说,问题规模越大,求解的代价会达到难以承受,这也就是我们常常提到的NP问题。