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

一、问题描述

你一定听说过这个故事。国王对发明国际象棋的大臣很佩服，问他要什么报酬，大臣说：请在第 1 个棋盘格放 1 粒麦子，在第 2 个棋盘格放 2 粒麦子，在第 3 个棋盘格放 4 粒麦子，在第 4 个棋盘格放 8 粒麦子，......后一格的数字是前一格的两倍，直到放完所有棋盘格（国际象棋共有 64 格）。

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

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

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

二、题目要求

考察

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

三、解题思路

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

1.公式法

• 是公比为 2，首项为 1，求解第 4 位元素和的等比数列。

• 利用头文件 #include<math.h>数学公式里面的 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>//定义头文件unsigned long long result;//定义unsigned型resultint main(){    result = pow(2,64)-1;//利用pow公式计算等比数列第64位的数值    printf("%llu",result);//特定格式输出结果    return 0;}

2.直接运算法

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

五、输出结果

输出结果：18446744073709551615