大整数加法

上次【计算机程序设计2】课程讲到了大整数运算,之前我没有接触过这个。仅仅大整数加法的代码我就写了好久=

百练

几次提交

代码主要分为3个部分,输入部分,算法处理加法部分,输出部分。几个麻烦的地方:

  1. 输入处理,感觉每次上机题输入部分我都要花好多时间。
  2. 因为数字加法是从最低位开始相加,而输入是从最高位开始读入(作为数组下标小的部分),所以需要倒序。

第一次提交

一开始我是用整型数组来表示大整数,但我忘记考虑了前导零的情况。(还有可能有其他错误)

/*
  ASCII 0~48, 9~57
*/

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

#define N 200

int main()
{
    int ai[N] = {0}, bi[N] = {0};    //ai,bi是倒序输入的数字
    int a[N] = {0}, b[N] = {0};      //a,b把倒序改成正序
    int s[N+1]={0};
    int i, j, k, n, m;

    //输入部分,从高位往低位输入
    for (i=0; (n=getchar()) != '\n'; i++)  ai[i] = n - 48;
    for (j=0; (n=getchar()) != '\n'; j++)  bi[j] = n - 48;
    for (k=0; k<i; k++)                    a[k] = ai[i-k-1];
    for (k=0; k<j; k++)                    b[k] = bi[j-k-1];

    //计算部分,从低位往高位计算
    for (k=0; k= 10) {
            s[k] = m - 10;
            s[k+1] = 1;
        }
        else {
            s[k] = m;
        }
    }

    //输出部分,从高位往低位输出
    if (s[k] != 0)           printf("%d", s[k]);
    for (i=k-1; i>=0; i--)   printf("%d", s[i]);
    printf("\n");

    return 0;
}

状态: Wrong Answer

第二次提交

考虑了前导零的情况,使得输入部分的代码变得麻烦了一些,但是0+0的情况将会输入错误。

/*
  ASCII 0~48, 9~57
*/

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

#define N 200

int main()
{
    int i, j, k, n, m;
    int ai[N] = {0}, bi[N] = {0};    //ai,bi是倒序输入的数字
    int a[N] = {0}, b[N] = {0};      //a,b把倒序改成正序
    int s[N+1] = {0};

    //输入部分,从高位往低位输入
    while ((n=getchar()) == '0');    //排除前导0
    ai[0] = n - 48;
    for (i=1; (n=getchar()) != '\n'; i++) {
        ai[i] = n - 48;
    }

    while ((n=getchar()) == '0');
    bi[0] = n - 48;
    for (j=1; (n=getchar()) != '\n'; j++) {
        bi[j] = n - 48;
    }
    //逆序改回顺序
    for (k=0; k<i; k++)  a[k] = ai[i-k-1];
    for (k=0; k<j; k++)  b[k] = bi[j-k-1];

    //计算部分,从低位往高位计算
    for (k=0; k= 10) {
            s[k] = m - 10;
            s[k+1] = 1;
        }
        else {
            s[k] = m;
        }
    }

    //输出部分,从高位往低位输出
    if (s[k] != 0)           printf("%d", s[k]);
    while (k > 0) {
        printf("%d", s[k-1]);
        k--;
    }
    printf("\n");

    return 0;
}

状态: Runtime Error

第三次提交

感觉用整型数组存储大整数,挺浪费内存的(int 在64位机器上是4个字节,而我们只需要表示0~9),而且输入部分很麻烦,所以改用字符数组(char 在64位机器上是1个字节)。

用了字符数组之后,输入部分做了较大的改动,为了排除前导零以及输入为0+0的情况,我采用了指针。

/*
  ASCII 0~48, 9~57
*/

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

#define N 200

int main()
{
    int k, m;
    char ai[N] = {0}, bi[N] = {0};    //ai,bi是倒序输入的数字
    char *pa = ai, *pb = bi;
    char a[N] = {0}, b[N] = {0};      //a,b把倒序改成正序
    char sum[N+1] = {0};
    int a_len, b_len, s_len;

    //输入部分,注意是从高位往低位输入
    scanf("%s", ai);
    scanf("%s", bi);

    //排除前导0
    while (*pa=='0' && *(pa+1)!='\0')  pa++;
    while (*pb=='0' && *(pb+1)!='\0')  pb++;
    a_len = strlen(pa);
    b_len = strlen(pb);

    //逆序改回顺序,并且把ASCII值换成数字大小
    for (k=0; k<a_len; k++)  a[k] = *(pa+a_len-k-1) - 48;
    for (k=0; k<b_len; k++)  b[k] = *(bi+b_len-k-1) - 48;

    //计算部分,从低位往高位计算
    for (k=0; k= 10) {
            sum[k] = m - 10;
            sum[k+1] = 1;
        }
        else {
            sum[k] = m;
        }
    }

    //输出部分,从高位往低位输出
    s_len = strlen(sum);
    if (sum[k] != 0)  printf("%d", sum[k]);
    while (k > 0) {
        printf("%d", sum[k-1]);
        k--;
    }
    printf("\n");

    return 0;
}

状态: Wrong Answer

第四次提交

花了快半个小时…才发现第三次提交代码中有一个笔误(第三次提交第32行,bi改成pb),其他并没有大的修改。感悟是,如果写代码的过程中进行了比较大的修改,经常会有一些细节被漏掉,这时候 debug 好浪费时间 = =。所以最好一开始就选择对的框架,避免半途中代码重构。

/*
  ASCII 0~48, 9~57
*/

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

#define N 200

int main()
{
    int k, m;
    char ai[N] = {0}, bi[N] = {0};    //ai,bi是倒序输入的数字
    char *pa = ai, *pb = bi;
    char a[N] = {0}, b[N] = {0};      //a,b把倒序改成正序
    char sum[N+1] = {0};
    int a_len, b_len;

    //输入部分,注意是从高位往低位输入
    scanf("%s", ai);
    scanf("%s", bi);

    //排除前导0
    while (*pa=='0' && *(pa+1)!='\0')  pa++;
    while (*pb=='0' && *(pb+1)!='\0')  pb++;
    a_len = strlen(pa);
    b_len = strlen(pb);

    //逆序改回顺序
    for (k=0; k<a_len; k++)  a[k] = *(pa+a_len-k-1) - 48;
    for (k=0; k<b_len; k++)  b[k] = *(pb+b_len-k-1) - 48;

    //计算部分,从低位往高位计算
    for (k=0; k= 10) {
            sum[k] = m - 10;
            sum[k+1] = 1;
        }
        else {
            sum[k] = m;
        }
    }

    //输出部分,从高位往低位输出
    if (sum[k] != 0)  printf("%d", sum[k]);
    while (k > 0) {
        printf("%d", sum[k-1]);
        k--;
    }
    printf("\n");

    return 0;
}

状态: Accepted

另外,我把这学期的上机代码放到了 GitHub 上

 

2 thoughts on “大整数加法

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.