【演算法】 藍橋杯 高精度加法

問題描述 
  輸入兩個整數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]);
      } 
 }