文章目录
一、高精度加法模板二、高精度减法模板三、高精度乘法模板3.1 高精乘以低精（普遍用到）高精乘以高精
四、高精度除法4.1、高精度除以低精度4.2、高精度除以高精度
一、高精度加法模板
输入两个数到变量中，然后用赋值语句求它们的和后输出 . 但是，我们知道，在 C/C++ 语言中任何数据类型都有一定表示范围. 当两个加数很大时，以前的算法显然不能求出精确解，因此我们需要寻求另一种方法 .在读小学时，我们做加法都采用竖式方法 . 这样我们方便写出两个整数相加的算法 . c[0]=1,c[1]=1,c[2]=1,c[3]=1; 需要注意c从个位开始的，输出需从最大位序倒叙输出（置输出要去除多余的零）
#include
using namespace std;
const int N = 10000;
#define LENGTH 1001
void HighAdd(string x, string y) {
int a[1000]={0}, b[1000]={0}, c[1000]={0}, len; //建立三个数组保存数
//逆置字符串数据，让两个数可以从低位加到高位
for (int i = 0; i < x.size(); i++)
a[i] = x[x.size() - i - 1]-'0';
for (int i = 0; i < y.size(); i++)
b[i] = y[y.size() - 1 - i]-'0';
//加起来的数的长度不会超过原先两个数的长度最大值
len = max(x.size(), y.size());
for (int i = 0; i < len; i++) {
c[i] += a[i] + b[i];//两数相加，再加上前面计算的进位
c[i + 1] += c[i]/10;//把进位存到i+1位上
c[i] %= 10;//模10取余0-9的数存在数组中
}
len++;//如果有进位就多显示一位（这句话很重要）
while ((c[len-1] == 0) && (len > 1)) len--;//去除前面的前导零,防止后面逆置输出多余的零
//重新逆置,从高位到低位
for (int i = len - 1; i >= 0; i--)
printf("%d", c[i]);
printf("\n");
}
二、高精度减法模板
类似加法，同样使用竖式。在做减法运算时，需要注意的是：需要有借位处理。
#include
using namespace std;
const int N = 10000;
#define LENGTH 1001
void HighSub(string x, string y) {
//建立三个数组保存数
int a[1000] = { 0 }, b[1000] = { 0 }, c[1000] = { 0 }, len;
//逆置字符串数据，让两个数可以从低位加到高位
for (int i = 0; i < x.size(); i++)
a[i] = x[x.size() - i - 1] - '0';
for (int i = 0; i < y.size(); i++)
b[i] = y[y.size() - 1 - i] - '0';
//加起来的数的长度不会超过原先两个数的长度最大值
len = max(x.size(), y.size());
for (int i = 0; i < len; i++) {
if (a[i] < b[i]) {
a[i + 1] -= 1;//向高一位借位
a[i] += 10;//给当前位加10
}
c[i] = a[i] - b[i];//再两数相减
}
while ((c[len - 1] == 0) && (len > 1)) len--;//去除前导零
//重新逆置,从高位到低位
for (int i = len - 1; i >= 0; i--)
printf("%d", c[i]);
printf("\n");
}
三、高精度乘法模板
和加法类似
3.1 高精乘以低精（普遍用到）
#include
using namespace std;
const int N = 10000;
#define LENGTH 1001
void HighMul(string x, int y) {
int a[1000] = { 0 }, len;
for (int i = 0; i < x.size(); i++)
a[i] = x[x.size() - i - 1] - '0';
len = x.size();
int tmp=0;
for (int i = 0; i < len; i++) {
a[i]= a[i] * y+tmp;//运算
tmp = a[i] / 10;//进位
a[i] %= 10;
}
//进位不为0
if (tmp != 0) {
a[len] = tmp;
len++;
while (a[len-1] > 0) //刚存进去的进位，判断是否大于10需要进位
{
a[len] = a[len - 1] / 10;
a[len - 1] %= 10;
len++;
}
}
while ((a[len - 1] == 0) && (len > 1)) len--;
for (int i = len - 1; i >= 0; i--)
printf("%d", a[i]);
}
高精乘以高精
主要怎么存储问题：
我们再声明一个数组c来储存答案。大家通过一个简单的乘法运算进行模拟就可以看出，以同样的储存规则， a[0] * b[0] = c[0]; a[0] * b[1] + a[1] * b[0] = c[1]; 逐渐我们可以发现规律： "c[i + j] += a[i] * b[j]"同过一个循环去实现，就可以把c[i + j]计算出来，需要指出的是，这里的计算我们还没有进行进位处理。
#include
using namespace std;
const int N = 10000;
#define LENGTH 1001
void HighMul(string x, string y) {
//与加法一样
int a[1000] = { 0 }, b[1000] = { 0 }, c[1000] = { 0 }, len;
for (int i = 0; i < x.size(); i++)
a[i] = x[x.size() - i - 1] - '0';
for (int i = 0; i < y.size(); i++)
b[i] = y[y.size() - 1 - i] - '0';
//与加法不同的是，长度最大变成两个数的长度之和
len =x.size()+ y.size();
for (int i = 0; i < x.size(); i++) {
for (int j = 0; j < y.size(); j++) {
c[i + j] += a[i] * b[j];//两数相乘，存到对应位置
c[i + j + 1] += c[i + j] / 10;//把进位加到前面一位上
c[i + j] %= 10;//取模存0-9的数
}
}
while ((c[len - 1] == 0) && (len > 1)) len--;
for (int i = len - 1; i >= 0; i--)
printf("%d", c[i]);
printf("\n");
}
四、高精度除法
4.1、高精度除以低精度
for (int i = 0; i < x.size(); i++) {
c[i] = (tmp * 10 + a[i]) / y;
tmp = (tmp * 10 + a[i]) % y;
}
算法原理用手写，说不清楚。
#include
using namespace std;
const int N = 10000;
#define LENGTH 1001
void HighDiv(string x, int y) {
int a[LENGTH]={0}, b[LENGTH]={0}, c[LENGTH]={0};
for (int i = 0; i < x.size(); i++) {
a[i] = x[i] - '0';
}
int tmp = 0;
for (int i = 0; i < x.size(); i++) {
c[i] = (tmp * 10 + a[i]) / y;
tmp = (tmp * 10 + a[i]) % y;
}
int cnt = 0;
while (c[cnt] == 0 && cnt < x.size())cnt++;
for (int i = cnt; i < x.size(); i++)cout << c[i];
}
4.2、高精度除以高精度
int compare(int a[], int b[]) //比较a和b的大小关系，若a>b则为1，a { int i; if (a[0] > b[0]) return 1; //a的位数大于b则a比b大 if (a[0] < b[0]) return -1; //a的位数小于b则a比b小 for (i = a[0]; i > 0; i--) //从高位到低位比较 { if (a[i] > b[i]) return 1; if (a[i] < b[i]) return -1; } return 0; //各位都相等则两数相等。 } void numcpy(int p[], int q[], int n) //复制p数组到q数组从det开始的地方 { for (int i = 1; i <= p[0]; i++) q[i + n - 1] = p[i]; q[0] = p[0] + n - 1; } void jian(int a[], int b[]) //计算a=a-b { int flag, i; flag = compare(a, b); //调用比较函数判断大小 if (flag == 0) { a[0] = 0; return; } //相等 if (flag == 1) //大于 { for (i = 1; i <= a[0]; i++) { if (a[i] < b[i]) { a[i + 1]--; a[i] += 10; } //若不够减则向上借一位 a[i] -= b[i]; } while (a[0] > 0 && a[a[0]] == 0) a[0]--; //修正a的位数 return; } } void HighDiv(string x, string y) { int a[LENGTH], b[LENGTH], c[LENGTH]; memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c)); a[0] = x.length(); for (int i = 1; i <= a[0]; i++) a[i] = x[a[0] - i] - '0'; b[0] = y.length(); for (int i = 1; i <= b[0]; i++) b[i] = y[b[0] - i] - '0'; int tmp[101]; c[0] = a[0] - b[0] + 1; for (int i = c[0]; i > 0; i--) { memset(tmp, 0, sizeof(tmp)); numcpy(b, tmp, i); while (compare(a, tmp) >= 0) { c[i]++; jian(a, tmp); } } while (c[0] > 0 && c[c[0]] == 0)c[0]--; for (int i = c[0] ; i > 0; i--) printf("%d", c[i]); printf("\n"); } 精彩链接
发表评论