高精度算法

教学目标：

1、学习高精度数的存储

2、学会简单高精度的运算：加、减、乘

3、掌握高精度运算的应用

教学重点、难点：

高精度乘，高精度运算的应用

教学过程：

一、为什么要进行高精度计算

计算机的特点：运算速度快、计算精度高、自动化等；

计算机的应用：数值运算和非数值运算，数值运算的一个重要问题就是精度问题。比如π的计算，小数点后面要几万位，计算机中的数据类型无法保存；或者数很大，超过了一般数的范围（integer:-32768——32767；longint:-2147483628——2147483627；real：-10³⁸——-10^-38或10^-38——10³⁸）。这时就属于高精度问题。

二、精度数的存储

数组：每个数组元素存储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;

         for I:=1 to maxlen+1 do

           begin

sum[i]:=A[i]+B[i]+t;

t:=sum[i] div 10;

sum[I]:=sum[I] mod 10;

               end;

         输出sum：if sum[maxlen+1]<>0 then write(sum[maxlen+1]);

                   for I:=maxlen downto 1 do write(sum[i]);

b)                减法：先减后借位；计算前，首先需要对被减数和减数进行比较，若减数比被减数大，则要先打印“-”号，然后交换被减数和减数求差。主要程序段如下：

t:=0;

For I:=1 to lena do

  Begin

c[I]:=a[I]-b[I]-t;

If c[I]<0 then begin c[I]:=c[I]+10;t:=1;end

          Else t:=0;

  End;

c)                  乘法：乘积的位数最大为两个因子的位数之和；先用被乘数的某位和乘数的每一位求积，填入相应   的位置而不考虑进位的问题，全部计算完后，对积进行一次进位处理。

   For I:=1 to lena do

Begin

  For j:=1 to lenb do cj[I+j-1]:=cj[I+j-1]+a[I]*b[j];

  T:=0;

  For j:=1 to lena+lenb do

    Begin

      Cj[j]:=cj[j]+t;

T:=cj[j] div 10;

Cj[j]:=cj[j] mod 10;

    End;

End;

例15-1：用高精度计算出S=1！+2！+3！+…+n！（n≤50），输入正整数N，输出计算结果S。

[算法设计]  本题涉及高精度加法和乘法运算，程序使用二个一维数组s和f分别存储到当前项为止的和与当前项的值，计算当前项的值采用递推的迭代的方法，即k!=(k-1)*k。

程序：

program eg15-1(input,output);

const maxlen=100;

type arraytype=array [0..maxlen] of longint;

var i,n:integer;

f,s:arraytype;

procedure mul(var a:arraytype; k:longint);

  var i:longint;

  begin

     for i:=0 to maxlen do f[i]:=f[i]*k;

     for i:=0 to maxlen-1 do

       begin

          a[i+1]:=a[i+1]+a[i] div 10;

          a[i]:=a[i] mod 10

       end

end;

procedure add(var a:arraytype;b:arraytype);

var i:longint;

begin

     for i:=0 to maxlen do a[i]:=a[i]+b[i];

     for i:=0 to maxlen-1 do

         if a[i]>=10 then

            begin

                 a[i+1]:=a[i+1]+1;

                 a[i]:=a[i]-10

            end

end;

procedure print(a:arraytype);

var i,j:longint;

begin

     i:=maxlen;

     while (i>0) and (a[i]=0) do i:=i-1;

     for j:=i downto 0 do write(a[j])

end;

begin  {main}

     write('Input n:');readln(n);

     for i:=0 to maxlen do s[i]:=0;

     for i:=1 to maxlen do f[i]:=0;

     f[0]:=1;

     for i:=1 to n do

       begin

          mul(f,i);

          add(s,f);

       end;

     print(s);

     writeln

end.

三、对高精度的思考和优化

要想提高高精度程序的效率，除了优化存储结构外，更关键的是优化算法的运算过程和方法。比如：计算两个8位数的和：

方法1：分成8个小整数（integer），每个都是一位数，需要做8次加法；

方法2：分成2个小整数（integer），每个为4位数，需要2次加法。

方法3：直接使用lingint，1次加法。

时间分析：用integer类型计算1位数和计算4位数，系统时间是基本一样的，所以，方法2比方法1优；用 longint计算比用integer计算，系统要花费更多的时间，但运算次数明显减少，实践证明：方法3比方法2快一点。

归纳：一般情况下，使用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  = 165                  STEP2：165+561 = 726

      STEP3：726+627 = 1353            STEP4：1353+3531 = 4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2<=N<=10或N=16）进制数M，求最少经过几步可以得到回文数。

