C++-高精度乘法ppt课件.ppt

《C++-高精度乘法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、高精度问题高精度运算所谓的高精度运算,是指参与运算的数(加数,减数,因子……）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。这个时候只能用数组来表示参与运算的数字，那么他们的运算也就不能简单的直接进行了。高精度加法1553Description输入两个整数x,y，输出它们的和。Input输入两个整数x,y（0<=x,y<=10^100）Output输出它们的和SampleInput123　　234SampleOutput357高精度加法高精度运算主要解决以下三个问题：1、加数、减数、运算结果的输入和存储2、运算过程3、结果输出高精度加法数字的输入

2、和存储1、运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。能表示多个数的数据类型有两种：数组和字符串。（1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；用数组表示数的优点：每一位都是数的形式，可以直接加减；运算时非常方便用数组表示数的缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；（2）字符串：字符串的最大长度是255，可以表示255位。用字符串表示数的优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；用字符串表示数的缺点：字符串中的每一位

3、是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便；（3）因此，综合以上所述，对上面两种数据结构取长补短：用字符串读入数据，用数组存储数据。高精度加法数据输入和存储Strings1,s2;Inta[101]={0},b[101]={0};Cin>>s1>>s2;Inti,j=0;For(i=s1.length();i>0;i--,j++)a[i]=s1[j]-’0’;For(i=s2.length(),j=0;i>0;i--,j++)b[i]=s2[j]-’0’;用数组a,b分别存储s1,s2并且将其字符转换为数值，不过存储时是倒序

4、存放。高精度加法运算过程：（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：8+2=10，向前一位进1，本位的值是0；可借助MOD、DIV运算完成这一步；（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；（4）如果两个加数位数不一样多，则按位数多的一个进行计算；竖式计算：138+12138+12——————————1410每位对齐，按位加，每位若超过10的需要进位150高精度加法运算过程：intc[

5、1000]={0};For(i=1;i<=max(s1.length(),s2.length());i++){c[i]=(a[i]+b[i])%10+c[i];c[i+1]=(a[i]+b[i])/10;//进位}因为存放s1,s2两个数到数组a,b中时，我们是倒序存放也就是个位存放在a[1]和b[1]中，因此我们从a[1]和b[1]开始每位求和其实已经完成了按位对齐的这一步。高精度加法输出结果：按数组c中的实际使用的位数倒序输出。if(c[i+1])i=i+1;//判断最高位相加之后是否还向上进位For(;i>1;i--)cout<

6、高精度×单精度For(i=1;i<=s1.length();i++)c[i]=a[i]*b;//b为乘数,求出每位上的乘积For(i=1;i<=s1.length();i++){c[i+1]=c[i]/10+c[i+1];//求出进位c[i]=c[i]%10;//求出每位上数}高精度乘法2、高精度×高精度a[3]a[2]/b[2]a[1]/b[1]a[i]345b[j]×23————————————a[i]×b[1]c[5]c[4]c[3]c[2]c[1]0091215a[i]×b[2]69+812+10————————————————c[i+1]+=c[i]

7、/10c[i]=c[i]%108035i=1..3j=1..2高精度乘法2、高精度×高精度For(i=1;i<=s1.length();i++)for(j=1;j<=s2.length();j++)c[j+i-1]+=a[i]*b[j];For(i=1;i<=s1.length()+s2.length()-1;i++){c[i+1]+=c[i]/10;c[i]=c[i]%10;}高精度除法1、高精度/单精度:模拟自然除法，每一位除以数b求商，（反复减去b，记录下循环的次数，当该位数值小于数b时，责循环次数即为该位上的商，然后将余数乘上10加下一位。）a[i]a

8、[4]a[3]a[2]a[1]1234