• 微信号
  • 微信号
您当前的位置：首页 > 学海无涯 > 茑语花香>C++ 基础算法 - 高精度

C++ 基础算法 - 高精度

孤峰 孤峰家 2023-09-21 86人阅读

今天，我们正式开始学习算法这一部分

而我们第一个要学习的算法是——高精度

高精度

高精度简单来说就是算数，我们知道，在 C++ 当中，专门存储数字的类型有 short，int，long long，float，double

但是，如果我们要存下一个很长的数，例如

2(100次方)=1267650600228229401496703205376

这肯定装不下，所以我们要利用 string 类型进行存储这么长的一串数字 ( 当然现在它已经不在是数字了，它变成了字符串 )

所以，我们对非常长的数字进行加减乘除或其他计算就可以被称为高精度

高精度的执行

所以，我们要思考高精度是如何进行计算的

我们知道，我们在做计算题时会列竖式，那么高精度就用到了竖式的思想，对每一位进行加减乘除的计算，然后再记录起来，较后输出

高精度加法的代码

在上面我们思考了高精度是如何执行的，现在我们来一步一步推测高精度的执行

第一步就是输入，我们知道输入的数是非常的大的，所以我们需要用到字符串

所以输入就是这样的

string x,y;


getline(cin,x);

getline(cin,y);

在我们输入字符串之后，也就是第二步，我们要对这两个字符串进行简单的倒置处理，之所以要倒置处理，是因为我们在计算时是从较低位开始进行计算的，但我们输入的字符串是从高位到低位的，所以我们将其进行倒置处理就是方便以后的处理

所以倒置处理就是这样的

int a[10000000],b[10000000];


int i,l=x.size(),r=y.size();


for(i=0;i<l;++i) a=x[l-i-1]-48;//l-i-1就是倒置

for(i=0;i<r;++i) b=y[r-i-1]-48;//而减48就是将字符转换为数字

在倒置之后，我们就要进行计算了，这里我们先进行最简单的加法计算

我们来回忆一下加法竖式计算是如何实现的

较低位相加，如果得出的值大于等于 10，我们就将 1 加到更高一位处，然后以此为循环，一直相加至较高位

那么我们就来用循环模拟这个过程即可

int c[10000000];


if(r>l) swap(r,l);//我们要算到较高的一个数的较高位


for(i=0;i<l;++i)


{


 c+=a+b;//将这一位上的数相加(必须要用+=因为这一位可能会有进位的1)


 c[i+1]+=c/10;//将这一位上的数的十位加到更高一位


 c%=10;//将本位变回一位数

}

这样我们就模拟出了相加的过程，然后就可以输出了 ... ( 真的么 )

while(l>0&&c[l]==0) l--;//在l为整数且含前导0时将较高值减少 for(i=l;i>=0;--i) printf("%d",c);//逆序的输出

这样，你就学会了高精度加法，是不是非常的简单呢

完整代码

#include<iostream>


#include<string>


#include<cstdio>


using namespace std;


string x,y;


int a[10000000],b[10000000],c[10000000];


int **in()


{


 getline(cin,x);


 getline(cin,y);


 int i,l=x.size(),r=y.size();


 for(i=0;i<l;++i) a=x[l-i-1]-48;


 for(i=0;i<r;++i) b=y[r-i-1]-48;


 if(r>l) swap(r,l);


 for(i=0;i<l;++i)


 {


c+=a+b;


c[i+1]+=c/10;


c%=10;


 }


 while(l>0&&c[l]==0) l--;


 for(i=l;i>=0;--i) printf("%d",c);


 return 0;

}

高精度减法

学习完了加法，现在就要来学习减法了，高精度减法相较于高精度加法，较大的难点就是在对每一位上的数以及判断正负上进行处理

首先，前面的与加法一样，都是输入

string x,y;


getline(cin,x);

getline(cin,y);

然后我们要干什么，我们都知道，两个数相减，如果被减数要小于减数，我们就调换被减数与减数的位置在进行加减运算，较后取其的绝对值即可 ; 但如果被减数不小于减数，我们就可以直接进行加减计算

那我们应该如何判断两个串的大小呢

我们想到了字符串进行大小判断的标准，我们在 C++ 数组一本通平台讲解中的 2048：【例5.18】串排序 中有讲到字符串的判断，而这种判断正好与我们需要的判断方式相同，那么我们就可以直接进行利用

