【算法】 蓝桥杯 高精度加法

时间:2024-01-26 12:08:00

问题描述 
  输入两个整数a和b,输出这两个整数的和。a和b都不超过100位。 

算法描述

  由于a和b都比较大,所以不能直接使用语言中的标准数据类型来存储。对于这种问题,一般使用数组来处理。定义一个数组A,A[0]用于存储a的个位,A[1]用于存储a的十位,依此类推。同样可以用一个数组B来存储b。计算c = a + b的时候,首先将A[0]与B[0]相加,如果有进位产生,则把进位(即和的十位数)存入r,把和的个位数存入C[0],即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加,这时还应将低位进上来的值r也加起来,即C[1]应该是A[1]、B[1]和r三个数的和.如果又有进位产生,则仍可将新的进位存入到r中,和的个位存到C[1]中。依此类推,即可求出C的所有位。

最后将C输出即可。 

输入格式 
  输入包括两行,第一行为一个非负整数a,第二行为一个非负整数b。两个整数都不超过100位,两数的最高位都不是0。

输出格式 
  输出一行,表示a + b的值。 

样例输入 
20100122201001221234567890 2010012220100122

样例输出 
20100122203011233454668012

 

本题目遇到的问题:

(1).对于输入的格式没有空格,是直接以字符串的形式输入的,要怎么样记录该字符串的长度呢

  最开始是用的scanf,但是没有空格的话会被当做一个数字,而不是数组的形式

  改成%s之后不知道该如何记录两个数组的长度,因为strlen函数不适用与整数型的字符串,并且也不能用\n作为计数条件进行计算

  然后想到既然用strlen可以的话,为什么不直接改成字符串数组呢,嗯。。就改成字符串数组:改了之后需要注意的是数组中的每个元素都要-'0'来获取到真正的数值,不然就是ASCII码

(2)对于计算的时候是两个数组是从后面对齐相加的,那么就需要从两个数组的最后开始加

  我开始想的是把输入的数组先翻转一下从0开始加然后再翻转

  但是在知道两个数组长度的情况下就可以用for()从最后开始循环到最前面

(3)对于输出的时候,因为把每个位数该是多少赋值给了C数组,并且也是从个位开始赋值给C中的下标为0的元素的,然后最开始给C数组用memset函数将数组初始化为0

  我们从C的最后面往前面找,找 到第一个不为0的数的时候就记录下来下标,这样就可以从n开始向前面输出(并且在这里不会导致3200000,这种没办法输出,因为低位数是在前面,

  后面的是高位数,应 该从第一个不为0的高位数开始输出)

具体的代码:

#include<stdio.h>
#include<string.h>
#define MAX 110 
int main()
{
    char A[MAX];//因为整形计算不了字符串的长度,不满足要求的输入格式,所以改成字符型 
    char B[MAX];
    char C[MAX];
    int i;
    int j;
    int k=0;
    int r=0;
    int s;
    int n;
    int maxA,maxB; 
    //因为A和B已经输入了所以不用全部赋值为0了 
    memset(C,0,sizeof(C));
    //先按照正常的顺序存进去,再调换位置 
    scanf("%s%s",A,B);//两个字符串数组可以一起存入 
    maxA=strlen(A);
    maxB=strlen(B); 
    //因为已经可以得出当前A和B的最后一位的位置,所以不用再反转数组 
     
    //当前记录的是位数都存在的时候,对应相加 
    for(i=maxA-1,j=maxB-1; i>=0&&j>=0; i--,j--)
    {
        s=(A[i]-'0')+(B[j]-'0')+r; 
        r=s/10;//进位 
        C[k]=s%10;//留在原位的数字 
        k++;
    }
    
    //当某一个长度大于另外一个长度的时候分类讨论
    if(maxA>maxB)
    {
        for(;i>=0;i--)
        {
            s=A[i]-'0'+r;
            r=s/10;//进位 
            C[k]=s%10;
            k++;
        }
     }
     else if(maxA<maxB)
     {
         for(;j>=0;j--)
         {
             s=B[i]-'0'+r;
             r=s/10;//进位 
            C[k]=s%10;
            k++;
         }
      }
      else
      {
          C[k]=r;//如果是处在两个都没有到尽头的时候,就是将最高位加了要进位的在前面加一位用需要进位的r进行保存 
          k++;
       } 
    //反着输出,记录第一个C中不为0的下标 
    for(i=MAX-1; i>=0; i--)
    {
        if(C[i]!=0)
        {
            break;
            n=i;
        }
     }
     for(j=i; j>=0; j--)
     {
         printf("%d",C[j]);
      } 
 }