版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
高精度运算High-precisionAlgorithm基本整数类型的取值范围类型数值范围占字节数
unsignedchar0..2551char-128..1271
int(long)-2147483648..21474836471094unsignedint(long)0..42949672954longlong-9223372036854775808..922337203685477580710188unsigned0..184467440737095516158Longlong
使用时有限制,例如,不能作为数组的下标等。为什么需要高精度运算当要处理的数据超过了任何一种数据类型所能容纳的范围,这种数称为高精度数,必须自定义类型来存储.同时还要自行编写高精度数的运算函数(加\减\乘\除等)高精度数的输入和存储在运算对象的数值范围为任何数据类型所无法容纳的情况下,采用数组(每一个元素对应一位十进制数,由其下标顺序指明位序号)来表示一个数,就称为高精度数。1、采用字符串形式输入,并将其转化为整数数组。2、用一个整型变量记录数据的实际长度(即数组的元素个数)字符串到整数数组的转换字符串存储时,数的高位被存放在字符串的低位。76321801234567转换成整数数组时,要把高精度数的低位“还原”到数组的低位。这样才便于后续计算。a[1]存放最低位,a[6]存放最高位。高精度数的位数可存放在a[0]中。也可以另用一个变量存放。字符串s681236701234567整型aconstintMAXLEN=241; //最大长度为240位typedef
int
hp[MAXLEN]; //定义hp为高精度类型voidStr2hp(strings,hp&a)//s转换后存入a{
inti,len;
memset(a,0,sizeof(a));//cleara
len=s.size(); a[0]=len; //savethelength for(i=0;i<len;i++) //convert
a[len-i]=s[i]-'0';}高精度数类型定义与读入输出voidPrint(hpa){
inti,len;
len=a[0]; //getthelength for(i=len;i>=1;i--)
cout<<a[i];
cout<<endl;}高精度加法问题描述:输入a,b(<10240)两个数,输出a+b的值。样例输入:9999999999999999999912345678901234567890样例输出:112345678901234567889算法分析算法思想类似于竖式加法运算,注意进位处理。把计算结果存到c中:(1)先计算:直接将a[i]和b[i]相加,结果放在c[i]中。…….a[3]a[2]a[1]…….b[3]b[2]b[1]+……c[3]c[2]c[1]思考:要进行多少位加法呢?应该取a或b中较长的位数。对10进制而言,c[i]中的数可能的取值范围是什么?合要求的取值范围是什么?需要作什么处理?算法分析(2)处理进位从最低位开始,逐位整理:把本位模10,向高一位进位:
c[i+1]+=c[i]/10;
c[i]=c[i]%10;思考:最多要处理多少位呢?因为两数相加最多向前进一位,所以我们把长度加1。len++;for(i=1;i<len;i++)//注意是i<len,写成i<=len结果不错,但道理不对{
c[i+1]+=c[i]/10;
c[i]=c[i]%10;}算法分析(3)去掉最高位的0因为两数相加,也可能不产生进位,因此要把这种情况下最高位的0去掉,其实就是减小和的长度len的值。While((len>1)&&(c[len]==0))
len--;注意,len>1的条件是必要的,因为如果和是0的话,想一想该如何保存。voidadd(hpa,hpb,hp&c)//Adda,btoc{hpd;
inti,len;
memset(d,0,sizeof(d));//d清0
if(a[0]>b[0])len=a[0];//求和的位数
elselen=b[0];for(i=1;i<=len;i++)//逐位相加
d[i]=a[i]+b[i];
len++;//位数加1
for(i=1;i<len;i++)//处理进位{
d[i+1]+=d[i]/10;
d[i]%=10;}while((len>1)&&(d[len]==0))//处理最高位
len--;d[0]=len;
memcpy(c,d,sizeof(d));//保存结果}思考:能不能不用d,直接让c参与加法运算呢?提示:结果要保存在a或b中,即Add(a,b,a),不用d行吗?高精度减法运算问题表述:
输入a,b(<10240)两个数,输出a-b的值。样例2输入:9991000样例2输出:-1样例1输入:456409样例1输出:47算法分析1、比较a和b的大小,从而确定结果的正负号2、依照由低位至高位的顺序进行减法运算。在每一次位运算中,若出现不够减的情况(a[i]<b[i]),则向高位借位。在进行了减运算后,若高位为0,则要减少结果的长度。在具体计算过程中,仍然用三位走的办法。voidsub(hpa,hpb,hp&c)//amustbegreaterthanb{
inti,len; hpd;
memset(d,0,sizeof(d));//cleard
len=a[0]; for(i=1;i<=len;i++)
d[i]=a[i]-b[i];for(i=1;i<=len;i++) if(d[i]<0) //处理借位 {
d[i]+=10; d[i+1]-=1; } while((len>1)&&(d[len]==0))//整理差的长度
len--; d[0]=len;
memcpy(c,d,sizeof(d));}写程序的小经验1、数组的清零:保存结果的数组使用前一般都要清零:For(i=0;i<MAXLEN;i++)
a[i]=0;Memset(a,0,sizeof(a))2、变量的使用要规范:如:循环控制变量一般用i、j、k,一般不要用m、n等。长度用len表示。这样容易找错误。比较两个高精度数大小当a>b,返回1;a<b,返回-1;a==b,返回0int
compare(hpa,hpb){
inti; if(a[0]>b[0])return1; if(a[0]<b[0])return-1; for(i=a[0];i>=1;i--) if(a[i]>b[i])return1; elseif(a[i]<b[i])return-1; return0;}求Fibonacci数列的第n项Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题的提出:有雌雄一对兔子,假定过两个月后便每个月可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子?已知:N<=1000F(i):第i个月后共有的兔子对数。F(1)=1;F(2)=1;f(3)=2;f(4)=3;f(5)=5;f(6)=8;递推公式F(i)=f(i-2)+f(i-1)//用基本类型就可解决unsignedlonglong
fibo(intn){ unsignedlonglongf0,f1,t;
inti; if((n==1)||(n==2))return1;f0=1;f1=1; for(i=3;i<=n;i++) { t=f0+f1; f0=f1; f1=t; } returnf1;}当N<=93小结:高精度运算毕竟比基本类型运算麻烦,费时,因此只有在确有必要时才使用voidfibo(intn,hp&ans){ hpf0,f1,t;
inti;
memset(ans,0,sizeof(ans)); f0[0]=1;f0[1]=1; f1[0]=1;f1[1]=1; if((n==1)||(n==2)) { ans[0]=1; ans[1]=1; return; }
for(i=3;i<=n;i++) { add(f0,f1,t); memcpy(f0,f1,sizeof(f1)); memcpy(f1,t,sizeof(t)); }
memcpy(ans,f1,sizeof(f1));}
小结:高精度数不一定非要经过“输入-转换”过程。也可能是通过计算直接产生。当N>93时高精度数乘以整型数运算问题表述:精确计算n的阶乘n!(7<n<80)样例输入:20样例输出:2432902008176640000算法分析估算n!所需的高精度数组长度被乘数(高精度)从低位向高位逐位乘以乘数(整数)1、估算n!所需的高精度数组长度因为80!<8080<10080=(102)80=10160所以80!可以用160个数组元素a[1],a[2],…,a[160]来存放,一个数组元素存放一个数位上的数字。同样的方法,可以估算出100!可以用200位的数组来存放。n!=1*2*3*…*k*(k+1)*…(n-1)*n可以知道,当n大于某个数时,n!将无法再用基本类型装下,需要用高精度数来存放,而每次的乘数则是一个基本整型,因此求n!的问题是一个高精度数乘以一个基本整型。2.高精度数乘以整型数voidmultiply(hpa,int
b,hp&c){hpd;
inti,len,t;
memset(d,0,sizeof(d));
len=a[0];for(i=1;i<=len;i++)
d[i]=a[i]*b;
for(i=1;i<=len;i++){d[i+1]+=d[i]/10;
d[i]%=10;}
len++;while(d[len]){d[len+1]=d[len]/10;
d[len]%=10;
len++;}while((d[len]==0)&&(len>1))
len--;d[0]=len;
memcpy(c,d,sizeof(d));}后一个for循环和while循环都是来处理进位用的。为什么要这么麻烦?因为我们不知道整数b有多少位。可以写一个函数去求一个整数的位数。然后就可以只用一个for循环处理进位了。可以把两个for循环合在一块,象后一页的程序一样。2.高精度数乘以整型数voidmultiply(hpa,int
b,hp&c){hpd;
inti,len,t;
memset(d,0,sizeof(d));
len=a[0];for(i=1;i<=len;i++){t=a[i]*b+d[i];
d[i]=t%10;d[i+1]=t/10;}
len++;while(d[len]){d[len+1]=d[len]/10;
d[len]%=10;
len++;}while((d[len]==0)&&(len>1))
len--;d[0]=len;
memcpy(c,d,sizeof(d));}intmain(){
intn,i;hpans;
cin>>n;ans[0]=1;ans[1]=1;for(i=2;i<=n;i++)
multiply(ans,i,ans);for(i=ans[0];i>=1;i--)
cout<<ans[i];
cout<<endl;return0;}高精度数乘以高精度数样例输入:1234567890098765432100样例输出:1219326311126352690000问题表述:输入a,b(<10100)两个数,输出a*b的值。算法分析1、积的位数为lena+lenb-1或者lena+lenb;2、如果暂且不考虑进位关系,则ai*bj应该累加在积的第j+i-1位上:c[i+j-1]:=a[i]*b[j]+c[i+j-1];3、可以先乘、后处理进位1、不考虑进位关系,a[i]*b[j]累加在积的第j+i-1位上,积用c存储。for(i=1;i<=lena;i++)for(j=1;j<=lenb;j++)c[i+j-1]=c[i+j-1]+a[i]*b[j];83764321228abc8376448505428abc8376453568abc1)b的第1位乘a的各位2)b的第2位乘a的各位3)处理c的各位进位2、从低位到高位逐位向前处理进位lenc=lena+lenb;for(i=1;i<=lenc;i++){c[i+1]=c[i+1]+c[i]/10;
c[i]=c[i]%10;}while((lenc>1)&&(c[lenc]==0)
lenc--;C[0]=lenc;voidhigh_multiply(hpa,hpb,hp&c){hpd;
inti,j,len;
memset(d,0,sizeof(d));for(i=1;i<=a[0];i++)for(j=1;j<=b[0];j++)d[i+j-1]+=a[i]*b[j];
len=a[0]+b[0]+1;for(i=1;i<=len;i++){d[i+1]+=d[i]/10;
d[i]=d[i]%10;}while((d[len]==0)&&(len>1))
len--;d[0]=len;
memcpy(c,d,sizeof(d));}intmain(){
inti;hpa,b,ans;strings1,s2;
cin>>s1;
cin>>s2;str2hp(s1,a);str2hp(s2,b);
high_multiply(a,b,ans);for(i=ans[0];i>=1;i--)
cout<<ans[i];
cout<<endl;return0;}高精度数除以整型数问题表述:输入a(<10240),b(<109)两个数,输出a/b的值和余数。样例输入:998877665544332211002001920样例输出:498959831334081077740算法分析1、基本方法是从被除数的最高位开始,逐位计算商和余数。存储商。余数则转移到下一次的被除数中。注意在下一次的计算中,余数
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年度大产权土地转让合同范本4篇
- 招标项目管理团队2025年度建设与培训合同3篇
- 二零二五年度出租车企业车辆油耗监控合同2篇
- 二零二五年度城市绿化项目农民工个人服务合同4篇
- 2025年度高速公路停车区车位代理销售合同4篇
- 2025年度船舶餐饮服务船员聘用合同范本4篇
- 2025年度苗木种植与生物多样性保护合同3篇
- 胞核钙蛋白酶1通过调控FoxO3a磷酸化促进肺纤维化AT2细胞上皮间质转化
- 联塑集团培训合同
- 2025年度汽车内饰模具加工与销售合同4篇
- 红色革命故事《王二小的故事》
- 《白蛇缘起》赏析
- 海洋工程用高性能建筑钢材的研发
- 苏教版2022-2023学年三年级数学下册开学摸底考试卷(五)含答案与解析
- 英语48个国际音标课件(单词带声、附有声国际音标图)
- GB/T 6892-2023一般工业用铝及铝合金挤压型材
- 冷库安全管理制度
- 2023同等学力申硕统考英语考试真题
- 家具安装工培训教案优质资料
- 在双减政策下小学音乐社团活动有效开展及策略 论文
- envi二次开发素材包-idl培训
评论
0/150
提交评论