int i,l=x.size(),r=y.size();


bool negative(false);//判断是否为负数


if(r>l||(r==l&&y>x)) swap(x,y),swap(l,r),negative=true;

//如果满足条件长度的大小判断或者是本身大小的判断就为负数

随后又是进行倒置处理

int a[10000000],b[10000000];


for(i=0;i<l;++i) a=x[l-i-1]-48;//l-i-1就是倒置

for(i=0;i<r;++i) b=y[r-i-1]-48;//而减48就是将字符转换为数字

随后就是按照竖式的方式进行减法计算，在这里，我们要注意的就是减法的退位，我们要如何进行退位呢

int c[10000000];


for(i=0;i<l;++i)


{


 if(a>=b) c=a-b;//我们就可以先进行减法计算并直接进行记录


 else c=a-b+10,a[i+1]--;//如果需要退位,我们就将高一位减1,本位加10

}
while(l>0&&c[l]==0) l--;//在l为整数且含前导0时将较高值减少

较后完成正负数的判断和逆序的输出即可

if(negative) printf("-");//特别判断是否为负数

for(i=l;i>=0;--i) printf("%d",c);//逆序的输出

有了高精度加法的铺垫，高精度减法就会显得很简单

完整代码

#include<iostream>


#include<string>


#include<cstdio>


using namespace std;


string x,y;


int a[10000000],b[10000000],c[10000000];


int **in()


{


 getline(cin,x);


 getline(cin,y);


 int i,l=x.size(),r=y.size();


 bool negative(false);


 if(r>l||(r==l&&y>x)) swap(x,y),swap(l,r),negative=true;


 for(i=0;i<l;++i) a=x[l-i-1]-48;


 for(i=0;i<r;++i) b=y[r-i-1]-48;


 for(i=0;i<l;++i)


 {


if(a>=b) c=a-b;


else c=a-b+10,a[i+1]--;


 }


 while(l>0&&c[l]==0) l--;


 if(negative) printf("-");


 for(i=l;i>=0;--i) printf("%d",c);


 return 0;

}

高精度乘法

在学习了高精度加减法后，我们就可以学习高精度乘法了

高精度乘法同样非常简单，只需在高精度加法的基础上改变一下即可

前面的输入，倒置都与高精度加法相同

string x,y;


int a[1000000],b[1000000];


getline(cin,x);


getline(cin,y);


int i,j,l=x.size(),r=y.size();


for(i=0;i<l;++i) a=x[l-i-1]-48;

for(i=0;i<r;++i) b=y[r-i-1]-48;

后面的去除前导 0，输出都与高精度加法相同

while(l>0&&c[l]==0) l--;

for(i=l;i>=0;--i) printf("%d",c);

有变化的就是进行计算的部分

我们知道，乘法竖式的计算方式为由低至高，一个数的每一位与另一个数相乘得到的积的和就为乘法竖式的总和

每一位的计算方式为：c[i+j]+=a*a[j]，如果这一位满了十，就需要进位，进位的处理方式与高精度加法相同，分为两部分，进十位，取个位

较后的方法如下

for(i=0;i<l;++i)//枚举第一个乘数的每个数位


{


 for(j=0;j<r;++j)//枚举第二个数的每个数位


 {


c[i+j]+=a*b[j];//将两个数位上的数相乘加到相应的位置上


c[i+j+1]+=c[i+j]/10;//处理进位


c[i+j]%=10;//留下个位


 }

}

处理完成了每个位，那么，我们要从哪里开始往回输出呢

l+=r;

从 l 的位置开始往后处理前导 0 即可

完整代码

#include<iostream>


#include<cstdio>


#include<string>


using namespace std;


string x,y;


int a[1000000],b[1000000],c[1000000];


int **in()


{


 getline(cin,x);


 getline(cin,y);


 int i,j,l=x.size(),r=y.size();


 for(i=0;i<l;++i) a=x[l-i-1]-48;


 for(i=0;i<r;++i) b=y[r-i-1]-48;


 for(i=0;i<l;++i)


 {


for(j=0;j<r;++j)


{


 c[i+j]+=a*b[j];


 c[i+j+1]+=c[i+j]/10;


 c[i+j]%=10;


}


 }


 l+=r;


 while(l>0&&c[l]==0) l--;


 for(i=l;i>=0;--i) printf("%d",c);


 return 0;

}

