2、学会简单高精度的运算：加、减、乘
3、掌握高精度运算的应用
教学重点、难点：
高精度乘，高精度运算的应用
教学过程：
一、为什么要进行高精度计算
计算机的特点：运算速度快、计算精度高、自动化等；
计算机的应用：数值运算和非数值运算，数值运算的一个重要问题就是精度问题。比如π的计算，小数点后面要几万位，计算机中的数据类型无法保存；或者数很大，超过了一般数的范围（integer:-32768——32767；longint:-2147483628——2147483627；real：-1038——-10-38或10-38——1038）。这时就属于高精度问题。
二、精度数的存储
数组：每个数组元素存储1位。每一位都可以直接加减，运算方便；但不能直接读入，读入后必须转化成数字；
字符串：最长255位，能直接输入输出，符合数值的输入习惯；但每位是一个字符，必须先转换成数字才能进行运算，运算时不方便。
一般，在输入数据不长于255个字符的情况下，通常采用字符串的方式读入，然后再倒置（为了低位对齐，方便以后的运算和进位）并转换成数字存入数组。这样，取长补短，简化操作。
三、高精度的运算
a)加法：先加后进位，注意进位问题；两数之和的位数最大为较大数的位数加1；
设进位标志为t，从低位往高位进，t=0表示本位运算无进位，t=1有进位；
每一项sum[i]:=A[i]+B[i]+t；程序如下：
定义数组A，B，长度为max，定义数组sum，长度为max+1；初始化为0；
假设以字符串输入，stra,strb；
求出长度lena,lenb；存入数组；
maxlen：=max(lena,lenb);
t:=0;
forI:=1tomaxlen+1do
begin
sum[i]:=A[i]+B[i]+t;
t:=sum[i]div10;
sum[I]:=sum[I]mod10;
end;
输出sum：ifsum[maxlen+1]<>0thenwrite(sum[maxlen+1]);
forI:=maxlendownto1dowrite(sum[i]);
b)减法：先减后借位；计算前，首先需要对被减数和减数进行比较，若减数比被减数大，则要先打印“-”号，然后交换被减数和减数求差。主要程序段如下：
ForI:=1tolenado
Begin
c[I]:=a[I]-b[I]-t;
Ifc[I]<0thenbeginc[I]:=c[I]+10;t:=1;end
Elset:=0;
End;
c)乘法：乘积的位数最大为两个因子的位数之和；先用被乘数的某位和乘数的每一位求积，填入相应的位置而不考虑进位的问题，全部计算完后，对积进行一次进位处理。
Forj:=1tolenbdocj[I+j-1]:=cj[I+j-1]+a[I]*b[j];
T:=0;
Forj:=1tolena+lenbdo
Cj[j]:=cj[j]+t;
T:=cj[j]div10;
Cj[j]:=cj[j]mod10;
例15-1：用高精度计算出S=1！+2！+3！+…+n！（n≤50），输入正整数N，输出计算结果S。
[算法设计]本题涉及高精度加法和乘法运算，程序使用二个一维数组s和f分别存储到当前项为止的和与当前项的值，计算当前项的值采用递推的迭代的方法，即k!=(k-1)*k。
程序：
programeg15-1(input,output);
constmaxlen=100;
typearraytype=array[0..maxlen]oflongint;
vari,n:integer;
f,s:arraytype;
proceduremul(vara:arraytype;k:longint);
vari:longint;
fori:=0tomaxlendof[i]:=f[i]*k;
fori:=0tomaxlen-1do
a[i+1]:=a[i+1]+a[i]div10;
a[i]:=a[i]mod10
end
procedureadd(vara:arraytype;b:arraytype);
fori:=0tomaxlendoa[i]:=a[i]+b[i];
ifa[i]>=10then
a[i+1]:=a[i+1]+1;
a[i]:=a[i]-10
procedureprint(a:arraytype);
vari,j:longint;
i:=maxlen;
while(i>0)and(a[i]=0)doi:=i-1;
forj:=idownto0dowrite(a[j])
begin{main}
write('Inputn:');readln(n);
fori:=0tomaxlendos[i]:=0;
fori:=1tomaxlendof[i]:=0;
f[0]:=1;
fori:=1tondo
mul(f,i);
add(s,f);
print(s);
writeln
end.
三、对高精度的思考和优化
要想提高高精度程序的效率，除了优化存储结构外，更关键的是优化算法的运算过程和方法。比如：计算两个8位数的和：
方法1：分成8个小整数（integer），每个都是一位数，需要做8次加法；
方法2：分成2个小整数（integer），每个为4位数，需要2次加法。
方法3：直接使用lingint，1次加法。
归纳：一般情况下，使用longint进行加减法运算时，每个小整数可保存到9位；乘法运算时，每个小整数可保存4位；除法运算时（设除数位数为x），当x<=8时，被除数存储时可把每个小整数开到9-x位；若x>8，则被除数和除数的每个小整数用1位，编程运算时最方便，效率也较高。
问题：k进制数的高精度运算
四、举例
例15-3、回文数
若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。
又如：对于10进制数87：
STEP1：87+78=165STEP2：165+561=726
STEP3：726+627=1353STEP4：1353+3531=4884
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
写一个程序，给定一个N（2<=N<=10或N=16）进制数M，求最少经过几步可以得到回文数。
如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”
样例：
INPUT
N=9M=87
OUTPUT
STEP=6
[算法设计]本问题的核心是高精度加法，具体处理起来可以分为三个部分。
第一，是对读入数据的处理。本题中，数据的进制是可变的，所以用整型数（即十进制数）不是很方便，考虑一般情况，我们可以采用字符串读入，再对数据作后期加工，把它的每一位都分离开来，存入一个数组digit里，数组invert存放数组digit的倒序，变量len记录了数据的位数。在转化过程中要注意到16进制的特殊性，要对于字母ABCDEF要单独处理。
第二，进行判断与运算。存储数据时用什么形式表示其实无所谓，关键是做加法运算的时候要符合n进制的规律。所以，运算时一律以10进制形式存储，存储该位数码对应的十进制数值，A用10，F用15表示。判断是否构成回文数时也一样用10进制，逐对比较对称的两个数位上的数字，看它们是否相等。做加法的次数以30次为限。
第三，输出结果。如果当前的数是回文数，则输出步数；否则按“Impossible”输出。
programeg15-4(input,output);
constmax=1000;
typearraytype=array[1..max]oflongint;
vari,n,len,step:longint;
str:string;
digit,invert:arraytype;
functionpalindrome(vardigit:arraytype;len:longint):boolean;
i:=1;j:=len;
while(i begini:=i+1;j:=j-1end; ifi write('Inputnumber:');readln(str); fori:=1tomaxdodigit[i]:=0; len:=length(str); fori:=1tolendo ifstr[i]>='A' thendigit[len+1-i]:=ord(str[i])-ord('A')+10 elsedigit[len+1-i]:=ord(str[i])-ord('0'); step:=0; while(step<30)andnot(palindrome(digit,len))do fori:=1tolendoinvert[i]:=digit[len+1-i]; fori:=1tolendodigit[i]:=digit[i]+invert[i]; ifdigit[i]>=nthen begindigit[i+1]:=digit[i+1]+1; digit[i]:=digit[i]-nend; ifdigit[len+1]>0thenlen:=len+1; step:=step+1 ifstep=30thenwriteln('Impossible!') elsewriteln('STEP=',step) 三、练习 循环结构的程序设计 1、While语句与当型循环的含义及使用方法 2、Repeat语句与直到型循环的含义及使用方法 3、for语句与计数循环的含义及使用方法 4、多重循环（循环的嵌套）的含义及使用方法 教学重、难点： 三种循环结构的理解及其在实践中的使用 许多处理过程中有连续的重复，这时候如果还是一句句地重复写的话，既麻烦又累赘，当要重复成千上万次时，这种重复的书写几乎是不可能实现的。直接简便的方法是用循环语句来实现循环。 一．While语句与当型循环 1．格式： while布尔表达式do语句； 2．说明： 格式中while和do都是保留字，布尔表达式表示条件，它的描述跟条件语句里的条件描述是一样的。 Do后面的语句可以是单一语句也可以是复合语句，称为循环体。只要布尔表达式成立时（即值为TRUE时）就执行循环体，如此反复直到布尔表达式不成立（值为FALSE）时停止。如果一开始就为布尔表达式就不成立（值为FALSE），那么循环体一次也不执行。 例5-1：输出1到100的算术平方根。 【分析】： 计算一个数的算术平方根可以用一个函数sqrt(i)，其中的I从1一直变化到100，通过循环来实现。 【程序清单】： programex5-1; vari:integer; i:=1; whilei<=100do writeln(‘Squrarerootof’,i,‘is‘,sqrt(i):8:4); i:=i+1; 【思考与提高】： 上面程序中I的初值为1，在循环体中，先是输出I的算术平方根再将I的值增加1，所以最后循环结束时I的值是101，while的条件也要写成I<=100或写为I<101，如果写成I<100，那么在I=99时满足循环的条件，先输出99的算术平方根，然后I的值增加1变为100，此时不满足循环的条件了，所以便结束循环，结果100的算术平方根没有输出。因此我们在用循环时一定要把握好控制循环的边界条件，不能随便扩大边界也不能随便缩小边界。 i:=0; whilei<100do writeln(……); 【注意】： 在while循环体中一定要有相应的语句使布尔表达式的值可能为false,否则就会构成死循环。 3、循环的强制终止 一般来说，只要循环的条件及循环体描述得当，循环都能顺利结束，不会产生死循环的。有时在程序运行中会有一些特殊的情况，需要终止当前循环的执行，如果将这个条件写到循环体外有不太方便，这时可以使用break来强制终止当前循环的执行。 二、Repeat语句与直到型循环 repeat 语句； ……； until布尔表达式； 2．说明 格式中repeat和until都是保留字，其间的语句构成循环体，最后一个语句的分号可以省略；until后的布尔表达式表示条件，描述的是循环结束的条件。 3．功能 反复执行循环体直到布尔表达式的值为true时为止。 4．示例： 上例的程序段可写为： writeln(‘Squarerootof‘,i,‘is‘,sqrt(i):8:4); untili>100; 5．While与Repeat语句对比 while和repeat语句一般情况下可以相互替换。它们的主要区别是： while是先判断后执行，而repeat是先执行后判断，因此while语句的循环体有可能一次也不执行，而repeat语句至少执行一次； 前者是当条件满足时执行，而后者是当条件不满足时执行； 前者的循环体是复合语句时要用begin、end，而后者却不一定要用。 三、for语句与计数循环 （1）for变量标识符：=初值表达式to终值表达式do语句； 从小到大执行的格式 （2）for变量标识符：=初值表达式downto终值表达式do语句； 从大到小执行的格式 格式中的for,to,downto,do都是保留字，to一般用在升序的计数，而downto用在降序的计数。变量标识符在这里称作是控制变量，必须是离散（有序）数据类型，如： fori:=1to100do…. forch:=’a’to‘z’do…. 3．示例 上面的例子用for语句写出的程序段为： fori:=1to100dowirteln(‘Squarerootof‘,i,’is’,sqrt(i):8:4); 也可以写成： fori:=100downto1do wirteln(‘Squarerootof‘,101-i,’is’,sqrt(101-i):8:4); for语句的形式简单，但它也有一定的局限性，主要是控制变量的值不能随意变化，每次只能取其后继(用to的情况)或前趋（用downto的情况），另一限制是控制变量只能用简单的有序的离散量，且循环次数已定，不能象while或repeat那样通过布尔表达式来控制循环的操作。 例5-2：用for语句计算前N（N>1）个自然数中所有偶数的和。 判定偶数可有多种方法，也可以不用判定而直接去构造偶数，由此得到更多的方法。 【方法1】： 构造偶数，1到n之间的偶数有NDIV2个，所以从第一个构造到最后一个偶数，并将它加到存储和的变量中。 sum:=0; forcounter:=1tondiv2do sum:=sum+2*counter; 【方法2】： 对1到n中任一个自然数进行检测，如果它除以2的余数为0表明它是偶数，则将其加到和中。 forcounter:=1tondo ifcountermod2=0thensum:=sum+counter; 【方法3】： 用标准函数odd(x)，判定是否是奇数，如果不是奇数说明它是偶数。 ifnotodd(counter)thensum:=sum+counter; 【方法4】： 在方法1中是构造偶数相加，也可以先相加，再考虑偶数的情况，如10以内的偶数为2、4、6、8、10，将它们标明序号为1、2、3、4、5，序号为原数的一半，因此只要求出序号的和，再将序号的和乘以2便得到偶数的和。 Forcounter:=1tondiv2dosum:=sum+counter; Counter:=counter*2; 注意：一般情况下不允许在for语句的循环体中改变控制变量的值。 四．多重循环（循环的嵌套） 当程序中要用到多个循环时，如果这些循环是并列的关系，那么它们彼此之间的控制变量不相互影响。 而当一个循环的循环体中又有循环时，这就是循环的嵌套，称为多重循环。如前面要大家输入的“输出九九乘法表”程序。 例5-3：编写程序输出如下的字母塔： A ABA ABCBA ……………. ABCD……DCBA 此题有两个关键：一是确定每一行前导空格符的数目；二是按一定规律输出英文大写字母，共26行。应能保证最后一行前导空格数目至少为0，设最后一行的前面空格数为10个，那么倒数第二行前面的空格数为11，倒数第三行的数目为12……，如果控制输出行的字符变量为c，则空格数为：ord(‘Z’)-ord(c)+10 programeg5-3; varch,c:char; forc:=’A’to‘Z’do write(‘‘:ord(‘Z’)-ord(c)+10);{输出空格数} forch:=’A’tocdowrite(ch);{输出一行的左半部分} forch:=pred(c)downto‘A’dowrite(ch);{输出一行的右半部分} writeln;{换行} 上面整个程序是个两重循环，而外循环的循环体是两个并列的循环，因此虽然程序中有三个for语句，但只是两重循环。 而程序中输出一行时是通过两个循环来实现的，能不能通过一个循环来实现呢？用字符型变量来控制循环不太方便，可以用整型变量来控制循环列方便一些，相应的程序段如下：