C语言高精度算法

C语言自带的整数类型在处理较大的数字时会因为超过范围而导致算法出错
所以便有了高精度算法，这里只列出C++的高精度算法
高精算法实际上就是小学学习的竖式运算的代码化而已，理解起来并没有什么难度
以下列出了几种常用的高精度算法：

1.高精度算法之高精度加法

#include<bits/stdc++.h>
using namespace std;
char string1[100],string2[100];
int number1[100],number2[100];
void plus_number(){
    int len;
    len=max(strlen(string1),strlen(string2));
    //len=strlen(string1)>strlen(string2)?strlen(string1):strlen(string2);
    //找到输入的数字里长度最长的那个
    memset(number1,0,sizeof(number1));
    memset(number2,0,sizeof(number2));
    //将输入的字符串初始化为0
    for (int i=strlen(string1)-1;i>=0;i--)
        number1[strlen(string1)-i-1]=string1[i]-'0';
    for (int i=strlen(string2)-1;i>=0;i--)
        number2[strlen(string2)-i-1]=string2[i]-'0';
    //将字符串转化为整数型数组，记得将数组倒过来存储，便于后续操作
    for (int i=0;i<len;i++){
        number1[i]+=number2[i];
        number1[i+1]+=number1[i]/10;
        number1[i]=number1[i]%10;
        //对应位的数据相加，如果加和大于9，则向前进一位，同时对10取余
    }
    if (number1[len]!=0) len++;
    //检查最大位是否相加后有产生进位
    while(number1[len-1]==0&&len>1) len--;
    //去掉0
    for (int i=len-1;i>=0;i--){
        cout<<number1[i];
    }
    cout<<endl;
    //输出结果
}
int main() {
    cin>>string1>>string2;
    plus_number();
    return 0;
}

2.高精度算法之高精度减法

#include<bits/stdc++.h>
using namespace std;
char string1[100],string2[100];
int number1[100],number2[100];
void sub_number(){
    int len;
    bool flag=false;
    len=max(strlen(string1),strlen(string2));
    //len=strlen(string1)>strlen(string2)?strlen(string1):strlen(string2);
    memset(number1,0,sizeof(number1));
    memset(number2,0,sizeof(number2));
    if (strlen(string1)<strlen(string2)||(strlen(string1)==strlen(string2)&&strcmp(string1,string2)<0)){
        flag=true;//记录是否为负数
        for (int i=strlen(string2)-1;i>=0;i--)
            number1[strlen(string2)-i-1]=string2[i]-'0';
        for (int i=strlen(string1)-1;i>=0;i--)
            number2[strlen(string1)-i-1]=string1[i]-'0';
    }else{
        for (int i=strlen(string1)-1;i>=0;i--)
            number1[strlen(string1)-i-1]=string1[i]-'0';
        for (int i=strlen(string2)-1;i>=0;i--)
            number2[strlen(string2)-i-1]=string2[i]-'0';
    }
    //将数据转换为大数减小数
    for (int i=0;i<len;i++){
        number1[i]-=number2[i];
        if (number1[i]<0){
            number1[i+1]--;
            number1[i]+=10;
        }
        //数据相减，如果减得的值为负数，就从前面一位“借十”
    }
    while(number1[len-1]==0&&len>1) len--;
    //确认答案的长度
    if (flag) cout<<"-";
    for (int i=len-1;i>=0;i--){
        cout<<number1[i];
    }
    cout<<endl;
    //输出答案
}
int main() {
    cin>>string1>>string2;
    sub_number();
    return 0;
}

3.高精度算法之高精度乘低精度