高精度除法 ( 余数 )

高精度除法与其它都不太一样，别的运算的数都是高精度，而高精度除法想要用高精度除以高精度比较难，所以这里暂时先学习高精度除以 int 类型的整数

因为是高精度除以 int 类型的整数，所以 b 字符串就不必存在了

这是前面的部分，除了它不需要逆序以外，都与其它相同，这里就不过多赘述了

string x;


int y,a[1000000],b[1000000];


getline(cin,x);


scanf("%d",&y);


if(y==0) return 0;//特判,如果除数为0时直接退出,否则会产生错误

for(i=0;i<l;++i) a=x-48;//这里不需要逆序

后面的部分也与其它运算方式相同，但因为它不需要逆序，所以是用 r 进行删除前导 0

while(b[r]==0&&r<l) r++;


for(i=r;i<l;++i) printf("%d",b);

printf("\n%d",s);//s为余数

而最重要的就是中间部分

按照除法竖式我们可以知道，每次用特定的几个数位除以除数，余下的就是余数，它也要参与下一次的运算，即：b=(a+s*10)/y 加上上一次剩下的余数的十倍除以除数即可，让后再次计算出余数，即：s=(a+s*10)Mody

for(i=0;i<l;++i)

{


 b=(a+s*10)/y;//得出本位的商


 s=(a+s*10)%y;//得出余数

}

完整代码

#include<iostream>


#include<cstdio>


#include<string>


using namespace std;


string x;


int y,a[1000000],b[1000000];


int **in()


{


 getline(cin,x);


 scanf("%d",&y);


 if(y==0) return 0;


 int i,j,s=0,l=x.size(),r=0;


 for(i=0;i<l;++i) a=x-48;


 for(i=0;i<l;++i)


 {


b=(a+s*10)/y;


s=(a+s*10)%y;


 }


 while(b[r]==0&&r<l) r++;


 for(i=r;i<l;++i) printf("%d",b);


 printf("\n%d",s);


 return 0;

}

另外，如果大家需要高精度除以高精度的代码，我将会出一篇关于这个的文章

一本通平台的讲解

1307 - 1309，1168 - 1175

1307：【例1.3】高精度乘法

#include<iostream>


#include<cstdio>


#include<string>


using namespace std;


string x,y;


int a[200],b[200],c[400];


int **in()


{


 cin>>x>>y;//这里必须用cin,我用getline时就错了,可能是因为两个数在同一行内


 int i,j,l=x.size(),r=y.size();


 for(i=0;i<l;++i) a=x[l-i-1]-48;//倒置


 for(i=0;i<r;++i) b=y[r-i-1]-48;


 for(i=0;i<l;++i)


 {


for(j=0;j<r;++j)


{


 c[i+j]+=a*b[j];


 c[i+j+1]+=c[i+j]/10;


 c[i+j]%=10;//标准的计算方式


}


 }


 l+=r;


 while(l>0&&c[l]==0) l--;//去除前导0


 for(i=l;i>=0;--i) printf("%d",c);//输出


 return 0;

}

这道题就是高精度乘法的模板，所以非常简单就能够通过了

1309：【例1.6】回文数(Noip1999)

#include<iostream>


#include<string>


#include<cstdio>


using namespace std;


int n,a[2000],b[2000],l;


string m;


bool palindrome(int x[])//判断回文,这里的x[]传输的是数组


{


 for(int i=0;i<=l/2;++i) if(x!=x[l-i-1]) return false;//当非回文时返回false


 return true;//否则返回true


}


int **in()


{


 cin>>n>>m;


 int i,j;


 l=m.size();


 for(i=0;i<l;++i)


 {


if(m[l-i-1]>='0'&&m[l-i-1]<='9') a=m[l-i-1]-48;//小于等于10进制的数


else a=m[l-i-1]-55;//大于10进制的数


 }


 for(i=0;i<=30;++i)//在30次以内


 {


if(palindrome(a))//判断回文


{


 printf("%d\n",i);//输出


 return 0;


}


else


{


 for(j=0;j<l;++j) b[j]=a[l-1-j];//要先进行保存,直接改变会导致错误


 for(j=0;j<l;++j)//加法计算


 {


a[j]+=b[j];


a[j+1]+=a[j]/n;


a[j]%=n;


 }


 l*=2;//将l*2


 while(a[l]==0&&l>0) l--;l++;//删除前导0,较后还要加上1


}


 }


 printf("Impossible\n");//否则就输出Impossible


 return 0;

}

