C语言计算棋盘上的麦粒

在印度有一个古老的传说：舍罕王打算奖赏国际象棋的发明人——宰相达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第 1 个小格里，赏给我 1 粒麦子，在第 2 个小格里给 2 粒，第 3 小格给 4 粒，像这样，后面一格里的麦粒数量总是前面一格里的麦粒数的 2 倍。请您把这样摆满棋盘上所有的 64 格的麦粒，都赏给您的仆人吧！”

国王觉得这要求太容易满足了，于是令人扛来一袋麦子，可很快就用完了。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度的麦粒全拿来，也满足不了那位宰相的要求。

那么，宰相要求得到的麦粒到底有多少呢？假如体积为 1 立方米的麦粒约为 1.42×10⁸粒，请编程计算宰相要求得到的麦粒体积为多少？

问题分析

根据题意，第一格放麦粒 2⁰ 粒，第二格放麦粒 2¹ 粒，第三格放麦粒 2² 粒，……，第 64 格放麦粒 2⁶³ 粒。假设 64 个格子里共放麦粒数量为 s，则：

s = 2⁰ + 2¹ + 2² + … + 2⁶³

设其体积为 t，则：

t = s / ( 1.42 × 10⁸ )

要计算 s 的值，需要 s 从 0 开始累加 64 次，而且每次累加的加数 n（棋盘上每格中的麦粒数）都是上一个加数的 2 倍。因此我们可以使用 for 循环语句来编程解决该问题。

在此，需要特别注意变量 n、s、t 的数据类型。因为越到后面每格中的麦粒数量就越大，第 64 格中的麦粒数为2⁶³，远远超出了 C 语言中长整型数的最大值（2³¹-1）。在计算机中，我们把一个数据的实际值大于计算机可以保存和处理的该类型数据的最大值的情况称为溢出，编程过程中要避免数据溢出的情况发生。

为了避免数据溢出，我们需要把变量 n、s、t 定义为最大可以处理 308 位数字的双精度浮点型（double）。

算法描述

1) 设麦粒总数 s 的初始值为 0，每一格里的麦粒数 n 初始值为 1；
2) 定义循环变量 i；
3) 设定 i 初始值为 1；用 i 控制累加次数；
4) s=s+n；
5) n=n*2；
6) i=i+1；
7) 如果 i<=64，则转到步骤 4，否则转到步骤 8；
8) t=s/(1.42*100000000)；
9) 输出 t 的值；
10) 结束。

代码清单 1：棋盘上的麦粒

#include <stdio.h>
#include <stdlib.h>
int main( )
{
    int i;
    double t;                //定义共需麦粒t立方米
    double s = 0;           //累加器初始化
    double n = 1;           //加数初始化
    for(i=1; i<=64; i++)  //重复64次
    {
        s += n;             //累加
        n *= 2;             //n=n*2,在前一个n的基础上再乘以2
    }
    t = s / (1.42*100000000);    //计算麦粒体积
    printf("共需%.0lf立方米的麦粒！\n",t);
    system("pause");
    return 0;
}

运行结果为：

共需129906648406立方米的麦粒！

程序运行时，循环变量 i 从 1 开始每次递增 1，加数 n 则每次增加为 2n，并累加到变量 s 中。程序运行期间，变量 i、n、s 的值变化情况如表 1 所示：

表 1：代码清单 1 运行过程中各变量的变化情况

循环变量 i	加数 n	累加后的和 s
		0
1	1	1(0+1)
2	2	3(1+2)
3	4	7(3+4)
4	8	15(7+8)
5	16	31(15+16)
6	32	63(31+32)
…	…	…