这期内容当中小编将会给大家带来有关使用C++怎么实现一个高精度算法,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。
1. 高精度加法
以3479957928375817 + 897259321544245为例:
3479 | 9579 | 2837 | 5817 |
---|---|---|---|
+897 | +2593 | +2154 | +4245 |
= | = | = | = |
4376 | 12172 | 4991 | 10062 |
进位0 | 进位1 | 进位0 | 进位1 |
4377 | 2172 | 4992 | 0062 |
C语言实现代码如下:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 200 //整数乘幂运算函数 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]; //字符串数组,以字符形式储存两个大数; int i = 0, step = 4, carry = 0; //step表示块长,carry为进位位; int lengtha, lengthb, maxlength, resultsize; //maxlength表示stra和strb二者长度较大的那个; int numa[N], numb[N],numc[N]; //依次储存被加数,加数,和; 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); //计算两个大数的长度 //字符数字转为四位一块的整数数字 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); //计算进位 } //计算最后和的块的总数 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. 高精度减法
与加法类似,不同的是要注意正负号和显示位数的变化。以99999037289799 - 100004642015000为例:
先判断被减数和减数哪个大,显然这里减数大,故输出结果为负数。在用大数减去小数,(若某一块相减为负数,则要向高位块借位)如下表
100 | 0046 | 4201 | 5000 |
---|---|---|---|
-99 | -9990 | -3728 | -9799 |
1 | 56 | 473 | 5201 |
借位0 | 借位1 | 借位0 | 借位1 |
0 | 56 | 472 | 5201 |
C语言实现代码如下:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 200 //整数乘幂运算函数 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]; //字符串数组,以字符形式储存两个大数; int i = 0, step = 4, borrow = 0, mark = 0; //step表示块长,borrow为借位位, mark为结果符号位; int lengtha, lengthb, maxlength, resultsize; //maxlength表示stra和strb二者长度较大的那个; int numa[N], numb[N],numc[N], *maxnum, *minnum; //依次储存被减数,减数,和; 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); //计算两个大数的长度 maxlength = lengtha >= lengthb ? lengtha : lengthb; //字符数字转为四位一块的整数数字 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); } //找出较大的数 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; //计算借位 } //计算最后和的块的总数 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. 高精度乘法
乘法可以看作是乘数每一位与被乘数相乘后再相加,以4296556241 x 56241为例:
被乘数 | 42 | 9655 | 6241 |
---|
乘数 | 5 | 6 | 2 | 4 | 1 |
---|
被乘数x乘数 | 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语言实现代码如下:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 200 //整数乘幂运算函数 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]; //字符串数组,以字符形式储存两个大数; int i = 0, j = 0, k = 0, step = 4, carry = 0; //step表示块长,carry为进位位; int lengtha, lengthb, resultsize, tmpsize, eachnum; //resultsize储存块的总数,eachnum用来储存乘数的每一位 int numa[N], numb[N], numc[N], tmp[N]; //依次储存被乘数数&积,乘数; 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); //计算两个大数的长度 //将被乘数字符数字转为四位一块的整数数字 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] = strb[i]-'0'; } resultsize = tmpsize = (lengtha-1)/step; //取乘数的每一位与被乘数的逐块相乘,并进位; for(i = 0; i < lengthb; ++i) { memcpy(tmp, numa, sizeof(numa)); //将numa数组赋值给tmp数组; k = i/step; //k储存每一块需要向高位块移动的次数; if(k) { for(j = tmpsize; j >= 0; --j) { tmp[j+k] = tmp[j]; tmp[j] = 0; } tmpsize += k; } //乘以乘数每一位扩展成的块; eachnum = numb[i]*Pow(10, i%step); for(j = 0; j <= tmpsize; ++j) { tmp[j] *= eachnum; } //大数相加 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. 高精度除法
高精度除法有两种,一种是高精度除以低精度,另一种是高精度除以高精度。前者只需将每一块除以低精度除数即可;后者则考虑用高精度减法来实现,即每次减去高精度除数,直到减到小于除数,则减的次数即为商,剩余的即为余数。
高精度除以低精度
以9876342876 / 343为例:
被除数 | 98 | 7634 | 2876 |
---|
除数 | 343 |
---|
向低位块进位 | 98 | 137 | 190 |
---|---|---|---|
商 | 0 | 2879 | 4002 |
余数 | 190 |
---|
C语言代码实现如下:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 200 //整数乘幂运算函数 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]; //字符串数组,以字符形式储存高精度被除数; int i = 0, step = 4, carry = 0; //step表示块长,carry为高位向低位进位位; int lengtha, resultsize; int numa[N], numb, numc[N], numd; //依次储存被除数,除数,商, 余数; memset(numa, 0, sizeof(numa)); memset(numc, 0, sizeof(numc)); //初始化为零; scanf("%s%d", stra, &numb); lengtha = strlen(stra); //计算被除数的长度 //字符数字转为四位一块的整数数字 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; //最低位块的余数即为整个除法的余数 //计算最后和的块的总数 while(!numc[resultsize]) --resultsize; //输出商 printf("%d", numc[resultsize]); for(i = resultsize-1; i >= 0; --i) { printf("%04d", numc[i]); //右对齐,补零输出; } //输出余数 printf("\n%d\n", numd); return 0; }
高精度除以高精度
以176342876 / 3453452为例:
被除数 | 176342876 |
---|---|
- (51 x 除数) | 51 x 3453452 |
余数 | 216824 |
商 | 51 |
C语言代码实现如下:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 200 //整数乘幂运算函数 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]; //字符串数组,以字符形式储存两个大数; 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]; //依次储存被除数数,除数数,商,余数; 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); //计算两个大数的长度 //字符数字转为四位一块的整数数字 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; //计算剩余数是否小于除数 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; } } //判断是否余数已经小于除数 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; //每减一个除数,商加一; 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; }
上述就是小编为大家分享的使用C++怎么实现一个高精度算法了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。