时间戳

首页 > 解决方案 > 添加大数的更好方法，Project Euler #13

c - 添加大数的更好方法，Project Euler #13

问题描述

项目欧拉问题13

对于 C 程序，我尝试了实用的方法来解决问题，即不在代码中定义数据，而是使用 scanf 进行输入。

但我不明白为什么输出是错误的！我得到 1373762303 而应该是 5537376230。对于 2-3 个数字来说似乎没问题。

#include <stdio.h>
#include <ctype.h>
#include <strings.h>
#define NUM 50
#define STRINGS 100
#define OUTPUT 10
int main(void) {
    char str[STRINGS][NUM+1];
    int answer[NUM+1] = {0};
    int carry = 0, out_digits = OUTPUT;

    for(int i = 0; i < STRINGS; i++){
        scanf("%s", str[i]);
        for(int j = NUM; j >=0; j--){
            answer[j] += (str[i][j] - 48) + carry;
            if(answer[j] > 9){
                carry = answer[j] / 10;
                answer[j] %= 10;
            }else{
                carry = 0;
            }
        }
    }
    printf("--------------------------------------------------\r\n");
    printf("%d",carry);
    for(int j = 0; j < OUTPUT-1; j++){
        printf("%d",answer[j]);
    }
    printf("\r\n--------------------------------------------------");
    return 0;
}

标签： c

解决方案

scanf用一个从输入构造的字符串填充你给它的数组，包括一个空终止符字节。您正确分配了 51 个字节，但是当您开始添加数字时，您从索引 50 开始，这是 nul 字节的索引。实际数字是从索引 0 到 49。

这意味着您将在某个时候进入答案的个位，因为该数字的答案计算为

answer[50] += (str[i][50] - 48) + carry;
//                        ^^^^ correction applied for ASCII

另一个问题是您忘记在添加每个新数字开始时将进位重置为零。

这可能有效（未经测试），但它仍然不能真正处理高位数字的溢出

for(int i = 0; i < STRINGS; i++){
    scanf("%s", str[i]);
    carry = 0;            // Reset the carry
    for(int j = NUM - 1; j >=0; j--){
        answer[j] += (str[i][j] - 48) + carry;
        if(answer[j] > 9){
            carry = answer[j] / 10;
            answer[j] %= 10;
        }else{
            carry = 0;
        }
    }
}

推荐阅读