实际上高精度就是说参与运算的数据和运算结果的范围,超出标准数据类型能表示的数据大小范围的运算。这个时候,如果要得到正确的计算结果,显然不能依靠普通方法实现了。而要在普通运算原理的基础上,加以辅助算法来实现超大数据的计算。例如:求两个100位的数据的和,或者计算两个100位的数字乘积。这时就要用到高精度算法了。
一 . 高精度加法
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memese(s,1,sizeof(s))
const int inf = 0x3f3f3f3f;
const int N=100005;
int a[N],b[N],len;//数组的大小决定了计算得高精度最大位数
int main(int argc, char * argv[])
{
std::ios::sync_with_stdio(false);
string str1,str2;
me0(a);
me0(b);
cin>>str1>>str2;//输入两个字符串
a[0]=str1.length();//取得第一个字符串的长度
for(int i=1;i<=a[0];i++)//把第一个字符串转换为整数,存放在数组a中
a[i]=str1[a[0]-i]-'0';
b[0]=str2.length();
for(int i=1;i<=b[0];i++)//把第二个字符串转换为整数,存放在数组b中
b[i]=str2[b[0]-i]-'0';
len=(a[0]>b[0]?a[0]:b[0]);//取两个字符串最大的长度
for(int i=1;i<=len;i++){
a[i]+=b[i];
a[i+1]+=a[i]/10;
a[i]%=10;
}
len++;//下面是去掉最高位的0,然后输出
while((a[len]==0)&&(len>1)) len--;
for(int i=len;i>=1;i--) cout<<a[i];
return 0;
}
二 . 高精度减法
1.高精度减法相比高精度加法来说,稍微复杂一点,因为减法在差为负数时处理的细节更多一点:当被减数小于减数时,差为负数,差的绝对值是减数减去被减数;在程序实现上用一个变量来存储符号位,用另一个数组存差的绝对值。
2.实现流程
(1).先比较大小
(2).决定输出符号,为正还是为负
(3).按位减法,并注意处理借位
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memese(s,1,sizeof(s))
const int inf = 0x3f3f3f3f;
const int N=100005;
int a[N];
int compare(string s1,string s2){ //s1大于等于s2返回0,否则返回1
if(s1.length()>s2.length()) return 0;
if(s1.length()<s2.length()) return 1;
for(int i=0;i<=s1.length();i++){
if(s1[i]>s2[i]) return 0;
if(s1[i]<s2[i]) return 1;
}
return 0;
}
int main(int argc, char * argv[])
{
std::ios::sync_with_stdio(false);
string str1,str2;
int a[N],b[N];
me0(a);
me0(b);
cin>>str1>>str2;
a[0]=str2.length();
for(int i=1;i<=a[0];i++)
a[i]=str1[a[0]-i]-'0';
b[0]=str2.length();
for(int i=1;i<=b[0];i++)
b[i]=str2[b[0]-i]-'0';
if((compare(str1,str2))==0){//大于等于,做按位减,并处理错位
for(int i=1;i<=a[0];i++){
a[i]-=b[i];
if(a[i]<0){
a[i+1]--;
a[i]+=10;
}
}
a[0]++;
while((a[a[0]]==0)&&(a[0]>1)) a[0]--;
for(int i=a[0];i>=1;i--)
cout<<a[i];
cout<<endl;
}
else{//小于
cout<<"-";
for(int i=1;i<=b[0];i++){
b[i]-=a[i];
if(b[i]<0){
b[i+1]--;
b[i]+=10;
}
}
b[0]++;
while((b[b[0]]==0)&&(b[0]>1)) b[0]--;
for(int i=b[0];i>=1;i--)
cout<<b[i];
cout<<endl;
}
return 0;
}
三 . 高精度乘法
高精度乘法实现原理:
1.由于数字较大,无法使用简单的数据结构进行存储,选用数组和字符串来存储数字,字符串方便我们对于高位整数的输入,而整形数组的简便有利于每个位数的计算,结合两者优点便可实现高精度乘法。
2.实现过程:
(1).通过两个字符串输入两个整数
(2).引入两个数组,将每个整数切割存储到数组里面
(3).进行每一位的运算
(4).处理进位
(5).输出结果
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memese(s,1,sizeof(s))
const int inf = 0x3f3f3f3f;
const int N=100005;
int a[N];
int main(int argc, char * argv[])
{
std::ios::sync_with_stdio(false);
string str1,str2;
int a[250],b[250],c[250],len; //250位以内的两个数相乘
me0(a);
me0(b);
cin>>str1>>str2;
a[0]=str1.length();
b[0]=str2.length();
for(int i=1;i<=a[0];i++)
a[i]=str1[a[0]-i]-'0';
for(int i=1;i<=b[0];i++)
b[i]=str2[b[0]-i]-'0';
me0(c);
for(int i=1;i<=a[0];i++)
for(int j=1;j<=b[0];j++){
c[i+j-1]+=a[i]*b[j];
c[i+j]+=c[i+j-1]/10;
c[i+j-1]%=10;
}
len=a[0]+b[0]+1; //去掉最高位0然后输出
while((c[len]==0)&&(len>1)) len--;
for(int i=len;i>=1;i--)
cout<<c[i];
cout<<endl;
return 0;
}
四 . 高精度除法
高精度除法实现原理:高精度除法这一块比较复杂,它可以分为两种情况:
第一种情况:高精除以低精,实际上就是对被除的每一位,包括前面的余数都除以除数。
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memese(s,1,sizeof(s))
const int inf = 0x3f3f3f3f;
const int N=100005;
int a[N];
int main(int argc, char * argv[])
{
std::ios::sync_with_stdio(false);
int a[100],c[100],b,x=0;
char a1[100],c1[100];
gets(a1);//被除数
cin>>b; //除数
int lena=strlen(a1);
for(int i=0;i<=lena-1;i++)
a[i+1]=a1[i]-48; //高精度放入a数组
for(int i=1;i<=lena;i++){
c[i]=(x*10+a[i])/b;
x=(x*10+a[i])%b;
}
int lenc=1;
while(c[lenc]==0&&lenc<lena)
lenc++;
for(int i=lenc;i<=lena;i++)
cout<<c[i];
cout<<endl;
return 0;
}
第二种情况:高精除以高精
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define me0(s) memset(s,0,sizeof(s))
#define me1(s) memese(s,1,sizeof(s))
int a[100],b[100],c[100];
int compare(int a[],int b[]){//比较a,b,若a>b为1,若a<b为-1,相等为0
if(a[0]>b[0]) return 1;
if(a[0]<b[0]) return -1;
for(int i=a[0];i>0;i--){
if(a[i]>b[i]) return 1;
if(a[i]<b[i]) return -1;
}
return 0;
}
void subduction(int a[],int b[]){//计算a=a-b
int flag;
flag=compare(a,b);
if(flag==0){
a[0]=0;
return ;
}
if(flag==1){
for(int 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)//删除前导0
a[0]--;
return ;
}
}
int main(int argc, char * argv[])
{
std::ios::sync_with_stdio(false);
char str1[100],str2[100];
me0(a);
me0(b);
me0(c);
cin>>str1>>str2;
a[0]=strlen(str1);//a[0]存储串1位数
b[0]=strlen(str2);//b[0]存储串2位数
for(int i=1;i<=a[0];i++)
a[i]=str1[a[0]-i]-'0';
for(int i=1;i<=b[0];i++)
b[i]=str2[b[0]-i]-'0';
int temp[100];
c[0]=a[0]-b[0]+1;
for(int i=c[0];i>0;i--){
me0(temp);
for(int j=1;j<=b[0];j++)//从i开始的地方,复制数组b到temp
temp[j+i-1]=b[j];
temp[0]=b[0]+i-1;
while(compare(a,temp)>=0){//减法模拟
c[i]++;
subduction(a,temp);
}
}
while(c[0]>0&&c[c[0]]==0)//删除前导0
c[0]--;
cout<<"shangwei: ";
if(c[0]==0)
cout<<0<<endl;
else{
for(int i=c[0];i>0;i--)
cout<<c[i];
cout<<endl;
}
cout<<"yushu: ";
if(a[0]==0)
cout<<0<<endl;
else{
for(int i=a[0];i>0;i--)
cout<<a[i];
cout<<endl;
}
return 0;
}
原博客 https://blog.csdn.net/fanyun_01/article/details/79967170