信息学奥赛基础算法教案.doc

《信息学奥赛基础算法教案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基础算法教案目录第一课算法简介1第二课多精度数值处理1第三课排列与组合6第四课枚举法9第五课递归与回溯法25第六课递推法42第七课贪心法50第八课分治法64第九课模拟法70习题79基础算法教案第80页共81页第一课算法简介算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征：①有穷性：一个算法必须能在执行有限步之后结束；②确切性：算法的每一步骤必须确切定义；③

2、输入：一个算法有零个或多个输入，以描述运算对象的初始情况。所谓0个输入是指算法本身给出了初始条件；④输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫无意义的；⑤可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法设计思路。下面，我们就对构成算法所依据的一些基本方法展开讨论，如递推法，递归法，枚举法，分治法，模拟法，贪心法等。第二课多精度数值处理课题：多精度数值的处理目标：知识目标：多精度值的加、减、乘、除能力目标：多精度值的处理，优化！重点：多精度的加、减、乘难点：进位与借位处

3、理板书示意：1）输入两个正整数，求它们的和2）输入两个正整数，求它们的差3）输入两个正整数，求它们的积4）输入两个正整数，求它们的商授课过程：所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行。看看下面的例子。例1从键盘读入两个正整数，求它们的和。分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，

4、如图1。这样，我们方便写出两个整数相加的算法。基础算法教案第80页共81页856+2551111图1A3A2A1+B3B2B1C4C3C2C1图2如果我们用数组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;v

5、arc);{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;be

6、ginwrite('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)dobegin基础算法教案第80页共81页x:=a[i]+b[i]+xdiv10;{两数相加，然后加前

7、次进位}c[i]:=xmod10;{保存第i位的值}i:=i+1end;ifx>=10then{处理最高进位}beginlenc:=i;c[i]:=1endelselenc:=i-1;fori:=lencdownto1dowrite(c[i]);{输出结果}writelnend.例2高精度减法。从键盘读入两个正整数，求它们的差。分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。因此，可以写出如下关系式ifa[i]