基础算法教案.doc

基础算法教案 目录

第一课 算法简介...........................................................................................................................................................1

第二课 多精度数值处理...............................................................................................................................................1

第三课 排列与组合.......................................................................................................................................................6

第四课 枚举法...............................................................................................................................................................9

第五课 递归与回溯法.................................................................................................................................................26

第六课 递推法.............................................................................................................................................................43

第七课 贪心法.............................................................................................................................................................51

计算机解题的过程。在这个过程中，无论是形成解题思路还是编写算法，都是在实施某种算法。前者

是推理实现的算法，后者是操作实现的算法。

计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征：

1 有穷性：一个算法必须能在执行有限步之后结束；

2 确切性：算法的每一步骤必须确切定义；

3 输入：一个算法有零个或多个输入，以描述运算对象的初始情况。所谓 0 个输入是指算法本

身给出了初始条件；

4 输出：一个算法有一个或多个输出，以反映对输入数据处理后的结果。没有输出的算法是毫

无意义的；

5 可行性：算法原则上能够精确的运行，而且其运算规模是可以承受的。

能力目标：多精度值的处理，优化！

重点：多精度的加、减、乘

难点：进位与借位处理

板书示意：

1）输入两个正整数，求它们的和

2）输入两个正整数，求它们的差

3）输入两个正整数，求它们的积

4）输入两个正整数，求它们的商

授课过程：

所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要

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

通常，读入的两个整数用可用字符串来存储，程序设计如下：

program exam1;

const

max=200;

var

a,b,c:array[1..max] of 0..9;

n:string;

lena,lenb,lenc,i,x:integer;

begin

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

i:=1;

while (i<=lena) or(i<=lenb) do begin

x := a[i] + b[i] + x div 10; {两数相加，然后加前次进位}

for i:=lenc downto 1 do write(c[i]); {输出结果}

writeln

end.

例 2 高精度减法。

从键盘读入两个正整数，求它们的差。

分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，

同时需要处理借位。

因此，可以写出如下关系式

if a[i]<b[i] then begin a[i+1]:=a[i+1]-1;a[i]:=a[i]+10 end

c[i]:=a[i]-b[i]

program exam2;

var

a,b,c:array[1..max] of 0..9;

n,n1,n2:string;

lena,lenb,lenc,i,x:integer;

begin

write('Input minuend:'); readln(n1);

write('Input subtrahend:'); readln(n2);

{处理被减数和减数}

if (length(n1)<length(n2)) or (length(n1)=length(n2)) and (n1<n2) then

begin

n:=n1;n1:=n2;n2:=n;

for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');

i:=1;

writeln

end.

例 3 高精度乘法。

从键盘读入两个正整数，求它们的积。

分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进乘法运

算时，必须进行错位相加，如图 3, 图 4。

分析 C 数组下标的变化规律，可以写出如下关系式

C

+C

+…

由此可见，C

跟 A[i]*B[j]乘积有关，跟上次的进位有关，还跟原 C

的值有关，分析下标规律，有

x:= A[i]*B[j]+ x DIV 10+ C[i+j-1];

C[i+j-1] := x mod 10;

类似，高精度乘法的参考程序：

program exam3;

const