这道题最重要的就是掌握高精度加法的核心思想，再加上进制的判断即可

1168：大整数加法

利用模板即可完成本题

#include<iostream>


#include<string>


#include<cstdio>


using namespace std;


string x,y;


int a[10000000],b[10000000],c[10000000];


int **in()


{


 getline(cin,x);


 getline(cin,y);


 int i,l=x.size(),r=y.size();


 for(i=0;i<l;++i) a=x[l-i-1]-48;


 for(i=0;i<r;++i) b=y[r-i-1]-48;


 if(r>l) swap(r,l);


 for(i=0;i<l;++i)


 {


c+=a+b;


c[i+1]+=c/10;


c%=10;


 }


 while(l>0&&c[l]==0) l--;


 for(i=l;i>=0;--i) printf("%d",c);


 return 0;

}

1169：大整数减法

这道题也是可以利用模板通过的

#include<iostream>


#include<string>


#include<cstdio>


using namespace std;


string x,y;


int a[10000000],b[10000000],c[10000000];


int **in()


{


 getline(cin,x);


 getline(cin,y);


 int i,l=x.size(),r=y.size();


 bool negative(false);


 if(r>l||(r==l&&y>x)) swap(x,y),swap(l,r),negative=true;


 for(i=0;i<l;++i) a=x[l-i-1]-48;


 for(i=0;i<r;++i) b=y[r-i-1]-48;


 for(i=0;i<l;++i)


 {


if(a>=b) c=a-b;


else c=a-b+10,a[i+1]--;


 }


 while(l>0&&c[l]==0) l--;


 if(negative) printf("-");


 for(i=l;i>=0;--i) printf("%d",c);


 return 0;

}

1170：计算2的N次方

#include<iostream>


#include<cstdio>


#include<string>


using namespace std;


int x,a[1000000],b[1000000],c[1000000];


int **in()


{


 int i,j,k,l,s=0;


 cin>>x;


 if(x==0){printf("0\n");return 0;}//特判


 a[0]=1;l=1;//初始化数字和长度


 for(k=1;k<=x;++k)


 {


s=0;//控制进位的数


for(i=0;i<l;++i)


{


 a=a*2+s;//将本位乘上2并加上进位


 s=a/10;//刷新进位


 a%=10;//将本位控制在10以内


}


a[l]=s;//较后一次进行进位


l++;while(l>0&&a[l]==0) l--;l++;


//尾数控制,较后要加1,因为while循环会将l减少至长度减1


 }


 while(l>0&&a[l]==0) l--;//再次删除前导0


 for(i=l;i>=0;--i) printf("%d",a);//输出


 return 0;

}

这其实就是一个高精度乘法的嵌套，因为：x(n)=x(n-1)*x 括号内表示N次方 这样就可以通过最基本的 2 向上推导了

1171：大整数的因子

这道题是要我们枚举除数，并判断哪些能够成立，但是这里只说了需要余数，并不需要除数，所以高精度计算可以简单一些

#include<iostream>


#include<string>


using namespace std;


string x;


int a[50];


int **in()


{


 getline(cin,x);


 int i,j,s=0,l=x.size();


 bool flag=true;


 if(l==1&&x[0]-48<2)//特判,如果数字只有1位且小于2时就不会有存在的k


 {


printf("none\n");


return 0;


 }


 for(i=0;i<l;i++) a[l-i-1]=x-48;//转化


 for(i=2;i<=9;i++)


 {


s=0,j=l-1;


while(j>=0)//取余数


{


 s*=10;//将原有的s的个位空出,其余为向上移动


 s+=a[j];//将个位放入数字


 s%=i;//试着求出余数


 j--;//继续判断下一位


}


if(s==0)//判断较后的s是否被除尽


{


 printf("%d ",i);


 flag=false;


}


 }


 if(flag) printf("none\n");//如果没有则输出none


 return 0;

}

在取余数的 while 循环中来说明一下

假设 s = 123，则在乘以 10 后就为 1230，就腾出了个位，随后加上 a [ j ]，就是将正序的数字加入 s 中，求出余数，例如 1234 ÷ 2 余 0，则我们就可以省略前面的位数，只需判断后面的余数即可，这样就可以简单的进行判断除尽与否了

