高精度:
首先,我们知道,在计算机中,是以2进制存储数字的。
一个int型整数占四个字节,能表示的最大数字为2^31-1。
那么,如果我要表示一个几百位、甚至上千位的数字,我需要多大的空间呢?
以一千位数为例,一千位数字最小为10^1000。
以2为底10^1000的对数
等于1000被以2为底10的对数
约等于3.32。
也就是说,这大约需要3320个字节。
如果说,计算机中有这样的类型,我们叫它超超超超超长整型,我们就可直接用来计算了
不幸的是,计算机中最大的整数类型,long long int,也只能占用了八个字节。
那么,如果实际生活中,我们需要计算几百位甚至几千位的长整数,我们应该怎么办呢?
这就是所谓的高精度问题。
无论多长的整数,都是由每一位的数码组成。
我们可以用一个数组,来存储这个长整数的每一位:
利用字符串输入,把字符串的每一位存储在数组里;
在计算中,当第X位大于10时,则使第X+1位增加第X位除十的倍数,使第X变为自己对十取余的余数;
然后再依次输出。
下面我们先来处理第一个问题:输入。
在计算的时候,我们要从后向前计算,从个位开始向十位计算。
所以,我们应该尽可能的把低位存储在数组的低位里。
一个好的习惯,开辟数组前宏定义一个最大值:
#define MAXN 1000
然后定义一个字符数组
char temp[MAXN + 5];
进行输入
cin >> temp;
然后将字符数组的每一位存储在数组中。
在这里,我们有一个小问题:
循环从1开始,可是到几结束?
所以,我们需要先获取一下temp数组的长度。
int length = strlen(temp);
这个函数在头文件string.h中,别忘了加到前面!
#include <string.h>
然后我们声明一个数组,用来存储数字。
int a[MAXN + 5];
进行每一位的提取:
for(int i = 1; i <= length; i++){
a[i] = temp [length - i] - '0';//倒着提取,最高位(第一位)存储在最大的地方(最后一位)
//但是注意,利用cin输入字符串时,第一位为0。所以a[1]应该为a[length - 1]
}
OK,到了这里,我们已经能完整的表示一个高精度数字。
请你以此类推,完成第二个数组的存储。
然后,下面我们进行一下高精度的加法。
在小学阶段,我们学习了竖式这个神奇的东西来帮助我们计算,而计算机的高精度计算与竖式同理。
1234567
+7654321
8888888
我们对每一位进行加法,然后存储在ans数组中,并且随时判断ans数组的每一位是否大于10。
下面是高精度加法的实现代码:
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
#define MAXN 105
int m[MAXN],n[MAXN];//m,n存储两个数字
int ans[MAXN];//ans存储答案
int main() {
char str1[MAXN],str2[MAXN];//两个字符数组用来输入
cin >> str1 >> str2;
//注:以下的很多注释的作用是用来调试,找bug用。
for (int i = 1; i <= strlen(str1); i++) {
//cout << i << ":";
m[i] = str1[strlen(str1) - i] - '0';
//cout << m[i] << " ";
}
for (int i = 1; i <= strlen(str2); i++) {
n[i] = str2[strlen(str2) - i] - '0';//转存
}
int maxn = max(strlen(str1), strlen(str2));
for (int i = 1; i <= maxn; i++) {
//cout << i << ":" << endl;
ans[i] += (m[i] + n[i]);//计算
//printf("ans[i]=%d,ans[i+1]=%d\n", ans[i], ans[i + 1]);
while (ans[i] >= 10) {//进位
ans[i] -= 10;
ans[i + 1]++;
//printf("ans[i]=%d,ans[i+1]=%d\n", ans[i], ans[i + 1]);
}
}
bool first = false;//第一个正整数前的0不要
for (int i = maxn+5; i >= 1; i--) {
if (!first && ans[i] == 0)continue;
else first = true;
cout << ans[i];
}
//cout << endl << 1234567 + 7654999;
return 0;
}