c - C 中使用数组的大整数

Question

#include <stdio.h>
#include <math.h>
int main(void) {
    int a[100], carry,i,j=0,length=0,temp,leftcarry=0,l,n;
    clrscr();
    scanf("%d",&n);
    for(i=0;i<100;i++) a[i]=0;
    for(i=1;i<=n;i++){
        a[j]+=i;
        while(a[j]>=10){
            carry=a[j]%10;
            if(a[j]>=pow(10,(j+1))){
                if(leftcarry==0){
                    a[j]=a[j]/10;
                    j++;
                    a[j]+=carry;
                    if(j>length)length=j;
                }
                else{
                    for(l=j+1;l<=length;l++){
                        temp=a[l+1];
                        a[l+1]=a[l];
                        a[l+2]=temp;
                    }
                    a[j+1]=carry;
                    leftcarry=0;
                    length=length+1;
                }
            }
            else{
                a[j]=a[j]/10;
                a[j-1]+=a[j];
                a[j]=carry;
                j--;
                if(a[j]>=10) leftcarry=1;
            }
           }
           j=length;
    }
    for(i=0;i<=length;i++){
        printf("%d",a[i]);
    }
    return 0;
}

我想获得一些使用数组处理大整数的经验，所以我编写了这段代码来查找前 n 个自然数的总和。对于给定的数字<45，我得到了正确的答案。但是对于给定的数字>=45，我得到的答案比正确答案小2。我想知道为什么会这样。我还想知道处理大整数的其他更简单的方法。谢谢。

编辑:谢谢大家的回答。现在问题已经解决了。

Answer 1

我认为这一行是一个错误:

    if(a[j]>=pow(10,(j+1))){

我不知道这是错误还是唯一的错误。

这表示“如果 j 位数字大于或等于 10^(j+1)”。

我认为进位测试只是“j 位数字是否大于或等于 10”。

该数字的“顺序”由它的位置来标识。有时称为位值表示法!就好像“十”列中的“数字”可以达到 99，而千位列中的“数字”可以达到 999。我认为这不是您想要的。

{999,99,9} 不是十进制数!应该是 {9,9,9,9,9,9}。

正如其他人也建议的那样，我强烈建议您实现小端模式，其中最低有效数字位于数组的开头。

然后整个加载就变得更容易，因为您不需要所有的重组代码来腾出空间。

那么您实现的算法将变为:

1. 将 i 添加到单元(位于 a[0])中。
2. 如果a[0]>9，则溢出!取出“多余的”，并迭代地向上移动数字(在数组中向上)添加多余的部分(除以 10)，以在每一步中寻找进一步的溢出。

您应该跟踪数字的“顺序”(a[i]!=0 时最大的 i)以检测固定长度数组的溢出。

您的下一个挑战是编写一个函数 int add_small(int a[100],int d,int p){}。将数字 d*10^p 添加到 a 其中 0<=d<=10 和 0

之后int add_big(int a[100],int b[100])在循环中调用add_small。

如果它对您的谷歌搜索有帮助(并且您还不知道)，您在这里所做的称为“二进制编码的十进制”。这是将 10 进制转换为计算机程序的一种非常自然的方法，但(事实上)并不是处理大整数的非常有效的方法。

它被认为有点硬核，但你应该引用计算机编程的艺术卷。 1 第 4.3.1 章“经典算法”。如果您不是计算机科学专业的本科生，您可以错过。如果您是计算机科学专业的本科生，您有义务立即去图书馆阅读。

编辑:我刚刚看了你的个人资料。 “CSE 本科生，一年级”。它是图书馆。

编辑:如果您坚持异端大端实现，则提示!

1. 设置 j=length-1
2. 设置 a[j]+=i(加法)
3. 如果 a[j]>=10 除以 10 并取余数。
4. 设置 a[j] 中的余数
5. 如果 j 为零，则进入完全溢出!
6. 否则，减少 j 并将步骤 3 中的除法结果添加到 a[j]，然后再次返回步骤 3。
7. 完成!
8. 完全溢出:如果 j 达到零，则将所有内容打乱到一个槽中，增加长度并将步骤 3 中的下溢除法放入 a[0]，如步骤 3 所示。

考虑到您的实现，您可能会多次完全下溢，因此需要成为一个循环。

我想说的是，你的程序中存在结构性错误，对于新手来说比经验丰富的程序员更常见。你只是想在一个循环中做太多事情。分而治之!这就是我们解决计算问题的方式。将您的函数分为一个普通的加法循环，然后是一个将溢出的数字放在数字末尾的改组循环。

正如我一直指出的，如果你是小端的话，事情会更简单!