1172：求10000以内n的阶乘

这道题就显得非常高级了，它要求的是 10000 以内的 n 的阶乘，但是它仍然可以用高精度解决，当输入 10000 时，就会得到很长的一串数字 

#include<iostream>

#include<string>


#include<cstdio>


using namespace std;


int a[110000];


int **in()


{


 int i,n,k,l=1;


 scanf("%d",&n);


 a[0]=1;


 for(k=2;k<=n;++k)


 {


for(i=0;i<l;++i) a*=k;//阶乘


for(i=0;i<l;++i)//防止溢出,分两次进行判断


{


 a[i+1]+=a/10;//进位


 a%=10;//控制位数


 if(i==l-1&&a[i+1]!=0) ++l;//判断是否进位了


}


 }


 for(i=l-1;i>=0;--i) printf("%d",a);//输出


 return 0;

}

1173：阶乘和

这道题就是将阶乘计算出来后进行相加即可

#include<iostream>


#include<cstdio>


using namespace std;


int l,a[10001],b[10001],n;


void factorial(int s)


{


 int i;


 for(i=0;i<l;++i) a*=s;


 for(i=0;i<l;++i)


 {


a[i+1]+=a/10;


a%=10;


 }


 if(a[l]!=0) l++;


}


void add()


{


 int i;


 for(i=0;i<l;i++) b+=a;


 for(i=0;i<l;i++)


 {


b[i+1]+=b/10;


b%=10;


if(b[i+1]!=0) l++;


 }


}


int **in()


{


 int i;


 scanf("%d",&n);


 a[l]=1;


 for(i=1;i<=n;i++) factorial(i),add();


 while(b[l]==0&&l>0) l--;


 for(i=l;i>=0;i--) printf("%d",b);


 return 0;

}

1174：大整数乘法

这道题就是标准的高精度乘法模板能过通过的题目

#include<iostream>


#include<cstdio>


#include<string>


using namespace std;


string x,y;


int a[1000000],b[1000000],c[1000000];


int **in()


{


 getline(cin,x);


 getline(cin,y);


 int i,j,l=x.size(),r=y.size();


 for(i=0;i<l;++i) a=x[l-i-1]-48;


 for(i=0;i<r;++i) b=y[r-i-1]-48;


 for(i=0;i<l;++i)//标准的乘法


 {


for(j=0;j<r;++j)


{


 c[i+j]+=a*b[j];


 c[i+j+1]+=c[i+j]/10;


 c[i+j]%=10;


}


 }


 l+=r;


 while(l>0&&c[l]==0) l--;


 for(i=l;i>=0;--i) printf("%d",c);


 return 0;

}

1175：除以13

这道题就是高精度除法，只不过给定了固定的除数罢了

#include<iostream>


#include<cstdio>


#include<string>


using namespace std;


string a;


int b=13,x[1000000],z[1000000];//将除数改为13即可


int **in()


{


 getline(cin,a);


 int i,j,s=0,l=a.size(),r=0;


 for(i=0;i<l;++i) x=a-48;


 for(i=0;i<l;++i)//标准的除法


 {


z=(x+s*10)/b;


s=(x+s*10)%b;


 }


 while(z[r]==0&&r<l) r++;


 for(i=r;i<l;++i) printf("%d",z);


 printf("\n%d",s);


 return 0;

}

那么高精度算法就讲到这里了。

文档下载

C++ 基础算法 - 高精度.doc
很赞哦！ ()

转载：感谢您阅览，转载请注明文章出处“来源从小爱孤峰知识网：一个分享知识和生活随笔记录的知识小站”。

链接：C++ 基础算法 - 高精度http://www.gufeng7.com/niaolang/1853.html

联系：如果侵犯了你的权益请来信告知我们删除。邮箱：119882116@qq.com

标签：

上一篇： C++ 算法

下一篇: C++ 基础算法 - 排序算法

猜你喜欢

我们一直用心在做标语

Copyright © 2016-2024从小爱孤峰公安备案号备案号：湘ICP备19014236号

站点声明:本站部分图片、文章来源于网络，版权归原作者所有，如有侵权，请联系我们删除。

sitemap | 隐私政策 | 免责声明