问题介绍

舍罕王赏麦问题是古印度非常著名的一个级数求和问题.舍罕王赏麦问题的大意如下:
传说国际象棋的发明者是古印度的西萨 • 班 • 达依尔,当时的国王是舍罕,世人称之为舍罕王。 当时舍罕王比较贪玩,位居宰相的西萨 • 班 • 达依尔便发明了国际象棋献给舍罕王。舍罕王非常喜欢,为了奖励西萨 • 班 • 达依尔,便许诺可以满足他提出的任何要求。
西萨 • 班 • 达依尔灵机一动,指着 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;
}
Last modification:March 31st, 2021 at 07:27 am
赠人玫瑰,手有余香。您的赞赏是对我最大的支持!