级数求和问题：舍罕王赏麦 - C++

问题介绍

舍罕王赏麦问题是古印度非常著名的一个级数求和问题.舍罕王赏麦问题的大意如下： 传说国际象棋的发明者是古印度的西萨 • 班 • 达依尔，当时的国王是舍罕，世人称之为舍罕王。 当时舍罕王比较贪玩，位居宰相的西萨 • 班 • 达依尔便发明了国际象棋献给舍罕王。舍罕王非常喜欢，为了奖励西萨 • 班 • 达依尔，便许诺可以满足他提出的任何要求。 西萨 • 班 • 达依尔灵机一动，指着 8x8=64 的棋盘说：“陛下，请您按棋盘的格子赏赐我一点 麦子吧，第 1 个小格赏我一粒麦子，第 2 个小格赏我两粒，第 3 个小格赏四粒，以后每一小格都比 前一个小格赏的麦粒数增加一倍，只要把棋盘上全部 64 个小格按这样的方法得到的麦粒都赏赐给我，我就心满意足了。” 舍罕王觉得这是一个很小的要求，便满口答应了，命人按要求给西萨 • 班 • 达依尔准备麦子。但是，不久大臣计算的结果令舍罕王大惊失色。问题是：舍罕王需要赏赐出多少粒麦子呢？

问题分析

国际象棋棋盘总共有8 \ 8 = 6 4 格。按照西萨 班 达依尔的要 求，每一格中放置的麦粒数量如下。 第 1 格：1 粒; 第 2 格：1 x 2 = 2 粒; 第 3 格：1 x 2 x 2 = 4 粒; 第 4 格：1 x 2 x 2 x 2 = 8 粒; ··· 将每一格的麦子粒数加起来：

$$ sum = 1 + 2 + 4 + 8 + 16 + \cdots $$

一直重复到 64 , 将棋盘 8 \ 8 = 64 格都计算完毕便可以计算出赏赐给西萨 • 班 • 达依尔的麦粒数量。如果使用数学的语言来描述，上述式子可以表述为如下形式：

$$ sum=2^0+2^1+2^2+2^3+\cdots+2^{63}=\sum_{i=1}^{63}{2^i} $$

为了方便，可以编写一个算法，用于计算舍罕王赏麦问题。算法的示例代码如下：

double wheat(int n)    //舍罕王赏麦算法
{
    int i;
    double temp, sum;

    temp = 1;
    sum = 0;
    for (i=1;i<=n;i++)
    {
        sum = sum + temp;
        temp = temp * 2;
    }
    return sum;
}

其中，输入参数 n 为棋盘总的格子数。程序中通过 for 循环来计算赏赐的总的麦粒数。程序中定义 sum 为 double 类型，这是因为运算结果是一个 20 位十进制的大数，由此可以看出赏赐数量的庞大。

代码实现

C++ :

#include <iostream>
using namespace std;

double wheat(int n)    //舍罕王赏麦算法
{
    int i;
    double temp, sum;

    temp = 1;
    sum = 0;
    for (i=1;i<=n;i++)
    {
        sum = sum + temp;
        temp = temp * 2;
    }
    return sum;
}
int main()
{
    int n;
    double sum;
    cout<<"舍罕王赏麦问题求解"<<endl;
    cout<<"请输入棋盘格的总数：";
    cin>>n;
    sum = wheat(n);
    cout<<"舍罕王赏总麦粒数为 "<<sum<<" 粒。"<<endl;
    cout<<"大约 "<<sum/25000/1000<<" 吨麦子。"<<endl;
    return 0;
}