基础算法教案Word下载.docx
《基础算法教案Word下载.docx》由会员分享，可在线阅读，更多相关《基础算法教案Word下载.docx（100页珍藏版）》请在冰点文库上搜索。
4）输入两个正整数，求它们的商
授课过程：
所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行。
看看下面的例子。
例1从键盘读入两个正整数，求它们的和。
分析：
从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。
但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。
而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。
在读小学时，我们做加法都采用竖式方法，如图1。
这样，我们方便写出两个整数相加的算法。
如果我们用数组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;
begin
i:
=1
while（i<
=a数组长度>
0）or（i<
=b数组的长度）dobegin
x:
=a[i]+b[i]+xdiv10;
{第i位相加并加上次的进位}
c[i]:
=xmod10;
{存储第i位的值}
i:
=i+1{位置指针变量}
end
end;
通常，读入的两个整数用可用字符串来存储，程序设计如下：
programexam1;
const
max=200;
var
a,b,c:
array[1..max]of0..9;
n:
string;
lena,lenb,lenc,i,x:
write（'
Inputaugend:
'
）;
readln（n）;
lena:
=length（n）;
{加数放入a数组}
fori:
=1tolenadoa[lena-i+1]:
=ord（n[i]）-ord（'
0'
Inputaddend:
lenb:
{被加数放入b数组}
=1tolenbdob[lenb-i+1]:
=1;
=lena）or（i<
=lenb）dobegin
x:
{两数相加，然后加前次进位}
c[i]:
{保存第i位的值}
i:
=i+1
end;
ifx>
=10then{处理最高进位}
beginlenc:
=i;
c[i]:
=1end
elselenc:
=i-1;
=lencdownto1dowrite（c[i]）;
{输出结果}
writeln
end.
例2高精度减法。
从键盘读入两个正整数，求它们的差。
分析：
类似加法，可以用竖式求减法。
在做减法运算时，需要注意的是：
被减数必须比减数大，同时需要处理借位。
因此，可以写出如下关系式
ifa[i]<
b[i]thenbegina[i+1]:
=a[i+1]-1;
a[i]:
=a[i]+10end
=a[i]-b[i]
类似，高精度减法的参考程序：
programexam2;
n,n1,n2:
Inputminuend:
readln（n1）;
Inputsubtrahend:
readln（n2）;
{处理被减数和减数}
if（length（n1）<
length（n2））or（length（n1）=length（n2））and（n1<
n2）then
begin
n:
=n1;
n1:
=n2;
n2:
=n;
-'
）{n1<
n2,结果为负数}
=length（n1）;
=length（n2）;
=ord（n1[i]）-ord（'
=ord（n2[i]）-ord（'
=a[i]-b[i]+10+x;
{不考虑大小问题，先往高位借10}
=xmod10;
=xdiv10-1;
{将高位借掉的1减去}
lenc:
while（c[lenc]=0）and（lenc>
1）dodec（lenc）;
{最高位的0不输出}
例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]:
类似，高精度乘法的参考程序：
programexam3;
const
max=200;
var
n1,n2:
lena,lenb,lenc,i,j,x:
Inputmultiplier:
Inputmultiplicand:
=1tolenadobegin
x:
=0;
forj:
=1tolenbdobegin{对乘数的每一位进行处理}
=a[i]*b[j]+xdiv10+c[i+j-1];
{当前乘积+上次乘积进位+原数}
c[i+j-1]:
c[i+j]:
=xdiv10;
{进位}
=i+j;
例４高精度除法。
从键盘读入两个正整数，求它们的商（做整除）。
做除法时，每一次上商的值都在０～９，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。
因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。
当然，为了程序简洁，可以避免高精度乘法，用0～9次循环减法取代得到商的值。
这里，我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法。
参考程序：
programexam4;
a,c:
x,b:
longint;
code,i,j:
Inputdividend:
Inputdivisor:
=1tolenadoa[i]:
=ord（n1[i]）-ord（'
val（n2,b,code）;
{按位相除}
=1tolenadobegin
c[i]:
=（x*10+a[i]）divb;
=（x*10+a[i]）modb;
{显示商}
j:
while（c[j]=0）and（j<
lena）doinc（j）;
{去除高位的0}
=jtolenadowrite（c[i]）;
实质上，在做两个高精度运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数。
例如图5就是采用4位保存的除法运算，其他运算也类似。
具体程序可以修改上述例题予以解决，程序请读者完成。
示例：
123456789÷
45=1’2345’6789÷
45
=274’3484
∵1div45=0，1mod45=1
∴取12345div45=274∵12345mod45=15
∴取156789div45=3484
∴答案为2743484,余数为156789mod45=9
图5
第三课排列与组合
排列与组合
如何利用程序就各种排列和组合
排列组合的运用
求出n的全排列和从m中取n个的组合
算法的理解
1）求全排列的算法
2）求组合数的算法
例5：
有3个人排成一个队列，问有多少种排对的方法，输出每一种方案？
如果我们将3个人进行编号，分别为1、2、3，显然我们列出所有的排列，123，132，213，231，312，321共六种。
可用循环枚举各种情况，参考程序：
programexam5;
i,j,k:
begin
forI:
=1to3do
forj:
fork:
if（i+j+k=6）and（i*j*k=6）thenwriteln（i,j,k）;
上述情况非常简单，因为只有3个人，但当有N个人时怎么办？
显然用循环不能解决问题。
下面我们介绍一种求全排列的方法。
设当前排列为P1P2,…,Pn，则下一个排列可按如下算法完成：
1．求满足关系式Pj-1<
Pj的J的最大值，设为I，即
I=max{j|Pj-1<
Pj,j=2..n}
2．求满足关系式Pi-1<
Pk的k的最大值，设为j，即
J=max{K|Pi-1<
Pk,k=1..n}
3．Pi-1与Pj互换得（P）=P1P2,…,Pn
4．（P）=P1P2,…,Pi-1Pi,…,Pn部分的顺序逆转，得P1P2,…,Pi-1PnPn-1,…,Pi便是下一个排列。
例：
设P1P2P3P4=3421
1．I=max{j|Pj-1<
Pj,j=2..n}=2
2．J=max{K|Pi-1<
Pk,k=1..n}=2
3．P1与P2交换得到4321
4．4321的321部分逆转得到4123即是3421的下一个排列。
程序设计如下：
maxn=100;
vari,j,m,t:
integer;
p:
array[1..maxn]ofinteger;
count:
{排列数目统计变量}
m:
readln（m）;
=1tomdobeginp[i]:
write（i）end;
writeln;
count:
repeat
{求满足关系式Pj-1<
Pj的J的最大值，设为I}
=m;
while（i>
1）and（p[i-1]>
=p[i]）dodec（i）;
ifi=1thenbreak;
{求满足关系式Pi-1<
Pk的k的最大值，设为j}
while（j>
0）and（p[i-1]>
=p[j]）dodec（j）;
ifj=0thenbreak;
{Pi-1与Pj互换得（P）=P1P2,…,Pm}
t:
=p[i-1];
p[i-1]:
=p[j];
p[j]:
=t;
{Pi,…,Pm的顺序逆转}
=1to（m-i+1）div2dobegin
=p[i+j-1];
p[i+j-1]:
=p[m-j+1];
p[m-j+1]:
=t
{打印当前解}
=1tomdowrite（p[i]）;
inc（count）;
untilfalse;
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表示，且假定C1<
C2<
…<
CR,CR<
=N-R+I,I=1,2,…,R。
2．当存在Cj<
N-R+J时，其中下标的最大者设为I，即
I=max{J|Cj<
N-R+J}，则作Ci:
=Ci+1,与之对应的操作有
Ci+1:
=Ci+1，Ci+2:
=Ci+1+1，….，CR:
=CR-1+1
参考程序：
programexam6;
constmaxn=10;
vari,j,n,m:
c:
array[1..maxn]ofinteger;
{c数组记录当前组合}
Begin
Write（'
n&
m:
readln（n,m）;
=1tomdobegin{初始化，建立第一个组合}
write（c[i]）;
whilec[1]<
n-m+1dobegin
while（c[j]>
n-m+1）and（j>
0）dodec（j）;
{求I=max{J|Cj<
N-R+J}}
c[j]:
=c[j]+1;
=j+1tomdoc[i]:
=c[i-1]+1;
{建立下一个组合}
=1tomdowrite（c[i]）;
writeln{输出}
End.
第四课枚举法
枚举法
枚举算法的本质和应用
枚举算法的应用！
利用枚举算法解决实际问题
枚举算法的次数确定
1）简单枚举（例7、例8、例9）
2）利用枚举解决逻辑判断问题（例10、例11）
3）枚举解决竞赛问题（例12、例13、例14）
所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。
一般思路：
●对命题建立正确的数学模型；
●根据命题确定的数学模型中各变量的变化范围（即可能解的范围）；
●利用循环语句、条件判断语句逐步求解或证明；
枚举法的特点是算法简单，但有时运算量大。
对于可能确定解的值域又一时找不到其他更好的算法时可以采用枚举法。
例7：
求满足表达式A+B=C的所有整数解，其中A，B，C为1~3之间的整数。
本题非常简单，即枚举所有情况，符合表达式即可。
算法如下：
forA:
=1to3do
forB:
forC:
ifA+B=Cthen
Writeln（A,‘+’,B,‘=’,C）;
上例采用的就是枚举法。
所谓枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。
能使命题成立的，即为解。
从枚举法的定义可以看出，枚举法本质上属于搜索。
但与隐式图的搜索有所区别，在采用枚举法求解的问题时，必须满足两个条件：
1预先确定解的个数n；
2对每个解变量A1，A2，……，An的取值，其变化范围需预先确定
A1∈{X11，……，X1p}
……
Ai∈{Xi1，……，Xiq}
An∈{Xn1，……，Xnk}
例7中的解变量有3个：
A，B，C。
其中
A解变量值的可能取值范围A∈{1，2，3}
B解变量值的可能取值范围B∈{1，2，3}
C解变量值的可能取值范围C∈{1，2，3}
则问题的可能解有27个
（A，B，C）∈{（1，1，1），（1，1，2），（1，1，3），
（1，2，1），（1，2，2），（1，2，3），
………………………………
（3，3，1），（3，3，2），（3，3，3）}
在上述可能解集合中，满足题目给定的检验条件的解元素，即为问题的解。
如果我们无法预先确定解的个数或各解的值域，则不能用枚举，只能采用搜索等算法求解。
由于回溯法在搜索每个可能解的枚举次数一般不止一次，因此，对于同样规模的问题，回溯算法要比枚举法时间复杂度稍高。
例8给定一个二元一次方程aX+bY=c。
从键盘输入a,b,c的数值，求X在[0，100]，Y在[0，100]范围内的所有整数解。
要求方程的在一个范围内的解，只要对这个范围内的所有整数点进行枚举，看这些点是否满足方程即可。
programexam8;
x,y:
Inputa,b,c:
readln（a,b,c）;
forx:
=0to100do
fory:
ifa*x+b*y=cthenwriteln（x,'
'
y）;
从上例可以看出，所谓枚举法,指的是从可能的解集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的.能使命题成立,即为其解。
例9巧妙填数
1
9
2
3
8
4
5
7
6
将1～9这九个数字填入九个空格中。
每一横行的三个数字组成一个三位数。
如果要使第二行的三位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数。
如图6:
图6
本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！
=362880种方案，在这些方案中符合问题条件的即为解。
因此可以采用枚举法。
但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。
这样仅需枚举400次。
因此设计参考程序：
programexam9;
i,j,k,s:
functionsum（s:
integer）:
sum:
=sdiv100+sdiv10mod10+smod10
functionmul（s:
mul:
=（sdiv100）*（sdiv10mod10）*（smod10）
=1to3do
=1to9do
ifj<
>
ithenfork:
if（k<
j）and（k<
i）thenbegin
s:
=i*100+j*10+k;
{求第一行数}
if3*s<
1000then
if（sum（s）+sum（2*s）+sum（3*s）=45）and
（mul（s）*mul（2*s）*mul（3*s）=362880）then{满足条件，并数字都由1~9组成}
writeln（s）;
writeln（2*s
升级会员 