基础算法教案

基础算法教案 目录第一课 算法简介 .1第二课 多精 度数值处理 .1第三课 排列与 组合 .6第四课 枚 举法 .9第五课 递归与回 溯法 .25第六课 递 推法 .42第七课 贪心法 .50第八课 分 治法 .64第九课 模 拟法 .70习 题 .79第一课 算法简介算法是一组（有限个）规则，它为某个特定问题提供了解决问题的运算序列。在信息学竞赛中，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征： 有穷性：一个算法必须能在执行有限步之后结束； 确切性：算法的每一步骤必须确切定义； 输入：一个算法有零个或多个输入，以描述运算对象的初始情况。所谓 0 个输入是指算法本身给出了初始条件； 输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫无意义的； 可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。为了获得一个既有效又优美的算法，必须首先了解一些基本的常用算法设计思路。下面，我们就对构成算法所依据的一些基本方法展开讨论，如递推法，递归法，枚举法，分治法，模拟法，贪心法等。第二课 多精度数值处理课题：多精度数值的处理目标：知识目标：多精度值的加、减、乘、除能力目标：多精度值的处理，优化！重点：多精度的加、减、乘难点：进位与借位处理板书示意：1） 输入两个正整数，求它们的和2） 输入两个正整数，求它们的差3） 输入两个正整数，求它们的积4） 输入两个正整数，求它们的商授课过程：所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算） ，而需要采用特殊的处理办法进行。看看下面的例子。例 1 从键盘读入两个正整数，求它们的和。分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在 pascal 语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图 1。这样，我们方便写出两个整数相加的算法。如果我们用数组 A、B 分别存储加数和被加数，用数组 C 存储结果。则上例有A1=6, A2=5, A3=8, B1=5,B2=5, B3=2, C4=1,C3=1, C2=1,C1=1,两数相加如图 2 所示。由上图可以看出：Ci:= Ai+Bi;if Ci10 then begin Ci:= Ci mod 10; Ci+1:= Ci+1+1 end;因此，算法描述如下：procedure add(a,b;var c); a,b,c 都为数组，a 存储被加数，b 存储加数，c 存储结果 var i,x:integer;begini:=1while (i0) or(i=10 then 处理最高进位begin lenc:=i;ci:=1 end else lenc:=i-1;for i:=lenc downto 1 do write(ci); 输出结果writelnend.例 2 高精度减法。从键盘读入两个正整数，求它们的差。分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。因此，可以写出如下关系式if ai1) do dec(lenc); 最高位的 0 不输出for i:=lenc downto 1 do write(ci);writelnend.例 3 高精度乘法。从键盘读入两个正整数，求它们的积。分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进乘法运算时，必须进行错位相加，如图 3, 图 4。分析 C 数组下标的变化规律，可以写出如下关系式C i = C i +C ”i +由此可见，C i跟 Ai*Bj乘积有关，跟上次的进位有关，还跟原 C i的值有关，分析下标规律，有x:= Ai*Bj+ x DIV 10+ Ci+j-1;Ci+j-1 := x mod 10; 类似，高精度乘法的参考程序：program exam3;constmax=200;vara,b,c:array1.max of 0.9;n1,n2:string;lena,lenb,lenc,i,j,x:integer;8 5 6 2 5 4 2 8 01 7 1 2 2 1 4 0 0图 3A 3 A 2 A 1 B 3 B 2 B 1 C4C3 C2 C1 C”5C”4C”3C”2 C 6 C 5 C 4 C 3 C 2 C 1图 4beginwrite(Input multiplier:); readln(n1);write(Input multiplicand:); readln(n2);lena:=length(n1); lenb:=length(n2);for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0);for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0);for i:=1 to lena do begin x:=0; for j:=1 to lenb do begin 对乘数的每一位进行处理x := ai*bj + x div 10 + ci+j-1; 当前乘积+上次乘积进位+原数 ci+j-1 := x mod 10;end;ci+j:= x div 10; 进位end;lenc:=i+j;while (clenc=0) and (lenc1) do dec(lenc);for i:=lenc downto 1 do write(ci);writelnend.例 高精度除法。从键盘读入两个正整数，求它们的商（做整除） 。分析：做除法时，每一次上商的值都在，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高精度乘法，用 09 次循环减法取代得到商的值。这里，我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法。参考程序：program exam4;constmax=200;vara,c:array1.max of 0.9;x,b:longint;n1,n2:string;lena:integer;code,i,j:integer;beginwrite(Input dividend:); readln(n1);write(Input divisor:); readln(n2);lena:=length(n1);for i:=1 to lena do ai := ord(n1i) - ord(0);val(n2,b,code);按位相除x:=0;for i:=1 to lena do beginci:=(x*10+ai) div b;x:=(x*10+ai) mod b;end;显示商j:=1;while (cj=0) and (j1) and (pi-1=pi) do dec(i);if i=1 then break;求满足关系式 Pi -1 0) and (pi-1=pj) do dec(j);if j=0 then break;Pi -1与 Pj互换得 (P) = P 1 P2 ,Pmt:=pi-1;pi-1:=pj;pj:=t;Pi, Pm的顺序逆转for j:=1 to (m-i+1) div 2 do begint:=pi+j-1;pi+j-1:=pm-j+1;pm-j+1:=tend;打印当前解for i:=1 to m do write(pi);inc(count);writeln;until false;writeln(count)End.例 6：求 N 个人选取 M 个人出来做游戏，共有多少种取法？例如：N=4，M=2 时，有12，13，14，23，24，34 共六种。分析：因为组合数跟顺序的选择无关。因此对同一个组合的不同排列，只需取其最小的一个（即按从小到大排序） 。因此，可以设计如下算法：1最后一位数最大可达 N，倒数第二位数最大可达 N-1，依此类推，倒数第 K 位数最大可达N-K+1。若 R 个元素组合用 C1C2 CR表示，且假定 C1n-m+1) and ( j0) do dec(j); 求 I=maxJ | CjN-R+J cj:=cj+1;for i:=j+1 to m do ci:=ci-1+1; 建立下一个组合for i:=1 to m do write(ci);writeln 输出end;End.第四课 枚举法课题：枚举法目标：知识目标：枚举算法的本质和应用能力目标：枚举算法的应用！重点：利用枚举算法解决实际问题难点：枚举算法的次数确定板书