算法题每日一练---第2天：棋盘放麦子

一、问题描述

你一定听说过这个故事。国王对发明国际象棋的大臣很佩服，问他要什么报酬，

大臣说：请在第 1 个棋盘格放 1 粒麦子，在第 2 个棋盘格放 2 粒麦子，在第 3 个棋盘格放 4 粒麦子，在第 4个棋盘格放 8 粒麦子，......后一格的数字是前一格的两倍，直到放完所有棋盘格（国际象棋共有 64格）。

国王以为他只是想要一袋麦子而已，哈哈大笑。

当时的条件下无法准确计算，但估算结果令人吃惊：即使全世界都铺满麦子也不够用！

请你借助计算机准确地计算，到底需要多少粒麦子。

二、题目要求

考察

模拟、公式法
建议用时10~25min

三、解题思路

由题目可以得知，从第一个棋盘开始，后面的麦子数量逐渐增加是前一个的2倍，对于计算机来说主要有两种求解方法，一种借助公式、一种直接运算。

1.公式法

• 是公比为2，首项为1，求解第4位元素和的等比数列。
• 利用头文件#include数学公式里面的pow(k,n)，其中k表示数字，n表示k的n次方
• 
  

2.直接运算法

• 使用两重for循环循环64次，每一次结果乘以倍数2。
• 定义sum=1，在for循环中求出剩下63次倍数关系。

拓展：

上述两种方法在代码编写的时候会遇到一个问题就是存储溢出，64位数值的和太大，平时所定义的int、long long 都不能够满足存储。

这时候可以用unsigned long long定义，unsigned long long的最大值：1844674407370955161最大19位，完全可以满足存储需求。定义所输出需要使用%llu 或者 %I64u。

四、编码实现

1.公式法

#include <iostream>#include <math.h>//定义头文件unsignedlonglongresult;//定义unsigned型resultintmain()
{
result=pow(2,64)-1;//利用pow公式计算等比数列第64位的数值printf("%llu",result);//特定格式输出结果return0;
}

2.直接运算法

#include <iostream>usingnamespacestd;
unsignedlonglongn,sum=0,m;//在main函数外面定义，取值范围会增大intmain()
{
for(inti=1;i<=64;i++)//循环64次    {
m=1;//定义m for(intj=1;j<i;j++)//求和        {
m=2*m;//彼此相乘            }
sum+=m;//等比数列求和     }
cout<<sum;//输出结果return0;
}

五、输出结果

输出结果：18446744073709551615