当前位置:首页 >> 学科竞赛 >>

10高精度计算


高精度计算

Task:
? ?

?

?

高精度加法 高精度减法 高精度乘法 高精度乘单精度 高精度乘高精度 高精度除法 高精度除单精度 高精度除高精度

Problem 1:a+b=?
输入:a b 输出:a+b的和 输入输出样例: Input: 1

2 Input:1234567890 8765432109 Output:3 Output:9999999999
PS: int32: -2147483648..2147483647 uint32:0..4294967295

Problem 1:a+b=?
观察人工计算的方法:竖式加法 223 + 996 ----------9 3+6=9 1 2+9=11,当前位1,进位1 2 2+9+1=12,当前位2,进位1 1 进位的1 ----------1219

例题1:高精度加法1553
【问题描述】输入两个整数x,y,输出它们的和。

【文件输入】输入两个整数x,y(0<=x,y<=10^100)
【文件输出】输出它们的和 【样例输入】 123 234

【样例输出】357

1、高精度数的存储,用字符串读入
void init(int a[]) { string s; cin>>s; //读入字符串s a[0]=s.length(); //用a[0]计算字符串s的位数 for(i=1;i<=a[0];i++)a[i]=s[a[0]-i]-'0'; //将数串s转换为数组a,并倒序存储. }

2、高精度加法
void jia(int a[],int b[]) //计算a=a+b { int i,k; if(a[0]<b[0])a[0]=b[0]; //确定加法最大位数 for(i=1;i<=a[0];i++)a[i]+=b[i]; //逐位相加 for(i=1;i<=a[0];i++) { a[i+1]+=a[i]/10; a[i]%=10; } //处理进位 if(a[a[0]+1]>0)a[0]++;//修正a的位数(a+b最多只能进一位) }

3、高精度结果的输出
void print(int a[]) //打印输出 { int i; if(a[0]==0){cout<<0<<endl;return;} for(i=a[0];i>=1;i--)cout<<a[i]; cout<<endl; }

Problem 2:a-b=?
竖式减法: 927 - 896 ----------1 7-6=1 3 12-9=3,借位12 0 (9-1)-8=0 ----------31 提示:注意是大数减小数

例题2:高精度减法1554
Description

输入两个整数x,y,输出它们的差x-y。
Input 输入两个整数x,y(0 <= x,y <= 10^100) Output 输出它们的差 Sample Input 234 123 Sample Output

111

1、高精度数比较
int compare(int a[],int b[]) //比较a和b的大小关系,若a>b则为1,a<b则为-1,a=b则为0 { 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>=1;i--) //否则a和b的位数相同,则从高位到低位比较 { if(a[i]>b[i])return 1; if(a[i]<b[i])return -1; } return 0;//各位都相等则两数相等。 }

2、高精度减法
思想:先判断大小,分情况用大数减小数的原则; 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]=a[i]-b[i]; } while(a[a[0]]==0) a[0]--; //修正a的位数 return; } if (flag==-1)//小于 则用a=b-a,返回-1 { cout<<"-"; for(i=1;i<=b[0];i++) { if(b[i]<a[i]){b[i+1]--;b[i]+=10;} //若不够减则向上借一位 a[i]=b[i]-a[i]; } a[0]=b[0]; while(a[a[0]]==0) a[0]--; //修正a的位数 return; } }

Problem 3:a*b=?
竖式乘法:
1. 高精度乘单精度,比如12345*9=?

12345 * 9 -------------45 36 27 18 + 9 -------------111105

练习: 5*9=45 4*9=36 3*9=27 2*9=18 1*9=9
输入N,求N!
(1<=N<=10000)

高精度数乘以单精度
void chengdan(int a[],int k) //a=a*k,k是单精度数 { int i; for(i=1;i<=a[0];i++)a[i]=a[i]*k;//先每位乘起来 for(i=1;i<=a[0];i++){a[i+1]+=a[i]/10;a[i]%=10;} //处理进位 while(a[a[0]+1]>0) {a[0]++;a[a[0]+1]=a[a[0]]/10;a[a[0]]=a[a[0]]%10;} //处理最高位相乘的进位 }

Problem 3:a*b=?
竖式乘法:
2. 高精度乘高精度,比如12345*12345=? 问题转化为若干个高精度乘单精度之和

例题3:高精度乘法1555
Description

输入两个整数x,y,输出它们的积。
Input 输入两个整数x,y(0 <= x,y <= 10^100) Output 输出它们的积 Sample Input 11 12 Sample Output

132