如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”

样例：

INPUT

        N = 9  M= 87

      OUTPUT

        STEP=6

[算法设计] 本问题的核心是高精度加法，具体处理起来可以分为三个部分。

第一，是对读入数据的处理。本题中，数据的进制是可变的，所以用整型数（即十进制数）不是很方便，考虑一般情况，我们可以采用字符串读入，再对数据作后期加工，把它的每一位都分离开来，存入一个数组digit里，数组invert存放数组digit的倒序，变量len记录了数据的位数。在转化过程中要注意到16进制的特殊性，要对于字母A B C D E F要单独处理。

第二，进行判断与运算。存储数据时用什么形式表示其实无所谓，关键是做加法运算的时候要符合n进制的规律。所以，运算时一律以10进制形式存储，存储该位数码对应的十进制数值，A用10，F用15表示。判断是否构成回文数时也一样用10进制，逐对比较对称的两个数位上的数字，看它们是否相等。做加法的次数以30次为限。

第三，输出结果。如果当前的数是回文数，则输出步数；否则按“Impossible”输出。

程序：

program eg15-4(input,output);

const max=1000;

type arraytype=array [1..max] of longint;

var i,n,len,step:longint;

    str:string;

    digit,invert:arraytype;

function palindrome(var digit:arraytype;len:longint):boolean;

var i,j:longint;

begin

     i:=1; j:=len;

     while (i<j) and (digit[i]=digit[j]) do

     begin i:=i+1; j:=j-1 end;

     if i<j then palindrome:=false else palindrome:=true

end;

begin

     write('Input n:'); readln(n);

     write('Input number:'); readln(str);

     for i:=1 to max do digit[i]:=0;

     len:=length(str);

     for i:=1 to len do

         if str[i]>='A'

            then digit[len+1-i]:=ord(str[i])-ord('A')+10

            else digit[len+1-i]:=ord(str[i])-ord('0');

     step:=0;

     while (step<30) and not(palindrome(digit,len)) do

     begin

          for i:=1 to len do invert[i]:=digit[len+1-i];

          for i:=1 to len do digit[i]:=digit[i]+invert[i];

          for i:=1 to len do

              if digit[i]>=n then

                 begin digit[i+1]:=digit[i+1]+1;

                       digit[i]:=digit[i]-n end;

          if digit[len+1]>0 then len:=len+1;

          step:=step+1

     end;

     if step=30  then writeln('Impossible!')

                 else writeln('STEP=',step)

end.

三、         练习

循环结构的程序设计

教学目标：

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，通过循环来实现。

【程序清单】：

program ex5-1;

var  i:integer;

begin

i:=1;

while i<=100 do

     begin

       writeln(‘Squrare root of’, i, ‘ is ‘, sqrt(i):8:4);

       i:=i+1;

     end;

end.

【思考与提高】：

    上面程序中I的初值为1，在循环体中，先是输出I的算术平方根再将I的值增加1，所以最后循环结束时I的值是101，while的条件也要写成I<=100或写为 I<101，如果写成I<100，那么在I=99时满足循环的条件，先输出99的算术平方根，然后I的值增加1变为100，此时不满足循环的条件了，所以便结束循环，结果100的算术平方根没有输出。因此我们在用循环时一定要把握好控制循环的边界条件，不能随便扩大边界也不能随便缩小边界。

    另一种写法：i的初值为0，条件的描述及循环体的相关语句的顺序都要作调整：

  i:=0;

while i<100 do

begin

i:=i+1;

writeln(……);

end;

【注意】：

在while循环体中一定要有相应的语句使布尔表达式的值可能为false,否则就会构成死循环。

3、循环的强制终止

一般来说，只要循环的条件及循环体描述得当，循环都能顺利结束，不会产生死循环的。有时在程序运行中会有一些特殊的情况，需要终止当前循环的执行，如果将这个条件写到循环体外有不太方便，这时可以使用break来强制终止当前循环的执行。

二、Repeat语句与直到型循环

1．格式：

repeat

      语句；

语句；

……；

语句；

until 布尔表达式；

2．说明

格式中repeat和until都是保留字，其间的语句构成循环体，最后一个语句的分号可以省略；until后的布尔表达式表示条件，描述的是循环结束的条件。

3．功能

反复执行循环体直到布尔表达式的值为true时为止。

4．示例：

上例的程序段可写为：

begin

i:=1;

repeat

   writeln(‘Square root of  ‘, i, ‘ is ‘,sqrt(i):8:4);

   i:=i+1;

until i>100;

end.

5．While与Repeat语句对比

