C/C++高精度算法的實現(xiàn)
更新時間：2020年02月02日 10:08:20 作者：孤獨な霊魂
這篇文章主要介紹了C/C++高精度算法的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
做ACM題的時候，經(jīng)常遇到大數(shù)的加減乘除，乘冪，階乘的計算，這時給定的數(shù)據(jù)類型往往不夠表示最后結(jié)果，這時就需要用到高精度算法。高精度算法的本質(zhì)是把大數(shù)拆成若干固定長度的塊，然后對每一塊進行相應(yīng)的運算。這里以考慮4位數(shù)字為一塊為例，且輸入的大數(shù)均為正整數(shù)（也可以考慮其他位，但要注意在每一塊進行相應(yīng)運算時不能超出數(shù)據(jù)類型的數(shù)值范圍；有負整數(shù)的話讀入時判斷一下正負號在決定運算）。
1. 高精度加法
以3479957928375817 + 897259321544245為例：
| 3479 | 9579 | 2837 | 5817 |
|---|---|---|---|
| +897 | +2593 | +2154 | +4245 |
| = | = | = | = |
| 4376 | 12172 | 4991 | 10062 |
| 進位0 | 進位1 | 進位0 | 進位1 |
| 4377 | 2172 | 4992 | 0062 |
C語言實現(xiàn)代碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
//整數(shù)乘冪運算函數(shù)
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of Addition
int main()
{
char stra[N], strb[N]; //字符串?dāng)?shù)組，以字符形式儲存兩個大數(shù)；
int i = 0, step = 4, carry = 0; //step表示塊長，carry為進位位；
int lengtha, lengthb, maxlength, resultsize; //maxlength表示stra和strb二者長度較大的那個；
int numa[N], numb[N],numc[N]; //依次儲存被加數(shù)，加數(shù)，和；
memset(numa, 0, sizeof(numa));
memset(numb, 0, sizeof(numb));
memset(numc, 0, sizeof(numc)); //初始化為零；
scanf("%s%s", stra, strb);
lengtha = strlen(stra);
lengthb = strlen(strb); //計算兩個大數(shù)的長度
//字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
for(i = lengthb-1; i >= 0; --i)
{
numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
}
maxlength = lengtha > lengthb ? lengtha : lengthb;
//逐塊相加，并進位
for(i = 0; i <= maxlength/step; ++i)
{
numc[i] = (numa[i] + numb[i])%Pow(10, step) + carry; //計算和
carry = (numa[i] + numb[i])/Pow(10, step); //計算進位
}
//計算最后和的塊的總數(shù)
resultsize = numc[maxlength/step] > 0 ? maxlength/step : maxlength/step - 1;
printf("%d", numc[resultsize]);
for(i = resultsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); //右對齊，補零輸出；
}
printf("\n");
return 0;
}
2. 高精度減法
與加法類似，不同的是要注意正負號和顯示位數(shù)的變化。以99999037289799 - 100004642015000為例：
先判斷被減數(shù)和減數(shù)哪個大，顯然這里減數(shù)大，故輸出結(jié)果為負數(shù)。在用大數(shù)減去小數(shù)，（若某一塊相減為負數(shù)，則要向高位塊借位）如下表
| 100 | 0046 | 4201 | 5000 |
|---|---|---|---|
| -99 | -9990 | -3728 | -9799 |
| 1 | 56 | 473 | 5201 |
| 借位0 | 借位1 | 借位0 | 借位1 |
| 0 | 56 | 472 | 5201 |
C語言實現(xiàn)代碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
//整數(shù)乘冪運算函數(shù)
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of Subtraction
int main()
{
char stra[N], strb[N]; //字符串?dāng)?shù)組，以字符形式儲存兩個大數(shù)；
int i = 0, step = 4, borrow = 0, mark = 0; //step表示塊長，borrow為借位位, mark為結(jié)果符號位；
int lengtha, lengthb, maxlength, resultsize; //maxlength表示stra和strb二者長度較大的那個；
int numa[N], numb[N],numc[N], *maxnum, *minnum; //依次儲存被減數(shù)，減數(shù)，和；
memset(stra, 0, sizeof(stra));
memset(strb, 0, sizeof(strb));
memset(numa, 0, sizeof(numa));
memset(numb, 0, sizeof(numb));
memset(numc, 0, sizeof(numc)); //初始化為零；
scanf("%s%s", stra, strb);
lengtha = strlen(stra);
lengthb = strlen(strb); //計算兩個大數(shù)的長度
maxlength = lengtha >= lengthb ? lengtha : lengthb;
//字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
for(i = lengthb-1; i >= 0; --i)
{
numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
}
//找出較大的數(shù)
maxnum = numa;
minnum = numb;
mark = 1;
for(i = (maxlength-1)/step; i >= 0; --i)
{
if(numa[i] > numb[i])
{
maxnum = numa;
minnum = numb;
mark = 1;
break;
}
else if(numa[i] < numb[i])
{
maxnum = numb;
minnum = numa;
mark = -1;
break;
}
}
//逐塊相減，并借位
for(i = 0; i <= maxlength/step; ++i)
{
numc[i] = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)%Pow(10,step); //計算差
borrow = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)/Pow(10, step) - 1; //計算借位
}
//計算最后和的塊的總數(shù)
resultsize = maxlength/step;
while(!numc[resultsize]) --resultsize;
printf("%d", mark*numc[resultsize]);
for(i = resultsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); //右對齊，補零輸出；
}
printf("\n");
return 0;
}
3. 高精度乘法
乘法可以看作是乘數(shù)每一位與被乘數(shù)相乘后再相加，以4296556241 x 56241為例：
| 被乘數(shù) | 42 | 9655 | 6241 |
|---|
| 乘數(shù) | 5 | 6 | 2 | 4 | 1 |
|---|
| 被乘數(shù)x乘數(shù) | 42 | 9655 | 6241 |
|---|---|---|---|
| 1 | 42 | 9655 | 6241 |
| 4 | 168*10 | 38620*10 | 24964*10 |
| 2 | 84*100 | 19310*100 | 12482*100 |
| 6 | 252*1000 | 57930*1000 | 37446*1000 |
| 5 | 210*10000 | 48275*10000 | 31205*10000 |
| 累加和 | 2362122 | 543006855 | 351000081 |
| 進位（從低位向高位） | 241 | 54304 | 35100 |
| 積 | 241 | 6426 | 1955 | 0081 |
|---|
C語言實現(xiàn)代碼如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
//整數(shù)乘冪運算函數(shù)
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of Multiplication
int main()
{
char stra[N], strb[N]; //字符串?dāng)?shù)組，以字符形式儲存兩個大數(shù)；
int i = 0, j = 0, k = 0, step = 4, carry = 0; //step表示塊長，carry為進位位；
int lengtha, lengthb, resultsize, tmpsize, eachnum; //resultsize儲存塊的總數(shù)，eachnum用來儲存乘數(shù)的每一位
int numa[N], numb[N], numc[N], tmp[N]; //依次儲存被乘數(shù)數(shù)&積，乘數(shù)；
memset(numa, 0, sizeof(numa));
memset(numb, 0, sizeof(numb));
memset(numc, 0, sizeof(numc)); //初始化為零；
scanf("%s%s", stra, strb);
lengtha = strlen(stra);
lengthb = strlen(strb); //計算兩個大數(shù)的長度
//將被乘數(shù)字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
//將乘數(shù)數(shù)字字符數(shù)字轉(zhuǎn)為一位一塊的整數(shù)數(shù)字
for(i = lengthb-1; i >= 0; --i)
{
numb[lengthb-1-i] = strb[i]-'0';
}
resultsize = tmpsize = (lengtha-1)/step;
//取乘數(shù)的每一位與被乘數(shù)的逐塊相乘，并進位；
for(i = 0; i < lengthb; ++i)
{
memcpy(tmp, numa, sizeof(numa)); //將numa數(shù)組賦值給tmp數(shù)組；
k = i/step; //k儲存每一塊需要向高位塊移動的次數(shù)；
if(k)
{
for(j = tmpsize; j >= 0; --j)
{
tmp[j+k] = tmp[j];
tmp[j] = 0;
}
tmpsize += k;
}
//乘以乘數(shù)每一位擴展成的塊；
eachnum = numb[i]*Pow(10, i%step);
for(j = 0; j <= tmpsize; ++j)
{
tmp[j] *= eachnum;
}
//大數(shù)相加
carry = 0; //進位置零；
for(j = 0; j <= resultsize; ++j)
{
numc[j] += tmp[j] + carry;
carry = numc[j]/Pow(10,step);
numc[j] %= Pow(10, step);
}
if(carry)
{
++resultsize;
numc[j] += carry;
}
}
//輸出
printf("%d", numc[resultsize]);
for(i = resultsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); //右對齊，補零輸出；
}
printf("\n");
return 0;
}
4. 高精度除法
高精度除法有兩種，一種是高精度除以低精度，另一種是高精度除以高精度。前者只需將每一塊除以低精度除數(shù)即可；后者則考慮用高精度減法來實現(xiàn)，即每次減去高精度除數(shù)，直到減到小于除數(shù)，則減的次數(shù)即為商，剩余的即為余數(shù)。
高精度除以低精度
以9876342876 / 343為例：
| 被除數(shù) | 98 | 7634 | 2876 |
|---|
| 除數(shù) | 343 |
|---|
| 向低位塊進位 | 98 | 137 | 190 |
|---|---|---|---|
| 商 | 0 | 2879 | 4002 |
| 余數(shù) | 190 |
|---|
C語言代碼實現(xiàn)如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
//整數(shù)乘冪運算函數(shù)
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of division
//(1)高精度除以低精度
int main()
{
char stra[N]; //字符串?dāng)?shù)組，以字符形式儲存高精度被除數(shù)；
int i = 0, step = 4, carry = 0; //step表示塊長，carry為高位向低位進位位；
int lengtha, resultsize;
int numa[N], numb, numc[N], numd; //依次儲存被除數(shù)，除數(shù)，商, 余數(shù)；
memset(numa, 0, sizeof(numa));
memset(numc, 0, sizeof(numc)); //初始化為零；
scanf("%s%d", stra, &numb);
lengtha = strlen(stra); //計算被除數(shù)的長度
//字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
carry = 0; //高位向低位進位位置零
resultsize = (lengtha-1)/step;
//逐塊相除，高位向低位進位
for(i = resultsize; i >= 0; --i)
{
numc[i] = (numa[i] + carry*Pow(10,step))/numb; //計算商
carry = (numa[i] + carry*Pow(10,step))%numb; //計算進位
}
numd = carry; //最低位塊的余數(shù)即為整個除法的余數(shù)
//計算最后和的塊的總數(shù)
while(!numc[resultsize]) --resultsize;
//輸出商
printf("%d", numc[resultsize]);
for(i = resultsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); //右對齊，補零輸出；
}
//輸出余數(shù)
printf("\n%d\n", numd);
return 0;
}
高精度除以高精度
以176342876 / 3453452為例：
| 被除數(shù) | 176342876 |
|---|---|
| - (51 x 除數(shù)) | 51 x 3453452 |
| 余數(shù) | 216824 |
| 商 | 51 |
C語言代碼實現(xiàn)如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
//整數(shù)乘冪運算函數(shù)
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of division
//(2)高精度除以高精度
int main()
{
char stra[N], strb[N]; //字符串?dāng)?shù)組，以字符形式儲存兩個大數(shù)；
int i = 0, step = 4, borrow = 0; //step表示塊長，borrow為進位位；
int lengtha, lengthb, tmpnum, numbsize, numcsize, numdsize, maxsize, mark; //maxlength表示stra和strb二者長度較大的那個；
int numa[N], numb[N], numc[N], numd[N]; //依次儲存被除數(shù)數(shù)，除數(shù)數(shù)，商，余數(shù)；
memset(stra, 0, sizeof(stra));
memset(strb, 0, sizeof(strb));
memset(numa, 0, sizeof(numa));
memset(numb, 0, sizeof(numb));
memset(numc, 0, sizeof(numc));
memset(numd, 0, sizeof(numd)); //初始化為零；
scanf("%s%s", stra, strb);
lengtha = strlen(stra);
lengthb = strlen(strb); //計算兩個大數(shù)的長度
//字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
for(i = lengthb-1; i >= 0; --i)
{
numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
}
memcpy(numd, numa, sizeof(numa));
numbsize = (lengthb-1)/step;
numcsize = 0;
numdsize = (lengtha-1)/step;
do
{
maxsize = numdsize > numbsize ? numdsize : numbsize;
//計算剩余數(shù)是否小于除數(shù)
mark = 1;
for(i = maxsize; i >= 0; --i)
{
if(numd[i] > numb[i])
{
mark = 1;
break;
}
else if(numd[i] < numb[i])
{
mark = -1;
break;
}
}
//判斷是否余數(shù)已經(jīng)小于除數(shù)
if(!(mark+1)) break;
borrow = 0; //借位置零；
//逐塊相減，并借位
for(i = 0; i <= maxsize; ++i)
{
tmpnum = (numd[i] - numb[i] + Pow(10, step) + borrow)%Pow(10,step); //計算差
borrow = (numd[i] - numb[i] + Pow(10, step) + borrow)/Pow(10,step) - 1; //計算借位
numd[i] = tmpnum;
}
while(!numd[numdsize]) --numdsize;
//每減一個除數(shù)，商加一；
borrow = 1;
for(i = 0; i <= numcsize; ++i)
{
numc[i] += borrow;
borrow = numc[i]/Pow(10,step);
numc[i] %= Pow(10,step);
}
if(borrow)
{
++numcsize;
numc[i] += borrow;
}
}while(1);
printf("%d", numc[numcsize]);
for(i = numcsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); //右對齊，補零輸出；
}
printf("\n");
printf("%d", numd[numdsize]);
for(i = numdsize-1; i >= 0; --i)
{
printf("%04d", numd[i]); //右對齊，補零輸出；
}
printf("\n");
return 0;
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
基于Matlab實現(xiàn)人工神經(jīng)網(wǎng)絡(luò)(ANN)回歸的示例詳解
這篇文章主要為大家詳細介紹了Matlab實現(xiàn)人工神經(jīng)網(wǎng)絡(luò)(ANN)回歸的相關(guān)資料，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起了解一下2023-02-02
C++數(shù)據(jù)結(jié)構(gòu)與算法之判斷一個鏈表是否為回文結(jié)構(gòu)的方法
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)與算法之判斷一個鏈表是否為回文結(jié)構(gòu)的方法,結(jié)合實例形式分析了回文結(jié)構(gòu)并結(jié)合實例給出了C++判斷回文的操作技巧,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了C語言全部內(nèi)存操作函數(shù)的實現(xiàn)詳細講解，作者用圖文代碼實例講解的很清晰，有感興趣的同學(xué)可以研究下2021-09-09
Cocos2d-x學(xué)習(xí)筆記之世界坐標(biāo)系、本地坐標(biāo)系、opengl坐標(biāo)系、屏幕坐標(biāo)系
這篇文章主要介紹了Cocos2d-x學(xué)習(xí)筆記之世界坐標(biāo)系、本地坐標(biāo)系、opengl坐標(biāo)系、屏幕坐標(biāo)系,本文用代碼和注釋講解了Cocos2d-x中的坐標(biāo)體系,需要的朋友可以參考下2014-09-09
本文詳細講解了C語言打印某一年中某月的日歷，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
這篇文章主要為大家詳細介紹了C++控制臺實現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
本篇文章是對C中含有if的宏定義進行了詳細的分析介紹，需要的朋友參考下2013-05-05
今天小編就為大家分享一篇基于ROS 服務(wù)通信模式詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
交叉編譯就是在當(dāng)前系統(tǒng)平臺上,開發(fā)編譯運行于其它平臺的程序,比如本文硬件環(huán)境是x86平臺,但是編譯出來的程序是在arm64架構(gòu)、mips64等架構(gòu)上運行,本文給大家分享QT5交叉編譯入門級教程(arm64、mips64),感興趣的朋友一起看看吧2023-11-11
在C++中只有一個字符串類，即basic_string，其管理著一個 '\0' 結(jié)尾的字符數(shù)組。頭文件：#include <string>，string類支持兩種輸入方式：cin方式和getline()方式2022-06-06