如何用枚举法是什么意思一一列出ABCD中取三个进行排列，取三个进行组合？
点击联系发帖人
时间：2018-08-17 16:49
请选择考试第3章 &算法与程序设计模块
3.1 &算 &&&法
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
常用的算法：列举了穷举搜索、递归、回溯、递推、模拟、分治、贪心、深度优先搜索、广度优先搜索等几种较为常用的算法，没有做过多的描述，一旦给出具体描述，容易使内容加深，产生严重学科取向的引导，符合教育部普通高中课程方案的特点，对于这些必需的方法和思想，关键不在于学生能不能，而在于教师是否想到，是否有过关注，引发学生对系统方法和思想的思考，重视建立编程思想，强化编程习惯的培养。
3.1.1 &算法的5个重要特性
1．有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2．确定性：算法中每一条指令必须有确切的含义，不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径。
3．可行性：一个算法是能行的。即算法中描述的操作是执行有限次运算来实现的。
4．输入：一个算法有零个或多个输入。
5．输出：一个算法有一个或多个输出。
3.1.2 &算法设计的要求
通常设计一个“好”的算法，应考虑达到以下目标。
1．正确性：算法应当满足具体问题的需求。
2．可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解。
3．健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。
4．效率与低存储量需求。
效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。
3.1.3 &算法分析
算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问题宜采用哪种算法。
算法的复杂度分时间复杂度和空间复杂度。时间复杂度是在运行算法时所耗费的时间为f(n)（即&n的函数）。空间复杂度是实现算法所占用的空间为（也为的函数）。称和为该算法的复杂度。
3.1.4 &程序设计
程序是对所要解决的问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构＋算法＝程序。
2．程序设计
程序设计就是设计、编制和调试程序的过程。程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计两个阶段。
除了好的程序设计方法和技术之外，程序设计风格也很重要。因为程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格可以使程序结构清晰合理，使程序代码便于维护。因此，程序设计风格对保证程序的质量很重要。
一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要阅读和跟踪程序，因此程序设计的风格总体而言应该强调简单和清晰，必须可以理解。可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。要形成良好的程序设计风格，主要应注重源程序文档化。
（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序的功能进行理解。
（2）程序注释：正确的注释能够帮助读者理解程序。
3．结构化程序设计
结构化程序设计方法是程序设计的先进方法和工具。采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。结构化程序语言仅使用顺序、选择和循环3种基本控制结构就足以表达出各种其他形式结构的程序设计方法。
总之，遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有明显的优点。其一，程序结构良好、易读、易理解和易维护；其二，可以提高编程工作的效率，降低软件开发成本。
（1）算法的时间复杂度是指（ &&&&）。
A．执行算法程序所需要的时间 &&&&&&&&&&&&&B．算法程序的长度
C．算法执行过程中所需要的基本运算次数 &&&D．算法程序中的指令条数
【解析】所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量。
（2）算法的空间复杂度是指（ &&&&&）。
A．算法程序的长度 &&&&&&&&&&&&&&&B．算法程序中的指令条数
C．算法程序所占的存储空间 &&&&&&&D．算法执行过程中所需要的存储空间
【解析】空间复杂度是指执行算法所需要的存储空间。算法所占用的存储空间包括算法程序所占的空间、输入初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
（3）算法指的是（ &&&）。
A．计算机程序 &&&&&&&&&&&&&&&&&&&B．解决问题的计算方法
C．排序算法&&&&&&&&&&&&&&&&&&&&&&D．解决问题的有限运算序列
【解析】所谓算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。
（4）算法能正确地实现预定功能的特性称为算法的（ &&&）。
A．正确性 &&&B．易读性 &&&&&C．健壮性 &&&&&&&D．高效率
【解析】针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。算法与计算公式是有差别的，在设计一个算法时，必须要考虑它的可行性，否则将得不到满意的结果。
（5）递归算法一般需要利用（ &&&）来实现。
A．栈 &&&&&&&B．队列 &&&&&&&C．循环链表 &&&&&D．双向链表
3.2 &穷举搜索法
有一些问题一时难以找到规律或者公式，或者根本没有规律、公式。这时可以利用计算机高速运算的特点，使用穷举来解决。穷举搜索法是穷举所有可能情形，并从中找出符合要求的解决。穷举搜索法所有可能情形，最直观的是联系循环的算法。
例1&&找出n个自然数（…,n）中个数的组合。例如，当，时，所有组 &&&&&&合为：
&&&&&&&&&&&&&5 &&&&&5 &&&&&3
&&&&&&&&&&&&5 &&&&&4 &&&&&2
&&&&&&&&&&&&5 &&&&&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:
&&&&&&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
&&&&&&&&&&&&&&&&&&t:=t+1;writeln(i:3,j:3,k:3);
&&&&&&&&&&&&&&&&
&&&&&&&&writeln('total=',t);
&&&&&&end.
这个程序，穷举了所有可能情形，从中选出符合条件的解，很多情况下穷举搜索法还是常用的。
例2&&算24点（poi24.pas）。&&&&&
【题目描述】
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲。在中国我们把这种游戏称为“算点”。您作为游戏者将得到个～之间的自然数作为操作数，而您的任务是对这个操作数进行适当的算术运算，要求运算结果等于。
您可以使用的运算只有：+，-，×，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，×2)/4是合法的，×(2/4)是不合法的）。下面我们给出一个游戏的具体例子：若给出的个操作数是：、、、，则一种可能的解答是×7=24。
只有一行，四个1～之间的自然数。
如果有解的话，只要输出一个解，输出的是3行数据，分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“”。如果两个操作数有大小的话则先输出大的。如果没有解，则输出“”
&&&&poi24.out
【算法分析】
计算24点主要应用四种运算。开始状态有四个操作数，一个运算符对应两个操作数，所以一开始选择两个操作数分别对四个操作符进行循环检测，每一次运算后产生了新的数，两个数运算变成一个数，整体是少了一个操作数，所以四个数最终是三次运算。由于操作的层数比较少（只有三层），所以可以用回溯的算法来进行检测，当找到一个解时便结束查找。如果所有的情况都找过后仍然没有，则输出无解的信息。
program &poi24;
type arr=array [1..4]
var i,result,n,len:
&&&&r:array [1..3,1..4]
&&&&infile,outfile:
&&assign(outfile,'poi24.out');
&&rewrite(outfile);
&&for i:=1 to 3 do
&&&&&&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,'/')
&&&&&&&&&&&&&&&&
&&&&&&&writeln(outfile,'=',r[i,4])
&&close(outfile);
procedure try(k:d:arr);
var a,b,i,j,l,t:
&&if k=1 then if d[1]=24halt end else
&&&&&else&&begin
&&&&&&&&&&for i:=1 to k-1 do
&&&&&&&&&&for j:=i+1 to k do
&&&&&&&&&&&begin
&&&&&&&&&&&a:=d[i]; b:=d[j];
&&&&&&&&&&&if a&b then begin t:=a;a:=b;b:=
&&&&&&&&&&&t:=0;
&&&&&&&&&&&for l:=1 to k do if (l&&i) and (l&&j) then begin t:=t+1;e[t]:=d[l]
&&&&&&&&&&&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
&&&&&&&&&&&&&
&&&&&&&&&&&&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
&&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);
彩虹7号（rainbow.pas）
X市是一个重要的军事基地，在这个基地中有一支名为“彩虹号”的特别部队。每个队员都有一个固定独立的编号≤X≤215)，他们的职责就是完成部队交给他们的任务，每个任务同样都有固定独立的编号≤N≤10)。在执行任务的过程中，为了保证任务的保密性和队员的安全，队员和队员之间的联系将必须由特别部队所提供的一种保密频段交互设备进行。
每个队员都需要一个身份验证口令进入系统，由于队员所执行的任务都是涉及国家安全或者极高机密的活动，如果队员使用的口令出现错误，他们将付出无法估计的代价。特别部队的队员都是层层筛选的精英人才，所以不希望发生这样的事情。因此队员必须牢记口令的设置方法。
口令S的内容满足：N=X。显然，有可能也很有可能是一个无理数，所以限定为一个实数，它包含整数部分和小数部分，不包含小数点（即将视作）。口令的长度 &&&&&≤M≤50)，将根据任务的难度而有所不同。
编程任务：给定X，，。计算口令的内容。
输入（rainbow .in）：文件输入，文件有且仅有一行包含个整型数，，，每个数之间以一个空格符隔开。
输出（rainbow.out）：文件输出，文件有且仅有一行，为的结果。
样例输入：2 2 10
样例输出：
注意：口令的最后一位请使用去尾法保留，不要使用四舍五入法保留。文件请不要包含多余的空格和换行。
3.3 &递 &归 &法
递归作为一种强有力的数学和算法描述工具在Pascal语言中被广泛使用。一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有定义本身的引用（在过程或自定义函数中，又包含自己调用自己），则称它们是递归的或者是递归定义的。
一个递归算法仅使用少量的程序编码就可描述出解题所需要的多次重复计算而不需要设计循环结构。使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的规模较小的问题来求解，进而最终导致原问题的解决。
例如：n!的定义，我们知道，在数学中n!一般定义为：
&&&&&&&&&&&&&&&&&1 &&&&&&&若n=0
&&&&&&&&&&&n!=
&&&&&&&&&&&&&&&&&n×(n-1)!&&若n&0
在n&0的公式中，又包含了（n-1），这就是递归定义。
利用递归方法，可以用有限的语句来定义对象的无限集合。但在递归定义中，应该至少有一条是非递归的，即初始定义。如上面例子中的第一条，否则就变成了循环定义，产生逻辑性错误。
&&&&n!的递归定义的程序：
&&&&&program&&find＿n；
&&&&&&&var n：integer；
&&&&&&&&&&&&&t：longint；
&&&&&&&procedure &find（n：integer）；
&&&&&&&begin
&&&&&&&&&if &n＝0 &then &t：＝1
&&&&&&&&&&&&&&&&&&&&&else &
&&&&&&&&&&&&&&&&&&&&&&&begin&&find（n-1）；
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&t：＝t＊n &end；
&&&&&&&end；
&&&&&&&begin
&&&&&&&write（'n＝'）；
&&&&&&&readln（n）；
&&&&&&&find（n）；
&&&&&&&writeln（n,'!＝'，t）
&&&&&end．
递归调用（n进栈）达到结束条件时（n=0，赋初值）就停止调用开始返回，再把保存的值取出（n出栈），使n恢复原来的值，并计算，返回主程序，输出结果。
3!递归是如何实现的？
（1）设n=3，开始调用过程find，称为第零层调用。
（2）由于公式2!，必须先求，即程序中的n-1)，此时系统自动先保存的原值，再设n=2，进入第一层递归调用。
（3）因为1!，所以系统又保存，并设n=1，进入第层调用。
（4）因为0!，所以保存，并设n=0，进入第层调用。
（5）因为n=0，终止调用，赋值，返回的入口点。
（6）取出执行时保存的，求出t=1，返回的入口点。
（7）取出执行时保存的，求出t=2，返回的入口点。
（8）取出执行时保存的，求出t=6，返回的入口点。
（9）返回主程序，输出结果：。
从上面分析的过程看到，由于递归调用，需用同一变量名n，但值不同，所以在调用前必须先把n的原值保存，再赋以新值，然后进入调用。调用结束后，再把保存的值取出，使n恢复原来的值。在过程中find中又包含find(n-1)，即又调用了它自己，这就是递归调用。包含有递归调用的算法，就叫做递归算法。
递归调用会产生无终止运算的可能性，因此必须在适当时候终止递归调用，即在程序中必须要有终止条件。上面程序中，过程find的第一条语句就是终止条件。一般地，根据递归定义设计的递归算法中，非递归的初始定义，就用作程序中的终止 &&&条件。
实践证明，不是所有问题都可以用递归的方法处理，用递归算法编写的程序也不一定是好程序。可以看出，执行递归的过程既浪费时间又费存储空间，因此有的语言系统，禁止使用递归，由于计算机存储容量的限制，编译系统也不允许递归。但因递归特别符合人们的思维习惯，递归算法的设计也要比非递归算法设计容易，所以当问题是递归定义，尤其是当涉及的数据结构是递归定义的时候，使用递归算法特别合适。
应用递归算法能够求解的问题一般具有两个特点：
①存在某个特定条件，在此条件下，可得到指定的解，即递归在终止状态。
②对任意给定的条件，有明确的定义规则，可以产生新的状态并将最终导出终止状态，即存在导致问题求解的递归步骤。
递归是用栈来实现的。不过，递归恐怕不像想象得这么简单。首先，它体现了一个数学思想：化归，即把一个问题转化成另一个的方法。递归比较特殊，它是转化成性质相似，但规模更小的问题。
例3&&阅读程序NOIp2001_G。
program gao7_1;
&&function ack(m,n:integer):
&&&&if&m=0 then&ack:=n+1&
else if n=0 then ack:=ack(m-1,1)else ack:=ack(m-1,ack(m,n-1))
begin writeln(ack(3,4));
这个程序我们可以用下面的函数表示。在解题时，一般都是用递归的方法去实现的，而递归方法将会计算五千多步，在竞赛时这种方法是不可用的，而递归往往可以用递推去实现，因此，我们在教学过程中就讲解了该函数的递推过程，现将推导过程表示如下：
（1）我们在递归过程中发现该函数总是要调用到=0，=1及=2的情况，因此，我们就考虑要推导（，）必须首先推导（，），（，）以及（，）的情况。
（2）（，）可以由函数直接得到，公式为（，）=N+1
（3）（，）=ACK（，）=1+1=0+2
& &&&ACK（，）=ACK（，（，））=ACK（，+1）=1+1+1=1+2
&&&&&ACK（，）=ACK（，（，））=ACK（，+2）=1+1+2=2+2
因此，我们可以联想到ACK（，）=N+2。这个公式可以用数学归纳法证明之。（略）
根据上面的方法，我们可以方便地推导出下面一些公式：
（4）（，）=ACK（，）=1+2=3（利用=1的公式）
&&&&&ACK（，）=ACK（，（，））=ACK（，+2）=3+2=5
（利用M=1的公式及（，））
ACK（，）=ACK（，（，））=ACK（，）=5+2=（2+1）*2+1
因此，我们可以联想到ACK（，）=（N+1）*2+1。同样，这个公式可以用数学归纳法证明之。（略）
（5）（，）=ACK（，）=(1+1)*2+1=5（利用=2的公式）
ACK（，）=ACK（，（，））=ACK（，）=（(1+1)*2+1+1）*2+1=2^3+2^2+1
ACK（，）=ACK（，（，））=ACK（，）=（2^3+2^2+1+1）*2+1=2^4+2^3+2^2+1=2^5-3
因此，我们可以联想到ACK（，）=2^(N+3)-3。
例4&&仍以例1为例，找个数的个数的组合。
&&&&&&&&输入：n，，
&&&&&&&&输出：5 &&&&&4 &&&&&3
&&&&&&&&&&&&&&5 &&&&&4 &&&&&2
&&&&&&&&&&&&&&5 &&&&&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 &&&&{组合的总数
分析：所提示的10组数。首先固定第一位数（如），其后是在另个数中再“组合”个数。这就将“个数中个数的组合”推到了“个数中个数的组合”上去了。第一位数可以是，（如，），个数中个数组合递推到-1个数中-1个数有组合，这是一个递归的算法。即：
&&&var &i:
&&&&begin &for &i:=n &downto &r &do
&&&&&&begin &
{固定i的输出位置}
&&&&&&&&comb(i-1,r-1); &
{原过程递推到i-1个数的r-1个数组合}
再考虑打印输出格式。
&&var &k,n,r:
&&&&Produrce &&comb(n,r:integer);
&&&&var &i,temp:
&&&&&begin &for &i:=n &downto &r &do
&&&&&&&if &(i&&n)and(k&&r) &then &&&
{k为过程外定义的}
&&&&&&&&&begin for temp:=1 to &(k-r)*3 &do &write(' &'); {确定i的输出位置}
&&&&&&&write(i:3);
&&&&&&&if i&1 then comb(i-1,r-1); &
{递推到下一情形}
&&&&&write('n,r=');readln(n,r);
&&&&&if &r&n &then
&&&&&&&begin &writeln('Input n,r error!');
&&&&&comb(n,r); &
{调用递归过程}
1．邮票面值设计（postag.pas）
【题目描述】
给定一个信封，最多只允许粘贴N张邮票，计算在给定（≤40) 种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大，使得-max之间的每一个邮资值都能得到。
例如，N=3，=2，如果面值分别为分、分，则在～6分之间的每一个邮资值都能得到（当然还有分、分和分）：如果面值分别为分、分，则在～7分之间的每一个邮资值都能得到。可以验证当，=2时，分就是可以得到连续的邮资最大值，所以max=7，面值分别为分、分。
【样例输入】
3 2&&{输入第一个数，第二个数，中间用空格间隔
【样例输出】
1 3&&&&{输出的第一行面值分别为l分、分}
max=7&{输出的第二连续的邮资最大值}
2．聪明的学生（guess.pas）
【题目描述】
一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A，和。有一天教授给他们人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。
这时，教授先对学生A发问了：“你能猜出自己的数吗？”回答：“不能。”
教授又转身问学生B：“你能猜出自己的数吗？”想了想，也回答：“不能。”
教授再问学生C同样的问题，思考了片刻后，摇了摇头：“不能。”
接着，教授又重新问A同样的问题，再问和，……，经过若干轮的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误地报了出来。
现在，如果告诉你：教授在第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是，你能推断出另外两个学生的头上贴的是什么数吗？
在没有人猜出自己头上的数之前，大家对教授提问的回答始终都是“不能”；而且除此之外在，，之间是没有进行任何信息交流的。也就是说，每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授的提问所做出的否定回答。
教授总是从学生A开始提问的。
你可以假定，这3个聪明的学生能够根据已知的条件在最早的轮次猜出自己的数，并且永远都不会猜错。稍经分析和推理，你将得出以下结论：总是头上贴着最大的那个数的人最先猜出自己头上的数。
【输入文件】
输入文件为guess.in。
该文件包括若干组测试数据，其中的每一行代表一组测试数据，由两个整数N和组成（即在教授第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M）。两个数之间用空格分隔开。最后，由-1 -1组成的一行标志着输入的数据结束。同时要求，＜＜＜＜。
【输出文件】
输出文件为guess.out。按照输入文件中的顺序依次给出各组数据的结果。
文件中对应每组数据输出的第一行是一个整数p，是可能情况的总数。接下来的p行，每一行包括个数，分别为贴在、、头上的个数。输出时，所有解按照头上的数增序排列；在头上的数相同的情况下，按照头上的数增序排列。
【样例输入】
【样例输出】
3.4 &回 &溯 &法
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构
例5&&再以例1说明，找个数中个数的组合。
分析：将自然数排列在数组A中。
&&&&&&A[1] &&&A[2] &&&A[3]
&&&&&&&5 &&&&&&4 &&&&&&3
&&&&&&&5 &&&&&&4 &&&&&&2
&&&&&&&3 &&&&&&2 &&&&&&1
排数时从A[1]到再到，后一个至少比前一个数小，并且应满足＞r。若≤就要回溯，该关系就是回溯条件。为直观起见，当输出一组组合数后，若最后一位为，也应作一次回溯（若不回，便由上述回溯条件处理）。
program &zuhe3;
&&type &tp=array[1..100]
&&&var &n,r:
procedure &comb2(n,r:a:tp);
&&&&&var &i,ri:
&&&&&&begin &ri:=1;a[1]:=n;
&&&&&&&&repeat &
&&&&&&&&&if &ri&&r &then &&
{没有搜索到底}
&&&&&&&&&&&if &ri+a[ri]&r &then &&&
｛判断是否回溯｝
&&&&&&&&&&&&&&&&&begin &
&&&&&&&&&&&&&&&&&&&a[ri+1]:=a[ri]-1;
&&&&&&&&&&&&&&&&&&&ri:=ri+1; &&&&&&&&&&&& {向前搜索}
&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&&&begin &ri:=ri-1;
a[ri]:=a[ri]-1;
&&&&&&&&&&else
&&&&&&&&&&&&begin &&for &j:=1 &to &r &do &write(a[j]:3);
{输出组合数}
&&&&&&&&&&&&&&if &a[r]=1 &then &
{是否回溯}
&&&&&&&&&&&&&&&&begin &ri:=ri-1;
a[ri]:=a[ri]-1;
&&&&&&&&&&&&&&else &a[ri]:=a[ri]-1; &
{递推到下一个数｝
&&&&&&&&&&&&
&&&&&&&&until &a[1]&&r-1;
begin &write('n,r=');
readln(n,r);
&&&&&&&if &r&n &then &begin &writeln('Input n,r error!');
&&&&&&&comb2(n,r);
&&&&&&&end.
1．马拦过河卒（knight.pas）
【题目描述】
棋盘上A点有一个过河卒，需要走到目标点。卒行走的规则：可以向下、或者向右。同时，在棋盘上点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点（）、点（）（为不超过的整数），同样马的位置坐标是需要给出的。现在要求你计算出卒从点能够到达点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
一行四个数据，分别表示B点坐标和马的坐标。
一个数据，表示所有的路径条数。
knight.out
2．走迷宫（maze.pas）&&&&&&&
【题目描述】
有一个m×n格的迷宫（表示有行、列），其中有可走的也有不可走的，如果用表示可以走，表示不可以走，文件读入这×n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-l表示无路）。
第一行是两个数m，＜＜，接下来是行列由和组成的数据，最后两行是起始点和结束点。
所有可行的路径，描述一个点时用（x,y）的形式，除开始点外，其他的都要用“→”表示方向。如果没有一条可行的路则输出-1。
【样例输入】
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
【样例输出】
(1,2)→→→→→→→→→→→→→
(1,1)→→→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→→→→→
(1,1)→→→→→→→→→→→
(1,1)→→→→→→→→→
3．组合的输出（track.pas）&&
【题目描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出个元素（不分顺序且≤n），我们可以简单地将个元素理解为自然数…，从中任取个数。现要求你不用递归的方法输出所有组合。
例如：n＝，＝，所有组合为：
l 2 3；l 2 4；1 2 5；l 3 4；l 3 5；1 4 5；2 3 4；2 3 5；2 4 5；3 4 5。
一行两个自然数n、＜＜，≤r≤n)。
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占3个字符的位置，所有的组合也按字典顺序。
【样例输入】
【样例输出】
3.5 &递 &&&推
递推是迭代算法中一种用若干步可重复的简单运算来描述复杂数学问题的方法，以便于计算机进行处理。它与递推关系的思想完全一致，由边界条件开始往后逐个推算，在一般情况下，效率较高，编程也非常的方便。但是，我们一般只需要求递推关系的第n项，而边界条件与第项前面之间的若干项的信息是我们不需要的，如果采用递推的方法来求解的话，第项之前的每一项都必须计算出来，最后才能得到所需要的第项的值。这是递推无法避免的，从而在一定程度上影响了程序的效率。当然在大多数情况下，采用递推的方法还是可行的，在竞赛中，使用递推的方法编程，通常会在时限内出解。当然，更好的求解方法还有母函数法、迭代归纳法等。
例1&&青蛙过河（frog.pas）。
【题目描述】
有一条河，左边一个石墩（A区）上有编号为，，，，…，的只青蛙，河中有个荷叶（区），还有个石墩（区），右边有一个石墩（区），如图所示。只青蛙要过河（从左岸石墩到右岸石墩），规则为：
图3-1 &青蛙过河示意图
（1）石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙（不论大小）。
（2）青蛙可以：→（表示可以从跳到，下同），→，→，→，→，→，→。
（3）当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大号的青蛙上面。
你的任务是对于给出的h、，计算并输出最多能有多少只青蛙可以根据以上规则顺利 &过河？
【样例输入】
2 3 &&{河中间有个石礅，个荷叶
【样例输出】
16 {最多有只青蛙可以按照规则过河
【算法分析】
从具体到一般，推导过程如下：
f(0,k)=k+1;
{如时，有只青蛙可以过河
f(1,k)=2(k+1); `
以此类推：f(2,k)=(2×(k+1))×2=22(k+1);
结论为：f(h,k)=2h(k+1)
program frog(input,output);
var h,k,i,s:
&&assign(input,'frog.in');
&&assign(output,'frog.out');
&&reset(input);
&&rewrite(output);
readln(h,k);
for i:=1 to h do&s:=s*2;
writeln(s);
close(input);close(output)
例2&&排序集合（sort.pas）。
【题目描述】
对于集合N={1,2,…的子集，定义一个称之为“小于”的关系：设1={X1,X2,…i}，（1＜X2＜…＜Xi），S2={Y1, Y2, …j}，（1＜Y2＜…＜Yj），如果存在一个k，（≤≤），使得1=Y1，…，k=Yk，且k=i或(k+1)&＜Y(k+1)，则称S1“小于”2。
你的任务是，对于任意的n(n≤及n)，求出第小的子集。
输入文件仅一行，包含两个用空格隔开的自然数，n和。
输出文件仅一行，使该子集的元素，由小到大排列。空集输出0。
【样例输入】
【样例输出】
【算法分析】
我们知道，n个元素构成的集合有n种情况。本题的意思是：把这些集合按照某种规则排序，然后输入k，输出第个集合。所以排序的规则是本题的关键，其实很简单，当＝时，个集合排序如下：＜＜＜＜＜＜＜，你发现规律了吗具体算法为：先推出第小的一个子集的第一个数宇是多少，第一个数字确定了之后，再推出第二个数字，从第一个数字加一直计算累加集合个数，直到得到不超过的最大的那个数字，就是第二位数字，这样一直递推，推到最后一个。注意：终止条件是有了个数字或者第个数字为空，这时递推终止，输出最后的结果。
program sort(input,output);
&&type arr=array[0..31]
&&&&&&n,i,j,k:
&&&&assign(input,'sort.in');
&&&&assign(output,'sort.out');
reset(input);
rewrite(output);
&&&&readln(n,k);
&&&&fillchar(a,sizeof(a),0);
&&&&a[n]:=1; a[0]:=1;
&&&&for i:=n-1 downto 1 do &&&&&{a[i]=2i-n}
&&&&&&a[i]:=a[i+1]*2;
&&&&&&i:=0; j:=1;
&&&&&&while k&1 do &&&&&&&&&&&&&&&{以下为一位一位推出数字}
&&&&&&begin
&&&&&&&&while (i&=n) and (k&a[i]) do
&&&&&&&&&&begin
&&&&&&&&&&&&dec(k,a[i]);
&&&&&&&&&&&&inc(i)
&&&&&&&&&&
&&&&&&&&if j&&1 then write(' ');
&&&&&&&&inc(j);
&&&&&&&&write(i);
&&&&&&&&a[i]:=1
&&&&if i=0 then writeln(0);{判空集}
&&&&close(input);close(output)
例3&&诸侯安置（empire.pas）。
【题目描述】
很久以前，有一个强大的帝国，它的国土成正方形状，如图3-2所示。
图3-2 &诸侯安置示意图（原图）
这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地（正方形中的一格）。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如图3-3为时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。
&&&&&&&&&&&&&（1） &&&&&&&&&&&&&&&&&&&&&&&&&&&（） &&&&&&&&&&&&&&&&&&&&&&&&&（）
图3-3 &诸侯安置示意图
致使国家动荡不安国王也不愿意看到他的诸侯们互相开战，因此，他希望通过合理地安排诸侯所处的位置，使他们两两之间都不能攻击。
现在，给出正方形的边长n，以及需要封地的诸侯数量，要求你求出所有可能的安置方案数。n≤，≤2-2n+1)。由于方案数可能很多，你只需要输出方案数除以的余数即可。
仅一行，两个整数n和，中间用一空格隔开。
一个整数，表示方案数除以504的余数。
【样例输入】
【样例输出】
【样例说明】
四种安置方案如图3-4所示。
注意：镜面和旋转的情况属于不同的方案。
&&&&&&&&&&&&&&&&&&&&（1） &&&&&&&（） &&&&&&（） &&&&&&&&（）
图3-4 &安置方案
【算法分析】
重新描述一下问题，其实就是在一个边长为2n-1的正菱形（如图为的情形）上摆放个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种
看到这道题目，我们就会立即想起一道经典的老题目：n皇后问题。这道题目与皇后问题非常相似。但有两个不同点：一是皇后问题可以斜着攻击对方棋子，而本题不能；二是皇后问题是在，的正方形棋盘上面放置个皇后，而本题却是在一个正菱形上摆放。我们试着先将皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，皇后的公式是：2×k!。但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。
首先，想到在2n-1列中任意取出列进行具体分析，这样一来问题就转化成：有一个长为的数列（无重复元素），每一个数在一个不定的区间当中，第个数一定在区间i,bi]之间，求这样的数列有多少种？如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度排一下序，就可以看出来，再用乘法原理进行求解即可。但是，最多可到，最多可到，穷举要进行种方案！显然无法在规定的时间内出解！那么怎么办呢？再继续分析一下问题发现，里面有重叠子问题。如果一个列作为最后一列，且这一列以及前面所有列共放置个诸侯，设有种情况，那么这一列后面的所有列共放置个棋子的方案数都要用到，从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图的形式（即列排序）。
设f[i,j]表示以第列为最后一列，放置个棋子的总方案数，得出公式：
注意：当k≥-1时，问题无解。
var i,j,k,n,l,s:
&&&&f:array[1..200,1..200]
function make(p:longint):
&&&&if odd(p) then make:=p else make:=p-1;
&&assign(input,'empire.in');reset(input);
&&assign(output,'empire.out');rewrite(output);
&&readln(n,k);
&&if k=0 then begin writeln(1);close(output);halt
&&if k&=2×n-1 then begin writeln(0);
close(output);
&&for i:=1 to 2×n-1 do
&&&&if odd(i) then f[i,1]:=i else f[i,1]:=i-1;
&&for i:=1 to 2×n-1 do
&&&&for j:=2 to i do
&&&&&&for l:=1 to i-j+1 do
&&&&&&&&f[i,j]:=(f[i,j]+f[i-l,j-1]&×(make(i)-j+1)) mod 504;
&&i:=2×n-1;
&&if k=1 then begin writeln((i×(i+1) div 2-i div 2) mod 504);
close(output);halt end else
&&&&for i:=k to 2×n-1 do inc(s,f[i,k]);
&&writeln(s mod 504);
&&close(input);
close(output);
行家的预算（travel.pas）
【题目描述】
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量（以升为单位）。每升汽油能行驶的距离D2、出发点每升汽油价格和沿途油站数（可以为零），油站离出发点的距离、每升汽油价格＝,2,…N)（计算结果四舍五入至小数点后两位）。如果无法到达目的地，则输出“o solution”。 &
第一行，第一个数两个城市之间的距离D2，第二个数汽车油箱的容量C，第三个数每升汽油能行驶的距离D2，第四个数出发点每升汽油价格P，第五个数沿途油站数N。
从第二行开始，每行有两个数，第一个数为油站i离出发点的距离，第二个数为每升汽油价格Pi，中间用空格间隔。
【样例输入】
275.6 &11.9 &27.4 &2.8 &2
102.0 &2.9 &&&&&&&&&&&
220.0&&2.2 &&&&&&&&&&
【样例输出】
26.95（该数据表示最小费用）
【算法分析】
看到题目后，很容易想到递推。事实上，要用的油是确定的（D1/D2），价钱最便宜的油的站的油显然应该多买，到达这个油站时汽车剩油不为的方案一定不是最优的。这是因为，如果剩下升油，显然不如当初少买升，改在这里买升划算！（最便宜嘛！）
每次都假装装满油，用的时候先用便宜的，因为把贵的留在后面“反悔”！这样计算费用时只考虑真正使用的。可以用优先队列（用堆来实现）来进行替换和使用油。也可以模拟但效率不高。
3.6 &模拟搜索（最原始的方法）
模拟题。按常规思想：逐步地模拟，直至又回到初始状态时为止。但这样全部模拟基本上无法在规定的时间内出解，必须做一些改进。模拟题并不需要太多的算法知识，主要考察选手的数据结构的应用以及编程能力。&
例1&&津津的储蓄计划（save.pas）。
【题目描述】
津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。
为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%利息、连本带息还给津津。因此，津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。
例如，11月初津津手中还有元，妈妈给了津津元。津津预计月的花销是元，那么她就会在妈妈那里存元，自己留下元。到了月末，津津手中会剩下元钱。
津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。
现在请你根据2004年月到月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到年年末，妈妈将津津平常存在她那里的钱加上20%的利息，一并还给津津之后，津津手中会有多少钱。
输入文件save.in包括行数据，每行包含一个小于的非负整数，分别表示月到月津津的预算。
输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，表示出现这种情况的第一个月；否则输出到年年末津津手中会有多少钱。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【算法分析】
最简单、最基本的模拟加判断，连数组都不用开。只要读清题目，然后动手做就可以了。解决此类问题没有什么技巧，最重要的是不在关键时刻出现低级错误。
var f1,f2:
&&&&a:array[1..12]
&&&&i,tol,s:
&assign(f1,'save.in');
&reset(f1);
&assign(f2,'save.out');
&rewrite(f2);
&tol:=0;s:=0;
&for i:=1 to 12 do
&&&readln(f1,a[i]);
&&&tol:=tol+300-a[i];
&&&if tol&0 then
&&&&&writeln(f2,'-',i);
&&&&&close(f2);
&&&s:=s+100*(tol div 100);
&&&tol:=tol mod 100;
&writeln(f2,tol+s+s div 5);
&close(f2);
例2&&小球钟（ball.pas）。
【问题描述】
时间是运动的一种方式。我们常常用运动来度量时间。例如，小球钟是一个通过不断在轨道上移动小球来度量时间的简单设备。每分钟，一个转动臂将一个小球从小球队列的底部挤走，并将它上升到钟的顶部并将它安置在一个表示分钟，5分钟，分钟和小时的轨道上。这里可以显示从：～：（这正是奇怪之处）范围内的时间，若有个球在分钟轨道，个球在分钟轨道，个球在分钟轨道及个球在小时轨道上，就显示时间：。
当小球通过钟的机械装置被移动后，它们就会改变其初始次序。仔细研究它们次序的改变，可以发现相同的次序会不断出现。由于小球的初始次序最后迟早会被重复，所以这段时间的长短是可以被度量的，这完全取决于所提供的小球的总数。
小球钟的运作：每分钟，最近最少被使用的那个小球从位于球钟底部的小球队列被移走，并将上升并安置于显示分钟的轨道上，这里可以放置4个小球。当第个小球滚入该轨道，它们的重量使得轨道倾斜，原先在轨道上的个小球按照与它们原先滚入轨道的次序相反的次序加入到钟底部的小球队列。引起倾斜的第个小球滚入显示分钟的轨道。该轨道可以放置个球。当第个小球滚入该轨道，它们的重量使得轨道倾斜，原先个小球同样以相反的次序加入钟底部的小球队列。而这第个小球滚入了显示分钟的轨道。这里可以放置个小球。当第个小球滚入该轨道，它们的重量使得轨道倾斜，原先在轨道上的个小球按照与它们原先滚入轨道的次序相反的次序加入到钟底部的小球队列，而这第个小球滚入了显示小时的轨道。该轨道同样可以放置个球，但这里有一个外加的固定的不能被移动的小球，这样小时的值域就变为～。从分钟轨道滚入的第个小球将使小时轨道倾斜，这个球同样以相反的次序加入钟底部的小球队列，然后那第个小球同样加入钟底部的小球队列。
输入定义了一序列的小球时钟。每个时钟都按照前面描述的那样运作。所有时钟的区别仅在于它们在1：时钟启动时刻小球初始个数的不同。在输入的每行上给出一个时钟的小球数，它并不包括那个在小时轨道上的固定的小球。合法的数据应在～之间。表明输入的结束。
输出中每一行只有一个数，表示对应的输入情形中给出的小球数量的时钟在经过多少天的运行可以回到它的初始小球序列。
【样例输入】
【样例输出】
【算法分析】
该题是典型的模拟题。按常规思想：逐分钟地模拟小球钟的运作，直至钟底部的小球队列重又回到初始状态时为止。这期间流逝的天数即为小球钟的运作周期。但这样全部模拟基本上无法在规定的时间内出解，必须做一些改进。
于是，我们想到通过模拟出每个小球回到原来位置上所需的天数，然后求它们的最小公倍数。但是，如果仍是单纯的模拟，速度仍然很慢。我们可以先模拟小球钟最先24小时的运行情况，得到一天后的钟底部的新小球队列。有了这个条件后，我们可以在两次的钟底部小球队列间建立起一种置换。设初始时，钟底部的小球编号依次是：,2,3,…n。一天后，钟底部的小球编号依次是：,p2,p3,…pn。则我们可以建立这样的置换：
1& 2& 3 …&n
p1 p2 p3 …&pn
注意到小球钟的运作规则保证了上述置换是不变的，就可以计算出小球钟运行48小时后，72小时后……，钟底部的小球队列情况，直至队列情况重新是1,2,3,…,n。这样，在求得以上置换的基础上，我们可以求每一个小球回到原位置的周期，然后求它们的最小公倍数即可。
program ball
var&n, i : m1, m2, m3, m4, m : c, c2 : now, long :
function gcd(a, b : longint) :
&&if b = 0 then gcd := a
&&else if b = 1 then gcd := 1
&&else gcd := gcd(b, a mod b);
function reverse(s : string) :
&&s2 := '';
&&while s && '' do
&&&&s2 := s[1] + s2;
&&&&delete(s, 1, 1);
&&reverse := s2;
&&assign(input, 'ball.in'); reset(input);
&&assign(output, 'ball.out'); rewrite(output);
&&readln(n);
&&while n & 0 do
&&&&m := '';
&&&&for i := 1 to n do m := m + chr(i);
&&&&repeat
&&&&&&c := m[1];
&&&&&&delete(m, 1, 1);
&&&&&&if length(m1) & 4 then m1 := m1 + c
&&&&&&else
&&&&&&&&begin
&&m := m + reverse(m1);
&&m1 := '';
&&if length(m2) & 2 then m2 := m2 + c
&&&&&&&&&&else
&&&&&&&&&&&&begin
&&&&&&m := m + reverse(m2);
&&&&&&m2 := '';
&&&&&&if length(m3) & 3 then m3 := m3 + c
&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&begin
&&&&&&&&&&m := m + reverse(m3);
&&&&&&&&&&m3 := '';
&&&&&&&&&&if length(m4) & 23 then m4 := m4 + c
&&&&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&&&&&begin
&&&&&&m := m + reverse(m4) +
&&&&&&m4 := '';
&&&&until (m1 ='') and (m2 = '') and (m3 = '') and (m4 = '');
&&&&now := 1;
&&&&for i := 1 to length(m) do
&&&&&&if m[i] && #0 then
&&&&&&begin
c := m[i];
&&&&&&&&m[i] := #0;
&&&&&&&&long := 1;
while m[ord(c)] && #0 do
&&&&&&&&begin
&&&&&&&&&&inc(long);
&&c2 := m[ord(c)];
&&&&&&&&&&m[ord(c)] := #0;
&&c := c2;
&&&&&&&&now := (now * long) div gcd(now, long);
&&&&writeln(now);
&&&&readln(n);
&&close(output);
&&close(input);
例3&&奶牛（eat.pas）。
【题目描述】
一个农夫有n（≤1000）头奶牛，可由于产奶太少，他决定把当天产奶最少的牛杀掉，但他有点舍不得，如果当天不只一头奶牛产奶，至少他便放过它们。这些奶牛产奶是周期性的，他已开始就想知道有多少奶牛可幸免遇难（可能会被全杀），每头奶牛周期不会超过（每头奶牛产奶量≤250）。
注：T——数据总数
N——奶牛总数
第一头奶牛周期天数，每天产奶数；
第二头奶牛周期天数，每天产奶数；
第n头奶牛周期天数，每天产奶数。
【样例输入】
【样例输出】
注：2——最后剩下2头奶牛
&&&&&& 6——最后一头牛是在第六天被杀的
【算法分析】
直述型模拟，每头奶牛产奶数 P:= p mod n +1；找最小值，最小值奶牛；用哈希表判奶牛是否死亡；注意每个数据的初始化。
program eat
var h,p,pro:array [1..1000+10]
&&&&m:array [1....250]
&&&&del:array [1..1000+10]
&&&&k,i,j,round,n:
&&&&ob,min,ans,ans2,now,change:
&&&&assign(input,'eat.in');reset(input);assign(output,'eat.out'); rewrite(output);
&&&&readln(k);
&&&&for round:= 1 to k do
&&&&&&&&fillchar(h,sizeof(h),0);
&&&&&&&&fillchar(m,sizeof(m),0);
&&&&&&&&fillchar(del,sizeof(del),0);
&&&&&&&&fillchar(pro,sizeof(pro),0);
&&&&&&&&ans:=0; &ans2:=0; &change:=0;
&&&&&&&&readln(n);
&&&&&&&&for i:= 1 to n do
&&&&&&&&begin
&&&&&&&&&&&&read(p[i]);
&&&&&&&&&&&&for j:= 1 to p[i] do read(m[i,j]);
&&&&&&&&&&&&
&&&&&&&&fillchar(h,sizeof(h),0);
&&&&&&&&while true do
&&&&&&&&begin
&&&&&&&&&&&inc(ans);
&&&&&&&&&&&for i:= 1 to n do&if not del[i] then
&&&&&&&&&&&begin
&&&&&&&&&&&&&h[i]:=h[i] mod p[i] +1;
&&&&&&&&&&&&&pro[i]:=m[i,h[i]];
&&&&&&&&&&&
&&&&&&&&&&&min:=
&&&&&&&&&&&for i:= 1 to n do if not del[i] then
&&&&&&&&&&&&&if pro[i]&min then min:=pro[i];
&&&&&&&&&&&&&&now:=0;
&&&&&&&&&&&for i:= 1 to n do if not del[i] then
&&&&&&&&&&&if pro[i]=min then begin inc(now); ob:=
&&&&&&&&&&&if now=1 then begin del[ob]:= ans2:= change:=0;
&&&&&&&&&&&else inc(change);
&&&&&&&&&&&if change&500
&&&&&&&&&&&allk:= for i:= 1 to n do if not del[i] then allk:=
&&&&&&&&&&&
&&&&&&&&ans:=0;
&&&&&&&&for i:= 1 to n do if not del[i] then inc(ans);
&&&&&&&&writeln(ans,' ',ans2);
&&&&close(input); &close(output);
例4&&猫和老鼠（catmou.pas）。
【题目描述】
猫和老鼠在10×10的方格中运动（如图），例如：
*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......
图3-6 &猫和老鼠在×10方格中的运动图
M=老鼠（）
猫和老鼠每秒中走一格，如果在某一秒末它们在同一格中，我们称它们“相遇”。
注意：“对穿”是不算相遇的。猫和老鼠的移动方式相同：平时沿直线走，下一步如果会走到障碍物上去或者出界，就用秒的时间做一个右转°。一开始它们都面向北方。
编程计算多少秒以后他们相遇。
【输入】10行，格式如图所示。
【输出】相遇时间T。如果无解，输出-1。
【样例输入】
&*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......
【样例输出】
【算法分析】
题目没什么好的办法，只有模拟猫和老鼠。
program catmon
&&ipt,opt:
&&a:array[0..11,0..11]
&&i,b,cl,cw,ml,mw,aim,bim:
&&assign(ipt,'catmou.in'); assign(opt,'catmou.out');
&&reset(ipt);
&&rewrite(opt);
&&&for i:=1 to 10 do
&&&&&for b:=1 to 9 do
&&&&&&read(ipt,a[b,i]);
&&&&&readln(ipt,a[10,i]);
&&&for i:=0 to 11 do
&&&&&a[i,0]:='*';
&&&&&a[i,11]:='*';
&&&&&a[0,i]:='*';
&&&&&a[11,i]:='*';
&&&for i:=1 to 10 do
&&&for b:=1 to 10 do
&&&&&if a[i,b]='C' then
&&&&&&begin
&&&&&&&cw:=b;
&&&&&&&cl:=i;
&&&&&if a[i,b]='M' then
&&&&&&begin
&&&&&&&mw:=b;
&&&&&&&ml:=i;
&&&aim:=1; bim:=1; k:=0;
&&&&if k&99999 then begin k:=-1;
&&&&inc(k);
&&&&if aim=1 then
&&&&&begin
&&&&&&if a[ml,mw-1]='*' then inc(aim);
&&&&&&if a[ml,mw-1]&&'*' then mw:=mw-1;
&&&&&begin
&&&&&if aim=2 then
&&&&&begin
&&&&&&if a[ml+1,mw]='*' then inc(aim);
&&&&&&if a[ml+1,mw]&&'*' then ml:=ml+1;
&&&&&begin
&&&&&if aim=3 then
&&&&&begin
&&&&&&if a[ml,mw+1]='*' then inc(aim);
&&&&&&if a[ml,mw+1]&&'*' then mw:=mw+1;
&&&&&begin
&&&&&if aim=4 then
&&&&&begin
&&&&&&if a[ml-1,mw]='*' then aim:=1;
&&&&&&if a[ml-1,mw]&&'*' then ml:=ml-1;
&&&&&if bim=1 then begin
&&&&&&if a[cl,cw-1]='*' then inc(bim);
&&&&&&if a[cl,cw-1]&&'*' then cw:=cw-1;
&&&&&begin
&&&&&if bim=2 then begin
&&&&&if a[cl+1,cw]='*' then inc(bim);
&&&&&if a[cl+1,cw]&&'*' then cl:=cl+1;
&&&&&begin
&&&&&if bim=3 then begin
&&&&&&if a[cl,cw+1]='*' then inc(bim);
&&&&&&if a[cl,cw+1]&&'*' then cw:=cw+1;
&&&&&&else
&&&&&&begin
&&&&&if bim=4 then begin
&&&&&&if a[cl-1,cw]='*' then bim:=1;
&&&&&&if a[cl-1,cw]&&'*' then cl:=cl-1;
&&&&&until (cl=ml) and (cw=mw);
&&&&&write(opt,k);
&&&&&close(ipt); close(opt);
例5&&字母运算（cowcul.pas）。
【题目描述】
有4个字母：、、、，它们可以相加，也能产生进位，如图所示：，，但他要进位现有个由上述字母构成的“数”（五位），只对第个数进行操作，有种操作。
图3-7 &字母运算示意图
A：把第个数变成两数之和；
L：在数后加一个（对进行操作后为，相当于字符串相加）；
R：在数前加一个（同上），去掉末位。
现给你两个数以及3个操作，再给你一个数（位），把两数最前面连续的去掉（变成），判断是否相等，相等输出，不等则输出。
【样例输入】
【样例输出】
COWCULATIONS OUTPUT
END OF OUTPUT
【算法分析】
此题为模拟题。做法：题目转换。题目中的U、、、，其实都是忽悠你的，说白了就是对应了四进制的加法、进位、让位等操作；这样题目就转换成了读入两个四进制数然后按操作与第三个数对比大小即可。时间：。
type num=array [0..100]
var a,b,x:
&&&&tests,round,i,j:
function magic(c:char):
&&&&case c of
&&&&'V': exit(0);
&&&&'U': exit(1);
&&&&'C': exit(2);
&&&&'D': exit(3);
&&&&exit(0);
function max(a,b:longint):
&&&&if a&b then exit(a) else exit(b);
procedure dd(var a: n:longint);
var l,r,t:
&&&&l:=1; r:=n;
&&&&while l&r do
&&&&&&&&t:=a[l]; a[l]:=a[r]; a[r]:=t;
&&&&&&&&inc(l); dec(r);
&&&&while a[n]=0 do dec(n);
&&&&a[0]:=n;
procedure sum(a: var b:num);
var l,r,t,i:
&&&&l:=max(a[0],b[0]);
&&&&for i:= 1 to l do
&&&&&&&&inc(b[i+1],(a[i]+b[i]) div 4);
&&&&&&&&b[i]:=(a[i]+b[i]) mod 4;
&&&&if b[l+1]&&0 then b[0]:=l+1 else b[0]:=l;
procedure add(var b:num);
&&&&for i:= b[0] downto 1 do b[i+1]:=b[i];
&&&&b[1]:=0;
&&&&inc(b[0]);
procedure dda(var b:num);
&&&&for i:= 2 to b[0] do b[i-1]:=b[i];
&&&&b[b[0]]:=0; &dec(b[0]);
function Compare(a,b:num):
&&&&l:=max(b[0],a[0]);
&&&&for i:= 1 to l do
&&&&if b[i]&&a[i] then exit(false);
&&&&exit(true);
&&&&assign(input,'cowcul.in'); reset(input);
&&&&assign(output,'cowcul.out'); rewrite(output);
&&&&writeln('COWCULATIONS OUTPUT');
&&&&readln(tests);
&&&&for round:= 1 to tests do
&&&&&&&&fillchar(a,sizeof(a),0);
&&&&&&&&fillchar(b,sizeof(b),0);
&&&&&&&&fillchar(x,sizeof(x),0);
&&&&&&&&for i:= 1 to 5 do begin read(c); a[i]:=magic(c) dd(a,5);
&&&&&&&&for i:= 1 to 5 do begin read(c); b[i]:=magic(c) dd(b,5);
&&&&&&&&for i:= 1 to 3 do
&&&&&&&&begin
&&&&&&&&&&&&readln(c);
&&&&&&&&&&&&case c of
&&&&&&&&&&&&'A': sum(a,b);
&&&&&&&&&&&&'L': add(b);
&&&&&&&&&&&&'R': dda(b);
&&&&&&&&&&&&
&&&&&&&&for i:= 1 to 8 do begin read(c); x[i]:=magic(c) dd(x,8);
&&&&&&&&if compare(b,x) then writeln('YES') else writeln('NO');
&&&&&&writeln('END OF OUTPUT');
&&&&&close(input); close(output);
例6&&内存分配（memory.pas）。
【题目描述】
内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。经典的内存分配过程是这样进行的：
（1）内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址开始的个连续的内存单元称为首地址为长度为的地址片。
（2）运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数及运行时间。在运行时间内（即时刻开始，时刻结束），这个被占用的内存单元不能再被其他进程使用。
（3）假设在T时刻有一个进程申请个单元，且运行时间为，则：
①若T时刻内存中存在长度为的空闲地址片，则系统将这个空闲单元分配给该进程。若存在多个长度为个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
②如果T时刻不存在长度为的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。
注意：在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其他进程不能先于队头进程被处理。
现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。
第一行是一个数N，表示总内存单元数（即地址范围从～N-1）。从第二行开始每行描述一个进程的3个整数T、、（≤N）。最后一行用3个0表示结束。数据已按从小到大排序。输入文件最多行，且所有数据都小于9。输入文件中同一行相邻两项之间用一个或多个空格隔开。
每组数据输出2行。第一行是全部进程都运行完毕的时刻。第二行是被放入过等待队列的进程总数。
【样例输入】
【样例输出】
【算法分析】
本题虽然数据规模比较大，但输入是比较随机的，也就是说，单纯的模拟就可以了。
具体的方法是，用一个堆存储每个进程的结束时间，以便及时释放内存；同时用一个双向链表按每个进程在内存中的顺序存储其地址，这样在有新进程申请时就可以通过遍历链表而找到合适的地址运行它（所说的“输入比较随机”，就是指输入没有故意使得每次插入进程时都要遍历整个链表）。当然，还要有一个等待队列。为了让堆和链表同时更新，需要在堆和链表的对应元素间建立互链。这样处理每个进程的流程就可以描述为：①读入一个进程的信息；②将在新进程开始前或开始时结束的进程删除，检查等待队列首的进程是否可以运行；③判断新进程是可以运行还是需放进等待队列。为了在所有进程都放进堆后可以清空堆，可以在最后假设读入了一个在无穷大时间结束的进程。
上述流程中的第②步的实现要注意：第一种做法，不能先把在新进程开始前或开始时结束的进程统统删除，再检查等待队列；第二种做法，也不能删除一个进程就检查一次队列。正确的做法是：把与堆顶进程同时结束的进程全部删除，检查等待队列，重复进行直至堆顶进程的结束时间晚于新进程的开始时间。为什么不能采用第二种做法呢？因为堆中元素仅仅按结束时间排序，若删除一个就检查一次等待队列，则可能造成在同时结束的进程中，地址大的先被删除，等待队列首的进程就正好被放在大地址了，而实际上它应该放在小地址，这样就造成了以后的混乱。
&&maxprogs=10001;
&&heap:array[0..maxprogs]of record fin:pchain:
&&chain:array[0..maxprogs]of&record left,right:&pheap,pre,&ext:&
&&wait:array[1..maxprogs]of record mem,time:
&&h,n,a,b,c,f,r,now,p:
function where(mem:longint):
&&&&where:=0;
&&&&while (chain[where].next&0) and
&&&&&&&&&&(chain[chain[where].next].left-chain[where].right&mem) do
&&&&&&where:=chain[where].
procedure ins(where,fintime,mem:longint);
&&&&inc(n);
&&&&with chain[n] do begin
&&&&&&left:=chain[where].right:=left+
&&&&&&pre:=next:=chain[where].
&&&&chain[where].next:=n;chain[chain[n].next].pre:=n;
&&&&inc(h);p:=h;q:=p shr 1;
&&&&while (p&1) and (fintime&heap[q].fin) do begin
&&&&&&heap[p]:=heap[q];
&&&&&&chain[heap[p].pchain].pheap:=p;
&&&&&&p:=q;q:=p shr 1;
&&&&with heap[p] do begin fin:=pchain:=n;
&&&&chain[n].pheap:=p;
function pop:
&&&&p,l,r:
&&&&pop:=heap[1].
&&&&p:=heap[1].chain[chain[p].pre].next:=chain[p].chain[chain[p].next].pre:=chain[p].
&&&&p:=1;l:=2;r:=3;
&&&&repeat
&&&&&&if (r&h) and (heap[h].fin&heap[r].fin) and (heap[r].fin&heap[l].fin) then begin
&&&&&&&&heap[p]:=heap[r];
&&&&&&&&chain[heap[p].pchain].pheap:=p;
&&&&&&&&p:=r;
&&&&&&else if (l&h) and (heap[h].fin&heap[l].fin) then begin
&&&&&&&&heap[p]:=heap[l];
&&&&&&&&chain[heap[p].pchain].pheap:=p;
&&&&&&&&p:=l;
&&&&&&else
&&&&&&l:=p*2;r:=l+1;
&&&&heap[p]:=heap[h];chain[heap[p].pchain].pheap:=p;
&&&&dec(h);
&&&&&&assign(input,'memory.in');reset(input);
&&&&&&assign(output,'memory.out');rewrite(output);
&&&&with heap[1] do begin fin:=pchain:=1;
&&&&with chain[0] do begin right:=0;next:=1;
&&&&with chain[1] do begin read(left);pheap:=1;pre:=0;next:=0;
&&&&f:=1;r:=0;
&&&&repeat
&&&&&&read(a,b,c);
&&&&&&if b=0 then a:=maxlongint-1;
&&&&&&while heap[1].fin&=a do begin
&&&&&&&&repeat now:=until heap[1].fin&
&&&&&&&&while f&=r do begin
&&&&&&&&&&p:=where(wait[f].mem);
&&&&&&&&&&if chain[p].next=0
&&&&&&&&&&ins(p,now+wait[f].time,wait[f].mem);
&&&&&&&&&&inc(f);
&&&&&&if b=0
&&&&&&p:=where(b);
&&&&&&if chain[p].next&0 then
&&&&&&&&ins(p,a+c,b)
&&&&&&else begin
&&&&&&&&inc(r);wait[r].mem:=b;wait[r].time:=c;
&&&&writeln(now);writeln(r);
&&&close(input);close(output);
1．购物（money.pas）。
【题目描述】
Dino同学喜欢去购物，但是他不想花很多钱，所以他总是挑那些打折的东西买，现在给出他买的所有东西的一个购物清单，以及每个物品打几折，问：他这次购物一共花了多少钱？
第一行一个n(1≤n≤100)表示一共买了多少个东西。后面紧接行，每行描述购买的一种物品：每行个整数，（≤ai≤10000,1≤bi≤10）。
一行，一个实数为Dino一共花了多少钱，答案保留位小数。
【样例输入】
【样例输出】
2．棋局（hiq.pas）。
【题目描述】
如图3-8所示。
1 &&&&&&&&2 &&&&&&&&3
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4 &&&&&&&&5 &&&&&&&&6
&&&&&&&&&&7 &&&&&&&&8 &&&&&&&&9 &&&&&&&10 &&&&&&&11 &&&&&&&12 &&&&&&&13
&&&&&&&&&14 &&&&&&&15 &&&&&&&16 &&&&&&&17 &&&&&&&18 &&&&&&&19 &&&&&&&20
&&&&&&&&&21 &&&&&&&22 &&&&&&&23 &&&&&&&24 &&&&&&&25 &&&&&&&26 &&&&&&&27 &&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&28 &&&&&&&29 &&&&&&&30
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&31 &&&&&&&32 &&&&&&&33
图3-8 &棋局示意图
数字相当于格子的编号，在它们上面有棋子，移动规则是：每次移动一个棋子，这个棋子必须跨越与其相邻的一个棋子到达一个空格子上（和跳棋类似），且只能横竖走，不能斜着走，移动完后，中间那个棋子就会被吃掉。
在一个棋局中，有很多棋子可以移动，那么移动哪一个呢？若把每个棋子移动后会到达的格子称为目标格子，则在这些目标格子中选择编号最大的一个，再在能达到此格子的棋子中选择编号最大的一个来移动。经过若干次移动后，就会出现不能移动的情况。此时，输出所有棋子所在编号的和。输入会告诉你哪些格子上有棋子，以0结束（不一定一行一组数据）。
【样例输入】
10 12 17 19 25 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0
【样例输出】
HI Q OUTPUT
END OF OUTPUT
“猜想”是一种重要的思维方法，对于确定证明方向，发现新定理，都有重大意义。&&
3.7 &贪 心 算 法&
1．算法思想
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在的问题：
（1）不能保证求得的最后解是最佳的。
（2）不能用来求最大或最小解问题。
（3）只能求满足某些约束条件的可行解的范围。&
实现该算法的过程：
（1）从问题的某一初始解出发。
（2）能朝给定总目标前进一步 求出可行解的一个解元素。
（3）由所有解元素组合成问题的一个可行解。
（4）贪心：找出所有度为的结点，把与它们相连的结点上都放上士兵，然后把这些度为的结点及已放上士兵的结点都去掉。重复上述过程直至数空为止。&
2．特点及使用范围
贪心算法的优点在于时间复杂度极低。贪心算法与其他最优化算法的区别在于：它具有不可后撤性，可以有后效性，一般情况下不满足最优化原理。贪心算法的特点就决定了它的适用范围，他一般不适用于解决可行性问题，仅适用于较容易得到可行解的最优性问题。这里较容易得到可行解的概念是：当前的策略选择后，不会或极少使后面出现无解的情况。另外，对于近年来出现的交互性题目，贪心算法是一个较好的选择。这是因为在题目中，一个策略的结果是随题目的进行而逐渐给出的，我们无法预先知道所选策略的结果，这与贪心算法不考虑策略的结果和其具有后效性的特点是不谋而合的。当然，贪心算法还可以为搜索算法提供较优的初始界值。
3．使用贪心算法的技巧（贪心与最优化算法的结合）
尽管贪心算法有一定的优越性，但它毕竟在一般情况下得不到最优解。因此，为了尽量减小贪心算法带来的副作用，使得最后得到的解更接近最优解，应该在算法尽可能多的地方使用有效的最优化算法（如动态规划）。
4．贪心算法的改进
贪心算法的缺点在于解的效果比较差，而最大优势在于极低的时间复杂度，而且往往时间复杂度远远低于题目的限制。那么，我们为什么不再花一部分时间来提高目标解的效果呢？这就是对贪心算法改进的必要性。 &
例1&&智力大冲浪（riddle.pas）。
【题目描述】
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段≤，它又给出了很多小游戏，每个小游戏都必须在规定期限前完成≤≤。如果一个游戏没能在规定期限前完成，则要从奖励费元中扣去一部分钱，为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！
注意：比赛绝对不会让参赛者赔钱!
输入文件riddle.in，共行。
第一行为m，表示一开始奖励给每位参赛者的钱；
第二行为n，表示有个小游戏；
第三行有n个数，分别表示游戏～的规定完成期限；
第四行有n个数，分别表示游戏～不能在规定期限前完成的扣款数。
输出文件riddle.out，仅行。表示小伟能赢取最多的钱。
【样例输入】
4 2 4 3 1 4 6
70 60 50 40 30 20 10
【样例输出】
【算法分析】
因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢？应该放在第个时段，因为放在～任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请参考下面的程序。
本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。当扫描到第n个时段，发现里面所分配任务的结束时间等于-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第～这个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现参考下面 &&的[程序2]。
program riddle1 (input, output);
var i,j,k,n,s,m:
&&&&a,b:array[1..100]
&&&&hash:array[1..100]
&&&&for i:=1 to n-1 do
&&&&&&for j:=i+1 to n do
&&&&&&&&if b[i]&b[j] then
&&&&&&&&&&begin p:=b[i];b[i]:=b[j];b[j]:=p;
&&&&&&&&&&&&&&&&p:=a[i];a[i]:=a[j];a[j]:=p;
&&fillchar(hash,sizeof(hash),true);
&&assign(input,'riddle.in');
&&reset(input);
&&assign(output,'riddle.out');
&&rewrite(output);
&&readln(m);
&&readln(n);
&&for i:=1 to n do
&&&&read(a[i]);
&&for i:=1 to n do
&&&&read(b[i]);
&&for i:=1 to n do
&&&&&&boo:=
&&&&&&for j:=a[i] downto 1 do
&&&&&&&&if hash[j] then begin boo:=hash[j]:=
&&&&&&if boo then begin
&&&&&&&&&&&&&&&&&&&&for k:=n downto 1 do
&&&&&&&&&&&&&&&&&&&&&&if hash[k] then begin hash[k]:=
&&&&&&&&&&&&&&&&&&&&inc(s,b[i]);
&&&&&&&&&&&&&&&&&&
&&writeln(m-s);
&&close(input);
&&close(output);
program riddle2(input,output);
&&&&&m,n,p,min,minx,total:
&&&&&w,t:array[1..100]
&&&&&assign(input,'riddle.in');
&&&&&assign(output,'riddle.out');
&&&&&reset(input);
&&&&&rewrite(output);
&&&&&readln(m);
&&&&&readln(n);
&&&&&for i:=1 to n do
&&&&&&read(t[i]);
&&&&for i:=1 to n do
&&&&&&read(w[i]);
&&&&for i:=1 to n-1 do
&&&&&&for j:=i+1 to n do
&&&&&&&&if (t[i]&t[j]) or (t[i]=t[j]) and (w[i]&w[j]) then
&&&&&&&&&&begin
&&&&&&&&&&&&p:=t[i];
&&&&&&&&&&&&t[i]:=t[j];
&&&&&&&&&&&&t[j]:=p;
&&&&&&&&&&&&p:=w[i];
&&&&&&&&&&&&w[i]:=w[j];
&&&&&&&&&&&&w[j]:=p;
&&&&&&&&&&
&&for i:=1 to n do
&&&&if (t[i]&i) and (i&=n) then
&&&&&&begin
&&&&&&&&min:=
&&&&&&&&for j:=1 to i do
&&&&&&&&&&if w[j]&min then
&&&&&&&&&&&&begin
&&&&&&&&&&&&&&min:=w[j];
&&&&&&&&&&&&&&minx:=j;
&&&&&&&&&&&&
&&&&&&&&&&total:=total+
&&&&&&&&&&for j:=minx to n-1 do
&&&&&&&&&&&&begin
&&&&&&&&&&&&&&w[j]:=w[j+1];
&&&&&&&&&&&&&&t[j]:=t[j+1];
&&&&&&&&&&&&
&&&&&&&&&&dec(n);
&&&&&&&&&&dec(i);
&&writeln(m-total);
&&close(input);
&&close(output);
例2&&合并果子（fruit.pas）。&
【题目描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如，有3种果子，数目依次为、2、9。可以先将、堆合并，新堆数目为，耗费体力为。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为，耗费体力为。所以多多总共耗费体力15=3+12。可以证明为最小的体力耗费值。
输入文件fruit.in包括两行。第一行是一个整数n(1≤n≤10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第个整数≤ai≤20000)是第i种果子的数目。
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于。
【样例输入】
【样例输出】
【数据规模】
对于30%的数据，保证有n≤1000；
对于50%的数据，保证有n≤5000；
对于全部的数据，保证有n≤10000。
【算法分析】
此题用贪心法。先将果子数排序，取其中最小的两堆合并，得到一个新堆；再排序，再取其中最小的两堆合并……直到只剩一堆。为尽快出解，排序的速度显得格外重要，可用快速排序算法。
program pruit
&&heap:array[1..10001]
procedure add (w:dword);
&&heap[i]:=w;
&&while (i&1) and (heap[i div 2]&heap[i]) do
&&&&sw:=heap[i div 2];
&&&&heap[i div 2]:=heap[i];
&&&&heap[i]:=
&&&&i:=i div 2;
&&while heap[em]&&0 do
&&&&inc(em);
procedure swap (s:word);
&&b:=s*2+1;
&&if (b&10001) or (heap[a]=0) and (heap[b]=0) then
&&&&heap[s]:=0;
&&&&if s&em then
&&&&&&em:=s;
&&if heap[a]=0 then
&&&&heap[s]:=heap[b];
&&&&swap(b);
&&if heap[b]=0 then
&&&&heap[s]:=heap[a];
&&&&swap(a);
&&if heap[a]&heap[b] then
&&&&heap[s]:=heap[b];
&&&&swap(b);
&&&&heap[s]:=heap[a];
&&&&swap(a);
function pop:
&&pop:=heap[1];
&&swap(1);
&&assign(input,'fruit.in');
&&assign(output,'fruit.out');
&&reset(input);
&&rewrite(output);
&&readln(n);
&&fillchar(heap,sizeof(heap),0);
&&for i:=1 to n do
&&&&read(w);
&&&&add(w);
&&for i:=1 to n-1 do
&&&&inc(sum,a+b);
&&&&add(a+b);
&&writeln(sum);
&&close(input);close(output);
例3&&建筑抢修（repair.pas）。
【题目描述】
小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏。经过了一场激烈的战斗，部落消灭了所有部落的入侵者。但是部落的基地里已经有个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。
现在的情况是：T部落基地里只有一个修理工人。虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。
你的任务是帮小刚合理制定一个修理顺序，以抢修尽可能多的建筑。
输入文件第一行是一个整数N，行每行两个整数、描述一个建筑：修理这个建筑需要秒，如果在秒之内还没有修理完成，这个建筑就报废了。
输出文件只有一行，是一个整数S，表示最多可以抢修个建筑。
【样例输入】
【样例输出】
【算法分析】
贪心 O(N Log N) + 高级数据结构。很容易想到动态规划。按截止时间排序，维护队列，如果能插入就插入，如不能插入，就把一个花费时间最大的替换下来。
const inf='repair.in';&ouf='repair.out';maxn=;
type PIT=^P
&Pnode=record l,r:PIT; s,k:
var f,g,a,b: array [0..maxn]
i,j,n,ans,now,x,e:
procedure Swap(var a,b:longint);
c:=a; a:=b; b:=c;
procedure Qsort(l,r:longint);
var i,j,p:
i:=l; j:=r; p:=b[(i+j)&&1];
while b[i]&p do inc(i);
while b[j]&p do dec(j);
if i&=j then
swap(b[i],b[j]);
swap(a[i],a[j]);
inc(i); &dec(j);
until i&j;
if l&j then Qsort(l,j);
if i&r then Qsort(i,r);
procedure Make(var p:PIT);
p^.l:= p^.r:= p^.s:=0; p^.k:=0;
procedure Ins(t:PIT; l,r,k:longint);
inc(t^.s);
if l=r then begin if t^.k=0 then t^.k:=k;
if k&=(l+r)&&1 then
if t^.l=nil then begin new(p); make(p); t^.l:=p;
ins(t^.l,l,(l+r)&&1,k);
if t^.r=nil then begin new(p); make(p); t^.r:=p;
ins(t^.r,(l+r)&&1+1,r,k);
procedure Del(t:PIT; l,r,k:longint);
dec(t^.s); if l=
if&k&=(l+r)&&1 then del(t^.l,l,(l+r)&&1,k) else del(t^.r,(l+r)&&1+1,r,k);
function RFS(t:PIT; l,r,k:longint):
if t=nil then exit(-1);
if l=r then exit(t^.k);
if t^.l=nil then d:=0 else d:=t^.l^.s;
if k&=d then exit(RFS(t^.l,l,(l+r)&&1,k))
&&&&else exit(RFS(t^.r,(l+r)&&1+1,r,k-d));
assign(input,inf); reset(input);&assign(output,ouf); rewrite(output);
readln(n);
for i:= 1 to n do readln(a[i],b[i]);
qsort(1,n);new(t); make(t); e:=
for i:= 1 to n do
if now+a[i]&b[i] then
inc(now,a[i]);inc(ans);
ins(t,0,e,a[i]);
x:=rfs(t,0,e,t^.s);
if x&a[i] then
dec(now,x);
inc(now,a[i]);
del(t,0,e,x);
ins(t,0,e,a[i]);
writeln(ans);
close(input); close(output);
木梳（comb.pas）
艾艺从小酷爱艺术，他梦想成为一名伟大的艺术家。最近他获得了一块材质不错的木板，其下侧为直线段，长为L，平均分为段，从左到右编号为…。木板的上侧为锯齿形，高度为整数，第段的高度为，≥2（如图所示）。
这么好的一段材料浪费了怪可惜的，艾艺决定好好加工一番做成一件艺术品。但他不是纯艺术家，他觉得每件艺术品都应有实用价值（否则只是华而不实），具有实用性的艺术品是他设计的理念。
根据这块木板的锯齿状，艾艺想到了每天起床后都要用到的一件日用品，便想把它做成梳子！他的设想是：用刻刀将某些上端的格子挖掉（如果把某个格子挖掉，那么这个格子上方的格子也必须被挖掉，但不能把一列中的格子全都挖掉），使得剩下的木板构成“规则锯齿形”（这样才好梳头）。
如图3-9所示，挖掉第、、列最上面的个格子和第列最上面的个格子后，剩下的区域就构成“规则锯齿形”（如图所示）。一个锯齿形称为“规则锯齿形”当且仅当它的上边界（图中红色曲线所示）的拐点序列不包含“”或者“”。图中红色曲线的拐点序列为：“”，（其中代表左拐，代表右拐），沿着曲线的最左端往右走，先左拐，再右拐，接着右拐，然后左拐，继续左拐，最后右拐。
为了最大限度地减少浪费，艾艺希望做出来的梳子面积最大。
图3-9 &木梳题示意图（） &&&&&&&&&&&&&&&&&图木梳题示意图（）
从文件input.txt中读入数据，文件第一行为整数，其中≤L≤100000，且有的数据满足≤104，表示木板下侧直线段的长。第二行为个正整数…，其中＜≤108，表示第段的高度。
输出文件output.txt中仅包含一个整数，表示为使梳子面积最大，需要从木板上挖掉的格子数。
【样例输入】
4 4 6 5 4 2 3 3 5（方案如图所示）
图3-11 &木梳题示意图（）
【样例输出】
3.8 &深度优先搜索
编程学到现在才真正到了高深部分，从这里往下学，你才知道什么叫做博大精深。今天我们要啃的这块硬骨头叫做深度优先搜索法。
首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出口出来。那老鼠会怎么走？当然是这样的：老鼠如果遇到直路，就一直往前走；如果遇到分叉路口，就任意选择其中的一个继续往下走；如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去；如果遇到了出口，老鼠的旅途就算结束了。深度优先搜索法的基本原则就是这样：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到条件的目标为止。
实现这一算法，我们要用到编程的另一大利器——递归。递归是一个很抽象的概念，但是在日常生活中，我们还是能够看到的。拿两面镜子来，把他们面对着面，你会看到什么？你会看到镜子中有无数个镜子？怎么回事？A镜子中有镜子的像，B镜子中有镜子的像，A镜子的像就是A镜子本身的真实写照，也就是说镜子的像包括了A镜子，还有镜子在镜子中的像……好累啊，又烦又绕口，还不好理解。换成计算机语言就是A调用，而又调用，这样间接的，就调用了本身，这实现了一个重复的功能。
他再举一个例子：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？他讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？他讲：……。好家伙！这样讲到世界末日还讲不完，老和尚讲的故事实际上就是前面的故事情节，这样不断地调用程序本身，就形成了递归。
万一这个故事中的某一个老和尚看这个故事不顺眼，就把他要讲的故事换成：“你有完没完啊！”，这样，整个故事也就嘎然而止了。我们编程就要注意这一点，在适当的时候，就必须要有一个这样的和尚挺身而出，把整个故事给停下来，或者使他不再往深一层次搜索。要不，我们的递归就会因计算机存储容量的限制而被迫溢出。切记！切记！！
我们把递归思想运用到上面的迷宫中，记老鼠现在所在的位置是(x,y)，那它现在有前后左右四个方向可以走，分别是(x+1,y)，(x-1,y)，(x,y+1)，(x,y-1)，其中一个方向是它来时的路，先不考虑，我们就分别尝试其他3个方向，如果某个方向是路而不是墙的话，老鼠就向那个方向迈出一步。在新的位置上，我们又可以重复前面的步骤。老鼠走到了死胡同又是怎么回事？就是除了来时的路，其他3个方向都是墙，这时这条路就走到了尽头，无法再向深一层发展，我们就应该沿来时的路回去，尝试另外的方向。
例1&&8皇后问题。
在标准国际象棋的棋盘上（8×8格）准备放置位皇后，我们知道，国际象棋中皇后的威力是最大的，她既可以横走竖走，还可以斜着走，遇到挡在她前进路线上的敌人，她就可以吃掉对手。要求在棋盘上安放8位皇后，使她们彼此互相都不能吃到对方，求皇后的放法。
这是一道很经典的题目了，我们先要明确一下思路，如何运用深度优先搜索法，完成这道题目。首先建立一个8×8格的棋盘，在棋盘的第一行的任意位置安放一只皇后。紧接着，我们就来放第二行，第二行的安放就要受一些限制了，因为与第一行的皇后在同一竖行或同一对角线的位置上是不能安放皇后的，接下来是第三行，……，或许我们会遇到这种情况，在摆到某一行的时候，无论皇后摆放在什么位置，她都会被其他行的皇后吃掉，这说明什么呢？这说明，我们前面的摆放是失败的，也就是说，按照前面的皇后的摆放方法，我们不可能得到正确的解。那这时怎么办？改啊！我们回到上一行，把原先摆好的皇后换另外一个位置，接着再回过头摆这一行，如果这样还不行或者上一行的皇后只有一个位置可放，那怎么办？我们回到上一行的上一行，这和老鼠碰了壁就回头是一个意思。就这样的不断地尝试、修正，再尝试、再修正，我们最终会得到正确的结论。
{8皇后问题参考程序}
const n=8;
var a,b:array [1..n]{数组a存放解：a[i]表示第i个皇后放在第a[i]列；}
c:array [1-n,n-1]
d:array [2..n+n] {数组b，c，d表示棋盘的当前情况：b[k]为1表示第k行已被占领为0表示为空；c、d表示对角线}
{打印结果}
for j:=1 to n do write(a[j]:4);
procedrue try(i:integer);
{递归搜索解}
{每个皇后的可放置位置。注意：一定要在过程中定义；否则当递归时会覆盖掉它的值，不能得到正确结果}
&&&& for j:=1 to n do
&&&& begin
&&&&&&&&& if (b[j]=0) and (c[i-j]=0) and & (d[i+j]=0) then{检查位置是否合法}
&&&&&&&&& begin
&&&& &&&& &&&& a[i]:=j;
{置第i个皇后的位置是第j行}
&&&& &&&& &&&& b[j]:=1;
{宣布占领行、对角线}
&&&& &&&& &&&& c[i-j]:=1;
&&&& &&&& &&&& d[i+j]:=1;
&&&& &&&& &&&& if i&n then try(i+1)&{如果未达目标则放置下一皇后，否则打印结果}
&&&& &&&& &&&& b[j]:=0;
{清空被占行、对角线，回溯}
&&&& &&&& &&&& c[i-j]:=0;
&&&& &&&& &&&& d[i+j]:=0;
&&&&&&&&& for k:=1 to n do b[k]:=0;
{初始化数据}
&&&&&&&&& for k:=1-n to n-1 do c[k]:=0;
&&&&&&&&& for k:=2 to n+n do d[k]:=0;
&&&&&&&&& try(1);
在深度优先搜索中，也是从初始结点开始扩展，但是扩展顺序却不同，深度优先搜索总是先扩展最新产生的结点。这就使得搜索沿着状态空间某条单一的路径进行下去，直到最后的结点不能产生新结点或者找到目标结点为止。当搜索到不能产生新的结点的时候，就沿着结点产生顺序的反方向寻找可以产生新结点的结点，并扩展它，形成另一条搜索路径。
深度优先搜索中扩展结点的原则是先产生的后扩展。因此，深度优先搜索第一个找到的解，并不一定是问题的最优解，要搜索完整个状态空间，才能确定哪个解是最优解。
深度优先搜索的算法如下：
（1）从初始结点开始，将待扩展结点依次放到open表中。open表为栈结构，即遵守后进先出的规则。
（2）如果open表空，即所有待扩展结点已全部扩展完毕，则问题无解，退出。
（3）取open表中最新加入的结点，即栈顶结点出栈，并用相应的算符扩展出所有的予结点，并按顺序将这些结点放入open表中。若没有子结点产生，则转（2）。
（4）如果某个子结点为目标结点，则找到问题的解（这不一定是最优解），结束。如果要求得问题的最优解，或者所有解，则转（2），继续搜索新的目标结点。
【深度优先搜索的算法】
procedure DFS;
&&&&open&&←1; &&data[open] .state ←初始状态;&
&&&Search Success &←&
&&&&&&¤tnode &&←data[open];
&&&&&&open &&←open-l;
&&&&&&while current&{还可以扩展}&do begin
&&&&&&&&&&new ←&operate &(currentnode.state);
&&&&&&&&&&if new&&{重复于已有的结点状态}&
&&&&&&&&&&open ←&open+l;
&&&&&&&&&data[open].state ←&
&&&&&&&&&data[open].last ←&
&&&&&&&&&&if new&&&{是目标状态}&then begin Search Success ←&
&&&until &(open&l) &or &(Search Success);
&&&if Search Success then Output(Reslut)
&&&else 0utput(No Answer);
例2&&选数（select.pas）。
【题目描述】
已知n（1≤n≤20）个整数x1,x2,…,xn（1≤xi≤5000000），以及一个整数k（k&n）。从n个整数中任选k个整数相加，可分别得到一系列的和。现在，要求你计算出和为素数共有多少种。
例如，当n=4，，个整数分别为、、、时，可得全部的组合与它们的和为：；；；。
现在，要求你计算出和为素数共有多少种。
例如，例2只有一种和为素数：。
n , k （，＜）
x1,x2，…（）
一个整数（满足条件的种数）。
【样例输入】
3 7 12 19
【样例输出】
【算法分析】
本题无数学公式可寻，看来只能搜索（组合的生成算法），其实1≤n≤20这个约束条件也暗示我们本题搜索是有希望的，组合的生成可用简单的DFS来实现，既搜索这k个整数在原数列中的位置，由于组合不同于排列，与这k个数的排列顺序无关，所以，可以令a[I]&a[I+1]（a[I]表示第I个数在原数列中的位置），这个组合生成算法的复杂度大约为C(n,k)，下面给出递归搜索算法的框架。
Proc &Search(dep)&&&&&&&&&&&
for i &- a[dep - 1] + 1 to N - (M - dep) do
1. a[dep] &- i
2. S &- S + x[i]
3. if dep & }
3.1 &算 &&&法
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
常用的算法：列举了穷举搜索、递归、回溯、递推、模拟、分治、贪心、深度优先搜索、广度优先搜索等几种较为常用的算法，没有做过多的描述，一旦给出具体描述，容易使内容加深，产生严重学科取向的引导，符合教育部普通高中课程方案的特点，对于这些必需的方法和思想，关键不在于学生能不能，而在于教师是否想到，是否有过关注，引发学生对系统方法和思想的思考，重视建立编程思想，强化编程习惯的培养。
3.1.1 &算法的5个重要特性
1．有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2．确定性：算法中每一条指令必须有确切的含义，不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径。
3．可行性：一个算法是能行的。即算法中描述的操作是执行有限次运算来实现的。
4．输入：一个算法有零个或多个输入。
5．输出：一个算法有一个或多个输出。
3.1.2 &算法设计的要求
通常设计一个“好”的算法，应考虑达到以下目标。
1．正确性：算法应当满足具体问题的需求。
2．可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解。
3．健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。
4．效率与低存储量需求。
效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。
3.1.3 &算法分析
算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问题宜采用哪种算法。
算法的复杂度分时间复杂度和空间复杂度。时间复杂度是在运行算法时所耗费的时间为f(n)（即&n的函数）。空间复杂度是实现算法所占用的空间为（也为的函数）。称和为该算法的复杂度。
3.1.4 &程序设计
程序是对所要解决的问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构＋算法＝程序。
2．程序设计
程序设计就是设计、编制和调试程序的过程。程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计两个阶段。
除了好的程序设计方法和技术之外，程序设计风格也很重要。因为程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格可以使程序结构清晰合理，使程序代码便于维护。因此，程序设计风格对保证程序的质量很重要。
一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要阅读和跟踪程序，因此程序设计的风格总体而言应该强调简单和清晰，必须可以理解。可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。要形成良好的程序设计风格，主要应注重源程序文档化。
（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序的功能进行理解。
（2）程序注释：正确的注释能够帮助读者理解程序。
3．结构化程序设计
结构化程序设计方法是程序设计的先进方法和工具。采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。结构化程序语言仅使用顺序、选择和循环3种基本控制结构就足以表达出各种其他形式结构的程序设计方法。
总之，遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有明显的优点。其一，程序结构良好、易读、易理解和易维护；其二，可以提高编程工作的效率，降低软件开发成本。
（1）算法的时间复杂度是指（ &&&&）。
A．执行算法程序所需要的时间 &&&&&&&&&&&&&B．算法程序的长度
C．算法执行过程中所需要的基本运算次数 &&&D．算法程序中的指令条数
【解析】所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量。
（2）算法的空间复杂度是指（ &&&&&）。
A．算法程序的长度 &&&&&&&&&&&&&&&B．算法程序中的指令条数
C．算法程序所占的存储空间 &&&&&&&D．算法执行过程中所需要的存储空间
【解析】空间复杂度是指执行算法所需要的存储空间。算法所占用的存储空间包括算法程序所占的空间、输入初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
（3）算法指的是（ &&&）。
A．计算机程序 &&&&&&&&&&&&&&&&&&&B．解决问题的计算方法
C．排序算法&&&&&&&&&&&&&&&&&&&&&&D．解决问题的有限运算序列
【解析】所谓算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。
（4）算法能正确地实现预定功能的特性称为算法的（ &&&）。
A．正确性 &&&B．易读性 &&&&&C．健壮性 &&&&&&&D．高效率
【解析】针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。算法与计算公式是有差别的，在设计一个算法时，必须要考虑它的可行性，否则将得不到满意的结果。
（5）递归算法一般需要利用（ &&&）来实现。
A．栈 &&&&&&&B．队列 &&&&&&&C．循环链表 &&&&&D．双向链表
3.2 &穷举搜索法
有一些问题一时难以找到规律或者公式，或者根本没有规律、公式。这时可以利用计算机高速运算的特点，使用穷举来解决。穷举搜索法是穷举所有可能情形，并从中找出符合要求的解决。穷举搜索法所有可能情形，最直观的是联系循环的算法。
例1&&找出n个自然数（…,n）中个数的组合。例如，当，时，所有组 &&&&&&合为：
&&&&&&&&&&&&&5 &&&&&5 &&&&&3
&&&&&&&&&&&&5 &&&&&4 &&&&&2
&&&&&&&&&&&&5 &&&&&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:
&&&&&&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
&&&&&&&&&&&&&&&&&&t:=t+1;writeln(i:3,j:3,k:3);
&&&&&&&&&&&&&&&&
&&&&&&&&writeln('total=',t);
&&&&&&end.
这个程序，穷举了所有可能情形，从中选出符合条件的解，很多情况下穷举搜索法还是常用的。
例2&&算24点（poi24.pas）。&&&&&
【题目描述】
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲。在中国我们把这种游戏称为“算点”。您作为游戏者将得到个～之间的自然数作为操作数，而您的任务是对这个操作数进行适当的算术运算，要求运算结果等于。
您可以使用的运算只有：+，-，×，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，×2)/4是合法的，×(2/4)是不合法的）。下面我们给出一个游戏的具体例子：若给出的个操作数是：、、、，则一种可能的解答是×7=24。
只有一行，四个1～之间的自然数。
如果有解的话，只要输出一个解，输出的是3行数据，分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“”。如果两个操作数有大小的话则先输出大的。如果没有解，则输出“”
&&&&poi24.out
【算法分析】
计算24点主要应用四种运算。开始状态有四个操作数，一个运算符对应两个操作数，所以一开始选择两个操作数分别对四个操作符进行循环检测，每一次运算后产生了新的数，两个数运算变成一个数，整体是少了一个操作数，所以四个数最终是三次运算。由于操作的层数比较少（只有三层），所以可以用回溯的算法来进行检测，当找到一个解时便结束查找。如果所有的情况都找过后仍然没有，则输出无解的信息。
program &poi24;
type arr=array [1..4]
var i,result,n,len:
&&&&r:array [1..3,1..4]
&&&&infile,outfile:
&&assign(outfile,'poi24.out');
&&rewrite(outfile);
&&for i:=1 to 3 do
&&&&&&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,'/')
&&&&&&&&&&&&&&&&
&&&&&&&writeln(outfile,'=',r[i,4])
&&close(outfile);
procedure try(k:d:arr);
var a,b,i,j,l,t:
&&if k=1 then if d[1]=24halt end else
&&&&&else&&begin
&&&&&&&&&&for i:=1 to k-1 do
&&&&&&&&&&for j:=i+1 to k do
&&&&&&&&&&&begin
&&&&&&&&&&&a:=d[i]; b:=d[j];
&&&&&&&&&&&if a&b then begin t:=a;a:=b;b:=
&&&&&&&&&&&t:=0;
&&&&&&&&&&&for l:=1 to k do if (l&&i) and (l&&j) then begin t:=t+1;e[t]:=d[l]
&&&&&&&&&&&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
&&&&&&&&&&&&&
&&&&&&&&&&&&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
&&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);
彩虹7号（rainbow.pas）
X市是一个重要的军事基地，在这个基地中有一支名为“彩虹号”的特别部队。每个队员都有一个固定独立的编号≤X≤215)，他们的职责就是完成部队交给他们的任务，每个任务同样都有固定独立的编号≤N≤10)。在执行任务的过程中，为了保证任务的保密性和队员的安全，队员和队员之间的联系将必须由特别部队所提供的一种保密频段交互设备进行。
每个队员都需要一个身份验证口令进入系统，由于队员所执行的任务都是涉及国家安全或者极高机密的活动，如果队员使用的口令出现错误，他们将付出无法估计的代价。特别部队的队员都是层层筛选的精英人才，所以不希望发生这样的事情。因此队员必须牢记口令的设置方法。
口令S的内容满足：N=X。显然，有可能也很有可能是一个无理数，所以限定为一个实数，它包含整数部分和小数部分，不包含小数点（即将视作）。口令的长度 &&&&&≤M≤50)，将根据任务的难度而有所不同。
编程任务：给定X，，。计算口令的内容。
输入（rainbow .in）：文件输入，文件有且仅有一行包含个整型数，，，每个数之间以一个空格符隔开。
输出（rainbow.out）：文件输出，文件有且仅有一行，为的结果。
样例输入：2 2 10
样例输出：
注意：口令的最后一位请使用去尾法保留，不要使用四舍五入法保留。文件请不要包含多余的空格和换行。
3.3 &递 &归 &法
递归作为一种强有力的数学和算法描述工具在Pascal语言中被广泛使用。一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有定义本身的引用（在过程或自定义函数中，又包含自己调用自己），则称它们是递归的或者是递归定义的。
一个递归算法仅使用少量的程序编码就可描述出解题所需要的多次重复计算而不需要设计循环结构。使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的规模较小的问题来求解，进而最终导致原问题的解决。
例如：n!的定义，我们知道，在数学中n!一般定义为：
&&&&&&&&&&&&&&&&&1 &&&&&&&若n=0
&&&&&&&&&&&n!=
&&&&&&&&&&&&&&&&&n×(n-1)!&&若n&0
在n&0的公式中，又包含了（n-1），这就是递归定义。
利用递归方法，可以用有限的语句来定义对象的无限集合。但在递归定义中，应该至少有一条是非递归的，即初始定义。如上面例子中的第一条，否则就变成了循环定义，产生逻辑性错误。
&&&&n!的递归定义的程序：
&&&&&program&&find＿n；
&&&&&&&var n：integer；
&&&&&&&&&&&&&t：longint；
&&&&&&&procedure &find（n：integer）；
&&&&&&&begin
&&&&&&&&&if &n＝0 &then &t：＝1
&&&&&&&&&&&&&&&&&&&&&else &
&&&&&&&&&&&&&&&&&&&&&&&begin&&find（n-1）；
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&t：＝t＊n &end；
&&&&&&&end；
&&&&&&&begin
&&&&&&&write（'n＝'）；
&&&&&&&readln（n）；
&&&&&&&find（n）；
&&&&&&&writeln（n,'!＝'，t）
&&&&&end．
递归调用（n进栈）达到结束条件时（n=0，赋初值）就停止调用开始返回，再把保存的值取出（n出栈），使n恢复原来的值，并计算，返回主程序，输出结果。
3!递归是如何实现的？
（1）设n=3，开始调用过程find，称为第零层调用。
（2）由于公式2!，必须先求，即程序中的n-1)，此时系统自动先保存的原值，再设n=2，进入第一层递归调用。
（3）因为1!，所以系统又保存，并设n=1，进入第层调用。
（4）因为0!，所以保存，并设n=0，进入第层调用。
（5）因为n=0，终止调用，赋值，返回的入口点。
（6）取出执行时保存的，求出t=1，返回的入口点。
（7）取出执行时保存的，求出t=2，返回的入口点。
（8）取出执行时保存的，求出t=6，返回的入口点。
（9）返回主程序，输出结果：。
从上面分析的过程看到，由于递归调用，需用同一变量名n，但值不同，所以在调用前必须先把n的原值保存，再赋以新值，然后进入调用。调用结束后，再把保存的值取出，使n恢复原来的值。在过程中find中又包含find(n-1)，即又调用了它自己，这就是递归调用。包含有递归调用的算法，就叫做递归算法。
递归调用会产生无终止运算的可能性，因此必须在适当时候终止递归调用，即在程序中必须要有终止条件。上面程序中，过程find的第一条语句就是终止条件。一般地，根据递归定义设计的递归算法中，非递归的初始定义，就用作程序中的终止 &&&条件。
实践证明，不是所有问题都可以用递归的方法处理，用递归算法编写的程序也不一定是好程序。可以看出，执行递归的过程既浪费时间又费存储空间，因此有的语言系统，禁止使用递归，由于计算机存储容量的限制，编译系统也不允许递归。但因递归特别符合人们的思维习惯，递归算法的设计也要比非递归算法设计容易，所以当问题是递归定义，尤其是当涉及的数据结构是递归定义的时候，使用递归算法特别合适。
应用递归算法能够求解的问题一般具有两个特点：
①存在某个特定条件，在此条件下，可得到指定的解，即递归在终止状态。
②对任意给定的条件，有明确的定义规则，可以产生新的状态并将最终导出终止状态，即存在导致问题求解的递归步骤。
递归是用栈来实现的。不过，递归恐怕不像想象得这么简单。首先，它体现了一个数学思想：化归，即把一个问题转化成另一个的方法。递归比较特殊，它是转化成性质相似，但规模更小的问题。
例3&&阅读程序NOIp2001_G。
program gao7_1;
&&function ack(m,n:integer):
&&&&if&m=0 then&ack:=n+1&
else if n=0 then ack:=ack(m-1,1)else ack:=ack(m-1,ack(m,n-1))
begin writeln(ack(3,4));
这个程序我们可以用下面的函数表示。在解题时，一般都是用递归的方法去实现的，而递归方法将会计算五千多步，在竞赛时这种方法是不可用的，而递归往往可以用递推去实现，因此，我们在教学过程中就讲解了该函数的递推过程，现将推导过程表示如下：
（1）我们在递归过程中发现该函数总是要调用到=0，=1及=2的情况，因此，我们就考虑要推导（，）必须首先推导（，），（，）以及（，）的情况。
（2）（，）可以由函数直接得到，公式为（，）=N+1
（3）（，）=ACK（，）=1+1=0+2
& &&&ACK（，）=ACK（，（，））=ACK（，+1）=1+1+1=1+2
&&&&&ACK（，）=ACK（，（，））=ACK（，+2）=1+1+2=2+2
因此，我们可以联想到ACK（，）=N+2。这个公式可以用数学归纳法证明之。（略）
根据上面的方法，我们可以方便地推导出下面一些公式：
（4）（，）=ACK（，）=1+2=3（利用=1的公式）
&&&&&ACK（，）=ACK（，（，））=ACK（，+2）=3+2=5
（利用M=1的公式及（，））
ACK（，）=ACK（，（，））=ACK（，）=5+2=（2+1）*2+1
因此，我们可以联想到ACK（，）=（N+1）*2+1。同样，这个公式可以用数学归纳法证明之。（略）
（5）（，）=ACK（，）=(1+1)*2+1=5（利用=2的公式）
ACK（，）=ACK（，（，））=ACK（，）=（(1+1)*2+1+1）*2+1=2^3+2^2+1
ACK（，）=ACK（，（，））=ACK（，）=（2^3+2^2+1+1）*2+1=2^4+2^3+2^2+1=2^5-3
因此，我们可以联想到ACK（，）=2^(N+3)-3。
例4&&仍以例1为例，找个数的个数的组合。
&&&&&&&&输入：n，，
&&&&&&&&输出：5 &&&&&4 &&&&&3
&&&&&&&&&&&&&&5 &&&&&4 &&&&&2
&&&&&&&&&&&&&&5 &&&&&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 &&&&{组合的总数
分析：所提示的10组数。首先固定第一位数（如），其后是在另个数中再“组合”个数。这就将“个数中个数的组合”推到了“个数中个数的组合”上去了。第一位数可以是，（如，），个数中个数组合递推到-1个数中-1个数有组合，这是一个递归的算法。即：
&&&var &i:
&&&&begin &for &i:=n &downto &r &do
&&&&&&begin &
{固定i的输出位置}
&&&&&&&&comb(i-1,r-1); &
{原过程递推到i-1个数的r-1个数组合}
再考虑打印输出格式。
&&var &k,n,r:
&&&&Produrce &&comb(n,r:integer);
&&&&var &i,temp:
&&&&&begin &for &i:=n &downto &r &do
&&&&&&&if &(i&&n)and(k&&r) &then &&&
{k为过程外定义的}
&&&&&&&&&begin for temp:=1 to &(k-r)*3 &do &write(' &'); {确定i的输出位置}
&&&&&&&write(i:3);
&&&&&&&if i&1 then comb(i-1,r-1); &
{递推到下一情形}
&&&&&write('n,r=');readln(n,r);
&&&&&if &r&n &then
&&&&&&&begin &writeln('Input n,r error!');
&&&&&comb(n,r); &
{调用递归过程}
1．邮票面值设计（postag.pas）
【题目描述】
给定一个信封，最多只允许粘贴N张邮票，计算在给定（≤40) 种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大，使得-max之间的每一个邮资值都能得到。
例如，N=3，=2，如果面值分别为分、分，则在～6分之间的每一个邮资值都能得到（当然还有分、分和分）：如果面值分别为分、分，则在～7分之间的每一个邮资值都能得到。可以验证当，=2时，分就是可以得到连续的邮资最大值，所以max=7，面值分别为分、分。
【样例输入】
3 2&&{输入第一个数，第二个数，中间用空格间隔
【样例输出】
1 3&&&&{输出的第一行面值分别为l分、分}
max=7&{输出的第二连续的邮资最大值}
2．聪明的学生（guess.pas）
【题目描述】
一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A，和。有一天教授给他们人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。
这时，教授先对学生A发问了：“你能猜出自己的数吗？”回答：“不能。”
教授又转身问学生B：“你能猜出自己的数吗？”想了想，也回答：“不能。”
教授再问学生C同样的问题，思考了片刻后，摇了摇头：“不能。”
接着，教授又重新问A同样的问题，再问和，……，经过若干轮的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误地报了出来。
现在，如果告诉你：教授在第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是，你能推断出另外两个学生的头上贴的是什么数吗？
在没有人猜出自己头上的数之前，大家对教授提问的回答始终都是“不能”；而且除此之外在，，之间是没有进行任何信息交流的。也就是说，每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授的提问所做出的否定回答。
教授总是从学生A开始提问的。
你可以假定，这3个聪明的学生能够根据已知的条件在最早的轮次猜出自己的数，并且永远都不会猜错。稍经分析和推理，你将得出以下结论：总是头上贴着最大的那个数的人最先猜出自己头上的数。
【输入文件】
输入文件为guess.in。
该文件包括若干组测试数据，其中的每一行代表一组测试数据，由两个整数N和组成（即在教授第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M）。两个数之间用空格分隔开。最后，由-1 -1组成的一行标志着输入的数据结束。同时要求，＜＜＜＜。
【输出文件】
输出文件为guess.out。按照输入文件中的顺序依次给出各组数据的结果。
文件中对应每组数据输出的第一行是一个整数p，是可能情况的总数。接下来的p行，每一行包括个数，分别为贴在、、头上的个数。输出时，所有解按照头上的数增序排列；在头上的数相同的情况下，按照头上的数增序排列。
【样例输入】
【样例输出】
3.4 &回 &溯 &法
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构
例5&&再以例1说明，找个数中个数的组合。
分析：将自然数排列在数组A中。
&&&&&&A[1] &&&A[2] &&&A[3]
&&&&&&&5 &&&&&&4 &&&&&&3
&&&&&&&5 &&&&&&4 &&&&&&2
&&&&&&&3 &&&&&&2 &&&&&&1
排数时从A[1]到再到，后一个至少比前一个数小，并且应满足＞r。若≤就要回溯，该关系就是回溯条件。为直观起见，当输出一组组合数后，若最后一位为，也应作一次回溯（若不回，便由上述回溯条件处理）。
program &zuhe3;
&&type &tp=array[1..100]
&&&var &n,r:
procedure &comb2(n,r:a:tp);
&&&&&var &i,ri:
&&&&&&begin &ri:=1;a[1]:=n;
&&&&&&&&repeat &
&&&&&&&&&if &ri&&r &then &&
{没有搜索到底}
&&&&&&&&&&&if &ri+a[ri]&r &then &&&
｛判断是否回溯｝
&&&&&&&&&&&&&&&&&begin &
&&&&&&&&&&&&&&&&&&&a[ri+1]:=a[ri]-1;
&&&&&&&&&&&&&&&&&&&ri:=ri+1; &&&&&&&&&&&& {向前搜索}
&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&&&begin &ri:=ri-1;
a[ri]:=a[ri]-1;
&&&&&&&&&&else
&&&&&&&&&&&&begin &&for &j:=1 &to &r &do &write(a[j]:3);
{输出组合数}
&&&&&&&&&&&&&&if &a[r]=1 &then &
{是否回溯}
&&&&&&&&&&&&&&&&begin &ri:=ri-1;
a[ri]:=a[ri]-1;
&&&&&&&&&&&&&&else &a[ri]:=a[ri]-1; &
{递推到下一个数｝
&&&&&&&&&&&&
&&&&&&&&until &a[1]&&r-1;
begin &write('n,r=');
readln(n,r);
&&&&&&&if &r&n &then &begin &writeln('Input n,r error!');
&&&&&&&comb2(n,r);
&&&&&&&end.
1．马拦过河卒（knight.pas）
【题目描述】
棋盘上A点有一个过河卒，需要走到目标点。卒行走的规则：可以向下、或者向右。同时，在棋盘上点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点（）、点（）（为不超过的整数），同样马的位置坐标是需要给出的。现在要求你计算出卒从点能够到达点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
一行四个数据，分别表示B点坐标和马的坐标。
一个数据，表示所有的路径条数。
knight.out
2．走迷宫（maze.pas）&&&&&&&
【题目描述】
有一个m×n格的迷宫（表示有行、列），其中有可走的也有不可走的，如果用表示可以走，表示不可以走，文件读入这×n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-l表示无路）。
第一行是两个数m，＜＜，接下来是行列由和组成的数据，最后两行是起始点和结束点。
所有可行的路径，描述一个点时用（x,y）的形式，除开始点外，其他的都要用“→”表示方向。如果没有一条可行的路则输出-1。
【样例输入】
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
【样例输出】
(1,2)→→→→→→→→→→→→→
(1,1)→→→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→
(1,1)→→→→→→→→→→→→→
(1,1)→→→→→→→→→→→
(1,1)→→→→→→→→→
3．组合的输出（track.pas）&&
【题目描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出个元素（不分顺序且≤n），我们可以简单地将个元素理解为自然数…，从中任取个数。现要求你不用递归的方法输出所有组合。
例如：n＝，＝，所有组合为：
l 2 3；l 2 4；1 2 5；l 3 4；l 3 5；1 4 5；2 3 4；2 3 5；2 4 5；3 4 5。
一行两个自然数n、＜＜，≤r≤n)。
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占3个字符的位置，所有的组合也按字典顺序。
【样例输入】
【样例输出】
3.5 &递 &&&推
递推是迭代算法中一种用若干步可重复的简单运算来描述复杂数学问题的方法，以便于计算机进行处理。它与递推关系的思想完全一致，由边界条件开始往后逐个推算，在一般情况下，效率较高，编程也非常的方便。但是，我们一般只需要求递推关系的第n项，而边界条件与第项前面之间的若干项的信息是我们不需要的，如果采用递推的方法来求解的话，第项之前的每一项都必须计算出来，最后才能得到所需要的第项的值。这是递推无法避免的，从而在一定程度上影响了程序的效率。当然在大多数情况下，采用递推的方法还是可行的，在竞赛中，使用递推的方法编程，通常会在时限内出解。当然，更好的求解方法还有母函数法、迭代归纳法等。
例1&&青蛙过河（frog.pas）。
【题目描述】
有一条河，左边一个石墩（A区）上有编号为，，，，…，的只青蛙，河中有个荷叶（区），还有个石墩（区），右边有一个石墩（区），如图所示。只青蛙要过河（从左岸石墩到右岸石墩），规则为：
图3-1 &青蛙过河示意图
（1）石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙（不论大小）。
（2）青蛙可以：→（表示可以从跳到，下同），→，→，→，→，→，→。
（3）当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大号的青蛙上面。
你的任务是对于给出的h、，计算并输出最多能有多少只青蛙可以根据以上规则顺利 &过河？
【样例输入】
2 3 &&{河中间有个石礅，个荷叶
【样例输出】
16 {最多有只青蛙可以按照规则过河
【算法分析】
从具体到一般，推导过程如下：
f(0,k)=k+1;
{如时，有只青蛙可以过河
f(1,k)=2(k+1); `
以此类推：f(2,k)=(2×(k+1))×2=22(k+1);
结论为：f(h,k)=2h(k+1)
program frog(input,output);
var h,k,i,s:
&&assign(input,'frog.in');
&&assign(output,'frog.out');
&&reset(input);
&&rewrite(output);
readln(h,k);
for i:=1 to h do&s:=s*2;
writeln(s);
close(input);close(output)
例2&&排序集合（sort.pas）。
【题目描述】
对于集合N={1,2,…的子集，定义一个称之为“小于”的关系：设1={X1,X2,…i}，（1＜X2＜…＜Xi），S2={Y1, Y2, …j}，（1＜Y2＜…＜Yj），如果存在一个k，（≤≤），使得1=Y1，…，k=Yk，且k=i或(k+1)&＜Y(k+1)，则称S1“小于”2。
你的任务是，对于任意的n(n≤及n)，求出第小的子集。
输入文件仅一行，包含两个用空格隔开的自然数，n和。
输出文件仅一行，使该子集的元素，由小到大排列。空集输出0。
【样例输入】
【样例输出】
【算法分析】
我们知道，n个元素构成的集合有n种情况。本题的意思是：把这些集合按照某种规则排序，然后输入k，输出第个集合。所以排序的规则是本题的关键，其实很简单，当＝时，个集合排序如下：＜＜＜＜＜＜＜，你发现规律了吗具体算法为：先推出第小的一个子集的第一个数宇是多少，第一个数字确定了之后，再推出第二个数字，从第一个数字加一直计算累加集合个数，直到得到不超过的最大的那个数字，就是第二位数字，这样一直递推，推到最后一个。注意：终止条件是有了个数字或者第个数字为空，这时递推终止，输出最后的结果。
program sort(input,output);
&&type arr=array[0..31]
&&&&&&n,i,j,k:
&&&&assign(input,'sort.in');
&&&&assign(output,'sort.out');
reset(input);
rewrite(output);
&&&&readln(n,k);
&&&&fillchar(a,sizeof(a),0);
&&&&a[n]:=1; a[0]:=1;
&&&&for i:=n-1 downto 1 do &&&&&{a[i]=2i-n}
&&&&&&a[i]:=a[i+1]*2;
&&&&&&i:=0; j:=1;
&&&&&&while k&1 do &&&&&&&&&&&&&&&{以下为一位一位推出数字}
&&&&&&begin
&&&&&&&&while (i&=n) and (k&a[i]) do
&&&&&&&&&&begin
&&&&&&&&&&&&dec(k,a[i]);
&&&&&&&&&&&&inc(i)
&&&&&&&&&&
&&&&&&&&if j&&1 then write(' ');
&&&&&&&&inc(j);
&&&&&&&&write(i);
&&&&&&&&a[i]:=1
&&&&if i=0 then writeln(0);{判空集}
&&&&close(input);close(output)
例3&&诸侯安置（empire.pas）。
【题目描述】
很久以前，有一个强大的帝国，它的国土成正方形状，如图3-2所示。
图3-2 &诸侯安置示意图（原图）
这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地（正方形中的一格）。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如图3-3为时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。
&&&&&&&&&&&&&（1） &&&&&&&&&&&&&&&&&&&&&&&&&&&（） &&&&&&&&&&&&&&&&&&&&&&&&&（）
图3-3 &诸侯安置示意图
致使国家动荡不安国王也不愿意看到他的诸侯们互相开战，因此，他希望通过合理地安排诸侯所处的位置，使他们两两之间都不能攻击。
现在，给出正方形的边长n，以及需要封地的诸侯数量，要求你求出所有可能的安置方案数。n≤，≤2-2n+1)。由于方案数可能很多，你只需要输出方案数除以的余数即可。
仅一行，两个整数n和，中间用一空格隔开。
一个整数，表示方案数除以504的余数。
【样例输入】
【样例输出】
【样例说明】
四种安置方案如图3-4所示。
注意：镜面和旋转的情况属于不同的方案。
&&&&&&&&&&&&&&&&&&&&（1） &&&&&&&（） &&&&&&（） &&&&&&&&（）
图3-4 &安置方案
【算法分析】
重新描述一下问题，其实就是在一个边长为2n-1的正菱形（如图为的情形）上摆放个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种
看到这道题目，我们就会立即想起一道经典的老题目：n皇后问题。这道题目与皇后问题非常相似。但有两个不同点：一是皇后问题可以斜着攻击对方棋子，而本题不能；二是皇后问题是在，的正方形棋盘上面放置个皇后，而本题却是在一个正菱形上摆放。我们试着先将皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，皇后的公式是：2×k!。但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。
首先，想到在2n-1列中任意取出列进行具体分析，这样一来问题就转化成：有一个长为的数列（无重复元素），每一个数在一个不定的区间当中，第个数一定在区间i,bi]之间，求这样的数列有多少种？如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度排一下序，就可以看出来，再用乘法原理进行求解即可。但是，最多可到，最多可到，穷举要进行种方案！显然无法在规定的时间内出解！那么怎么办呢？再继续分析一下问题发现，里面有重叠子问题。如果一个列作为最后一列，且这一列以及前面所有列共放置个诸侯，设有种情况，那么这一列后面的所有列共放置个棋子的方案数都要用到，从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图的形式（即列排序）。
设f[i,j]表示以第列为最后一列，放置个棋子的总方案数，得出公式：
注意：当k≥-1时，问题无解。
var i,j,k,n,l,s:
&&&&f:array[1..200,1..200]
function make(p:longint):
&&&&if odd(p) then make:=p else make:=p-1;
&&assign(input,'empire.in');reset(input);
&&assign(output,'empire.out');rewrite(output);
&&readln(n,k);
&&if k=0 then begin writeln(1);close(output);halt
&&if k&=2×n-1 then begin writeln(0);
close(output);
&&for i:=1 to 2×n-1 do
&&&&if odd(i) then f[i,1]:=i else f[i,1]:=i-1;
&&for i:=1 to 2×n-1 do
&&&&for j:=2 to i do
&&&&&&for l:=1 to i-j+1 do
&&&&&&&&f[i,j]:=(f[i,j]+f[i-l,j-1]&×(make(i)-j+1)) mod 504;
&&i:=2×n-1;
&&if k=1 then begin writeln((i×(i+1) div 2-i div 2) mod 504);
close(output);halt end else
&&&&for i:=k to 2×n-1 do inc(s,f[i,k]);
&&writeln(s mod 504);
&&close(input);
close(output);
行家的预算（travel.pas）
【题目描述】
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量（以升为单位）。每升汽油能行驶的距离D2、出发点每升汽油价格和沿途油站数（可以为零），油站离出发点的距离、每升汽油价格＝,2,…N)（计算结果四舍五入至小数点后两位）。如果无法到达目的地，则输出“o solution”。 &
第一行，第一个数两个城市之间的距离D2，第二个数汽车油箱的容量C，第三个数每升汽油能行驶的距离D2，第四个数出发点每升汽油价格P，第五个数沿途油站数N。
从第二行开始，每行有两个数，第一个数为油站i离出发点的距离，第二个数为每升汽油价格Pi，中间用空格间隔。
【样例输入】
275.6 &11.9 &27.4 &2.8 &2
102.0 &2.9 &&&&&&&&&&&
220.0&&2.2 &&&&&&&&&&
【样例输出】
26.95（该数据表示最小费用）
【算法分析】
看到题目后，很容易想到递推。事实上，要用的油是确定的（D1/D2），价钱最便宜的油的站的油显然应该多买，到达这个油站时汽车剩油不为的方案一定不是最优的。这是因为，如果剩下升油，显然不如当初少买升，改在这里买升划算！（最便宜嘛！）
每次都假装装满油，用的时候先用便宜的，因为把贵的留在后面“反悔”！这样计算费用时只考虑真正使用的。可以用优先队列（用堆来实现）来进行替换和使用油。也可以模拟但效率不高。
3.6 &模拟搜索（最原始的方法）
模拟题。按常规思想：逐步地模拟，直至又回到初始状态时为止。但这样全部模拟基本上无法在规定的时间内出解，必须做一些改进。模拟题并不需要太多的算法知识，主要考察选手的数据结构的应用以及编程能力。&
例1&&津津的储蓄计划（save.pas）。
【题目描述】
津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。
为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%利息、连本带息还给津津。因此，津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。
例如，11月初津津手中还有元，妈妈给了津津元。津津预计月的花销是元，那么她就会在妈妈那里存元，自己留下元。到了月末，津津手中会剩下元钱。
津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。
现在请你根据2004年月到月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到年年末，妈妈将津津平常存在她那里的钱加上20%的利息，一并还给津津之后，津津手中会有多少钱。
输入文件save.in包括行数据，每行包含一个小于的非负整数，分别表示月到月津津的预算。
输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，表示出现这种情况的第一个月；否则输出到年年末津津手中会有多少钱。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【算法分析】
最简单、最基本的模拟加判断，连数组都不用开。只要读清题目，然后动手做就可以了。解决此类问题没有什么技巧，最重要的是不在关键时刻出现低级错误。
var f1,f2:
&&&&a:array[1..12]
&&&&i,tol,s:
&assign(f1,'save.in');
&reset(f1);
&assign(f2,'save.out');
&rewrite(f2);
&tol:=0;s:=0;
&for i:=1 to 12 do
&&&readln(f1,a[i]);
&&&tol:=tol+300-a[i];
&&&if tol&0 then
&&&&&writeln(f2,'-',i);
&&&&&close(f2);
&&&s:=s+100*(tol div 100);
&&&tol:=tol mod 100;
&writeln(f2,tol+s+s div 5);
&close(f2);
例2&&小球钟（ball.pas）。
【问题描述】
时间是运动的一种方式。我们常常用运动来度量时间。例如，小球钟是一个通过不断在轨道上移动小球来度量时间的简单设备。每分钟，一个转动臂将一个小球从小球队列的底部挤走，并将它上升到钟的顶部并将它安置在一个表示分钟，5分钟，分钟和小时的轨道上。这里可以显示从：～：（这正是奇怪之处）范围内的时间，若有个球在分钟轨道，个球在分钟轨道，个球在分钟轨道及个球在小时轨道上，就显示时间：。
当小球通过钟的机械装置被移动后，它们就会改变其初始次序。仔细研究它们次序的改变，可以发现相同的次序会不断出现。由于小球的初始次序最后迟早会被重复，所以这段时间的长短是可以被度量的，这完全取决于所提供的小球的总数。
小球钟的运作：每分钟，最近最少被使用的那个小球从位于球钟底部的小球队列被移走，并将上升并安置于显示分钟的轨道上，这里可以放置4个小球。当第个小球滚入该轨道，它们的重量使得轨道倾斜，原先在轨道上的个小球按照与它们原先滚入轨道的次序相反的次序加入到钟底部的小球队列。引起倾斜的第个小球滚入显示分钟的轨道。该轨道可以放置个球。当第个小球滚入该轨道，它们的重量使得轨道倾斜，原先个小球同样以相反的次序加入钟底部的小球队列。而这第个小球滚入了显示分钟的轨道。这里可以放置个小球。当第个小球滚入该轨道，它们的重量使得轨道倾斜，原先在轨道上的个小球按照与它们原先滚入轨道的次序相反的次序加入到钟底部的小球队列，而这第个小球滚入了显示小时的轨道。该轨道同样可以放置个球，但这里有一个外加的固定的不能被移动的小球，这样小时的值域就变为～。从分钟轨道滚入的第个小球将使小时轨道倾斜，这个球同样以相反的次序加入钟底部的小球队列，然后那第个小球同样加入钟底部的小球队列。
输入定义了一序列的小球时钟。每个时钟都按照前面描述的那样运作。所有时钟的区别仅在于它们在1：时钟启动时刻小球初始个数的不同。在输入的每行上给出一个时钟的小球数，它并不包括那个在小时轨道上的固定的小球。合法的数据应在～之间。表明输入的结束。
输出中每一行只有一个数，表示对应的输入情形中给出的小球数量的时钟在经过多少天的运行可以回到它的初始小球序列。
【样例输入】
【样例输出】
【算法分析】
该题是典型的模拟题。按常规思想：逐分钟地模拟小球钟的运作，直至钟底部的小球队列重又回到初始状态时为止。这期间流逝的天数即为小球钟的运作周期。但这样全部模拟基本上无法在规定的时间内出解，必须做一些改进。
于是，我们想到通过模拟出每个小球回到原来位置上所需的天数，然后求它们的最小公倍数。但是，如果仍是单纯的模拟，速度仍然很慢。我们可以先模拟小球钟最先24小时的运行情况，得到一天后的钟底部的新小球队列。有了这个条件后，我们可以在两次的钟底部小球队列间建立起一种置换。设初始时，钟底部的小球编号依次是：,2,3,…n。一天后，钟底部的小球编号依次是：,p2,p3,…pn。则我们可以建立这样的置换：
1& 2& 3 …&n
p1 p2 p3 …&pn
注意到小球钟的运作规则保证了上述置换是不变的，就可以计算出小球钟运行48小时后，72小时后……，钟底部的小球队列情况，直至队列情况重新是1,2,3,…,n。这样，在求得以上置换的基础上，我们可以求每一个小球回到原位置的周期，然后求它们的最小公倍数即可。
program ball
var&n, i : m1, m2, m3, m4, m : c, c2 : now, long :
function gcd(a, b : longint) :
&&if b = 0 then gcd := a
&&else if b = 1 then gcd := 1
&&else gcd := gcd(b, a mod b);
function reverse(s : string) :
&&s2 := '';
&&while s && '' do
&&&&s2 := s[1] + s2;
&&&&delete(s, 1, 1);
&&reverse := s2;
&&assign(input, 'ball.in'); reset(input);
&&assign(output, 'ball.out'); rewrite(output);
&&readln(n);
&&while n & 0 do
&&&&m := '';
&&&&for i := 1 to n do m := m + chr(i);
&&&&repeat
&&&&&&c := m[1];
&&&&&&delete(m, 1, 1);
&&&&&&if length(m1) & 4 then m1 := m1 + c
&&&&&&else
&&&&&&&&begin
&&m := m + reverse(m1);
&&m1 := '';
&&if length(m2) & 2 then m2 := m2 + c
&&&&&&&&&&else
&&&&&&&&&&&&begin
&&&&&&m := m + reverse(m2);
&&&&&&m2 := '';
&&&&&&if length(m3) & 3 then m3 := m3 + c
&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&begin
&&&&&&&&&&m := m + reverse(m3);
&&&&&&&&&&m3 := '';
&&&&&&&&&&if length(m4) & 23 then m4 := m4 + c
&&&&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&&&&&begin
&&&&&&m := m + reverse(m4) +
&&&&&&m4 := '';
&&&&until (m1 ='') and (m2 = '') and (m3 = '') and (m4 = '');
&&&&now := 1;
&&&&for i := 1 to length(m) do
&&&&&&if m[i] && #0 then
&&&&&&begin
c := m[i];
&&&&&&&&m[i] := #0;
&&&&&&&&long := 1;
while m[ord(c)] && #0 do
&&&&&&&&begin
&&&&&&&&&&inc(long);
&&c2 := m[ord(c)];
&&&&&&&&&&m[ord(c)] := #0;
&&c := c2;
&&&&&&&&now := (now * long) div gcd(now, long);
&&&&writeln(now);
&&&&readln(n);
&&close(output);
&&close(input);
例3&&奶牛（eat.pas）。
【题目描述】
一个农夫有n（≤1000）头奶牛，可由于产奶太少，他决定把当天产奶最少的牛杀掉，但他有点舍不得，如果当天不只一头奶牛产奶，至少他便放过它们。这些奶牛产奶是周期性的，他已开始就想知道有多少奶牛可幸免遇难（可能会被全杀），每头奶牛周期不会超过（每头奶牛产奶量≤250）。
注：T——数据总数
N——奶牛总数
第一头奶牛周期天数，每天产奶数；
第二头奶牛周期天数，每天产奶数；
第n头奶牛周期天数，每天产奶数。
【样例输入】
【样例输出】
注：2——最后剩下2头奶牛
&&&&&& 6——最后一头牛是在第六天被杀的
【算法分析】
直述型模拟，每头奶牛产奶数 P:= p mod n +1；找最小值，最小值奶牛；用哈希表判奶牛是否死亡；注意每个数据的初始化。
program eat
var h,p,pro:array [1..1000+10]
&&&&m:array [1....250]
&&&&del:array [1..1000+10]
&&&&k,i,j,round,n:
&&&&ob,min,ans,ans2,now,change:
&&&&assign(input,'eat.in');reset(input);assign(output,'eat.out'); rewrite(output);
&&&&readln(k);
&&&&for round:= 1 to k do
&&&&&&&&fillchar(h,sizeof(h),0);
&&&&&&&&fillchar(m,sizeof(m),0);
&&&&&&&&fillchar(del,sizeof(del),0);
&&&&&&&&fillchar(pro,sizeof(pro),0);
&&&&&&&&ans:=0; &ans2:=0; &change:=0;
&&&&&&&&readln(n);
&&&&&&&&for i:= 1 to n do
&&&&&&&&begin
&&&&&&&&&&&&read(p[i]);
&&&&&&&&&&&&for j:= 1 to p[i] do read(m[i,j]);
&&&&&&&&&&&&
&&&&&&&&fillchar(h,sizeof(h),0);
&&&&&&&&while true do
&&&&&&&&begin
&&&&&&&&&&&inc(ans);
&&&&&&&&&&&for i:= 1 to n do&if not del[i] then
&&&&&&&&&&&begin
&&&&&&&&&&&&&h[i]:=h[i] mod p[i] +1;
&&&&&&&&&&&&&pro[i]:=m[i,h[i]];
&&&&&&&&&&&
&&&&&&&&&&&min:=
&&&&&&&&&&&for i:= 1 to n do if not del[i] then
&&&&&&&&&&&&&if pro[i]&min then min:=pro[i];
&&&&&&&&&&&&&&now:=0;
&&&&&&&&&&&for i:= 1 to n do if not del[i] then
&&&&&&&&&&&if pro[i]=min then begin inc(now); ob:=
&&&&&&&&&&&if now=1 then begin del[ob]:= ans2:= change:=0;
&&&&&&&&&&&else inc(change);
&&&&&&&&&&&if change&500
&&&&&&&&&&&allk:= for i:= 1 to n do if not del[i] then allk:=
&&&&&&&&&&&
&&&&&&&&ans:=0;
&&&&&&&&for i:= 1 to n do if not del[i] then inc(ans);
&&&&&&&&writeln(ans,' ',ans2);
&&&&close(input); &close(output);
例4&&猫和老鼠（catmou.pas）。
【题目描述】
猫和老鼠在10×10的方格中运动（如图），例如：
*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......
图3-6 &猫和老鼠在×10方格中的运动图
M=老鼠（）
猫和老鼠每秒中走一格，如果在某一秒末它们在同一格中，我们称它们“相遇”。
注意：“对穿”是不算相遇的。猫和老鼠的移动方式相同：平时沿直线走，下一步如果会走到障碍物上去或者出界，就用秒的时间做一个右转°。一开始它们都面向北方。
编程计算多少秒以后他们相遇。
【输入】10行，格式如图所示。
【输出】相遇时间T。如果无解，输出-1。
【样例输入】
&*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......
【样例输出】
【算法分析】
题目没什么好的办法，只有模拟猫和老鼠。
program catmon
&&ipt,opt:
&&a:array[0..11,0..11]
&&i,b,cl,cw,ml,mw,aim,bim:
&&assign(ipt,'catmou.in'); assign(opt,'catmou.out');
&&reset(ipt);
&&rewrite(opt);
&&&for i:=1 to 10 do
&&&&&for b:=1 to 9 do
&&&&&&read(ipt,a[b,i]);
&&&&&readln(ipt,a[10,i]);
&&&for i:=0 to 11 do
&&&&&a[i,0]:='*';
&&&&&a[i,11]:='*';
&&&&&a[0,i]:='*';
&&&&&a[11,i]:='*';
&&&for i:=1 to 10 do
&&&for b:=1 to 10 do
&&&&&if a[i,b]='C' then
&&&&&&begin
&&&&&&&cw:=b;
&&&&&&&cl:=i;
&&&&&if a[i,b]='M' then
&&&&&&begin
&&&&&&&mw:=b;
&&&&&&&ml:=i;
&&&aim:=1; bim:=1; k:=0;
&&&&if k&99999 then begin k:=-1;
&&&&inc(k);
&&&&if aim=1 then
&&&&&begin
&&&&&&if a[ml,mw-1]='*' then inc(aim);
&&&&&&if a[ml,mw-1]&&'*' then mw:=mw-1;
&&&&&begin
&&&&&if aim=2 then
&&&&&begin
&&&&&&if a[ml+1,mw]='*' then inc(aim);
&&&&&&if a[ml+1,mw]&&'*' then ml:=ml+1;
&&&&&begin
&&&&&if aim=3 then
&&&&&begin
&&&&&&if a[ml,mw+1]='*' then inc(aim);
&&&&&&if a[ml,mw+1]&&'*' then mw:=mw+1;
&&&&&begin
&&&&&if aim=4 then
&&&&&begin
&&&&&&if a[ml-1,mw]='*' then aim:=1;
&&&&&&if a[ml-1,mw]&&'*' then ml:=ml-1;
&&&&&if bim=1 then begin
&&&&&&if a[cl,cw-1]='*' then inc(bim);
&&&&&&if a[cl,cw-1]&&'*' then cw:=cw-1;
&&&&&begin
&&&&&if bim=2 then begin
&&&&&if a[cl+1,cw]='*' then inc(bim);
&&&&&if a[cl+1,cw]&&'*' then cl:=cl+1;
&&&&&begin
&&&&&if bim=3 then begin
&&&&&&if a[cl,cw+1]='*' then inc(bim);
&&&&&&if a[cl,cw+1]&&'*' then cw:=cw+1;
&&&&&&else
&&&&&&begin
&&&&&if bim=4 then begin
&&&&&&if a[cl-1,cw]='*' then bim:=1;
&&&&&&if a[cl-1,cw]&&'*' then cl:=cl-1;
&&&&&until (cl=ml) and (cw=mw);
&&&&&write(opt,k);
&&&&&close(ipt); close(opt);
例5&&字母运算（cowcul.pas）。
【题目描述】
有4个字母：、、、，它们可以相加，也能产生进位，如图所示：，，但他要进位现有个由上述字母构成的“数”（五位），只对第个数进行操作，有种操作。
图3-7 &字母运算示意图
A：把第个数变成两数之和；
L：在数后加一个（对进行操作后为，相当于字符串相加）；
R：在数前加一个（同上），去掉末位。
现给你两个数以及3个操作，再给你一个数（位），把两数最前面连续的去掉（变成），判断是否相等，相等输出，不等则输出。
【样例输入】
【样例输出】
COWCULATIONS OUTPUT
END OF OUTPUT
【算法分析】
此题为模拟题。做法：题目转换。题目中的U、、、，其实都是忽悠你的，说白了就是对应了四进制的加法、进位、让位等操作；这样题目就转换成了读入两个四进制数然后按操作与第三个数对比大小即可。时间：。
type num=array [0..100]
var a,b,x:
&&&&tests,round,i,j:
function magic(c:char):
&&&&case c of
&&&&'V': exit(0);
&&&&'U': exit(1);
&&&&'C': exit(2);
&&&&'D': exit(3);
&&&&exit(0);
function max(a,b:longint):
&&&&if a&b then exit(a) else exit(b);
procedure dd(var a: n:longint);
var l,r,t:
&&&&l:=1; r:=n;
&&&&while l&r do
&&&&&&&&t:=a[l]; a[l]:=a[r]; a[r]:=t;
&&&&&&&&inc(l); dec(r);
&&&&while a[n]=0 do dec(n);
&&&&a[0]:=n;
procedure sum(a: var b:num);
var l,r,t,i:
&&&&l:=max(a[0],b[0]);
&&&&for i:= 1 to l do
&&&&&&&&inc(b[i+1],(a[i]+b[i]) div 4);
&&&&&&&&b[i]:=(a[i]+b[i]) mod 4;
&&&&if b[l+1]&&0 then b[0]:=l+1 else b[0]:=l;
procedure add(var b:num);
&&&&for i:= b[0] downto 1 do b[i+1]:=b[i];
&&&&b[1]:=0;
&&&&inc(b[0]);
procedure dda(var b:num);
&&&&for i:= 2 to b[0] do b[i-1]:=b[i];
&&&&b[b[0]]:=0; &dec(b[0]);
function Compare(a,b:num):
&&&&l:=max(b[0],a[0]);
&&&&for i:= 1 to l do
&&&&if b[i]&&a[i] then exit(false);
&&&&exit(true);
&&&&assign(input,'cowcul.in'); reset(input);
&&&&assign(output,'cowcul.out'); rewrite(output);
&&&&writeln('COWCULATIONS OUTPUT');
&&&&readln(tests);
&&&&for round:= 1 to tests do
&&&&&&&&fillchar(a,sizeof(a),0);
&&&&&&&&fillchar(b,sizeof(b),0);
&&&&&&&&fillchar(x,sizeof(x),0);
&&&&&&&&for i:= 1 to 5 do begin read(c); a[i]:=magic(c) dd(a,5);
&&&&&&&&for i:= 1 to 5 do begin read(c); b[i]:=magic(c) dd(b,5);
&&&&&&&&for i:= 1 to 3 do
&&&&&&&&begin
&&&&&&&&&&&&readln(c);
&&&&&&&&&&&&case c of
&&&&&&&&&&&&'A': sum(a,b);
&&&&&&&&&&&&'L': add(b);
&&&&&&&&&&&&'R': dda(b);
&&&&&&&&&&&&
&&&&&&&&for i:= 1 to 8 do begin read(c); x[i]:=magic(c) dd(x,8);
&&&&&&&&if compare(b,x) then writeln('YES') else writeln('NO');
&&&&&&writeln('END OF OUTPUT');
&&&&&close(input); close(output);
例6&&内存分配（memory.pas）。
【题目描述】
内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。经典的内存分配过程是这样进行的：
（1）内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址开始的个连续的内存单元称为首地址为长度为的地址片。
（2）运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数及运行时间。在运行时间内（即时刻开始，时刻结束），这个被占用的内存单元不能再被其他进程使用。
（3）假设在T时刻有一个进程申请个单元，且运行时间为，则：
①若T时刻内存中存在长度为的空闲地址片，则系统将这个空闲单元分配给该进程。若存在多个长度为个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
②如果T时刻不存在长度为的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。
注意：在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其他进程不能先于队头进程被处理。
现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。
第一行是一个数N，表示总内存单元数（即地址范围从～N-1）。从第二行开始每行描述一个进程的3个整数T、、（≤N）。最后一行用3个0表示结束。数据已按从小到大排序。输入文件最多行，且所有数据都小于9。输入文件中同一行相邻两项之间用一个或多个空格隔开。
每组数据输出2行。第一行是全部进程都运行完毕的时刻。第二行是被放入过等待队列的进程总数。
【样例输入】
【样例输出】
【算法分析】
本题虽然数据规模比较大，但输入是比较随机的，也就是说，单纯的模拟就可以了。
具体的方法是，用一个堆存储每个进程的结束时间，以便及时释放内存；同时用一个双向链表按每个进程在内存中的顺序存储其地址，这样在有新进程申请时就可以通过遍历链表而找到合适的地址运行它（所说的“输入比较随机”，就是指输入没有故意使得每次插入进程时都要遍历整个链表）。当然，还要有一个等待队列。为了让堆和链表同时更新，需要在堆和链表的对应元素间建立互链。这样处理每个进程的流程就可以描述为：①读入一个进程的信息；②将在新进程开始前或开始时结束的进程删除，检查等待队列首的进程是否可以运行；③判断新进程是可以运行还是需放进等待队列。为了在所有进程都放进堆后可以清空堆，可以在最后假设读入了一个在无穷大时间结束的进程。
上述流程中的第②步的实现要注意：第一种做法，不能先把在新进程开始前或开始时结束的进程统统删除，再检查等待队列；第二种做法，也不能删除一个进程就检查一次队列。正确的做法是：把与堆顶进程同时结束的进程全部删除，检查等待队列，重复进行直至堆顶进程的结束时间晚于新进程的开始时间。为什么不能采用第二种做法呢？因为堆中元素仅仅按结束时间排序，若删除一个就检查一次等待队列，则可能造成在同时结束的进程中，地址大的先被删除，等待队列首的进程就正好被放在大地址了，而实际上它应该放在小地址，这样就造成了以后的混乱。
&&maxprogs=10001;
&&heap:array[0..maxprogs]of record fin:pchain:
&&chain:array[0..maxprogs]of&record left,right:&pheap,pre,&ext:&
&&wait:array[1..maxprogs]of record mem,time:
&&h,n,a,b,c,f,r,now,p:
function where(mem:longint):
&&&&where:=0;
&&&&while (chain[where].next&0) and
&&&&&&&&&&(chain[chain[where].next].left-chain[where].right&mem) do
&&&&&&where:=chain[where].
procedure ins(where,fintime,mem:longint);
&&&&inc(n);
&&&&with chain[n] do begin
&&&&&&left:=chain[where].right:=left+
&&&&&&pre:=next:=chain[where].
&&&&chain[where].next:=n;chain[chain[n].next].pre:=n;
&&&&inc(h);p:=h;q:=p shr 1;
&&&&while (p&1) and (fintime&heap[q].fin) do begin
&&&&&&heap[p]:=heap[q];
&&&&&&chain[heap[p].pchain].pheap:=p;
&&&&&&p:=q;q:=p shr 1;
&&&&with heap[p] do begin fin:=pchain:=n;
&&&&chain[n].pheap:=p;
function pop:
&&&&p,l,r:
&&&&pop:=heap[1].
&&&&p:=heap[1].chain[chain[p].pre].next:=chain[p].chain[chain[p].next].pre:=chain[p].
&&&&p:=1;l:=2;r:=3;
&&&&repeat
&&&&&&if (r&h) and (heap[h].fin&heap[r].fin) and (heap[r].fin&heap[l].fin) then begin
&&&&&&&&heap[p]:=heap[r];
&&&&&&&&chain[heap[p].pchain].pheap:=p;
&&&&&&&&p:=r;
&&&&&&else if (l&h) and (heap[h].fin&heap[l].fin) then begin
&&&&&&&&heap[p]:=heap[l];
&&&&&&&&chain[heap[p].pchain].pheap:=p;
&&&&&&&&p:=l;
&&&&&&else
&&&&&&l:=p*2;r:=l+1;
&&&&heap[p]:=heap[h];chain[heap[p].pchain].pheap:=p;
&&&&dec(h);
&&&&&&assign(input,'memory.in');reset(input);
&&&&&&assign(output,'memory.out');rewrite(output);
&&&&with heap[1] do begin fin:=pchain:=1;
&&&&with chain[0] do begin right:=0;next:=1;
&&&&with chain[1] do begin read(left);pheap:=1;pre:=0;next:=0;
&&&&f:=1;r:=0;
&&&&repeat
&&&&&&read(a,b,c);
&&&&&&if b=0 then a:=maxlongint-1;
&&&&&&while heap[1].fin&=a do begin
&&&&&&&&repeat now:=until heap[1].fin&
&&&&&&&&while f&=r do begin
&&&&&&&&&&p:=where(wait[f].mem);
&&&&&&&&&&if chain[p].next=0
&&&&&&&&&&ins(p,now+wait[f].time,wait[f].mem);
&&&&&&&&&&inc(f);
&&&&&&if b=0
&&&&&&p:=where(b);
&&&&&&if chain[p].next&0 then
&&&&&&&&ins(p,a+c,b)
&&&&&&else begin
&&&&&&&&inc(r);wait[r].mem:=b;wait[r].time:=c;
&&&&writeln(now);writeln(r);
&&&close(input);close(output);
1．购物（money.pas）。
【题目描述】
Dino同学喜欢去购物，但是他不想花很多钱，所以他总是挑那些打折的东西买，现在给出他买的所有东西的一个购物清单，以及每个物品打几折，问：他这次购物一共花了多少钱？
第一行一个n(1≤n≤100)表示一共买了多少个东西。后面紧接行，每行描述购买的一种物品：每行个整数，（≤ai≤10000,1≤bi≤10）。
一行，一个实数为Dino一共花了多少钱，答案保留位小数。
【样例输入】
【样例输出】
2．棋局（hiq.pas）。
【题目描述】
如图3-8所示。
1 &&&&&&&&2 &&&&&&&&3
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&4 &&&&&&&&5 &&&&&&&&6
&&&&&&&&&&7 &&&&&&&&8 &&&&&&&&9 &&&&&&&10 &&&&&&&11 &&&&&&&12 &&&&&&&13
&&&&&&&&&14 &&&&&&&15 &&&&&&&16 &&&&&&&17 &&&&&&&18 &&&&&&&19 &&&&&&&20
&&&&&&&&&21 &&&&&&&22 &&&&&&&23 &&&&&&&24 &&&&&&&25 &&&&&&&26 &&&&&&&27 &&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&28 &&&&&&&29 &&&&&&&30
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&31 &&&&&&&32 &&&&&&&33
图3-8 &棋局示意图
数字相当于格子的编号，在它们上面有棋子，移动规则是：每次移动一个棋子，这个棋子必须跨越与其相邻的一个棋子到达一个空格子上（和跳棋类似），且只能横竖走，不能斜着走，移动完后，中间那个棋子就会被吃掉。
在一个棋局中，有很多棋子可以移动，那么移动哪一个呢？若把每个棋子移动后会到达的格子称为目标格子，则在这些目标格子中选择编号最大的一个，再在能达到此格子的棋子中选择编号最大的一个来移动。经过若干次移动后，就会出现不能移动的情况。此时，输出所有棋子所在编号的和。输入会告诉你哪些格子上有棋子，以0结束（不一定一行一组数据）。
【样例输入】
10 12 17 19 25 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0
【样例输出】
HI Q OUTPUT
END OF OUTPUT
“猜想”是一种重要的思维方法，对于确定证明方向，发现新定理，都有重大意义。&&
3.7 &贪 心 算 法&
1．算法思想
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在的问题：
（1）不能保证求得的最后解是最佳的。
（2）不能用来求最大或最小解问题。
（3）只能求满足某些约束条件的可行解的范围。&
实现该算法的过程：
（1）从问题的某一初始解出发。
（2）能朝给定总目标前进一步 求出可行解的一个解元素。
（3）由所有解元素组合成问题的一个可行解。
（4）贪心：找出所有度为的结点，把与它们相连的结点上都放上士兵，然后把这些度为的结点及已放上士兵的结点都去掉。重复上述过程直至数空为止。&
2．特点及使用范围
贪心算法的优点在于时间复杂度极低。贪心算法与其他最优化算法的区别在于：它具有不可后撤性，可以有后效性，一般情况下不满足最优化原理。贪心算法的特点就决定了它的适用范围，他一般不适用于解决可行性问题，仅适用于较容易得到可行解的最优性问题。这里较容易得到可行解的概念是：当前的策略选择后，不会或极少使后面出现无解的情况。另外，对于近年来出现的交互性题目，贪心算法是一个较好的选择。这是因为在题目中，一个策略的结果是随题目的进行而逐渐给出的，我们无法预先知道所选策略的结果，这与贪心算法不考虑策略的结果和其具有后效性的特点是不谋而合的。当然，贪心算法还可以为搜索算法提供较优的初始界值。
3．使用贪心算法的技巧（贪心与最优化算法的结合）
尽管贪心算法有一定的优越性，但它毕竟在一般情况下得不到最优解。因此，为了尽量减小贪心算法带来的副作用，使得最后得到的解更接近最优解，应该在算法尽可能多的地方使用有效的最优化算法（如动态规划）。
4．贪心算法的改进
贪心算法的缺点在于解的效果比较差，而最大优势在于极低的时间复杂度，而且往往时间复杂度远远低于题目的限制。那么，我们为什么不再花一部分时间来提高目标解的效果呢？这就是对贪心算法改进的必要性。 &
例1&&智力大冲浪（riddle.pas）。
【题目描述】
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段≤，它又给出了很多小游戏，每个小游戏都必须在规定期限前完成≤≤。如果一个游戏没能在规定期限前完成，则要从奖励费元中扣去一部分钱，为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！
注意：比赛绝对不会让参赛者赔钱!
输入文件riddle.in，共行。
第一行为m，表示一开始奖励给每位参赛者的钱；
第二行为n，表示有个小游戏；
第三行有n个数，分别表示游戏～的规定完成期限；
第四行有n个数，分别表示游戏～不能在规定期限前完成的扣款数。
输出文件riddle.out，仅行。表示小伟能赢取最多的钱。
【样例输入】
4 2 4 3 1 4 6
70 60 50 40 30 20 10
【样例输出】
【算法分析】
因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢？应该放在第个时段，因为放在～任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请参考下面的程序。
本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。当扫描到第n个时段，发现里面所分配任务的结束时间等于-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第～这个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现参考下面 &&的[程序2]。
program riddle1 (input, output);
var i,j,k,n,s,m:
&&&&a,b:array[1..100]
&&&&hash:array[1..100]
&&&&for i:=1 to n-1 do
&&&&&&for j:=i+1 to n do
&&&&&&&&if b[i]&b[j] then
&&&&&&&&&&begin p:=b[i];b[i]:=b[j];b[j]:=p;
&&&&&&&&&&&&&&&&p:=a[i];a[i]:=a[j];a[j]:=p;
&&fillchar(hash,sizeof(hash),true);
&&assign(input,'riddle.in');
&&reset(input);
&&assign(output,'riddle.out');
&&rewrite(output);
&&readln(m);
&&readln(n);
&&for i:=1 to n do
&&&&read(a[i]);
&&for i:=1 to n do
&&&&read(b[i]);
&&for i:=1 to n do
&&&&&&boo:=
&&&&&&for j:=a[i] downto 1 do
&&&&&&&&if hash[j] then begin boo:=hash[j]:=
&&&&&&if boo then begin
&&&&&&&&&&&&&&&&&&&&for k:=n downto 1 do
&&&&&&&&&&&&&&&&&&&&&&if hash[k] then begin hash[k]:=
&&&&&&&&&&&&&&&&&&&&inc(s,b[i]);
&&&&&&&&&&&&&&&&&&
&&writeln(m-s);
&&close(input);
&&close(output);
program riddle2(input,output);
&&&&&m,n,p,min,minx,total:
&&&&&w,t:array[1..100]
&&&&&assign(input,'riddle.in');
&&&&&assign(output,'riddle.out');
&&&&&reset(input);
&&&&&rewrite(output);
&&&&&readln(m);
&&&&&readln(n);
&&&&&for i:=1 to n do
&&&&&&read(t[i]);
&&&&for i:=1 to n do
&&&&&&read(w[i]);
&&&&for i:=1 to n-1 do
&&&&&&for j:=i+1 to n do
&&&&&&&&if (t[i]&t[j]) or (t[i]=t[j]) and (w[i]&w[j]) then
&&&&&&&&&&begin
&&&&&&&&&&&&p:=t[i];
&&&&&&&&&&&&t[i]:=t[j];
&&&&&&&&&&&&t[j]:=p;
&&&&&&&&&&&&p:=w[i];
&&&&&&&&&&&&w[i]:=w[j];
&&&&&&&&&&&&w[j]:=p;
&&&&&&&&&&
&&for i:=1 to n do
&&&&if (t[i]&i) and (i&=n) then
&&&&&&begin
&&&&&&&&min:=
&&&&&&&&for j:=1 to i do
&&&&&&&&&&if w[j]&min then
&&&&&&&&&&&&begin
&&&&&&&&&&&&&&min:=w[j];
&&&&&&&&&&&&&&minx:=j;
&&&&&&&&&&&&
&&&&&&&&&&total:=total+
&&&&&&&&&&for j:=minx to n-1 do
&&&&&&&&&&&&begin
&&&&&&&&&&&&&&w[j]:=w[j+1];
&&&&&&&&&&&&&&t[j]:=t[j+1];
&&&&&&&&&&&&
&&&&&&&&&&dec(n);
&&&&&&&&&&dec(i);
&&writeln(m-total);
&&close(input);
&&close(output);
例2&&合并果子（fruit.pas）。&
【题目描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如，有3种果子，数目依次为、2、9。可以先将、堆合并，新堆数目为，耗费体力为。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为，耗费体力为。所以多多总共耗费体力15=3+12。可以证明为最小的体力耗费值。
输入文件fruit.in包括两行。第一行是一个整数n(1≤n≤10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第个整数≤ai≤20000)是第i种果子的数目。
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于。
【样例输入】
【样例输出】
【数据规模】
对于30%的数据，保证有n≤1000；
对于50%的数据，保证有n≤5000；
对于全部的数据，保证有n≤10000。
【算法分析】
此题用贪心法。先将果子数排序，取其中最小的两堆合并，得到一个新堆；再排序，再取其中最小的两堆合并……直到只剩一堆。为尽快出解，排序的速度显得格外重要，可用快速排序算法。
program pruit
&&heap:array[1..10001]
procedure add (w:dword);
&&heap[i]:=w;
&&while (i&1) and (heap[i div 2]&heap[i]) do
&&&&sw:=heap[i div 2];
&&&&heap[i div 2]:=heap[i];
&&&&heap[i]:=
&&&&i:=i div 2;
&&while heap[em]&&0 do
&&&&inc(em);
procedure swap (s:word);
&&b:=s*2+1;
&&if (b&10001) or (heap[a]=0) and (heap[b]=0) then
&&&&heap[s]:=0;
&&&&if s&em then
&&&&&&em:=s;
&&if heap[a]=0 then
&&&&heap[s]:=heap[b];
&&&&swap(b);
&&if heap[b]=0 then
&&&&heap[s]:=heap[a];
&&&&swap(a);
&&if heap[a]&heap[b] then
&&&&heap[s]:=heap[b];
&&&&swap(b);
&&&&heap[s]:=heap[a];
&&&&swap(a);
function pop:
&&pop:=heap[1];
&&swap(1);
&&assign(input,'fruit.in');
&&assign(output,'fruit.out');
&&reset(input);
&&rewrite(output);
&&readln(n);
&&fillchar(heap,sizeof(heap),0);
&&for i:=1 to n do
&&&&read(w);
&&&&add(w);
&&for i:=1 to n-1 do
&&&&inc(sum,a+b);
&&&&add(a+b);
&&writeln(sum);
&&close(input);close(output);
例3&&建筑抢修（repair.pas）。
【题目描述】
小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏。经过了一场激烈的战斗，部落消灭了所有部落的入侵者。但是部落的基地里已经有个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。
现在的情况是：T部落基地里只有一个修理工人。虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。
你的任务是帮小刚合理制定一个修理顺序，以抢修尽可能多的建筑。
输入文件第一行是一个整数N，行每行两个整数、描述一个建筑：修理这个建筑需要秒，如果在秒之内还没有修理完成，这个建筑就报废了。
输出文件只有一行，是一个整数S，表示最多可以抢修个建筑。
【样例输入】
【样例输出】
【算法分析】
贪心 O(N Log N) + 高级数据结构。很容易想到动态规划。按截止时间排序，维护队列，如果能插入就插入，如不能插入，就把一个花费时间最大的替换下来。
const inf='repair.in';&ouf='repair.out';maxn=;
type PIT=^P
&Pnode=record l,r:PIT; s,k:
var f,g,a,b: array [0..maxn]
i,j,n,ans,now,x,e:
procedure Swap(var a,b:longint);
c:=a; a:=b; b:=c;
procedure Qsort(l,r:longint);
var i,j,p:
i:=l; j:=r; p:=b[(i+j)&&1];
while b[i]&p do inc(i);
while b[j]&p do dec(j);
if i&=j then
swap(b[i],b[j]);
swap(a[i],a[j]);
inc(i); &dec(j);
until i&j;
if l&j then Qsort(l,j);
if i&r then Qsort(i,r);
procedure Make(var p:PIT);
p^.l:= p^.r:= p^.s:=0; p^.k:=0;
procedure Ins(t:PIT; l,r,k:longint);
inc(t^.s);
if l=r then begin if t^.k=0 then t^.k:=k;
if k&=(l+r)&&1 then
if t^.l=nil then begin new(p); make(p); t^.l:=p;
ins(t^.l,l,(l+r)&&1,k);
if t^.r=nil then begin new(p); make(p); t^.r:=p;
ins(t^.r,(l+r)&&1+1,r,k);
procedure Del(t:PIT; l,r,k:longint);
dec(t^.s); if l=
if&k&=(l+r)&&1 then del(t^.l,l,(l+r)&&1,k) else del(t^.r,(l+r)&&1+1,r,k);
function RFS(t:PIT; l,r,k:longint):
if t=nil then exit(-1);
if l=r then exit(t^.k);
if t^.l=nil then d:=0 else d:=t^.l^.s;
if k&=d then exit(RFS(t^.l,l,(l+r)&&1,k))
&&&&else exit(RFS(t^.r,(l+r)&&1+1,r,k-d));
assign(input,inf); reset(input);&assign(output,ouf); rewrite(output);
readln(n);
for i:= 1 to n do readln(a[i],b[i]);
qsort(1,n);new(t); make(t); e:=
for i:= 1 to n do
if now+a[i]&b[i] then
inc(now,a[i]);inc(ans);
ins(t,0,e,a[i]);
x:=rfs(t,0,e,t^.s);
if x&a[i] then
dec(now,x);
inc(now,a[i]);
del(t,0,e,x);
ins(t,0,e,a[i]);
writeln(ans);
close(input); close(output);
木梳（comb.pas）
艾艺从小酷爱艺术，他梦想成为一名伟大的艺术家。最近他获得了一块材质不错的木板，其下侧为直线段，长为L，平均分为段，从左到右编号为…。木板的上侧为锯齿形，高度为整数，第段的高度为，≥2（如图所示）。
这么好的一段材料浪费了怪可惜的，艾艺决定好好加工一番做成一件艺术品。但他不是纯艺术家，他觉得每件艺术品都应有实用价值（否则只是华而不实），具有实用性的艺术品是他设计的理念。
根据这块木板的锯齿状，艾艺想到了每天起床后都要用到的一件日用品，便想把它做成梳子！他的设想是：用刻刀将某些上端的格子挖掉（如果把某个格子挖掉，那么这个格子上方的格子也必须被挖掉，但不能把一列中的格子全都挖掉），使得剩下的木板构成“规则锯齿形”（这样才好梳头）。
如图3-9所示，挖掉第、、列最上面的个格子和第列最上面的个格子后，剩下的区域就构成“规则锯齿形”（如图所示）。一个锯齿形称为“规则锯齿形”当且仅当它的上边界（图中红色曲线所示）的拐点序列不包含“”或者“”。图中红色曲线的拐点序列为：“”，（其中代表左拐，代表右拐），沿着曲线的最左端往右走，先左拐，再右拐，接着右拐，然后左拐，继续左拐，最后右拐。
为了最大限度地减少浪费，艾艺希望做出来的梳子面积最大。
图3-9 &木梳题示意图（） &&&&&&&&&&&&&&&&&图木梳题示意图（）
从文件input.txt中读入数据，文件第一行为整数，其中≤L≤100000，且有的数据满足≤104，表示木板下侧直线段的长。第二行为个正整数…，其中＜≤108，表示第段的高度。
输出文件output.txt中仅包含一个整数，表示为使梳子面积最大，需要从木板上挖掉的格子数。
【样例输入】
4 4 6 5 4 2 3 3 5（方案如图所示）
图3-11 &木梳题示意图（）
【样例输出】
3.8 &深度优先搜索
编程学到现在才真正到了高深部分，从这里往下学，你才知道什么叫做博大精深。今天我们要啃的这块硬骨头叫做深度优先搜索法。
首先我们来想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出口出来。那老鼠会怎么走？当然是这样的：老鼠如果遇到直路，就一直往前走；如果遇到分叉路口，就任意选择其中的一个继续往下走；如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去；如果遇到了出口，老鼠的旅途就算结束了。深度优先搜索法的基本原则就是这样：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到条件的目标为止。
实现这一算法，我们要用到编程的另一大利器——递归。递归是一个很抽象的概念，但是在日常生活中，我们还是能够看到的。拿两面镜子来，把他们面对着面，你会看到什么？你会看到镜子中有无数个镜子？怎么回事？A镜子中有镜子的像，B镜子中有镜子的像，A镜子的像就是A镜子本身的真实写照，也就是说镜子的像包括了A镜子，还有镜子在镜子中的像……好累啊，又烦又绕口，还不好理解。换成计算机语言就是A调用，而又调用，这样间接的，就调用了本身，这实现了一个重复的功能。
他再举一个例子：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？他讲：从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，讲什么呢？他讲：……。好家伙！这样讲到世界末日还讲不完，老和尚讲的故事实际上就是前面的故事情节，这样不断地调用程序本身，就形成了递归。
万一这个故事中的某一个老和尚看这个故事不顺眼，就把他要讲的故事换成：“你有完没完啊！”，这样，整个故事也就嘎然而止了。我们编程就要注意这一点，在适当的时候，就必须要有一个这样的和尚挺身而出，把整个故事给停下来，或者使他不再往深一层次搜索。要不，我们的递归就会因计算机存储容量的限制而被迫溢出。切记！切记！！
我们把递归思想运用到上面的迷宫中，记老鼠现在所在的位置是(x,y)，那它现在有前后左右四个方向可以走，分别是(x+1,y)，(x-1,y)，(x,y+1)，(x,y-1)，其中一个方向是它来时的路，先不考虑，我们就分别尝试其他3个方向，如果某个方向是路而不是墙的话，老鼠就向那个方向迈出一步。在新的位置上，我们又可以重复前面的步骤。老鼠走到了死胡同又是怎么回事？就是除了来时的路，其他3个方向都是墙，这时这条路就走到了尽头，无法再向深一层发展，我们就应该沿来时的路回去，尝试另外的方向。
例1&&8皇后问题。
在标准国际象棋的棋盘上（8×8格）准备放置位皇后，我们知道，国际象棋中皇后的威力是最大的，她既可以横走竖走，还可以斜着走，遇到挡在她前进路线上的敌人，她就可以吃掉对手。要求在棋盘上安放8位皇后，使她们彼此互相都不能吃到对方，求皇后的放法。
这是一道很经典的题目了，我们先要明确一下思路，如何运用深度优先搜索法，完成这道题目。首先建立一个8×8格的棋盘，在棋盘的第一行的任意位置安放一只皇后。紧接着，我们就来放第二行，第二行的安放就要受一些限制了，因为与第一行的皇后在同一竖行或同一对角线的位置上是不能安放皇后的，接下来是第三行，……，或许我们会遇到这种情况，在摆到某一行的时候，无论皇后摆放在什么位置，她都会被其他行的皇后吃掉，这说明什么呢？这说明，我们前面的摆放是失败的，也就是说，按照前面的皇后的摆放方法，我们不可能得到正确的解。那这时怎么办？改啊！我们回到上一行，把原先摆好的皇后换另外一个位置，接着再回过头摆这一行，如果这样还不行或者上一行的皇后只有一个位置可放，那怎么办？我们回到上一行的上一行，这和老鼠碰了壁就回头是一个意思。就这样的不断地尝试、修正，再尝试、再修正，我们最终会得到正确的结论。
{8皇后问题参考程序}
const n=8;
var a,b:array [1..n]{数组a存放解：a[i]表示第i个皇后放在第a[i]列；}
c:array [1-n,n-1]
d:array [2..n+n] {数组b，c，d表示棋盘的当前情况：b[k]为1表示第k行已被占领为0表示为空；c、d表示对角线}
{打印结果}
for j:=1 to n do write(a[j]:4);
procedrue try(i:integer);
{递归搜索解}
{每个皇后的可放置位置。注意：一定要在过程中定义；否则当递归时会覆盖掉它的值，不能得到正确结果}
&&&& for j:=1 to n do
&&&& begin
&&&&&&&&& if (b[j]=0) and (c[i-j]=0) and & (d[i+j]=0) then{检查位置是否合法}
&&&&&&&&& begin
&&&& &&&& &&&& a[i]:=j;
{置第i个皇后的位置是第j行}
&&&& &&&& &&&& b[j]:=1;
{宣布占领行、对角线}
&&&& &&&& &&&& c[i-j]:=1;
&&&& &&&& &&&& d[i+j]:=1;
&&&& &&&& &&&& if i&n then try(i+1)&{如果未达目标则放置下一皇后，否则打印结果}
&&&& &&&& &&&& b[j]:=0;
{清空被占行、对角线，回溯}
&&&& &&&& &&&& c[i-j]:=0;
&&&& &&&& &&&& d[i+j]:=0;
&&&&&&&&& for k:=1 to n do b[k]:=0;
{初始化数据}
&&&&&&&&& for k:=1-n to n-1 do c[k]:=0;
&&&&&&&&& for k:=2 to n+n do d[k]:=0;
&&&&&&&&& try(1);
在深度优先搜索中，也是从初始结点开始扩展，但是扩展顺序却不同，深度优先搜索总是先扩展最新产生的结点。这就使得搜索沿着状态空间某条单一的路径进行下去，直到最后的结点不能产生新结点或者找到目标结点为止。当搜索到不能产生新的结点的时候，就沿着结点产生顺序的反方向寻找可以产生新结点的结点，并扩展它，形成另一条搜索路径。
深度优先搜索中扩展结点的原则是先产生的后扩展。因此，深度优先搜索第一个找到的解，并不一定是问题的最优解，要搜索完整个状态空间，才能确定哪个解是最优解。
深度优先搜索的算法如下：
（1）从初始结点开始，将待扩展结点依次放到open表中。open表为栈结构，即遵守后进先出的规则。
（2）如果open表空，即所有待扩展结点已全部扩展完毕，则问题无解，退出。
（3）取open表中最新加入的结点，即栈顶结点出栈，并用相应的算符扩展出所有的予结点，并按顺序将这些结点放入open表中。若没有子结点产生，则转（2）。
（4）如果某个子结点为目标结点，则找到问题的解（这不一定是最优解），结束。如果要求得问题的最优解，或者所有解，则转（2），继续搜索新的目标结点。
【深度优先搜索的算法】
procedure DFS;
&&&&open&&←1; &&data[open] .state ←初始状态;&
&&&Search Success &←&
&&&&&&¤tnode &&←data[open];
&&&&&&open &&←open-l;
&&&&&&while current&{还可以扩展}&do begin
&&&&&&&&&&new ←&operate &(currentnode.state);
&&&&&&&&&&if new&&{重复于已有的结点状态}&
&&&&&&&&&&open ←&open+l;
&&&&&&&&&data[open].state ←&
&&&&&&&&&data[open].last ←&
&&&&&&&&&&if new&&&{是目标状态}&then begin Search Success ←&
&&&until &(open&l) &or &(Search Success);
&&&if Search Success then Output(Reslut)
&&&else 0utput(No Answer);
例2&&选数（select.pas）。
【题目描述】
已知n（1≤n≤20）个整数x1,x2,…,xn（1≤xi≤5000000），以及一个整数k（k&n）。从n个整数中任选k个整数相加，可分别得到一系列的和。现在，要求你计算出和为素数共有多少种。
例如，当n=4，，个整数分别为、、、时，可得全部的组合与它们的和为：；；；。
现在，要求你计算出和为素数共有多少种。
例如，例2只有一种和为素数：。
n , k （，＜）
x1,x2，…（）
一个整数（满足条件的种数）。
【样例输入】
3 7 12 19
【样例输出】
【算法分析】
本题无数学公式可寻，看来只能搜索（组合的生成算法），其实1≤n≤20这个约束条件也暗示我们本题搜索是有希望的，组合的生成可用简单的DFS来实现，既搜索这k个整数在原数列中的位置，由于组合不同于排列，与这k个数的排列顺序无关，所以，可以令a[I]&a[I+1]（a[I]表示第I个数在原数列中的位置），这个组合生成算法的复杂度大约为C(n,k)，下面给出递归搜索算法的框架。
Proc &Search(dep)&&&&&&&&&&&
for i &- a[dep - 1] + 1 to N - (M - dep) do
1. a[dep] &- i
2. S &- S + x[i]
3. if dep & }
我要回帖
更多关于 隐枚举法 的文章
更多推荐
- ·这是什么最好看免费观看高清电影大全？
- ·红歌大全100首老歌儿童歌曲(免费100首必听经典老歌歌100首)
- ·为什么有人会把喜欢看日漫与恨日本矛盾吗等同于忘记国耻
- ·1990年北京园艺博览会会徽及寓意亚运会的会徽是长城的形象
- ·怎么把蔡徐坤喜欢吃什么零食的甜甜圈抠下来
- ·求分享QQ美化包免费
- ·做设计的，感觉没前途。像我这样活着浪费空气，死了浪费土地赚不到钱的人，还不如死了。
- ·一天800兆的米粉卡，如果一天之内都联通米粉卡没用流量会扣钱不会扣费？
- ·七台河初中逸夫毕业的，高中苏州田家炳高中一本率毕业的二班小黑王子今，理科生。高考是(不告诉你们)分
- ·人类飞向太空的资料历程中，有什么里程碑事件？
- ·不会求解 武极大神帮帮忙们帮帮忙
- ·投影仪三点成圆的投影仪测量方法视频
- ·理科女生大学理科女生适合报考什么专业业？
- ·验光师资格证怎么考必须中专吗
- ·你们知道哪个网站的求租求租厂库房信息息比较多吗？库房无忧APP怎么样？
- ·跪求九幽将军百度云凤凰，百度云
- ·激光脱络腮胡有用吗真的行吗？能永久脱掉吗
- ·在湖南妈妈15页遗书找个爱妈妈？
- ·聚苯乙烯可以做什么增加聚氨酯pu的硬度吗
- ·哈工大威海航空专业服务专业我想查一下这个学校一个朋友的的背景，
- ·如何用枚举法是什么意思一一列出ABCD中取三个进行排列，取三个进行组合？
- ·大象快报邀请码的邀请码的要输入能有红包的应该是填的是什么呢？
- ·我当前企业团队区别于群体的一个的共同目标有哪些？
- ·加分政策中的报考汉幼儿语言表演儿歌大全授课的普通高等学校是什么意思?加多少分？
- ·谁知道甘肃庆阳镇原邮编新城耿沟石头崾岘特种野猪养殖场具体情况吗？
- ·水泥中外掺矿粉胶砂配比20%，水泥配比占多少
- ·我的泄露个人隐私怎么定罪私
- ·我空间意境有7G为什么用不了？
- ·球球大作战怎么刷宇宙能量块9.0版本能卡好宇宙能量块吗?
- ·校友会排名是依照什么？为什么西藏广西大学排名一个211校友会排名到二百多？
- ·谁知道这个字擘是什么字？
- ·螺旋扩弓器器断了
- ·求游戏人生第二季本子！ios手机接收！
- ·任何事情用英语怎么说?？
- ·小孩子能不能把尿晚上不让把尿怎么办
