高精度算法

1.高精度实现2的n次方

对应牛客网链接：

2的N次方_牛客题霸_牛客网 (nowcoder.com)

题目描述：

解题思路：

由于N的范围较大如果我们采用long long 类型的数字进行存储肯定会栈溢出，因此我们只能使用数组进行模拟也就是高精度。

1.我们将数组的第一个位置和第二个位置设置为1，第一个位置的数字代表长度，第二个位置的数字代表初始值。

1 1

第一次*2：

1 2

第二次*2：

1 4

第三次乘2

1 8

第四次*2

116

此时我们发现16大于10产生了进位，此时我们需要对16进行取余，并且长度+1：

2 6 1

第四次*2:

2 16 2

对16进行取余并进位：

2 6 3

重复上述步骤就完成了模拟了。

对应代码：

#include<iostream>
#include<vector>
using namespace std;
int main(){
   int n;
   cin>>n;
   vector<int>arr(n);
   arr[0]=1;//代表当前长度
   arr[1]=1;//代表初始值
    for(int i=0;i<n;i++){
        int carry=0;//进位
        for(int j=1;j<=arr[0];j++){
            arr[j]=arr[j]*2+carry;//加上进位
            carry=arr[j]/10;//进位
            arr[j]%=10;//取余
        }
        if(carry){//如果有进位
            arr[++arr[0]]=carry;//进位不是0就是1
        }
    }
    for(int i=arr[0];i>=1;i--){//反项输出
        cout<<arr[i];
    }
    
}

2.高精度实现阶乘

对应牛客网链接：

求整数的阶乘_牛客题霸_牛客网 (nowcoder.com)

题目描述：

解题思路：

本题思路和上题基本一样只不过本题每次乘的数不在是2而是i，进位可能不在是10可能会很大，具体请看代码：

对应代码：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>arr(3*n);
    arr[0]=1;
    arr[1]=1;
    for(int i=1;i<=n;i++){
        int carry=0;//进位
        for(int j=1;j<=arr[0];j++){
            arr[j]=arr[j]*i+carry;//每次*i并且加上进位
            carry=arr[j]/10;//进位
            arr[j]%=10;
        }
        while(carry){//直到进位为0
            arr[++arr[0]]=carry%10;//进位可能很大，超过10
            carry/=10;
        }
    }
    for(int i=arr[0];i>=1;i--){//逆序输出
        cout<<arr[i];
    }
}

3.高精度实现加法

高精度加法博主之前已经写过了在这里就不写了。

对应链接：

(1249条消息) 加法模板一类题一网打尽_一个山里的少年的博客-CSDN博客

4.高精度实现减法

对应OJ链接：

P2142 高精度减法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

高精度实现减法和加法有一点点去别如果第一个数小于第二个数时会出现负数，因此我们默认第一个数比较大，如果第一个数小则交换。在根据小学的减法规则不够就向前借位，具体请看代码

对应代码：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    string s1,s2;
    cin>>s1>>s2;
    if(s1.size()<s2.size()||(s1.size()==s2.size()&&s1<s2)){
        //第一数小于第二个数
        s1.swap(s2);
        cout<<"-";
    }
    vector<int>a(s1.size()+1);
    vector<int>b(s1.size()+1);
    vector<int>c(s1.size()+1);
    for(int i=0;i<s1.size();i++){
        a[s1.size()-i]=s1[i]-'0';
    }
    for(int i=0;i<s2.size();i++){
        b[s2.size()-i]=s2[i]-'0';
    }
    for(int i=1;i<=s1.size();i++){
        if(a[i]<b[i]){//不够减向前借位
            a[i+1]--;
            a[i]+=10;
        }
        
        c[i]=a[i]-b[i];

    }
    int len=s1.size();
    while(c[len]==0&&len>1){//消除前导0
        len--;
    }
    for(int i=len;i>=1;i--){
        cout<<c[i];
    }
    
}

5.高精度实现乘法

高精度乘法其实和就是在模拟我们小学时的计算方法：

对应代码：

class Solution {

public:

    string multiply(string num1, string num2) {

        int n1=num1.size();

        int n2=num2.size();

        string res(n1+n2,'0');

        for(int i=n2-1;i>=0;i--){

            for(int j=n1-1;j>=0;j--){

                int tmp=(res[i+j+1]-'0')+(num1[j]-'0')*(num2[i]-'0');

                res[i+j+1]=tmp%10+'0';//当前位

                res[i+j]+=tmp/10; //前一位加上进位，res[i+j]已经初始化为'0'，加上int类型自动转化为char，所以此处不加'0'

            }

        }

        

//去除首位的前导零

        for(int i=0;i<n1+n2;i++){

            if(res[i]!='0')

                return res.substr(i);

        }

        return "0";

       

        

    }

};

6.高精度实现阶乘和

对应OJ链接：

P1009 [NOIP1998 普及组] 阶乘之和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

解题思路：

解题思路分为两部：

1.现计算阶乘

2.计算和

解题请看代码

对应代码：

#include<vector>
#include<iostream>
using namespace std;
void fact(int n,vector<int>&tmp) {
    int carry = 0;//进位
    for (int j = 1; j <= tmp[0]; j++) {
        tmp[j] = tmp[j] * n + carry;
        carry = tmp[j] / 10;
        tmp[j] %= 10;
    }
    while (carry) {
        tmp[++tmp[0]] = carry % 10;
        carry /= 10;
    }
}
void add(vector<int>&sum,vector<int>&tmp) {
    if (sum[0] < tmp[0]) {
        sum[0] = tmp[0];
    }
    int carry = 0;//进位
    for (int i = 1; i <= sum[0]; i++) {
        sum[i] = sum[i] + carry + tmp[i];
        carry = sum[i] / 10;
        sum[i] %= 10;
    }
    if (carry) {
        sum[++sum[0]] = carry;
    }
}
int main() {
    int n;
    cin >> n;

    vector<int>sum(2 * n);
    sum[0] = 1;//代表长度；
    vector<int>tmp(2 * n);
    tmp[0] = 1;//代表长度
    tmp[1] = 1;//代表初始值
    for (int i = 1; i <= n; i++) {
        fact(i,tmp);
        add(sum, tmp);
    }

    for (int i = sum[0]; i >= 1; i--) {
        cout << sum[i];
    }
    return 0;
}

7.高精度计算序列和

对应OJ链接：

题目详情 - 7-38 数列求和-加强版 (20 分) (pintia.cn)

题目描述：

给定某数字A（1≤A≤9）以及非负整数N（0≤N≤100000），求数列之和S=A+AA+AAA+⋯+AA⋯A（N个A）。例如A=1, N=3时，S=1+11+111=123。

输入数字A与非负整数N。

输出其N项数列之和S的值。

1 3

123

解题思路和加法基本一样，老铁可以在纸上画一画。

对应代码：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,A;
    cin>>A>>n;
    if(n==0){
        cout<<0;
        return 0;
    }
    long long  carry=0;//进位
    vector<int>arr(5*n);
    int high=0;
    int i;
    for( i=0;i<n;i++){
        arr[i]=((n-i)*A+carry)%10;//取余10；
         carry=((n-i)*A+carry)/10;//计算进位
        high=i;//记录最高位
    }
    if(carry){//看是否有进位
        arr[i]=carry;
        high=i;//修改最高位
    }
    for(int j=high;j>=0;j--){
        cout<<arr[j];
    }
}