高精度② P1601 A+B Problem

A+B Problem

目錄

1.1 題目描述

1.2 我の代碼

1.3 佬の代碼

1.4 易錯點

1.5 總結

1.1題目描述

1.2 我の代碼

#include <stdio.h>
#include <string.h>
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    int len1,len2,flag=1;;
    int a[250],b[250],e[250];
    char c[250],d[250];

	//資料處理
    scanf("%s",c);
    getchar();
    len1=strlen(c);
    scanf("%s",d);
    getchar();
    len2=strlen(d);

    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(e,0,sizeof(e));
    for(int i=1;i<=len1;i++){
        a[len1-i+1]=c[i-1]-'0';
    }
    //将字元串數組逆序儲存在int類型數組中
    //原因為：若正序放，如果首位出現進位需要将整個數組向後位移一位
    for(int i=1;i<=len2;i++){
        b[len2-i+1]=d[i-1]-'0';
    }

	//算法核心
    for(int i=1;i<=len1||i<=len2;i++){
        e[i]+=a[i]+b[i];//将每一位相加，并且加上之前的進位
        if(e[i]>9){
            while(e[i]>9){//注意是循環，直到e[i]<10
                e[i]=e[i]-10;
                e[i+1]+=1;//e[i]每減10，e[i+1]進一位
            }
        }
    }

	//輸出部分
    flag=max(len1,len2)+1;//加一是為了防止首位出現進位的情況
    for(int i=flag;i>0;i--){
        if(flag&&e[i]==0)continue;
            flag=0;//隻要出現一個不為0的，flag=0
            //去除字首零（實際上最多隻有一個字首0）
        printf("%d",e[i]);
    }
    getchar();

}
           

1.3佬の代碼

#include<stdio.h>
#include<string>
#include<string.h>
#include<iostream>
using namespace std;
//compare比較函數：相等傳回0，大于傳回1，小于傳回-1
int compare(string str1,string str2)
{
    if(str1.length()>str2.length()) return 1;
    else if(str1.length()<str2.length())  return -1;
    else return str1.compare(str2);
}
//高精度加法
//隻能是兩個正數相加
string add(string str1,string str2)//高精度加法
{
    string str;
    int len1=str1.length();
    int len2=str2.length();
    //前面補0，弄成長度相同
    if(len1<len2)
    {
        for(int i=1;i<=len2-len1;i++)
           str1="0"+str1;
    }
    else
    {
        for(int i=1;i<=len1-len2;i++)
           str2="0"+str2;
    }
    len1=str1.length();
    int cf=0;
    int temp;
    for(int i=len1-1;i>=0;i--)
    {
        temp=str1[i]-'0'+str2[i]-'0'+cf;
        //佬直接在循環裡減‘0’，節約了部分代碼空間
        cf=temp/10;//進位
        //節約了循環的時間
        temp%=10;
        str=char(temp+'0')+str;
    }
    if(cf!=0)  str=char(cf+'0')+str;//把最後的進位也加上
    return str;
}
           

1.4 易錯點

1. 數組開大
2. 注意首位進位的情況，及去除字首0
3. 注意進位

1.5 總結

高精度的核心：

用數組存儲越界數字的每一位，通過模拟加減乘除來得到運算結果

加法算法核心：

//算法核心
    for(int i=1;i<=len1||i<=len2;i++){
        e[i]+=a[i]+b[i];
        if(e[i]>9){
           e[i+1]=e[i]/10;
            e[i]=e[i]%10;
        }