再分麦粒（C语言）

题目描述

在国际象棋棋盘上 (共 64 格) 放麦粒，第一格一粒，…… 后面一格总是前面一格的两倍，摆满整个棋盘后，可放置的麦粒数达到了 18446744073709551615, 如果再继续增加格子，比如格子数到达 3021377 时，放置的麦粒数将达到 909526 位。现要求给定的格子数 n (小于 3100000), 计算放置麦粒数目的最后 500 位数字.

输入描述

一个正整数 n

输出描述

麦粒总数的最后 500 位 (不足 500 位时最高位补 0)

样例输入

11213

样例输出

37229319592369288171375276702260450911735069504025016667755214932073643654199488477010363909372005757899989580775775126621113057905717449417222016070530243916116705990451304256206318289297738303095152430549772239514964821601838628861446301936017710546777503109263030994747397618576207373447725441427135362428360863669327157635983045447971816718801639869547525146305655571843717916875669140320724978568586718527586602439602335283513944980064327030278104224144971883680541689784796267391476087696392191

代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 500

long long num;
int result[N] = {0};
int result1[N] = {0};

void Product()
{
    long long i = 0, s = 0, count = 0, j;

    //这样设计是为了保证第一格的数值不被漏下，也就是2^0 = 1;
    result[499] = 1;
    result1[499] = 1;

    for(i = 0; i < num - 1; i ++)
    {
        //result数组的任务是计算对应的格子中的数量。
        count = 0;

        for(j = N - 1; j >= 0; j --)
        {
            s = result[j] * 2;
            result[j] = (count + s) % 10;
            count = s / 10;
        }

        //result1数组的任务是计算所有格子中的麦粒数量。
        count = 0;

        for(j = N - 1; j >= 0; j --)
        {
            s = result[j] + result1[j];
            result1[j] = (count + s) % 10;
            count = s / 10;
        }

    }
}

void Print()
{
    int i = 0;

        for(i = 0; i < N; i ++)
            printf("%d", result1[i]);

        printf("\n");
}
int main()
{
    while(scanf("%lld", &num) != EOF)
    {
        Product( );
        Print( );

        for(int i = 0; i < N; i ++)
        {
            result[i] = 0;
            result1[i] = 0;
        }
    }
    return 0;
}

分析

• 首先要意识到，这其实就是等比数列求和问题，只不过数据量太大，需要用数组；
• 在乘的过程中，可以借用高精度乘法的思想；
• 设置两个数组，一个是某一格子中的麦粒数量，另一个是前n个格子的麦粒和；
• 循环输入，记得初始化。

注意

每一次使用count前记得斟酌是否需要重新给count重新赋值为0或某个数。

附加（此代码c11可通过而c++14不可ac）

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 500

long long num = 0;
int result[N] = {0};
int result1[N] = {0};

void Product()
{
    long long i = 0;

    //这样设计是为了保证第一格的数值不被漏下，也就是2^0 = 1;
    result[499] = 1;
    result1[499] = 1;

    for(i = 0; i < num - 1; i ++)
    {
        number1();
        number2();
    }
}

void number1()
{
    int count = 0, s = 0, j;

    //result数组的任务是计算对应的格子中的数量。
    for(j = N - 1; j >= 0; j --)
    {
        s = result[j] * 2;
        result[j] = (count + s) % 10;
        count = s / 10;
    }
}

void number2()
{
    int count = 0, s = 0, j;

    //result1数组的任务是计算所有格子中的麦粒数量。
    for(j = N - 1; j >= 0; j --)
    {
        s = result[j] + result1[j];
        result1[j] = (count + s) % 10;
        count = s / 10;
    }
}

void Print()
{
    int i = 0;

    for(i = 0; i < N; i ++)
        printf("%d", result1[i]);

    printf("\n");
}

int main()
{
    while(scanf("%lld", &num) != EOF)
    {
        Product();
        Print();

        for(int i = 0; i < N; i ++)
        {
            result[i] = 0;
            result1[i] = 0;
        }
    }
    return 0;
}

如果有哪位大神知道问题出在哪里，请教教我，感谢！！！

欢迎大家留言，谢谢观看。