#include <bits/stdc++.h>
using namespace std;
char string1[100];
int number[100],low;
void multiply(){
    int len=strlen(string1);
    memset(number,0,sizeof(number));
    for (int i=0;i<len;i++)
        number[len-i-1]=string1[i]-'0';
        //数字倒置,与上面两种方法相似
    int carry=0;//进位
    for (int i=0;i<len;i++){
        number[i]=number[i]*low+carry;
        carry=number[i]/10;
        number[i]%=10;
    }
    //乘法的奥义就是被乘的那个数的每一位总是要乘以乘数
    //所以有“number[i]=number[i]*low+carry;”
    if (carry!=0){
        //这里主要是在处理最后一个进位
        //因为他可能出现的情况有多种：
        //carry大于100...之类的
        //所以还需要再处理一下
        number[len]=carry;
        len++;
        while(number[len-1]>=10){
            number[len]=number[len-1]/10;
            number[len-1]%=10;
            len++;//注意长度
        }
    }
    while (number[len-1]==0&&len>1){
        len--;
    }
    for (int i=len-1;i>=0;i--)
        cout<<number[i];
    cout<<endl;//输出答案
}
int main() {
    cin>>string1>>low;
    multiply();
    return 0;
}

4.高精度算法之高精度乘以高精度

#include <bits/stdc++.h>
using namespace std;
char string1[100],string2[100];
int number1[100],number2[100],ans[10000];
void multiply(){
    int len1=strlen(string1);
    int len2=strlen(string2);
    memset(number2,0,sizeof(number1));
    memset(number1,0,sizeof(number1));
    memset(ans,0,sizeof(number1));
    for (int i=0;i<len1;i++)
        number1[len1-i-1]=string1[i]-'0';
    for(int i=0;i<len2;i++)
        number2[len2-i-1]=string2[i]-'0';
    for (int i=0;i<len1;i++){
        for (int j=0;j<len2;j++){
            ans[i+j]+=number1[i]*number2[j];
            //这个地方可能有点难以理解，拿张草稿纸扒拉两下，你会明白的
        }
    }
    int l=len1+len2-1;
    for (int i=0;i<l;i++){
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
    }
    if (ans[l]>0) l++;
    while (ans[l-1]>=10){
        ans[l]=ans[l-1]/10;
        ans[l-1]%=10;
        l++;
    }
    while (ans[l-1]==0&&l>1) l--;
    for (int i=l-1;i>=0;i--)
        cout<<ans[i];
    cout<<endl;
}
int main() {
    cin>>string1>>string2;
    multiply();
    return 0;
}
/*
    这个版本的乘法与上一个版本的区别在于它开辟了一个新的数组来存储答案
    理解起来可能更加有难度，但是个人更加推荐使用该版本来进行乘法计算
*/

5.高精度算法之高精度除以高精度

/*
    这种方法是将被除数拆成ans个除数，待到被除数已经无法拆出除数时
    得到的ans便是整除的值
*/
#include <bits/stdc++.h>
using namespace std;
char string1[100],string2[100];
int number1[100],number2[100];
int len1,len2;

inline bool cmp(){
    //用于比较两个数的大小关系
    // 大于或等于就返回真值，否则就为假值
    if (len1>len2) return true;
    if (len1<len2) return false;
    for(int i=len1-1;i>=0;i--){
        if (number1[i]>number2[i]) return true;
        if (number1[i]<number2[i]) return false;
    }
    return true;
}

void division(){
    memset(number1,0,sizeof(number1));
    memset(number2,0,sizeof(number1));
    len1=strlen(string1);
    len2=strlen(string2);
    for (int i=len1-1;i>=0;i--)
        number1[len1-i-1]=string1[i]-'0';
    for (int i=len1-1;i>=0;i--)
        number2[len1-i-1]=string2[i]-'0';
    int ans=0;
    while (cmp()){
        ans++;
        for (int i=0;i<len1;i++){
            number1[i]-=number2[i];
            if (number1[i]<0){
                number1[i]+=10;
                number1[i+1]--;
            }
        }
        while (number1[len1]==0&&len1>1) len1--;
    }
    cout<<ans;
}

int main() {
    cin>>string1>>string2;
    division();
    return 0;
}