LQ0262 棋盘放麦子【大数+亿进制】

2023/6/5 20:27:15

题目来源：蓝桥杯2012初赛 Java C组C题

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

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

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

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

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

问题分析
这是一个大数计算问题。
用Python语言来实现比较简单，因为有大数类型及运算符。
用Java语言来实现也比较简单，可以用大数来实现，不过也许迭代计算会比较快一些。
用C语言来实现，则需要模拟大数计算，这里采用亿进制来实现。采用迭代计算，计算2ⁿ(n=1,2,3,…,64)时，可以避免重复计算。

AC的C语言程序如下：

/* LQ0262 棋盘放麦子 */

#include <stdio.h>
#include <string.h>

typedef long long LL;
#define MOD 100000000LL
#define N 3
LL a[N], sum[N];

int main()
{
    memset(a, 0, sizeof a);
    memset(sum, 0, sizeof sum);

    a[0] = 1;
    for (int i = 1; i <= 64; i++) {
        /* sum += a; */
        LL carry = 0;
        for (int j = 0; j < N; j++) {
            sum[j] += a[j] + carry;
            carry = sum[j] / MOD;
            sum[j] %= MOD;
        }

        /* a *= 2 */
        carry = 0;
        for (int j = 0; j < N; j++) {
            a[j] = a[j] * 2 + carry;
            carry = a[j] / MOD;
            a[j] %= MOD;
        }
    }

    printf("%lld%08lld%08lld\n", sum[2], sum[1], sum[0]);

    return 0;
}

AC的Java语言程序如下：

/* LQ0262 棋盘放麦子 */

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger sum = new BigInteger("0");
        BigInteger TWO  = new BigInteger("2");
        for (int i = 0; i < 64 ; i++)
            sum = sum.add(TWO.pow(i));
        System.out.println(sum);
    }
}

AC的Java语言程序如下：

/* LQ0262 棋盘放麦子 */

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger sum = new BigInteger("0");
        BigInteger a = new BigInteger("1");
        BigInteger TWO  = new BigInteger("2");
        for (int i = 1; i <= 64 ; i++) {
            sum = sum.add(a);
            a = a.multiply(TWO);
        }
        System.out.println(sum);
    }
}