網站首頁 編程語言 正文
前言
高精度的運算在算法題尤為常見,在處理一些大型數據的項目中也需要用到。雖然Boost庫中有處理高精度問題的模板,但是標準庫中并沒有。為了方便學習,本文提供了高精度運算的模板,供大家參考。
什么是大整數?
眾所周知,最大的整型long long的范圍是【-9223372036854775808~9223372036854775807】,即使是無符號位的unsigned long long最大值也只是擴大一倍,那當題目需要用到或需要輸出比long long類型的范圍還要大的數字時,我們是不是就不能用常規辦法去接收這些數字了。這個時候使用大整數就可以解決上述問題——也就是解決接收超出整型范圍數字的問題。
大整數的表示
其實大整數的表示方法也不難,我們使用數組就可以了(當然C++的vector容器也是可以的,原理都一樣,但為了照顧C語言的小伙伴,本文用數組表示)。
假設現在有一個int類型數組d[1000],那么我們可以用數組中的每一位元素表示大整數中的每一位數字,比如有整數123456789,那么我們可以用d[0]表示億位上的【1】,用d[1]表示千萬位上的【2】...以此類推,我們就可以用一個長度為9的數組表示這個大整數了。
當然為了契合我們后面四則運算的思維,我們將數組元素的順序翻轉一次,也就是在數組靠前的元素表示低位,而靠后的元素表示高位(原因后面會講到),也就是如下圖所示:
而為了方便我們獲取當前大整數的長度,我們可以使用一個結構體(或者一個類,與C語言的結構體不同,在C++中的結構體也可以定義成員函數)來表示。
//struct of bign(big number)
struct bign {
int d[1000];
int len;
bign()//構造函數
{
this->len = 0;
memset(d, 0, sizeof(d));
}
};
當然,一般輸入大整數時,都是先用字符串讀入,然后再把字符串另存為至bign結構體。
bign change(const string str)//將整數轉換為begin c語言用const char*
{
bign a;
a.len = str.size();//bign的長度就是字符串的長度 c語言用strlen()函數
for (int i = 0; i < a.len; i++)
{
a.d[i] = str[a.len - i - 1] - '0';
}
return a;
}
大整數的運算
對于大整數的四則運算,我們需要模擬在小學期間學習四則運算的思路和過程,也就是把我們在草稿紙上運算的過程,抽象成代碼的邏輯。
1、高精度加法
加法實現方式與我們以前學到的加法一樣。對于某一位的運算:我們將該位上的兩個數字與進位相加,得到的結果取個位數作為該結果,十位數作為新的進位。
bign add(bign a, bign b)
{
bign c;
int carry = 0; //carry是進位標志
for (int i = 0; i < a.len || i < b.len; i++) //以較長的為界限
{
int temp = a.d[i] + b.d[i] + carry; //兩個對應位與進位相加
c.d[c.len++] = temp % 10; //取個位數為該位的結果
carry = temp / 10; //取十位數為新的進位
}
if (carry) //如果最后的進位不為0,則直接賦給結果的最高位
{
c.d[c.len++] = carry;
}
return c;
}
這里要注意,這樣寫法的條件是兩個對象都是非負整數。如果有雙方異號,可以在轉換到數組這一步時去掉符號,再使用高精度減法;如果雙方都為負數,那么去掉負號后采用高精度加法,最后負號加回去即可。?
2、高精度減法
通過對減法步驟的拆分可以得到一個簡練的步驟:對某一位,比較被減位和減位,如果不夠減,則令被減位的高位減1,被減位加10再進行減法(借一位);如果夠減,那就直接減。最后需要注意減法后高位可能有多余的0,要去除它們,但要保證結果至少有一位數。
bign sub(bign a, bign b) //a - b
{
bign c;
for (int i = 0; i < a.len || i < b.len; i++) //以較長的為界限
{
if (a.d[i] < b.d[i]) //不夠減
{
a.d[i + 1]--; //向高位借位
a.d[i] += 10; //向前位借10
}
c.d[c.len++] = a.d[i] - b.d[i]; //減法結果為當前位
}
while (c.len >= 2 && c.d[c.len - 1] == 0) //剩余的位數不小于十位,并且最高位是0
{
c.len--; //去除高位的0,同時至少保留一位最低位
}
return c;
}
3、高精度乘以低精度
所謂高精度乘以低精度,就是bign*int的運算。
對某一位來說是這樣的步驟:取bign的某位與int型整體相乘,再與進位相加,所得結果的個位數作為該結果,高位部分作為新的進位。對于a、b異號的情況只需要一個標志位變量記錄,在輸出的時候加上負號就行了。
bign multi(bign a, int b)
{
bign c;
int carry = 0; //進位
for (int i = 0; i < a.len; i++)
{
int temp = a.d[i] * b + carry;
c.d[c.len++] = temp % 10; //個位作為該結果
carry = temp / 10; //高位部分作為新的進位
}
while (carry != 0) //和加法不一樣,乘法的進位可能不止一位,因此用while
{
c.d[c.len++] = carry % 10;
carry /= 10;
}
return c;
}
4、高精度除以低精度
高精度除以低精度,就是bign/int的運算。考慮到有時還需要知道計算之后的余數,于是就把余數寫成引用的形式傳入,當然也可以把余數設成全局變量。?
對于某一位來說:上一步的余數乘以10加上該步的位,得到該步當前的被除數,將其與除數比較;如果不夠除,則該位的商為0;如果夠除,則商即為對應的商,余數即為對應的余數。和其他運算一樣,要注意結果可能有多余的0,要去掉它們,但也要保證結果至少有一位數。
bign divide(bign a, int b, int& r) //r為余數
{
bign c;
c.len = a.len;//被除數的每一位和商的每一位是一一對應的,因此先令長度相等
for (int i = a.len - 1; i >= 0; i--) //從高位開始
{
r = r * 10 + a.d[i]; //和上一位遺留的余數組合
if (r < b) c.d[i] = 0; //不夠除,該位為0
else //夠除
{
c.d[i] = r / b; //商
r = r % b; //獲得新的余數
}
}
while (c.len >= 2 && c.d[c.len - 1] == 0)
{
c.len--; //去除高位的0,同時至少保留一位最低位
}
return c;
}
如果大家對于上述的邏輯還不清楚的話,可以自己在稿紙上舉例幾個簡單的數算算,實際思路和我們運算時的思路是一樣的哈。
大整數的表示
最后,當我們要打印出大整數時則要注意了,在上文中,我們為了方便運算,將數組中的位序翻轉了一次,所以打印時就是需要從后往前輸出。
而如果我們輸入的數據是【04】,那么輸出的結果就不是單純的【4】了,一般來說這不是我們想要的結果是吧。那么為了解決這個問題,我們可以在打印的時候加上一個標志位來判斷。
void print(bign ans)
{
int flag = 0;
for (int i = ans.len - 1; i >= 0; i--)
{
if (ans.d[i] != 0) //標志位如果首位是0 則不輸出
{
flag = 1;
}
if (flag)
{
cout << ans.d[i];
}
}
if (!flag)
cout << 0; //包含輸出0的情況
}
補充:使用示例
例題1(貪心+大整數)
題目:洛谷P1080 國王游戲
分析
此題需要先貪心找到排序規律為按照每個人的左右手乘積非降序排列,在計算最小值時累乘的過程中可能數字溢出,所以要使用大整數,但是根據題目描述大整數開100001位是不夠的需要開的更大,但是實際測試數據并沒有這么大。
AC代碼
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10001;
pair<int,int> nums[maxn]; //first 右手,second左手
struct bign{ //存123時: d={3,2,1}llen =3;
int d[maxn];
int len;
bign(){
memset(d,0,sizeof(d));
len = 0;}
}res,sum,ans; //res最終結果,sum累乘結果,ans比較變量
bign multi(bign a,int b){ //高精度大整數與低精度的乘法
bign c;
int carry = 0; //進位
for(int i=0;i<a.len;i++){
int temp = a.d[i]*b + carry;
//printf("%d*%d+%d\n",a.d[i],b,carry);
c.d[c.len++] = temp%10;
carry = temp / 10;
}
while(carry!=0){
c.d[c.len++] = carry%10;
carry/=10;
}
return c;
}
bign divide(bign a,int b,int& r){ //高精度除以低精度,r為余數
bign c;
c.len = a.len;
r=0;
for(int i=a.len-1;i>=0;i--){
r = r*10 + a.d[i];
if(r<b) c.d[i] = 0;
else{
c.d[i] = r/b;
r %= b;
}
}
while(c.len-1>=1&&c.d[c.len-1]==0){
c.len--;
}
return c;
}
int compare(bign a,bign b){ //比較a和b的大小,a>b返回1,相等返回0,a<b返回-1
if(a.len>b.len) return 1;
if(a.len<b.len) return -1;
for(int i=a.len-1;i>=0;i--){
if(a.d[i]>b.d[i]) return 1;
if(a.d[i]<b.d[i]) return -1;
}
return 0;
}
void print(bign a){ //輸出大整數
for(int i=a.len-1;i>=0;i--)
printf("%d",a.d[i]);
return;
}
int cmp(pair<int,int> a,pair<int,int> b){
return a.first*a.second<b.first*b.second;
}
int main(){
int n;
scanf("%d",&n);
scanf("%d %d",&nums[0].first,&nums[0].second);
for(int i=1;i<=n;i++)
scanf("%d %d",&nums[i].first,&nums[i].second);
sort(nums+1,nums+1+n,cmp);
sum.d[0] = 1; sum.len = 1;
for(int i=1;i<=n;i++){
int r = 0; //存余數
sum = multi(sum,nums[i-1].first);
ans = divide(sum,nums[i].second,r);
if(compare(ans,res)==1)
res = ans;
}
print(res);
return 0;
}
總結
原文鏈接:https://blog.csdn.net/ZER00000001/article/details/127722669
相關推薦
- 2023-07-26 TypeScript中的對象類型(可選屬性 只讀屬性 交叉類型)
- 2022-07-14 如何批量刪除Docker中已經停止的容器的幾種方法_docker
- 2022-03-29 在pyqt5中展示pyecharts生成的圖像問題_python
- 2022-03-03 實現不需要手動浮空瀏覽器緩存,程序可以獲取最新版本
- 2022-09-24 Go?類型轉化工具庫cast函數詳解_Golang
- 2022-02-10 antd table 增加底部合計行統計
- 2022-07-19 Linux手工配置靜態ip地址
- 2023-06-03 python中with的具體用法_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤:Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列,發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支