1、1算法详解及练习题目 录第一讲 穷举法 - 1第二讲 字符与字符串处理 - 16第三讲 不同进制转换 - 25第四讲 高精度计算 - 26第五讲 数据排序 - 30第六讲 约瑟夫问题（纸牌问题）- 34第七讲 矩阵（递推问题）- 40第八讲 排列组合 - 43第九讲 贪心算法 - 47第十讲 递归算法 - 56第一讲 穷举法一、穷举法的基本概念穷举方法是基于计算机特点而进行解题的思维方法。一般是在一时找不出解决问题的更好途径（即从数学上找不到求解的公式或规则）时，可以根据问题中的的部分条件（约束条件）将所有可能解的情况列举出来，然后通过一 一验证是否符合整个问题的求解要求，而得到问题的解。这样
2、解决问题的方法我们称之为穷举算法。穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举出来的情况数目会大得惊人，就是用高速的电子计算机运行，其等待运行结果的时间也将使人无法忍受。因此，我们在用穷举方法解决问题时，应尽可能将明显的不符合条件的情况排除在外，以尽快取得问题的解。二、算法模式 问题解的可能搜索的范围： 用循环或循环嵌套结构实现，写出符合问题解的条件。能使程序优化的语句，以便缩小搜索范围，减少程序运行时间。三、使用穷举法设计算法例 1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你编一程序，
3、帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别设为x,y,z）,以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*3+y*2+z)为判定条件，穷举各种鸡的个数。下面是解这个百鸡问题的程序var x,y,z:integer;2beginfor x:=0 to 100 dofor y:=0 to 100 dofor z:=0 to 100 do枚举所有可能的解if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln(x=,x,y=,y,z=,z);
4、 验证可能的解，并输出符合题目要求的解end.上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡（x,y） ，第三种鸡就可以根据约束条件求得（z=100-x-y） ，这样就缩小了枚举范围，请看下面的程序：var x,y,z:integer;beginfor x:=0 to 100 dofor y:=0 to 100-x dobeginz:=100-x-y;if (x*3+y*2+z div 3=100)and(z mod 3=0)then writeln(x=,x,y=,y,z=,z);end;end.未经优化的程序循环了 1013 次，时间复杂度为 O(n3)；优化后的程序只循
5、环了（102*101/2）次 ，时间复杂度为 O(n2)。从上面的对比可以看出，对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：例 2、将 1,2.9 共 9 个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3 的比例,试求出所有满足条件的三个三位数.例如:三个三位数 192,384,576 满足以上条件.(NOIP1998pj)算法分析：这是 1998 年全国分区联赛普及组试题（简称 NOIP1998pj，以下同） 。此题数据规模不大，可
6、以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：for a:=1 to 9 do for b:=1 to 9 dofor i:=1 to 9 do这样下去，枚举次数就有 99 次，如果我们分别设三个数为 x,2x,3x，以 x 为枚举对象，穷举的范围就减少为 93，在细节上再进一步优化，枚举范围就更少了。程序如下：var3t,x:integer; s,st:string; c:char;beginfor x:=123 to 329 do枚举所有可能的解begint:=0;str(x,st);把整数 x 转化为字符串，存放在 st 中str(x*2,s); st:=st+s
7、;str(x*3,s); st:=st+s;for c:=1 to 9 do枚举 9 个字符，判断是否都在 st 中if pos(c,st)0 then inc(t) else break;如果不在 st 中，则退出循环if t=9 then writeln(x, ,x*2, ,x*3);end;end.在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果， 我们再看看下面的例子。例 3：古希腊人认为因子的和等于它本身的数是一个完全数（自身因子除外） ，例如 28的因子是 1、2、4、7、14，且 1+2+4+7+14=28，则 28 是一个完全数，编写
8、一个程序求21000 内的所有完全数。分析：本题是一个搜索问题，搜索范围 21000，找出该范围内的完全数；完全数必须满足的条件：因子的和等于该数据的本身。问题关键在于将该数的因子一一寻找出来，并求出因子的和。程序如下：Program p3_1 ;Var a,b,s :integer ;BeginFor a:=2 to 1000 do Begins:=0 ;For b:=1 to a -1 doIf a mod b =0 then s:=s+b ; 分解因子并求和 If a=s then begin Write( a, = ,1, );打印 a=1For b:=2 to a -1 do If
9、a mod b=0 then write( +, b );打印加法式子Writeln ; End;End;End.4当程序运行后，输出结果：6 = 1 + 2 + 328 = 1 + 2 + 4 + 7 + 14 496 =1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248例 4：（第七届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题）在 A，B 两个城市之间设有 N 个路站(如下图中的 S1，且 N x0 then beginx0:=x; x1:=a ; x2:=b ; x3:=c ; x4:=d 保存最大面值邮票 write( x1：5, x2：5, x3
10、：5, x4：5 );writeln( :10, x0=, x0 );end; end;end.程序运行后，其输出结果是： 1 2 3 4 x0=12 解答结果有 11 组 1 2 3 5 x0=1310.1 3 6 10 x0=23 1 4 7 8 x0=24实例三：如图所示的 8 个格子中放入 18 八个数字，使得相邻的和对角线的数字之差不为 1。编程找出所有放法。我们先不考虑后一条件，只考虑第一个条件，即把 18 八个数字放入 8 个格子中。这是容易做到的，就是 8 个数字的全排列，共有 8!=40320 种放法。然后对这 8!个可行解用后一个条件加以检验，输出符合条件的解。对于后一个条
11、件中“相邻”的判断，可以建立一个邻接表来解决：i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 j 1 1 1 1 2 2 2 3 3 3 4 5 5 6 72 2 3 4 3 5 6 4 6 7 7 6 8 7 8表中表示哪两个格子是相邻的，linki,1和 linki,2是相邻的格子的编号。全排列的产生，可以用八重循环，也可以用专门的算法，程序留给同学们自己去完成。利用穷举策略编制的程序，其运算量一般是很大的，因此如何提高算法效率是穷举算法一个很重要的问题。一般应尽量减少可行解的个数，使得第二步的检验运算量尽可能地少。例如对于例 5-1，如何来优化算法呢?如果注意到 b
12、3 和 b6 两个格子，与它们“相邻”的格子有 6 个，也就是说，放入这两个格子中的数，必须和 6 个数不连续，仅可以和一个数是连续的，这样的数只有 2 个，即 1 和 8。这样，b1，b3，b6，b8；4 个格子中数的放法仅有两种可能：2、8、1、7 和 7、1、8、2。而 b2、b4、b5、b7 四个格子中的数仅需在 36 四个数中选择。经过上述优化，可行解仅有：24！48 个，大大减少了计算量。并且检验是否符合要求，也只需检查(1，2)，(1，4)，(2，5)，(4，7)，(5，8)，(7，8)这 6 对数之差就可以了。按改进的算法编制的 PASCAL 程序如下： program exampleb；uses Crt：const link：array1.6，1.2 of integer=(1,2),(1,4),(2,5),(4,7),(5,8),(7,8);var b:array1.8 of integer;procedure print;beginwriteln( ,b1:2);writeln(b2:2,b3:2,b4:2);writeln(b5:2,b6:2,b7:2);writeln(,b8)
