《信息学奥赛算法教程pascal》由会员分享，可在线阅读，更多相关《信息学奥赛算法教程pascal（92页珍藏版）》请在金锄头文库上搜索。
1、第3章 算法与程序设计模块信息学奥赛辅导教程第3章 算法与程序设计模块3.1 算 法算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。常用的算法：列举了穷举搜索、递归、回溯、递推、模拟、分治、贪心、深度优先搜索、广度优先搜索等几种较为常用的算法，没有做过多的描述，一旦给出具体描述，容易使内容加深，产生严重学科取向的引导，符合教育部普通高中课程方案的特点，对于这些必需的方法和思想，关键不在于学生能不能，而在于教师是否想到，是否有过关注，引发学生对系统方法和思想的思考，重视建立编程思想，强化编程习惯的培养。3.1.1 算法的5个重要特性1有穷性：一个算法必须
2、总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。2确定性：算法中每一条指令必须有确切的含义，不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径。3可行性：一个算法是能行的。即算法中描述的操作是执行有限次运算来实现的。 4输入：一个算法有零个或多个输入。5输出：一个算法有一个或多个输出。3.1.2 算法设计的要求通常设计一个“好”的算法，应考虑达到以下目标。1正确性：算法应当满足具体问题的需求。2可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解。3健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明
3、其妙的输出结果。 4效率与低存储量需求。效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。3.1.3 算法分析算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问题宜采用哪种算法。 算法的复杂度分时间复杂度和空间复杂度。时间复杂度是在运行算法时所耗费的时间为f(n)（即n的函数）。空间复杂度是实现算法所占用的空间为g(n)（也为n的函数）。称O(f(n)和O(g(n)为该算法的复杂度。 3.1.4 程序设计1程序程序是对所要解决的问题的各个对象和
4、处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构算法程序。2程序设计程序设计就是设计、编制和调试程序的过程。程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计两个阶段。除了好的程序设计方法和技术之外，程序设计风格也很重要。因为程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格可以使程序结构清晰合理，使程序代码便于维护。因此，程序设计风格对保证程序的质量很重要。一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要阅读和
5、跟踪程序，因此程序设计的风格总体而言应该强调简单和清晰，必须可以理解。可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。要形成良好的程序设计风格，主要应注重源程序文档化。（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序的功能进行理解。（2）程序注释：正确的注释能够帮助读者理解程序。3结构化程序设计结构化程序设计方法是程序设计的先进方法和工具。采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。结构化程序语言仅使用顺序、选择和循环3种基本控制结构就足以表达出各种其他形式结构的程序设计方法。总之，遵循结构化程序的设计原则，按结构化程序设
6、计方法设计出的程序具有明显的优点。其一，程序结构良好、易读、易理解和易维护；其二，可以提高编程工作的效率，降低软件开发成本。练习题（1）算法的时间复杂度是指（ ）。A执行算法程序所需要的时间 B算法程序的长度C算法执行过程中所需要的基本运算次数 D算法程序中的指令条数【解析】所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量。【答案】C（2）算法的空间复杂度是指（ ）。A算法程序的长度 B算法程序中的指令条数C算法程序所占的存储空间 D算法执行过程中所需要的存储空间【解析】空间复杂度是指执行算法所需要的存储空间。算法所占用的存储空间包括算法程序所
7、占的空间、输入初始数据所占的存储空间以及算法执行过程中所需要的额外空间。【答案】D（3）算法指的是（ ）。A计算机程序 B解决问题的计算方法C排序算法 D解决问题的有限运算序列【解析】所谓算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。【答案】D（4）算法能正确地实现预定功能的特性称为算法的（ ）。A正确性 B易读性 C健壮性 D高效率【解析】针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此算法在
8、执行过程中往往要受到计算工具的限制，使执行结果产生偏差。算法与计算公式是有差别的，在设计一个算法时，必须要考虑它的可行性，否则将得不到满意的结果。【答案】A（5）递归算法一般需要利用（ ）来实现。A栈 B队列 C循环链表 D双向链表【答案】A3.2 穷举搜索法有一些问题一时难以找到规律或者公式，或者根本没有规律、公式。这时可以利用计算机高速运算的特点，使用穷举来解决。穷举搜索法是穷举所有可能情形，并从中找出符合要求的解决。穷举搜索法所有可能情形，最直观的是联系循环的算法。例1 找出n个自然数（1,2,3,n）中r个数的组合。例如，当n=5，r=3时，所有组 合为： 5 5 3 5 4 2 5
9、4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2 1 total=10 组合的总数程序 program zuhe11; const n=5; var i,j,k,t:integer; begin t:=0; for i:=n downto 1 do for j:=n downto 1 do for k:=n downto 1 do if (ij) and (ik) and (ij) and (jk) then begin t:=t+1;writeln(i:3,j:3,k:3); end; writeln(total=,t); end.这个程序，穷举了所有可
10、能情形，从中选出符合条件的解，很多情况下穷举搜索法还是常用的。例2 算24点（poi24.pas）。 【题目描述】几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲。在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个19之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。您可以使用的运算只有：+，-，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(22)/4是合法的，2(2/4)是不合法的）。下面我们给出一个游戏的具体例子：若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3
11、7=24。【输入】只有一行，四个19之间的自然数。【输出】如果有解的话，只要输出一个解，输出的是3行数据，分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“=24”。如果两个操作数有大小的话则先输出大的。如果没有解，则输出“no answer!”【样例】poi24.in poi24.out1 2 3 72+1=373=2121+3=24【算法分析】计算24点主要应用四种运算。开始状态有四个操作数，一个运算符对应两个操作数，所以一开始选择两个操作数分别对四个操作符进行循
12、环检测，每一次运算后产生了新的数，两个数运算变成一个数，整体是少了一个操作数，所以四个数最终是三次运算。由于操作的层数比较少（只有三层），所以可以用回溯的算法来进行检测，当找到一个解时便结束查找。如果所有的情况都找过后仍然没有，则输出无解的信息。程序program poi24; point24type arr=array 1.4 of integer;var i,result,n,len:integer; d:arr; r:array 1.3,1.4 of integer; infile,outfile:text;procedure print;var i,j:integer;begin as
13、sign(outfile,poi24.out); rewrite(outfile); for i:=1 to 3 do begin for j:=1 to 3 do if j2 then write(outfile,ri,j) else case ri,j of 1:write(outfile,+); 2:write(outfile,-); 3:write(outfile,*); 4:write(outfile,/) end; writeln(outfile,=,ri,4) end; close(outfile);end;procedure try(k:integer;d:arr);var a,b,i,j,l,t:integer; e:arr;begin if k=1 then if d1=24 then begin print;halt end else
