[算法综合资料.doc

程序设计的常用算法 目录 一、常用策略 1、枚举策略 2、归纳策略 3、分治策略 4、最优策略 二、递归算法 三、有哪些信誉好的足球投注网站算法 1、深度优先有哪些信誉好的足球投注网站 2、广度优先有哪些信誉好的足球投注网站 四、其它数学方法的应用 五、动态规划 六、综合训练题 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 第一部分 常用策略 （一）枚举策略 1、算法思想 枚举策略又叫列举法，算法思想是：根据问题中的条件（约束条件）将可能的解列举出来，然后一一验证是否符合题目要求，从而找到问题的解。应用枚举策略解题的关键是：根据问题的条件确定解的范围，和对可能的解进行验证。 2、应用举例 例1_1: 找水仙花数 一个三位数各位数字的立方和等于它本身，这样的三位数称为水仙花数。请编程找出所有的水仙花数。 分析：根据水仙花数的定义可知，水仙花数一定是三位数，因此，可能的范围是100至999的所有数，将这些数一一列举进行验证，从而找出所有的水仙花数。程序如下： program Liti1_1; var a,b,c,d: integer; begin for a:=100 to 999 do begin b:=a mod 10; c:=(a div 10) mod 10; d:=a div 100; if (a=b*b*b+c*c*c+d*d*d) then writeln(a); end; end. 其中a 是枚列变量，b、c、d分别表示个位、十位、百位上的数字。 例1_2: 百钱买百鸡问题 用100元钱到市上买鸡，已知大的公鸡每只5元，大的母鸡每只4元，小鸡每元3只，现在要用100元去买100只鸡，要求每种鸡至少买一只，问买公鸡、母鸡和小鸡各多少只？有多少种方案？ 分析：设x、y、z分别表示买公鸡、母鸡、小鸡的只数，那么依题意可知它们的范围分别为：x: 1—100/5; y: 1—(100-x*5)/4; 根据条件小鸡的只数为100-x-y, 如果符合钱总额为100，鸡的总只数为100，则找到问题的一组解。故可编如下： program Liti1_2; var x, y, z: integer; a,b,c,total: integer; begin a:=trunc(100/5); total:=0; for x:=1 to a do begin b:=trunc((100-x*5)/4); for y:=1 to b do begin z:=100-x-y; c:=trunc(z/3); if x*5+y*4+c=100 then begin writeln(‘gong ji’,x, ‘ ’, ‘mu gi: ’,y, ‘ ’,’xiao ji:’,z); total:=total+1; end; end; end; writeln(‘total=’,total); end. 例1_3: 有四种重量不同的砝码(重量分别为A，B，C，D，且ABCD)，每种砝码有三个，要求称出重量为A~M的重量为连续的X种货物，每次最多只能用三个砝码，问：M是几？ 例如： 输入砝码重量为1，4，5，9 输出为： 15 program lx; …… for I:=0 to 3 do for j:=0 to 3 do for k:=0 to 3 do if I+j+k+l =3 then begin x=A*I+B*J+C*K+D*L; p(x)=1 end; for I :=A to 3 *D+1 if p(i)=0 then begin max:=I-1 ; halt end; ３、小结：枚举法的思想应用很广，由于枚举法要将所有可能的解一一列举出来验证，因此，运算量很大，编程时应尽量缩小范围，充分利用题目给定的条件，减少程序的运算量。 4、练习： 练习1—1：一个四位数是一个完全平方数，它减去一个每位数字都相同的四位数（如1111）后，仍是一个四位的完全平方数。请编程打印出所有这样的四位数。 练习1-2：编程求具有下现两个性质的最小自然n; (1) n的个位数是６； (2) 若将n的个