當前位置:網站首頁>高精度模板

高精度模板

2022-01-28 10:44:55 曉木_

聲明

這篇文章的代碼僅僅只是一個模板。

高精度加法

思想:和兩數的加法類似(從小數比特加加到大數比特,),
在這裏插入圖片描述
一個數在數組裏是倒著放,方便加法
性質:方便放

代碼實現:

#include<iostream>
#include<string>
#include <vector>
using namespace std;

vector<int> add(vector<int>&A,vector<int>&B)
{
    
    vector<int> ret;
    int j=0;//進比特
    int n=A.size();
    int m=B.size();
    for (int i = 0; i < n||i<m; i ++ )
    {
    
        if(i<n) j+=A[i];
        if(i<m) j+=B[i];
        ret.push_back(j%10);
        j/=10;
    }
    if(j) ret.push_back(j);  //如果兩個數的最高比特加起來大於10 則要放入進制比特,
    return ret;
}
int main()
{
    
    string a,b;
    cin>>a,cin>>b;
    vector<int>A,B;
    //把數進行逆置存放與數組中
    for(int i=a.size()-1;i>=0;i--)//逆置存放
    {
    
        A.push_back(a[i]-'0');
    }
    for(int i=b.size()-1;i>=0;i--)//逆置存放
    {
    
        B.push_back(b[i]-'0');
    }
    auto C=add(A,B);//auto 為c++11的語法,也可以寫成vector<int> C=add(A,B);
    for(int i=C.size()-1;i>=0;i--) 
       printf("%d",C[i]);//逆序輸出,得到兩個大樹的答案
    return 0;
}

高精度减法

和加法類似,只是需要注意前導0。 在這裏插入圖片描述

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool cmp(vector<int>& A,vector<int>& B)
{
    
    int n=A.size();
    int m=B.size();
    if(n!=m) return n>m;
    for(int i=n-1;i>=0;i--)
    {
    
        if(A[i]!=B[i]) return A[i]>B[i];
    } 
    return true;
}
vector<int> sub(vector<int>& A,vector<int>& B)
{
        
//由於前面進行了比較,所以這裏A的值固定比B的大
    vector<int> ret;
    int n=A.size();
    
    for (int i = 0,t=0; i < n; i ++ )
    {
    
        t=A[i]-t;
        if(i<B.size()) t-=B[i];
        ret.push_back((t+10)%10);
        if(t<0) t=1;
        else t=0;
    }
    while(ret.size()>1&&ret.back()==0) ret.pop_back();
    //删除前導0,兩個數A和B的比特數,且最高比特數字一樣,則會產生前導0;要删除掉
    return ret;
}
int main()
{
    
    string a,b;
    cin>>a>>b;
    vector<int> A,B;
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
    if(cmp(A,B)){
     //比較A和B的大小
    auto C=sub(A,B);
    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    }
    else
    {
    
    auto C=sub(B,A);
    printf("-");
    for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    }
    return 0;
}

高精度乘法

高精乘低精度

在這裏插入圖片描述

#include<iostream>
#include<string>
#include<vector>
using namespace std;

vector<int> mul(vector<int>& A,int b)
{
    
    vector<int> C;
    int t=0;
    int n=A.size();
    for (int i = 0; i < n||t; i ++ )
    {
    
        if(i<n) t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1&&C.back()==0) C.pop_back();
    return C;
}
int main()
{
    
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i=a.size()-1;i>=0;i--) {
    
        A.push_back(a[i]-'0');
    }
    auto C=mul(A,b);
    for (int i = C.size()-1; i >=0 ; i -- ) printf("%d",C[i]);
    return 0;
}

高精乘高精

兩個數組倒著,和高精*低精類似 ,自己接兩個數組的每個數先相乘後的值放到ret數組對應的比特置裏,先不管進制,後面在進行O(N)的處理進制,

//高精*高精
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int> mul(vector<int>& A, vector<int>& B)
{
    
	vector<int> ret(A.size()+B.size());
	for (int i = 0; i < A.size() ; i++)
		for (int j = 0; j < B.size(); j++)
			ret[i + j] = A[i] * B[j];

	int t = 0;
	for (int i = 0; i < ret.size() - 1; i++)
	{
    
		t += ret[i];
		ret[i] = t % 10;
		t /= 10;
	}
	
	while (ret.size() > 1 && ret.back() == 0) ret.pop_back(); //删除前導0 
	return ret;
}
int main()
{
    
	string a, b;
	cin >> a >> b;
	vector<int> A, B;
	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i]-'0');
	for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i]-'0');
	auto C = mul(A, B);
	for (int i = C.size() - 1; i >= 0; i--)
	{
    
		printf("%d", C[i]);
	}
	return 0;
}

高精度除法

高精度/低精度

注意這次的A是由高為傳輸至低比特,由於在除法的手算過程中,發現從高比特進行處理,

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

vector<int> mul(vector<int>& A, int b)
{
    
	vector<int> ret;
	int r = 0;//r錶示餘數
	//由最高比特進行處理
	for (int i = 0; i < A.size(); i++)
	{
    
		//將上次的餘數*10在加上當前比特的數字,便是該比特需要除的被除數
		r = r * 10 + A[i];
		//所得即為商在這一比特的數字
		ret.push_back(r / b); 
		r %= b;
	}
	//删除前面的0
	reverse(ret.begin(), ret.end());
	while (ret.size() > 1 && ret.back() == 0) ret.pop_back();
	return ret;
}
int main()
{
    
	string a;
	int b;
	cin >> a >> b;
	vector<int> A;
	for (int i = 0; i < a.size(); i++) A.push_back(a[i]-'0');
	auto C = mul(A, b);
	for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
	return 0;

}

高精/高精
參考此鏈接參考此鏈接

版權聲明
本文為[曉木_]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201281044553559.html

隨機推薦