Python求解“棋盘米粒倍增”问题

牟晓东

印度有个古老传说：舍罕王打算奖赏国际象棋的发明人——西萨宰相，在被问及想要得到的赏赐时，西萨回答说：“在棋盘的第1格放1粒大米，第2格放2粒，第3格放4粒，之后的每一格中的米粒数目都是相邻前一格的两倍，一直放到最后的第64格，我只要这一棋盘的大米。”

最初国王不以为意，但最终的结果却是举全国之力都无法填满这个棋盘。果真是这样吗？我们使用Python编程来解决这个“棋盘米粒倍增”问题。

1.常规的循环求和法

首先通过“sum = 0”语句建立并为变量sum赋值为0，准备存放最终的米粒数目;接着使用for循环：“for i in range（64）：”，其中的range（）函数负责提供从0到63共64个循环计数;由于每格中米粒的数目可表示为“2的（n-1）次方”，所以循环体语句为“sum += 2 ** i”，将每次循环得到的该格子中米粒的数量与之前所有格子中米粒的数量和进行求和;循环结束后通过print语句将求和结果输出。

将程序保存为chessrice1.py，运行后得到结果（如图1）：

棋盘米粒的总数为：184467440737

09551615 粒。

2.使用列表推导式计算

Python的列表推导式在逻辑上等同于循环语句，优点是形式简洁且速度快，它能够以非常简洁的方式对列表（或其他可迭代对象）中的元素进行遍历、过滤或再次计算，从而快速生成满足特定需求的列表。

Python的列表推导式可分解为“表达式+循环”两部分，比如通过“sum = sum（[2**i for i in range（64）]）”这一个语句即可完成所有64格子中米粒的数量求和，其中的“2**i”即“表达式”部分，作用是计算每格中的米粒数量;后面的“for i in range（64）”是“循环”部分，作用是控制完成从0到63共64次循环;sum变量的赋值，是通过内置求和sum（）函数来完成的。

之前使用常规循环求和法得到的结果是一个20位长的天文数字，单位是“粒”，不够直观。经查询，1千克大米约有52000粒，通过“mass = int（sum / 52000000）”语句，将这些大米的数目转换成单位为“吨”并进行求整，赋值给mass变量，最后打印输出。

将程序保存为chessrice2.py，运行后得到结果（如图2）：

棋盘米粒的总数为：184467440737

09551615 粒。

这些米粒的总质量为：3547450783

40 吨。

米粒总数的计算结果与循环求和法一致，它们的总质量是个12位数字，约是3547.5亿吨！中国目前每年产大米约2亿吨，所以国王无论如何也拿不出数量如此庞大的大米，根本就填不满宰相的棋盘。

3.两种方法打印“九九乘法表”

不管是使用常规循环求和还是使用列表推导式，我们都可以正确求解“棋盘米粒倍增”问题，二者在各种问题的求解过程中都比较方便，包括循环的嵌套，比如打印“九九乘法表”。

（1）常规的双层循环嵌套

外层循环语句为“for i in range（1，10）：”，作用是从1到9循环;内层循环语句为“for j in range（1，i+1）：”，同样是使用range（）进行对应次数的循环;循环体语句为“print（‘{0}*{1} = {2}.format（j，i，i*j），end=‘ ） ”，这个print语句用到了Python的format（）方法进行字符串格式化，其中的“{0}”、“{1}”和“{2}”是位置参数，作用是将后面“format（j，i，i*j）”中的三个变量的对应数值进行占位输出;“end=‘ ”的作用是設置末尾不换行，而不是print的默认“换行”值;内层循环结束后是一个“print（）”空语句，作用是换行，即打印完同一个乘数（比如同是乘以3）的一行循环后，回车换行。

将程序保存为ninenine1.py，运行后得到“九九乘法表”（如图3）。

（2）列表推导式循环嵌套

外层循环语句仍为“for i in range（1，10）：”，内层直接就是一个列表推导式（因为本身就是一层循环）：“print（“”.join（[“%d*%d=%-2d”%（j，i，j*i） for j in range（1，i+1）]））”。这个print语句中的“join（）”方法是将序列中的元素以指定的字符连接生成一个新字符串，依次连接到前面的“”空串后面;其中的“%d”的作用是将数据按照整型格式化输出，“-”表示左对齐，“2”表示数字不足两位时进行位数补齐（不足位置用空格）。列表推导式后面的循环部分是“for j in range（1，i+1）”语句，与常规双层循环嵌套的内层循环语句完全相同。

将程序保存为ninenine2.py，运行后，同样也得到了“九九乘法表”（如图4）。