第1页 / 共108页
第2页 / 共108页
第3页 / 共108页
第4页 / 共108页
第5页 / 共108页
第6页 / 共108页
第7页 / 共108页
第8页 / 共108页
NOIP算法竞赛必读资料（已整理）.doc
信息学奥赛辅导教程
第3章 算法与程序设计模块
3.1 算 法
3.1.1 算法的5个重要特性
3.1.2 算法设计的要求
3.1.3 算法分析
3.1.4 程序设计
1．程序
2．程序设计
3．结构化程序设计
练习题
3.2 穷举搜索法
练习题
彩虹7号（rainbow.pas）
3.3 递 归 法
练习题
1．邮票面值设计（postag.pas）
2．聪明的学生（guess.pas）
3.4 回 溯 法
练习题
1．马拦过河卒（knight.pas）
2．走迷宫（maze.pas）
3．组合的输出（track.pas）
3.5 递 推
练习题
行家的预算（travel.pas）
3.6 模拟搜索（最原始的方法）
练习题
1．购物（money.pas）。
2．棋局（hiq.pas）。
猜想
“猜想”是一种重要的思维方法，对于确定证明方向，发现新定理，都有重大意义。
3.7 贪 心 算 法
1．算法思想
2．特点及使用范围
3．使用贪心算法的技巧（贪心与最优化算法的结合）
4．贪心算法的改进
练习题
木梳（comb.pas）
3.8 深度优先搜索
练习题
生日蛋糕（cake.exe）
3.9 广度优先搜索
练习题
1．聪明的打字员（clever.pas）
2．Sramoc问题（sramoc.pas）
3.10 双向广度优先搜索
1．广度双向搜索算法
2．算法说明
3．算法描述
练习题
九数码游戏（num9.pas）
3.11 有趣的数学问题
练习题
1．乘积最大（produc.pas）
2．砝码称重（g4.pas）
3.12 剪枝、优化
3.13 动 态 规 划
1．动态规划的基本方法
练习题
1．祖玛（zuma.pas）
2．选课（choose.pas）
表3-1 选修课学分表
3．祭祀（river.pas）
信息学奥赛辅导教程
第 3 章 算法与程序设计模块
3.1 算
法
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示
一个或多个操作。
常用的算法：列举了穷举搜索、递归、回溯、递推、模拟、分治、贪心、深度优先搜
索、广度优先搜索等几种较为常用的算法，没有做过多的描述，一旦给出具体描述，容易使
内容加深，产生严重学科取向的引导，符合教育部普通高中课程方案的特点，对于这些必需
的方法和思想，关键不在于学生能不能，而在于教师是否想到，是否有过关注，引发学生对
系统方法和思想的思考，重视建立编程思想，强化编程习惯的培养。
3.1.1 算法的 5 个重要特性
1．有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每
一步都可在有穷时间内完成。
2．确定性：算法中每一条指令必须有确切的含义，不会产生二义性。并且在任何条件
下，算法只有唯一的一条执行路径。
3．可行性：一个算法是能行的。即算法中描述的操作是执行有限次运算来实现的。
4．输入：一个算法有零个或多个输入。
5．输出：一个算法有一个或多个输出。
3.1.2 算法设计的要求
通常设计一个“好”的算法，应考虑达到以下目标。
1．正确性：算法应当满足具体问题的需求。
2．可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人
对算法的理解。
3．健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫
明其妙的输出结果。
4．效率与低存储量需求。
效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算
法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。
第 3 章 算法与程序设计模块
3.1.3 算法分析
算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以
探讨某种具体算法适用于哪类问题，或某类问题宜采用哪种算法。
算法的复杂度分时间复杂度和空间复杂度。时间复杂度是在运行算法时所耗费的时间为
f(n)（即 n 的函数）。空间复杂度是实现算法所占用的空间为 g(n)（也为 n 的函数）。称 O(f(n))
和 O(g(n))为该算法的复杂度。
3.1.4 程序设计
1．程序
程序是对所要解决的问题的各个对象和处理规则的描述，或者说是数据结构和算法的描
述，因此有人说，数据结构＋算法＝程序。
2．程序设计
程序设计就是设计、编制和调试程序的过程。程序设计是一门技术，需要相应的理论、
技术、方法和工具来支持。就程序设计方法和技术的发展而言，主要经过了结构化程序设计
和面向对象的程序设计两个阶段。
除了好的程序设计方法和技术之外，程序设计风格也很重要。因为程序设计风格会深刻
影响软件的质量和可维护性，良好的程序设计风格可以使程序结构清晰合理，使程序代码便
于维护。因此，程序设计风格对保证程序的质量很重要。
一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是
由人来编写的，为了测试和维护程序，往往还要阅读和跟踪程序，因此程序设计的风格总体
而言应该强调简单和清晰，必须可以理解。可以认为，著名的“清晰第一，效率第二”的论
点已成为当今主导的程序设计风格。要形成良好的程序设计风格，主要应注重源程序文档化。
（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序的功能进行
理解。
（2）程序注释：正确的注释能够帮助读者理解程序。
3．结构化程序设计
结构化程序设计方法是程序设计的先进方法和工具。采用结构化程序设计方法编写程
序，可使程序结构良好、易读、易理解、易维护。结构化程序语言仅使用顺序、选择和循环
3 种基本控制结构就足以表达出各种其他形式结构的程序设计方法。
总之，遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有明显的优
点。其一，程序结构良好、易读、易理解和易维护；其二，可以提高编程工作的效率，降低
软件开发成本。
·101·
信息技术与信息学竞赛
练习题
（1）算法的时间复杂度是指（
）。
A．执行算法程序所需要的时间
C．算法执行过程中所需要的基本运算次数
B．算法程序的长度
D．算法程序中的指令条数
【解析】所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用
算法所执行的基本运算次数来度量。
【答案】C
（2）算法的空间复杂度是指（
A．算法程序的长度
C．算法程序所占的存储空间
）。
B．算法程序中的指令条数
D．算法执行过程中所需要的存储空间
【解析】空间复杂度是指执行算法所需要的存储空间。算法所占用的存储空间包括算法
程序所占的空间、输入初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
【答案】D
（3）算法指的是（
A．计算机程序
C．排序算法
）。
B．解决问题的计算方法
D．解决问题的有限运算序列
【解析】所谓算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一
个计算机程序在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算
法可解的。但算法不等于程序，也不等于计算方法。
【答案】D
（4）算法能正确地实现预定功能的特性称为算法的（
A．正确性
B．易读性
C．健壮性
）。
D．高效率
【解析】针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又
总是在某个特定的计算工具上执行的，因此算法在执行过程中往往要受到计算工具的限制，
使执行结果产生偏差。算法与计算公式是有差别的，在设计一个算法时，必须要考虑它的可
行性，否则将得不到满意的结果。
【答案】A
（5）递归算法一般需要利用（
A．栈
【答案】A
B．队列
）来实现。
C．循环链表
D．双向链表
3.2 穷举搜索法
有一些问题一时难以找到规律或者公式，或者根本没有规律、公式。这时可以利用计算
机高速运算的特点，使用穷举来解决。穷举搜索法是穷举所有可能情形，并从中找出符合要
求的解决。穷举搜索法所有可能情形，最直观的是联系循环的算法。
例 1 找出 n 个自然数（1,2,3,…,n）中 r 个数的组合。例如，当 n=5，r=3 时，所有组
合为：
·102·
第 3 章 算法与程序设计模块
5
5
5
5
5
5
4
4
4
3
total=10
［程序］
3
2
1
2
1
1
2
1
1
1
5
4
4
3
3
2
3
3
2
2
{组合的总数}
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 (i<>j) and (i<>k) and (i>j) and (j>k) then
begin
end;
t:=t+1;writeln(i:3,j:3,k:3);
writeln('total=',t);
end.
这个程序，穷举了所有可能情形，从中选出符合条件的解，很多情况下穷举搜索法还是
常用的。
例 2 算 24 点（poi24.pas）。
【题目描述】
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲。在中国我们把这种游戏称
为“算 24 点”。您作为游戏者将得到 4 个 1～9 之间的自然数作为操作数，而您的任务是对
这 4 个操作数进行适当的算术运算，要求运算结果等于 24。
您可以使用的运算只有：+，-，×，/，您还可以使用（）来改变运算顺序。注意：所
有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2×2)/4 是合法的，2×(2/4)
是不合法的）。下面我们给出一个游戏的具体例子：若给出的 4 个操作数是：1、2、3、7，
则一种可能的解答是 1+2+3×7=24。
【输入】
只有一行，四个 1～9 之间的自然数。
【输出】
如果有解的话，只要输出一个解，输出的是 3 行数据，分别表示运算的步骤。其中第一
行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数
据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“=24”。
如果两个操作数有大小的话则先输出大的。如果没有解，则输出“no answer!”
【样例】
·103·
信息技术与信息学竞赛
poi24.in
1 2 3 7
poi24.out
2+1=3
7×3=21
21+3=24
【算法分析】
计算 24 点主要应用四种运算。开始状态有四个操作数，一个运算符对应两个操作数，
所以一开始选择两个操作数分别对四个操作符进行循环检测，每一次运算后产生了新的数，
两个数运算变成一个数，整体是少了一个操作数，所以四个数最终是三次运算。由于操作的
层数比较少（只有三层），所以可以用回溯的算法来进行检测，当找到一个解时便结束查找。
如果所有的情况都找过后仍然没有，则输出无解的信息。
［程序］
{point24}
program poi24;
type 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
assign(outfile,'poi24.out');
rewrite(outfile);
for i:=1 to 3 do
begin
for j:=1 to 3 do
if j<>2 then write(outfile,r[i,j])
else case r[i,j] of
1:write(outfile,'+');
2:write(outfile,'-');
3:write(outfile,'*');
4:write(outfile,'/')
end;
writeln(outfile,'=',r[i,4])
end;
close(outfile);
end;
procedure try(k:integer;d:arr);
var a,b,i,j,l,t:integer;
e:arr;
begin
else begin
if k=1 then if d[1]=24 then begin print;halt end else
for i:=1 to k-1 do
for j:=i+1 to k do
begin
a:=d[i]; b:=d[j];
if a
第 3 章 算法与程序设计模块
for l:=1 to k do if (l<>i) and (l<>j) then begin t:=t+1;e[t]:=d[l]
end;
r[5-k,1]:=a;
r[5-k,3]:=b;
r[5-k,4]:=-1;
for l:=1 to 4 do
begin
case l of
1:r[5-k,4]:=a+b;
2:r[5-k,4]:=a-b;
3:r[5-k,4]:=a*b;
4:if b<>0 then if a mod b=0 then r[5-k,4]:=a div b
end;
r[5-k,2]:=l;
if r[5-k,4]<>-1 then
begin
e[t+1]:=r[5-k,4];
try(k-1,e)
end
end
end
end;
end;
begin
end.
assign(infile,'poi24.in');
reset(infile);
for i:=1 to 4 do read(infile,d[i]);
close(infile);
try(4,d);
assign(outfile,'poi24.out');
rewrite(outfile);
writeln(outfile,'no answer!');
close(outfile);
·105·
信息技术与信息学竞赛
练习题
彩虹 7 号（rainbow.pas）
X 市是一个重要的军事基地，在这个基地中有一支名为“彩虹 7 号”的特别部队。每个
队员都有一个固定独立的编号 X(1≤X≤215)，他们的职责就是完成部队交给他们的任务，每
个任务同样都有固定独立的编号 N(1≤N≤10)。在执行任务的过程中，为了保证任务的保密
性和队员的安全，队员和队员之间的联系将必须由特别部队所提供的一种保密频段交互设备
进行。
每个队员都需要一个身份验证口令进入系统，由于队员所执行的任务都是涉及国家安全
或者极高机密的活动，如果队员使用的口令出现错误，他们将付出无法估计的代价。特别部
队的队员都是层层筛选的精英人才，所以不希望发生这样的事情。因此队员必须牢记口令的
设置方法。
口令 S 的内容满足：SN=X。显然，S 有可能也很有可能是一个无理数，所以限定 S 为
一个实数，它包含整数部分和小数部分，不包含小数点（即 0.1 将视作 01）。口令的长度
M(10≤M≤50)，将根据任务的难度而有所不同。
编程任务：给定 X，N，M。计算口令的内容 S。
输入（rainbow .in）：文件输入，文件有且仅有一行包含 3 个整型数 X，N，M，每个
数之间以一个空格符隔开。
输出（rainbow.out）：文件输出，文件有且仅有一行，为 S 的结果。
样例输入：2 2 10
样例输出：1414213652
注意：口令的最后一位请使用去尾法保留，不要使用四舍五入法保留。文件请不要包
含多余的空格和换行。
3.3 递 归 法
递归作为一种强有力的数学和算法描述工具在 Pascal 语言中被广泛使用。一个函数、
过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有定义本身的引用（在
过程或自定义函数中，又包含自己调用自己），则称它们是递归的或者是递归定义的。
一个递归算法仅使用少量的程序编码就可描述出解题所需要的多次重复计算而不需要
设计循环结构。使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题
相类似的规模较小的问题来求解，进而最终导致原问题的解决。
例如：n!的定义，我们知道，在数学中 n!一般定义为：
n!=
1
若 n=0
n×(n-1)! 若 n>0
·106·
第 3 章 算法与程序设计模块
在 n>0 的 公 式中 ， 又 包 含 了（n-1）!， 这 就是 递 归 定 义 。
利 用 递 归 方 法 ， 可 以 用 有 限 的 语 句 来 定 义 对 象 的 无 限 集 合 。 但 在 递 归 定 义 中 ，
应 该 至 少 有 一 条 是 非 递 归 的 ， 即 初 始 定 义 。 如 上 面 例 子 中 的 第 一 条 ， 否 则 就 变 成 了
循 环 定义 ， 产 生 逻 辑性 错 误 。
procedure find（n：integer）；
begin
if n＝0 then t：＝1
else
begin find（n-1）；
t：＝t＊n end；
n!的 递 归定 义 的 程 序 ：
program find＿n；
var n：integer；
t：longint；
end；
begin
write（'n＝'）；
readln（n）；
find（n）；
writeln（n,'!＝'，t）
end．
递 归 调用 （n 进 栈 ）达 到 结 束 条 件时 （n=0，t 赋 初 值 1） 就 停止 调 用 开 始 返回 ，
再 把 保存 的 值 取 出（n 出 栈 ），使 n 恢 复 原来 的 值 ，并 计 算 t，返 回 主程 序 ，输 出 结
果 t。
3!递归是如何实现的？
（1） 设 n=3， 开 始调 用 过 程 find， 称 为第 零 层 调 用 。
（2） 由 于 公 式 3!=3 2!， 必 须 先 求 2!， 即 程 序 中 的 f(n-1)， 此 时 系 统 自 动 先 保
存 n 的 原 值 3， 再 设 n=2， 进 入第 一 层 递 归 调用 。
（3） 因 为 2!=2 1!， 所 以系 统 又 保 存 2， 并 设 n=1， 进 入第 2 层 调 用。
（4） 因 为 1!=1 0!， 所 以保 存 1， 并 设 n=0， 进 入第 3 层 调 用。
（5） 因 为 n=0， 终 止调 用 ，t 赋 值 1， 返 回 4 的 入 口点 。
（6） 取 出执 行 4 时 保 存的 1， 求 出 t=1 t=1， 返 回 3 的 入 口点 。
（7） 取 出执 行 3 时 保 存的 2， 求 出 t=2 t=2， 返 回 2 的 入 口点 。
（8） 取 出执 行 2 时 保 存的 3， 求 出 t=3 t=6， 返 回 1 的 入 口点 。
（9） 返 回主 程 序 ， 输 出结 果 ：t=6。
从 上 面分 析 的 过 程 看到 ，由 于 递归 调 用 ，需 用 同一 变 量 名 n，但 值 不同 ，所 以 在
调 用 前 必 须 先 把 n 的 原 值 保 存 ， 再 赋 以 新 值 ， 然 后 进 入 调 用 。 调 用 结 束 后 ， 再 把 保
存 的 值 取 出 ， 使 n 恢 复 原 来 的 值 。 在 过 程 中 find 中 又 包 含 find(n-1)， 即 又 调 用 了 它
自 己 ，这 就 是 递 归 调用 。 包 含 有 递归 调 用 的 算 法， 就 叫 做 递 归算 法 。
递 归 调 用 会 产 生 无 终 止 运 算 的 可 能 性 ， 因 此 必 须 在 适 当 时 候 终 止 递 归 调 用 ， 即
在 程 序 中 必 须 要 有 终 止 条 件 。 上 面 程 序 中 ， 过 程 find 的 第 一 条 语 句 就 是 终 止 条 件 。
一 般 地 ， 根 据 递 归 定 义 设 计 的 递 归 算 法 中 ， 非 递 归 的 初 始 定 义 ， 就 用 作 程 序 中 的 终
止
条 件 。
·107·
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
