Pascal基础算法教案.doc

WORD格式可编辑 专业知识分享 基础算法教案 目录 TOC \o 1-1 \h \z \u HYPERLINK \l _To第一课 算法简介 PAGEREF _To\h 1 HYPERLINK \l _To第二课 多精度数值处理 PAGEREF _To\h 1 HYPERLINK \l _To第三课 排列与组合 PAGEREF _To\h 6 HYPERLINK \l _To第四课 枚举法 PAGEREF _To\h 9 HYPERLINK \l _To第五课 递归与回溯法 PAGEREF _To\h 25 HYPERLINK \l _To第六课 递推法 PAGEREF _To\h 42 HYPERLINK \l _To第七课 贪心法 PAGEREF _To\h 50 HYPERLINK \l _To第八课 分治法 PAGEREF _To\h 64 HYPERLINK \l _To第九课 模拟法 PAGEREF _To\h 70 HYPERLINK \l _To习题 PAGEREF _To\h 79 第一课 算法简介 算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。 计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征： 有穷性：一个算法必须能在执行有限步之后结束； 确切性：算法的每一步骤必须确切定义； 输入：一个算法有零个或多个输入，以描述运算对象的初始情况。所谓0个输入是指算法本身给出了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫无意义的； 可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。 为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法设计思路。下面，我们就对构成算法所依据的一些基本方法展开讨论，如递推法，递归法，枚举法，分治法，模拟法，贪心法等。 第二课 多精度数值处理 课题：多精度数值的处理 目标： 知识目标：多精度值的加、减、乘、除 能力目标：多精度值的处理，优化！ 重点：多精度的加、减、乘 难点：进位与借位处理 板书示意： 输入两个正整数，求它们的和 输入两个正整数，求它们的差 输入两个正整数，求它们的积 输入两个正整数，求它们的商 授课过程： 所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行。看看下面的例子。 例1 从键盘读入两个正整数，求它们的和。 分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。 这样，我们方便写出两个整数相加的算法。 8 5 6 + 2 5 5 1 1 1 1 图1 A3 A2 8 5 6 + 2 5 5 1 1 1 1 图1 A3 A2 A1 + B3 B2 B1 C4 C3 C2 C1 图2 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]; if C[i]10 then begin C[i]:= C[i] mod 10; C[i+1]:= C[i+1]+1 end; 因此，算法描述如下： procedure add(a,b;var c); { a,b,c都为数组，a存储被加数，b存储加数，c存储结果 } var i,x:integer; begin i:=1 while (i=a数组长度0) or(i=b数组的长度) do begin x := a[i] + b