算法大全.docx
- 文档编号:16407820
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:81
- 大小:67.40KB
算法大全.docx
《算法大全.docx》由会员分享,可在线阅读,更多相关《算法大全.docx(81页珍藏版)》请在冰点文库上搜索。
算法大全
算法详解及练习题
目录
第一讲穷举法------------------------------1
第二讲字符与字符串处理--------------------16
第三讲不同进制转换------------------------25
第四讲高精度计算--------------------------26
第五讲数据排序----------------------------30
第六讲约瑟夫问题(纸牌问题)---------------34
第七讲矩阵(递推问题)---------------------40
第八讲排列组合----------------------------43
第九讲贪心算法----------------------------47
第十讲递归算法----------------------------56
第一讲穷举法
一、穷举法的基本概念
穷举方法是基于计算机特点而进行解题的思维方法。
一般是在一时找不出解决问题的更好途径(即从数学上找不到求解的公式或规则)时,可以根据问题中的的部分条件(约束条件)将所有可能解的情况列举出来,然后通过一一验证是否符合整个问题的求解要求,而得到问题的解。
这样解决问题的方法我们称之为穷举算法。
穷举算法特点是算法简单,但运行时所花费的时间量大。
有些问题所列举出来的情况数目会大得惊人,就是用高速的电子计算机运行,其等待运行结果的时间也将使人无法忍受。
因此,我们在用穷举方法解决问题时,应尽可能将明显的不符合条件的情况排除在外,以尽快取得问题的解。
二、算法模式
问题解的可能搜索的范围:
用循环或循环嵌套结构实现,写出符合问题解的条件。
能使程序优化的语句,以便缩小搜索范围,减少程序运行时间。
三、使用穷举法设计算法
例1:
百钱买百鸡问题:
有一个人有一百块钱,打算买一百只鸡。
到市场一看,大鸡三块钱一只,小鸡一块钱三只,不大不小的鸡两块钱一只。
现在,请你编一程序,帮他计划一下,怎么样买法,才能刚好用一百块钱买一百只鸡?
算法分析:
此题很显然是用枚举法,我们以三种鸡的个数为枚举对象(分别设为x,y,z),以三种鸡的总数(x+y+z)和买鸡用去的钱的总数(x*3+y*2+z)为判定条件,穷举各种鸡的个数。
下面是解这个百鸡问题的程序
varx,y,z:
integer;
begin
forx:
=0to100do
fory:
=0to100do
forz:
=0to100do{枚举所有可能的解}
if(x+y+z=100)and(x*3+y*2+zdiv3=100)and(zmod3=0)thenwriteln('x=',x,'y=',y,'z=',z);{验证可能的解,并输出符合题目要求的解}
end.
上面的条件还有优化的空间,三种鸡的和是固定的,我们只要枚举二种鸡(x,y),第三种鸡就可以根据约束条件求得(z=100-x-y),这样就缩小了枚举范围,请看下面的程序:
varx,y,z:
integer;
begin
forx:
=0to100do
fory:
=0to100-xdo
begin
z:
=100-x-y;
if(x*3+y*2+zdiv3=100)and(zmod3=0)thenwriteln('x=',x,'y=',y,'z=',z);
end;
end.
未经优化的程序循环了1013次,时间复杂度为O(n3);优化后的程序只循环了(102*101/2)次,时间复杂度为O(n2)。
从上面的对比可以看出,对于枚举算法,加强约束条件,缩小枚举的范围,是程序优化的主要考虑方向。
在枚举算法中,枚举对象的选择也是非常重要的,它直接影响着算法的时间复杂度,选择适当的枚举对象可以获得更高的效率。
如下例:
例2、将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:
2:
3的比例,试求出所有满足条件的三个三位数.
例如:
三个三位数192,384,576满足以上条件.(NOIP1998pj)
算法分析:
这是1998年全国分区联赛普及组试题(简称NOIP1998pj,以下同)。
此题数据规模不大,可以进行枚举,如果我们不加思地以每一个数位为枚举对象,一位一位地去枚举:
fora:
=1to9do
forb:
=1to9do
………
fori:
=1to9do
这样下去,枚举次数就有99次,如果我们分别设三个数为x,2x,3x,以x为枚举对象,穷举的范围就减少为93,在细节上再进一步优化,枚举范围就更少了。
程序如下:
var
t,x:
integer;s,st:
string;c:
char;
begin
forx:
=123to329do{枚举所有可能的解}
begin
t:
=0;
str(x,st);{把整数x转化为字符串,存放在st中}
str(x*2,s);st:
=st+s;
str(x*3,s);st:
=st+s;
forc:
='1'to'9'do{枚举9个字符,判断是否都在st中}
ifpos(c,st)<>0theninc(t)elsebreak;{如果不在st中,则退出循环}
ift=9thenwriteln(x,'',x*2,'',x*3);
end;
end.
在枚举法解题中,判定条件的确定也是很重要的,如果约束条件不对或者不全面,就穷举不出正确的结果, 我们再看看下面的例子。
例3:
古希腊人认为因子的和等于它本身的数是一个完全数(自身因子除外),例如28的因子是1、2、4、7、14,且1+2+4+7+14=28,则28是一个完全数,编写一个程序求2~1000内的所有完全数。
分析:
本题是一个搜索问题,搜索范围2~1000,找出该范围内的完全数;完全数必须满足的条件:
因子的和等于该数据的本身。
问题关键在于将该数的因子一一寻找出来,并求出因子的和。
程序如下:
Programp3_1;
Vara,b,s:
integer;
Begin
Fora:
=2to1000do
Begin
s:
=0;
Forb:
=1toa-1do
Ifamodb=0thens:
=s+b;{分解因子并求和}
Ifa=sthenbeginWrite(a,‘=’,1,);{打印a=1}
Forb:
=2toa-1do
Ifamodb=0thenwrite(’+’,b);{打印加法式子}
Writeln;End;
End;
End.
当程序运行后,输出结果:
6=1+2+3
28=1+2+4+7+14
496=1+2+4+8+16+31+62+124+248
例4:
(第七届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题)
在A,B两个城市之间设有N个路站(如下图中的S1,且N<100),城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20,且每条路段上的距离均为一个整数)。
A,B的一条通路是指:
从A出发,可经过任一路段到达S1,再从S1出发经过任一路段,…最后到达B。
通路上路段距离之和称为通路距离(最大距离≤1000)。
当所有的路段距离给出之后,求出所有不同距离的通路个数(相同距离仅记一次)。
例如:
上图所示是当N=1时的情况:
从A到B的通路条数为6,但因其中通路5+5=4+6,所以满足条件的不同距离的通路条数为5。
算法说明:
本题采用穷举算法。
数据结构:
(1)N:
记录A,B间路站的个数;
(2)数组D(I,0)记录第I-1到第I路站间路段的个数;(3)D(I,1),D(I,2),…记录每个路段距离;(4)数组G记录可取到的距离。
PROGRAMCHU7_6;
VARI,J,N,S:
INTEGER;
B:
ARRAY[0..100]OFINTEGER;
D:
ARRAY[0..100,0..20]OFINTEGER;
G:
ARRAY[0..1000]OF0..1;
BEGIN
READLN(N);
FORI:
=1TON+1DO
BEGIN READLN(D[I,0]);
FORJ:
=1TOD[I,0]DO READLN(D[I,J]);
END;
D[0,0]:
=1;
FORI:
=1TON+1DO B[I]:
=1; B[0]:
=0;
FORI:
=0TO1000DO G[I]:
=0;
WHILE ① DO
BEGIN
S:
=0;
FORI:
=1TON+1DO S:
= ②
G[S]:
=1;J:
=N+1;
WHILE ③ DOJ:
=J-1;
B[J]:
=B[J]+1;
FORI:
=J+1TON+1DO B[I]:
=1;
END;
S:
=0;
FORI:
=1TO1000DO ④ ;
WRITELN(S);READLN;
END.
答案:
①B[0]=0 ②S+D[I,B[I]];③B[J]=D[J,0]④S:
=S+G[I]
例5(第八届全国青少年信息学奥林匹克联赛(NOIP2002)试题)
将n个整数分成k组(k≤n,要求每组不能为空),显然这k个部分均可得到一个各自的和s1,s2,……sk,定义整数P为:
P=(S1-S2)2+(S1一S3)2+……+(S1-Sk)2+(s2-s3)2+……+(Sk-1-Sk)2
问题求解:
求出一种分法,使P为最小(若有多种方案仅记一种)
程序说明:
数组:
a[1],a[2],...A[N]存放原数
s[1],s[2],...,s[K]存放每个部分的和
b[1],b[2],...,b[N]穷举用临时空间
d[1],d[2],...,d[N]存放最佳方案
程序:
program exp4;
Var i,j,n,k :
integer;
a :
array [1..100] of integer;
b,d:
array [0..100] of integer;
s :
array[1..30] of integer;
begin
readln(n,k);
for I:
=1 to n do read(a[I]);
for I:
=0 to n do b[I]:
=1;
cmin:
=1000000;
while (b[0]=1) do
begin
for I:
=1 to k do ①
for I:
=1 to n do ②
sum:
=0;
for I:
=1 to k-1 do
for j:
= ③
sum:
=sum+(s[I]-s[j])*(s[I]-s[j]);
if ④ then
begincmin:
=sum;
for I:
=1 to n do d[I]:
=b[I];end;
j:
=n;
while ⑤ do j:
=j-1;
b[j]:
=b[j]+1;
for I:
=j+1 to n do ⑥
end;
writeln(cmin);
for I:
=1 to n do write(d[I]:
40);
writeln;
end.
四、穷举算法的深入应用
实例一:
一根29厘米长的尺子,只允许在上面刻七个刻度,要能用它量出1~29厘米的各种长度。
试问这根尺的刻度应该怎样选择?
分析:
(1)从1~29厘米中选择七个刻度的所有可能情况数是:
C(7,29)=29·28·27·26·25·24·23/1·2·3·4·5·6·7
=29·9·26·5·2·23=29·26·23·90=1560780
(2)对于每一组刻度的选择都需要判断是否能将1~29厘米的各种刻度量出来,例如选择的刻度为:
a1,a2,a3,a4,a5a,6,a7那么能量出的刻度为:
a1,29-a1;2
a2,a2-a1,29-a2;3
a3,a3-a1,a3-a2,29-a3;4
a4,a4-a1,a4-a2,a4-a3,29-a4;5
a5,a5-a1,a5-a2,a5-a3,a5-a4,29-a5;6
a6,a6-a1,a6-a2,a6-a3,a6-a4,a6-a5,29-a6;7
a7-a1,a7-a2,a7-a2,a7-a3,a7-a4,a7-a5,a7-a6,29-a7;8
共可量出2+3+4+5+6+7+8种刻度,即35种刻度,事实上其中有许多刻度是重复的,不可能复盖1~29。
例如:
取a1,a2,a3,a4,a5,a6,a7为1,3,6,10,15,21,28能量出的刻度为:
1,28
3,2,26
6,5,3,23
10,9,7,4,19
15,14,12,9,5,14
21,20,18,15,11,6,8
28,27,25,22,18,13,7,1
缺16,17,24(29即尺子长度)
如果找出了刻度a1,a2,a3,a4,a5,a6,a7那么我们可以利用其对称性29-a1,29-a2,29-a3,29-a4,29-a5,29-a6,29-a7,也是一组解,所以求解过程中可仅考虑a1 很显然要使1,28两种刻度能量出来,则在七个刻度就必须有1或28;这样就可设a1=1(或a1=28)。 本题就变成了只要在2~27中选取六个刻度问题了。 其刻度选择的数目为C(626)=26·25·24·23·22·21=26·5·23·11·7=230230 1·2·3·4·5·6 这样解的范围就从百万变成了十万的数量级,大大减少运行次数。 因此,我们在用穷举法求问题解时,应注意程序的优化,尽可能减少搜索时间。 {程序优化} (3)为了判定七个刻度是否能够度量1~29的所有长度,可以用集合的方法,也可以用数组的0,1数据判断。 下面的程序使用了数组的0,1方法。 Programp12_2; Constn=29;m=1; Vara: array[1..7]ofinteger; b: array[1..n]of0..1;{记录能量的刻度} f: Boolean; I,j: integer; BEGIN a[1]: =m; fora[2]: =2ton-7do fora[3]: =a[2]+1ton-6do fora[4]: =a[3]+1ton-5do fora[5]: =a[4]+1ton-4do fora[6]: =a[5]+1ton-3do fora[7]: =a[6]+1ton-2do begin fori: =1to29dob[i]: =0; fori: =1TO7do begin b[a[i]]: =1;b[n-a[i]]: =1;b[n]: =1;{初始化} forj: =i+1TO7dob[abs(a[j]-a[i])]: =1 end; j: =0; fori;=1tondoj: =j+b[i]; ifj=nthenbegin fori: =1to7dowrite(a[i]: 4); writeln; end; end; end. 运行程序的结果: 当m=1时得出两组刻度 121418212427141017222427 m=28时也可获得两组刻度 2825713192528258111527 这两组刻度实际上是m=1的对称情况,所以问题的解实质上为两组结果。 如果调整n=30可以发现在这样的情况下程序无解,这说明取30cm长的尺子,若仍取七个刻度,要能量出1~30cm的各种长度,是不可能的。 实例二: 邮局发行一套票面有四种不同值的邮票,如果每封信所贴邮票张数不超过三枚,存在整数R,使得用不超过三枚的邮票,可以贴出连续的整数1、2、3,…,R来,找出这四种面值数,使得R值最大。 分析: 本题知道每封信邮票数的范围(<=3),邮票有四种类型,编程找出能使面值最大邮票。 其算法是: (1)面值不同的四种邮票,每封信所贴邮票不超过3张。 (2)用这四种邮票贴出连序的整数,并且使R值最大。 (3)用穷举法,找出所有符合条件的解。 (4)本题用集合的方法统计邮票的面值,提高判重的速度。 设邮票的面值分别为: A,B,C,D,根据题意设: A Programp12_3; vara,b,c,d: integer; x,x0,x1,x2,x3,x4: integer; st1: setof1..100; Functionnumber(a,b,c,d: integer): integer; varn1,n2,n3,n4,sum: integer; begin st1: =[]; forn1: =0to3do{每种邮票所取的张数} forn2: =0to3-n1do forn3: =0to3-n1-n2do forn4: =0to3-n1-n2-n3do begin ifn1+n2+n3+n4<=3then begin sum: =n1*a+n2*b+n3*c+n4*d; {计算信封的邮票面值} st1: =st1+[sum] end; end; sum: =1; whilesuminst1do sum: =sum+1; number: =sum-1; end;{函数结束} BEGIN{main} a: =1;x0: =0; forb: =a+1to3*a+1do forc: =b+1to3*b+1do{每种邮票的可取值的范围} ford: =c+1to3*c+1do begin x: =number(a,b,c,d);{调用函数求每封信的邮票总面值} ifx>x0then begin x0: =x;x1: =a;x2: =b;x3: =c;x4: =d {保存最大面值邮票} write(x1: 5,x2: 5,x3: 5,x4: 5); writeln(‘‘: 10,'x0=',x0); end; end; end. 程序运行后,其输出结果是: 1234x0=12 {解答结果有11组}1235x0=13 ……. 13610x0=23 1478x0=24 实例三: 如图所示的8个格子中放入1~8八个数字,使得相邻的和对角线的数字之差不为1。 编程找出所有放法。 我们先不考虑后一条件,只考虑第一个条件,即把1~8八个数字放入8个格子中。 这是容易做到的,就是8个数字的全排列,共有8! =40320种放法。 然后对这8! 个可行解用后一个条件加以检验,输出符合条件的解。 对于后一个条件中“相邻”的判断,可以建立一个邻接表来解决: i│1234567891011121314 ──┼────────────────────── j1│11122233345567 2│23435646776878 表中表示哪两个格子是相邻的,link[i,1]和link[i,2]是相邻的格子的编号。 全排列的产生,可以用八重循环,也可以用专门的算法,程序留给同学们自己去完成。 利用穷举策略编制的程序,其运算量一般是很大的,因此如何提高算法效率是穷举算法一个很重要的问题。 一般应尽量减少可行解的个数,使得第二步的检验运算量尽可能地少。 例如对于例5-1,如何来优化算法呢? 如果注意到b3和b6两个格子,与它们“相邻”的格子有6个,也就是说,放入这两个格子中的数,必须和6个数不连续,仅可以和一个数是连续的,这样的数只有2个,即1和8。 这样,b1,b3,b6,b8;4个格子中数的放法仅有两种可能: 2、8、1、7和7、1、8、2。 而b2、b4、b5、b7四个格子中的数仅需在3~6四个数中选择。 经过上述优化,可行解仅有: 2×4! =48个,大大减少了计算量。 并且检验是否符合要求,也只需检查(1,2),(1,4),(2,5),(4,7),(5,8),(7,8)这6对数之差就可以了。 按改进的算法编制的PASCAL程序如下: programexampleb; usesCrt: constlink: array[1..6,1..2]ofinteger= ((1,2),(1,4),(2,5),(4,7),(5,8),(7,8)); varb: array[1..8]ofinteger; procedureprint; begin writeln('',b[1]: 2); writeln(b[2]: 2,b[3]: 2,b[4]: 2); writeln(b[5]: 2,b[6]: 2,b[7]: 2); writeln('',b[8]) end; functionchoose: boolean; vari: integer; begin choose: =false; fori: =1to6do ifabs(b[link[i,1]]-b[link[i,2]])=1thenexit; choose: =true end; proceduretry; begin forb[2]: =3to6do forb[4]: =3to6do ifb[2]<>b[4]then forb[5]: =3to6do if(b[5]<>b[2])and(b[5]<>b[4])then begin b[7]: =18-b[2]-b[4]-b[5]; ifchoosethenprint; end; end; {mainprogram} begin clrscr; b[1]: =2;b[3]:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 大全