信息学奥赛算法教学课件Pascal.doc
《信息学奥赛算法教学课件Pascal.doc》由会员分享,可在线阅读,更多相关《信息学奥赛算法教学课件Pascal.doc(92页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、|信息学奥赛辅导教程第 3 章 算法与程序设计模块3.1 算 法算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。常用的算法:列举了穷举搜索、递归、回溯、递推、模拟、分治、贪心、深度优先搜索、广度优先搜索等几种较为常用的算法,没有做过多的描述,一旦给出具体描述,容易使内容加深,产生严重学科取向的引导,符合教育部普通高中课程方案的特点,对于这些必需的方法和思想,关键不在于学生能不能,而在于教师是否想到,是否有过关注,引发学生对系统方法和思想的思考,重视建立编程思想,强化编程习惯的培养。3.1.1 算法的 5 个重要特性1有穷性:一个算法必须总是(对任何合法
2、的输入值)在执行有穷步之后结束,且每一步都可在有穷时间内完成。2确定性:算法中每一条指令必须有确切的含义,不会产生二义性。并且在任何条件下,算法只有唯一的一条执行路径。3可行性:一个算法是能行的。即算法中描述的操作是执行有限次运算来实现的。 4输入:一个算法有零个或多个输入。5输出:一个算法有一个或多个输出。3.1.2 算法设计的要求通常设计一个“好”的算法,应考虑达到以下目标。1正确性:算法应当满足具体问题的需求。2可读性:算法主要是为了人的阅读与交流,其次才是机器执行。可读性好有助于人对算法的理解。3健壮性:当输入数据非法时,算法也能适当地做出反应或进行处理,而不会产生莫明其妙的输出结果。
3、4效率与低存储量需求。效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决,执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。第 3 章 算法与程序设计模块1013.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信息技术与信息学竞赛102(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 个数的组
9、合。例如,当 n=5,r=3 时,所有组 合为: 5 5 35 4 25 4 15 3 25 3 15 2 14 3 24 3 14 2 13 2 1total=10 组合的总数程序program zuhe11;const n=5;var i,j,k,t:integer;begin t:=0;for i:=n downto 1 dofor j:=n downto 1 dofor k:=n downto 1 doif (ik) and (ij) and (jk) thenbegin t:=t+1;writeln(i:3,j:3,k:3);end;writeln(total=,t);end.第 3
10、 章 算法与程序设计模块103这个程序,穷举了所有可能情形,从中选出符合条件的解,很多情况下穷举搜索法还是常用的。例 2 算 24 点(poi24.pas)。 【题目描述】几十年前全世界就流行一种数字游戏,至今仍有人乐此不疲。在中国我们把这种游戏称为“算 24 点”。您作为游戏者将得到 4 个 19 之间的自然数作为操作数,而您的任务是对这 4 个操作数进行适当的算术运算,要求运算结果等于 24。您可以使用的运算只有:+,-,/,您还可以使用()来改变运算顺序。注意:所有的中间结果须是整数,所以一些除法运算是不允许的(例如,(22)/4 是合法的,2(2/4)是不合法的)。下面我们给出一个游戏
11、的具体例子:若给出的 4 个操作数是:1、2、3、7,则一种可能的解答是 1+2+37=24。【输入】只有一行,四个 19 之间的自然数。【输出】如果有解的话,只要输出一个解,输出的是 3 行数据,分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果,第二行是第一行的结果和一个输入的数据、运算符、运算后的结果;第三行是第二行的结果和输入的一个数、运算符和“=24”。如果两个操作数有大小的话则先输出大的。如果没有解,则输出“no answer!”【样例】poi24.in poi24.out1 2 3 7 2+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
13、:text;procedure print;var i,j:integer;beginassign(outfile,poi24.out);rewrite(outfile);for i:=1 to 3 dobeginfor j:=1 to 3 doif jj) then begin t:=t+1;et:=dl end;r5-k,1:=a;r5-k,3:=b;r5-k,4:=-1;for l:=1 to 4 dobegincase l of1:r5-k,4:=a+b;2:r5-k,4:=a-b;3:r5-k,4:=a*b;4:if b-1 thenbeginet+1:=r5-k,4;try(k-1
14、,e)endendendend;end;beginassign(infile,poi24.in);reset(infile);for i:=1 to 4 do read(infile,di);close(infile);try(4,d);assign(outfile,poi24.out);rewrite(outfile);writeln(outfile,no answer!);close(outfile);end.练习题彩虹 7 号(rainbow.pas)X 市是一个重要的军事基地,在这个基地中有一支名为 “彩虹 7 号”的特别部队。每个队员都有一个固定独立的编号 X(1X2 15),他们的
15、职责就是完成部队交给他们的任务,每个任务同样都有固定独立的编号N(1N 10) 。在执行任务的过程中,为了保证任务的保密性和队员的安全,队员和队员之间的联系将必须由特别部队所提供的一种保密频段交互设备进行。第 3 章 算法与程序设计模块105每个队员都需要一个身份验证口令进入系统,由于队员所执行的任务都是涉及国家安全或者极高机密的活动,如果队员使用的口令出现错误,他们将付出无法估计的代价。特别部队的队员都是层层筛选的精英人才,所以不希望发生这样的事情。因此队员必须牢记口令的设置方法。口令 S 的内容满足:S N=X。显然,S 有可能也很有可能是一个无理数,所以限定 S 为一个实数,它包含整数部
16、分和小数部分,不包含小数点(即 0.1 将视作 01)。口令的长度 M(10M50) ,将根据任务的难度而有所不同。 编程任务:给定 X,N,M。计算口令的内容 S。输入(rainbow .in):文件输入,文件有且仅有一行包含 3 个整型数 X,N,M,每个数之间以一个空格符隔开。输出(rainbow.out ):文件输出,文件有且仅有一行,为 S 的结果。样例输入:2 2 10样例输出:1414213652注意:口令的最后一位请使用去尾法保留,不要使用四舍五入法保留。文件请不要包含多余的空格和换行。3.3 递 归 法递归作为一种强有力的数学和算法描述工具在 Pascal 语言中被广泛使用。
17、一个函数、过程、概念或数学结构,如果在其定义或说明内部又直接或间接地出现有定义本身的引用(在过程或自定义函数中,又包含自己调用自己),则称它们是递归的或者是递归定义的。一个递归算法仅使用少量的程序编码就可描述出解题所需要的多次重复计算而不需要设计循环结构。使用递归求解问题,通常可以将一个比较大的问题层层转化为一个与原问题相类似的规模较小的问题来求解,进而最终导致原问题的解决。例如:n!的定义,我们知道,在数学中 n!一般定义为:1 若 n=0n!=n(n-1)! 若 n0在 n0 的 公 式 中 , 又 包 含 了 ( n-1) !, 这 就 是 递 归 定 义 。利 用 递 归 方 法 ,
18、可 以 用 有 限 的 语 句 来 定 义 对 象 的 无 限 集 合 。 但 在 递 归 定 义 中 , 应 该 至 少 有 一 条 是 非递 归 的 , 即 初 始 定 义 。 如 上 面 例 子 中 的 第 一 条 , 否 则 就 变 成 了 循 环 定 义 , 产 生 逻 辑 性 错 误 。n!的 递 归 定 义 的 程 序 :program findn ;var n: integer;t:longint;procedure find(n:integer);beginif n0 then t: 1else begin find(n-1);t:tn end;end;beginwrite(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息学 算法 教学 课件 Pascal
限制150内