Pascal基础算法教案

基础算法教案第0页共81页基础算法教案目录第一课算法简介................................................................................................................................................1第二课多精度数值处理....................................................................................................................................1第三课排列与组合............................................................................................................................................6第四课枚举法....................................................................................................................................................9第五课递归与回溯法......................................................................................................................................25第六课递推法..................................................................................................................................................42第七课贪心法..................................................................................................................................................50第八课分治法..................................................................................................................................................64第九课模拟法..................................................................................................................................................70习题....................................................................................................................................................................79基础算法教案第1页共81页第一课算法简介算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征：①有穷性：一个算法必须能在执行有限步之后结束；②确切性：算法的每一步骤必须确切定义；③输入：一个算法有零个或多个输入，以描述运算对象的初始情况。所谓0个输入是指算法本身给出了初始条件；④输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫无意义的；⑤可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法设计思路。下面，我们就对构成算法所依据的一些基本方法展开讨论，如递推法，递归法，枚举法，分治法，模拟法，贪心法等。第二课多精度数值处理课题：多精度数值的处理目标：知识目标：多精度值的加、减、乘、除能力目标：多精度值的处理，优化！重点：多精度的加、减、乘难点：进位与借位处理板书示意：1）输入两个正整数，求它们的和2）输入两个正整数，求它们的差3）输入两个正整数，求它们的积4）输入两个正整数，求它们的商授课过程：所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行。看看下面的例子。例1从键盘读入两个正整数，求它们的和。分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。这样，我们方便写出两个整数相加的算法。基础算法教案第2页共81页如果我们用数组A、B分别存储加数和被加数，用数组C存储结果。则上例有A[1]=6,A[2]=5,A[3]=8,B[1]=5,B[2]=5,B[3]=2,C[4]=1,C[3]=1,C[2]=1,C[1]=1,两数相加如图2所示。由上图可以看出：C[i]:=A[i]+B[i];ifC[i]10thenbeginC[i]:=C[i]mod10;C[i+1]:=C[i+1]+1end;因此，算法描述如下：procedureadd(a,b;varc);{a,b,c都为数组，a存储被加数，b存储加数，c存储结果}vari,x:integer;begini:=1while(i=a数组长度0)or(i=b数组的长度)dobeginx:=a[i]+b[i]+xdiv10;{第i位相加并加上次的进位}c[i]:=xmod10;{存储第i位的值}i:=i+1{位置指针变量}endend;通常，读入的两个整数用可用字符串来存储，程序设计如下：programexam1;constmax=200;vara,b,c:array[1..max]of0..9;n:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputaugend:');readln(n);lena:=length(n);{加数放入a数组}fori:=1tolenadoa[lena-i+1]:=ord(n[i])-ord('0');write('Inputaddend:');readln(n);lenb:=length(n);{被加数放入b数组}fori:=1tolenbdob[lenb-i+1]:=ord(n[i])-ord('0');i:=1;while(i=lena)or(i=lenb)dobegin856+2551111图1A3A2A1+B3B2B1C4C3C2C1图2基础算法教案第3页共81页x:=a[i]+b[i]+xdiv10;{两数相加，然后加前次进位}c[i]:=xmod10;{保存第i位的值}i:=i+1end;ifx=10then{处理最高进位}beginlenc:=i;c[i]:=1endelselenc:=i-1;fori:=lencdownto1dowrite(c[i]);{输出结果}writelnend.例2高精度减法。从键盘读入两个正整数，求它们的差。分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。因此，可以写出如下关系式ifa[i]b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10endc[i]:=a[i]-b[i]类似，高精度减法的参考程序：programexam2;constmax=200;vara,b,c:array[1..max]of0..9;n,n1,n2:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputminuend:');readln(n1);write('Inputsubtrahend:');readln(n2);{处理被减数和减数}if(length(n1)length(n2))or(length(n1)=length(n2))and(n1n2)thenbeginn:=n1;n1:=n2;n2:=n;write('-'){n1n2,结果为负数}end;lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');i:=1;基础算法教案第4页共81页while(i=lena)or(i=lenb)dobeginx:=a[i]-b[i]+10+x;{不考虑大小问题，先往高位借10}c[i]:=xmod10;{保存第i位的值}x:=xdiv10-1;{将高位借掉的1减去}i:=i+1end;lenc:=i;while(c[lenc]=0)and(lenc1)dodec(lenc);{最高位的0不输出}fori:=lencdownto1dowrite(c[i]);writelnend.例3高精度乘法。从键盘读入两个正整数，求它们的积。分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进乘法运算时，必须进行错位相加，如图3,图4。分析C数组下标的变化规律，可以写出如下关系式Ci=C’i+C”i+…由此可见，Ci跟A[i]*B[j]乘积有关，跟上次的进位有关，还跟原Ci的值有关，分析下标规律，有x:=A[i]*B[j]+xDIV10+C[i+j-1];C[i+j-1]:=xmod10;类似，高精度乘法的参考程序：programexam3;constmax=200;vara,b,c:array[1..max]of0..9;n1,n2:string;lena,lenb,lenc,i,j,x:integer;beginwrite('Inputmultiplier:');readln(n1);856×254280171221400图3A3A2A1×B3B2B1C’4C’3C’2C’1C”5C”4C”3C”2C6C5C4C3C2C1图4基础算法教案第5页共81页write('Inputmultiplicand:');readln(n2);lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');fori:=1tolenadobeginx:=0;forj:=1tolenbdobegin{对乘数的每一位进行处理}x:=a[i]*b[j]+xdiv10+c[i+j-1];{当前乘积+上次乘积进位+原数}c[i+j-1]:=xmod10;end;c[i+j]:=xdiv10;{进位}end;lenc:=i+j;while(c[lenc]=0)and(lenc1)dod