首页 > 编程学习 > LQ0262 棋盘放麦子【大数+亿进制】

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

发布时间:2022/11/27 11:00:00

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

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

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

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

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

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

问题分析
这是一个大数计算问题。
用Python语言来实现比较简单,因为有大数类型及运算符。
用Java语言来实现也比较简单,可以用大数来实现,不过也许迭代计算会比较快一些。
用C语言来实现,则需要模拟大数计算,这里采用亿进制来实现。采用迭代计算,计算2n(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);
    }
}

AC的Python语言程序如下:

print(2**64-1)
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式