while和repeat语句一般情况下可以相互替换。它们的主要区别是：

while是先判断后执行，而repeat是先执行后判断，因此while语句的循环体有可能一次也不执行，而repeat语句至少执行一次；

前者是当条件满足时执行，而后者是当条件不满足时执行；

前者的循环体是复合语句时要用begin、end，而后者却不一定要用。

三、for语句与计数循环

1．格式：

（1）for 变量标识符：=初值表达式 to终值表达式 do 语句；

 从小到大执行的格式

（2）for 变量标识符：=初值表达式 downto终值表达式 do 语句；

 从大到小执行的格式

2．说明

格式中的for,to,downto,do都是保留字，to一般用在升序的计数，而downto用在降序的计数。变量标识符在这里称作是控制变量，必须是离散（有序）数据类型，如：

for i:=1 to 100  do ….

for ch:=’a’  to  ‘z’  do….

3．示例

上面的例子用for语句写出的程序段为：

for i:=1 to 100 do wirteln(‘Square root of ‘ ,i,’ is’, sqrt(i):8:4);

也可以写成：

for i:=100 downto 1 do

 wirteln(‘Square root of ‘ ,101-i,’ is’, sqrt(101-i):8:4);

for语句的形式简单，但它也有一定的局限性，主要是控制变量的值不能随意变化，每次只能取其后继(用to的情况)或前趋（用downto的情况），另一限制是控制变量只能用简单的有序的离散量，且循环次数已定，不能象while或repeat那样通过布尔表达式来控制循环的操作。

例5-2：用for 语句计算前N（N>1）个自然数中所有偶数的和。

【分析】：

判定偶数可有多种方法，也可以不用判定而直接去构造偶数，由此得到更多的方法。

【方法1】：

构造偶数，1到n之间的偶数有 N  DIV 2个，所以从第一个构造到最后一个偶数，并将它加到存储和的变量中。

sum:=0;

for counter:=1 to n div 2 do

 sum:=sum+2*counter;

【方法2】：

    对1到n中任一个自然数进行检测，如果它除以2的余数为0表明它是偶数，则将其加到和中。

 for counter:=1 to n do

 if counter mod 2=0 then sum:=sum+counter;

【方法3】：

用标准函数odd(x)，判定是否是奇数，如果不是奇数说明它是偶数。

for counter:=1 to n do

if not odd(counter) then sum:=sum+counter;

【方法4】：

   在方法1中是构造偶数相加，也可以先相加，再考虑偶数的情况，如10以内的偶数为2、4、6、8、10，将它们标明序号为1、2、3、4、5，序号为原数的一半，因此只要求出序号的和，再将序号的和乘以2便得到偶数的和。

 For counter:=1 to n div 2 do sum:=sum+counter;

 Counter:=counter*2;

注意：一般情况下不允许在for语句的循环体中改变控制变量的值。

四．多重循环（循环的嵌套）

当程序中要用到多个循环时，如果这些循环是并列的关系，那么它们彼此之间的控制变量不相互影响。

而当一个循环的循环体中又有循环时，这就是循环的嵌套，称为多重循环。如前面要大家输入的“输出九九乘法表”程序。

例5-3：编写程序输出如下的字母塔：

    A

             ABA

            ABCBA

…………….

ABCD……DCBA

【分析】：

此题有两个关键：一是确定每一行前导空格符的数目；二是按一定规律输出英文大写字母，共26行。应能保证最后一行前导空格数目至少为0，设最后一行的前面空格数为10个，那么倒数第二行前面的空格数为11，倒数第三行的数目为12……，如果控制输出行的字符变量为c，则空格数为：ord(‘Z’)-ord(c)+10

【程序清单】：

program eg5-3;

var ch,c:char;

begin

for c:=’A’ to ‘Z’ do

 begin

  write(‘ ‘:ord(‘Z’)-ord(c)+10);   {输出空格数}

  for ch:=’A’ to c do write(ch);    {输出一行的左半部分}

  for ch:=pred(c) downto ‘A’ do write(ch);   {输出一行的右半部分}

  writeln;               {换行}

 end;

end.

【思考与提高】：

上面整个程序是个两重循环，而外循环的循环体是两个并列的循环，因此虽然程序中有三个for语句，但只是两重循环。

而程序中输出一行时是通过两个循环来实现的，能不能通过一个循环来实现呢？用字符型变量来控制循环不太方便，可以用整型变量来控制循环列方便一些，相应的程序段如下：

for I:=1 to 26 do

 begin

 write(‘’:36-I);

 for j:=1-I to I-1 do write(chr(64+I-abs(j)));

 writeln;

end;