高精度数乘以高精度
void chenggao(int a[],int b[],int c[]) { int i,j,len; for(i=1;i<=a[0];i++) for(j=1;j<=b[0];j++)c[i+j-1]+=a[i]*b[j]; c[0]=a[0]+b[0]; //位数最多为两个高精度为数之和 for(i=1;i<=c[0];i++){c[i+1]+=c[i]/10;c[i]%=10;} //处理进位 while(c[0]>0&&c[c[0]]==0)c[0]--; }

Problem 4:a/b=?
竖式除法 36 12345 √ 452678 37035 8232 82328 74070 8258

12345*3=37035 45267-37035=8232 下一位再次减法 12345*6=74070 82328-74070=8258 余数

例题4:高精度除单精度1556
Description

输入两个整数x,y,输出它们的商。
Input 输入两个整数x,y(0 <= x <= 10^100,y <= 30000) Output 输出它们的商 Sample Input 123 12 Sample Output

10

高精度数除以单精度
void chudan(int a[],int b,int c[],int d)//商c=a/b,余数d=a%b { int i; d=0; //余数初始化 for(i=a[0];i>=1;i--) //按照由高位到底位的顺序,逐位相除 { d=d*10+a[i]; //接受了来自第i+1位的余数 c[i]=d/b; //计算商的第i位 d=d%b; //计算第i位的余数 } c[0]=a[0]; while(c[0]>0&&c[c[0]]==0)c[0]--;//计算商的有效位数 }

高精度数除以单精度----优化
void chudan(int a[],int b) { int i,d=0; for(i=a[0];i>=1;i--)//按照由高位到底位的顺序,逐位相除 { d=d*10+a[i]; //接受了来自第i+1位的余数 a[i]=d/b; //计算商的第i位 d=d%b; //计算第i位的余数 } while(a[0]>0&&a[a[0]]==0)a[0]--;//计算商的有效位数 }

例题5:高精度除高精度1557
Description 输入两个整数x,y,输出它们的商和余数。 Input 输入两个整数x,y(0 <= x,y <= 10^100) Output 输出共计两行,第一行为它们的商,第二行为他们的余数 Sample Input 123 12 Sample Output 10 3

高精度除高精度
void numcpy(int b[],int tmp[],int i)//复制b数组到tmp数组从i开始 { for(int j=1;j<=b[0];j++)tmp[j+i-1]=b[j]; tmp[0]=b[0]+i-1; } void chugao(int a[],int b[],int c[]) { int i,j,tmp[101]; c[0]=a[0]-b[0]+1;//商的最大位数 for(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]--; }

例题6:求n! 1570
Description 精确计算n的阶乘n!(1 <= n < 350) Input 输入n Output 输出n的阶乘的值 Sample Input 3 Sample Output 6

例题7:回文数(NOIP1999普及)1267
【问题描述】 若一个数(首位不为零)从左向右读与从右向左读都是一样, 我们就将其称之为回文数。例如:给定一个 10进制数 56,将 56加 65(即把56从右向左读),得到 121是一个回文数。 又如,对于10进制数87: STEPl:87+78=165; STEP2:165+561= 726; STEP3:726+627=1353; STEP4:1353+3531=4884 在这里的一步是指进行了一次N进制的加法,上例最少用了4 步得到回文数4884。 写一个程序,给定一个N(2<n<=16)进制数 M.求最少经过几 步可以得到回文数。如果在30步以内(包含30步)不可能得到回文 数,则输出“Impossible” 【样例输入】9 87 【样例输出】6


相关文章:
c语言大作业高精度计算
c语言大作业高精度计算_计算机软件及应用_IT/计算机_专业资料。学班学姓 摘要 ...执行计算后,数组元素会出现大于 10 的数,为避免混乱,通过此函数将其转化为原先...
大作业题目_算法型10
高精度计算 题目:高精度计算是指位数较长(超出 C 语言数据类型范围)的计算问题...输出 0. 退出 10. ACM/ICPC 试题 题目:编写 http://acm.uva.es 或 http...
C语言的高精度算法
高精度计算一. 加法 先判断出两个数哪个较长,两个数从个位对齐后, 从个...[0]='1'; 首先开线性表,把在 0-10^100 的数 p[0][1]='\0'; 都...
高精度模板(算法必备)
高精度模板(算法必备)_工学_高等教育_教育专区。高精度计算模板注意:减法、除法...[i]) - 48 + int2) %10; int2 = (int(str1[i]) - 48 + int(...
高精度运算和简单优化方法(C语言)
高精度运算和简单优化方法(C语言)_IT/计算机_专业资料。高精度运算和简单优化方法...计算 while(i<la||i<lb) { x=a[i]+10-b[i]+x; c[i]=x%10; a...
高精度计算n阶乘的c语言源代码和解释
高精度计算n阶乘的c语言源代码和解释_计算机软件及应用_IT/计算机_专业资料。利用...>= 10) { if(i==3*HEAD_M-1) d[0]+= c[i-2*HEAD_M]/10; else...
pascal高精度计算器
pascal高精度计算器_计算机软件及应用_IT/计算机_专业资料。高精度计算器: 程序...(x*10+a[i]) div y; x:=(x*10+a[i]) mod y; end; j:=1; ...
根据以下公式编程序计算e的近似值,精度要求为:10E-6:
根据以下公式编程序计算e的近似值,精度要求为:10E-6:_计算机软件及应用_IT/计算机...[i]); //输出最高位,若有前导 0 则不输出 i--; //按顺序输出其他...
抽样调查中精确度的计算
二、抽样推断精确度的定义及计算 (一)精确度定义我们知道测量的精度是指测量值...(占因变量平均数 10.17 的 1.9%) ,都说明了回归方程质量较高,具有较高的...
从10米迈向1米定位精度 室内定位技术详解
10米迈向1米定位精度 室内定位技术详解_纺织/轻工业_工程科技_专业资料。从 ...定位算法对标签位置进行分析,多路径分辨能力强、精度 高, 定位精度可达亚米级。...
更多相关标签:
php 高精度计算 | 高精度计算 | 高精度计算器 | 在线高精度计算器 | 高精度计算pi值 | 高精度计算pi | java 高精度计算 | js 高精度计算 |