计算基础教程 4

授课内容高精度运算学时2教学目标知识目标理解高精度运算的概念与适用场景掌握高精度数据的字符串输入与数组逆序存储方法掌握高精度加减乘除的基本运算原理了解高精度与低精度运算的区别和实现思路能力目标提升超大整数问题的存储与处理能力强化模拟手工运算的算法设计能力培养高精度程序编写与调试优化能力重点与难点重点高精度数的逆序存储与位数对齐方法高精度加法、减法、乘法的实现步骤高精度与低精度混合运算的处理技巧进位、借位、前导零的处理规则难点高精度乘法的位数对齐与进位处理高精度除法的模拟过程与余数处理教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章解决普通数据类型无法存储的超大整数运算问题高精度是算法竞赛、编程考级的高频必考内容学会用数组模拟数字，突破计算机数值范围限制掌握加减乘除全套高精度算法，提升底层编程能力为大数处理、密码学、阶乘等问题提供基础实现方案第二部分：新课讲解一、高精度运算概述1、什么是高精度运算非常大的数据，超过了编程语言内置数据类型的最大表示范围时（一般指整数，超过了longlong的表示范围），必须自行存储与运算，就是高精度运算。2、高精度数据的存储高精度数据一般以字符串的方式读取，读取后分离出各位数字并反向存放于数组中，如下图所示。二、高精度加法1、高精度加高精度原理二个高精度数相加是通过完全模拟手工加法来实现的，在手工加法中，将二个数从个位开始逐位相加，并考虑低位向前的进位即可。核心代码inta[100],b[100],c[101]; //全局数组，已初始化为0intx=0; //记录进位for(i=0;i<len1||i<len2; i++)//从个位开始，逐位相加{ c[i]=a[i]+b[i]+x; //两数相加 x=c[i]/10; //计算进位 c[i]%=10;}c[i]=x; //最高位的进位if(c[i]==0)i--; //如果最高位没有进位，则和的实际有效位数减一while(i>=0)cout<<c[i--]; //输出结果2、高精度加低精度原理将低精度数加到高精度数的个位上，而后不断向前进位即可。以“987+556”为例，我们将“987”视为高精度数，首先将它的各位数字分离并存储至数组，结果为：a[0]=7，a[1]=8，a[2]=9。然后，再进行如下计算：将a[0]加上556，得到563，扣除进位值56，得a[0]=3。将a[1]加上进位值56，得到64，再扣除向上的进位值6，得a[1]=4。将a[2]加上进位值6，得a[2]=15。注意，a[2]中的值虽然大于9，但可以不用再向前进位。因如果将a[2]、a[1]、a[0]依次输出到屏幕，这些数字“粘接”在一起之后就是正确结果：1543。核心代码见课本。三、高精度减法1、高精度减高精度原理模拟手工减法，从个位开始逐位相减。减法需要解决二个问题：不够减及借位。为了便于统一处理，要求被减数必须大于等于减数。如果被减数小于减数，需要先输出“-”，然后交换二者。在完成某一位的相减之前，需要先判断是否够减，若不减需要提交借位。{ for(intj=0;j<n-1-i;j++) //内层循环n-1-i次 { if(a[j]>a[j+1]) //需要将a[j]与a[j+1]交换 { inttemp; temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } }核心代码strings1,s2;cin>>s1>>s2; //输入被减数、减数inti=s1.length()-s2.length();if(i<0||i==0&&s1<s2)//被减数小时，输出负号并交换s1与s2{ cout<<'-'; swap(s1,s2);}….for(i=0;i<=len1||i<=len1; i++){ if(a[i]<b[i]) //预先判断是否够减 { a[i]+=10; //不够减，向高位借1当10 a[i+1]--; } c[i]=a[i]-b[i]; //对应位相减 }while(c[i]==0&&i>0)i--;//删除结果中的前导0（结果为0保留一个0）while(i>=0)cout<<c[i--];//输出结果2、高精度减低精度原理将高精度数的个位减去低精度数，然后不断从低位向高位借位，直到每一位数字都大于等于0。核心代码见课本。四、高精度乘法1、高精度乘高精度原理仍然是模拟手工乘法，以图11-3为例进行介绍，运算过程如下：要点如果二个乘数分别为m位与n位，则结果最长为m+n位。a[i]与b[j]相乘的结果，应该记入到c[i+j]。核心代码for(inti=0;i<len1;i++)//乘法遵循交换律，不区分被乘数与乘数{ intx=0; //用于存放进位 for(intj=0;j<len2;j++) { c[i+j]+=a[i]*b[j]+x;//原有内容+当前乘积+进位 x=c[i+j]/10; c[i+j]%=10; } c[i+len2]=x; //结果中最高位向前的进位}inti=len1+len2;//结果的最高位数while(c[i]==0&&i>0)i--; //删除前导0while(i>=0) cout<<c[i--];//输出乘积2、高精度乘低精度原理将高精度数的各位数字与低精度数分别相乘，然后再针对运算结果中的每一位数字处理向前进位（将低位数中10以上的部分加到上一位上）即可。核心代码见课本。五、高精度除法1、高精度除以低精度原理模拟手工除法，以567÷53为例进行介绍（我们假设567为高精度数据），其运算过程如下图所示。被除数的存储除法操作是从被除数的高位开始运算的，因此在存储时并不需要反转方向。核心代码for(i=0;i<len;i++) //按位相除{ x=x*10+s[i]-48; //x内为上一步操作的余数 c[i]=x/b; //本步操作的商 x%=b; //本步操作的余数}i=0;while(c[i]==0&&i<len-1)i++; //删除前导0cout<<"商=";while(i<len)cout<<c[i++]; //输出商。cout<<"余数