信息学奥赛_算法教程_Pascal.doc

第3章 算法与程序设计模块信息学奥赛辅导教程第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的函数）。空间复杂度是实现算法所占用的空间为g(n)（也为n的函数）。称O(f(n)和O(g(n)为该算法的复杂度。 3.1.4 程序设计1程序程序是对所要解决的问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构算法程序。2程序设计程序设计就是设计、编制和调试程序的过程。程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计两个阶段。除了好的程序设计方法和技术之外，程序设计风格也很重要。因为程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格可以使程序结构清晰合理，使程序代码便于维护。因此，程序设计风格对保证程序的质量很重要。一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要阅读和跟踪程序，因此程序设计的风格总体而言应该强调简单和清晰，必须可以理解。可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。要形成良好的程序设计风格，主要应注重源程序文档化。（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序的功能进行理解。（2）程序注释：正确的注释能够帮助读者理解程序。3结构化程序设计结构化程序设计方法是程序设计的先进方法和工具。采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。结构化程序语言仅使用顺序、选择和循环3种基本控制结构就足以表达出各种其他形式结构的程序设计方法。总之，遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有明显的优点。其一，程序结构良好、易读、易理解和易维护；其二，可以提高编程工作的效率，降低软件开发成本。练习题（1）算法的时间复杂度是指（ ）。A执行算法程序所需要的时间 B算法程序的长度C算法执行过程中所需要的基本运算次数 D算法程序中的指令条数【解析】所谓算法的时间复杂度，是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量。【答案】C（2）算法的空间复杂度是指（ ）。A算法程序的长度 B算法程序中的指令条数C算法程序所占的存储空间 D算法执行过程中所需要的存储空间【解析】空间复杂度是指执行算法所需要的存储空间。算法所占用的存储空间包括算法程序所占的空间、输入初始数据所占的存储空间以及算法执行过程中所需要的额外空间。【答案】D（3）算法指的是（ ）。A计算机程序 B解决问题的计算方法C排序算法 D解决问题的有限运算序列【解析】所谓算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。【答案】D（4）算法能正确地实现预定功能的特性称为算法的（ ）。A正确性 B易读性 C健壮性 D高效率【解析】针对实际问题设计的算法，人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的，因此算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。算法与计算公式是有差别的，在设计一个算法时，必须要考虑它的可行性，否则将得不到满意的结果。【答案】A（5）递归算法一般需要利用（ ）来实现。A栈 B队列 C循环链表 D双向链表【答案】A3.2 穷举搜索法有一些问题一时难以找到规律或者公式，或者根本没有规律、公式。这时可以利用计算机高速运算的特点，使用穷举来解决。穷举搜索法是穷举所有可能情形，并从中找出符合要求的解决。穷举搜索法所有可能情形，最直观的是联系循环的算法。例1 找出n个自然数（1,2,3,n）中r个数的组合。例如，当n=5，r=3时，所有组 合为： 5 5 3 5 4 2 5 4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2 1 total=10 组合的总数程序 program zuhe11; const n=5; var i,j,k,t:integer; begin t:=0; for i:=n downto 1 do for j:=n downto 1 do for k:=n downto 1 do if (ij) and (ik) and (ij) and (jk) then begin t:=t+1;writeln(i:3,j:3,k:3); end; writeln(total=,t); end.这个程序，穷举了所有可能情形，从中选出符合条件的解，很多情况下穷举搜索法还是常用的。例2 算24点（poi24.pas）。 【题目描述】几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲。在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个19之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。您可以使用的运算只有：+，-，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(22)/4是合法的，2(2/4)是不合法的）。下面我们给出一个游戏的具体例子：若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+37=24。【输入】只有一行，四个19之间的自然数。【输出】如果有解的话，只要输出一个解，输出的是3行数据，分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“=24”。如果两个操作数有大小的话则先输出大的。如果没有解，则输出“no answer!”【样例】poi24.in poi24.out1 2 3 72+1=373=2121+3=24【算法分析】计算24点主要应用四种运算。开始状态有四个操作数，一个运算符对应两个操作数，所以一开始选择两个操作数分别对四个操作符进行循环检测，每一次运算后产生了新的数，两个数运算变成一个数，整体是少了一个操作数，所以四个数最终是三次运算。由于操作的层数比较少（只有三层），所以可以用回溯的算法来进行检测，当找到一个解时便结束查找。如果所有的情况都找过后仍然没有，则输出无解的信息。程序program poi24; point24type arr=array 1.4 of integer;var i,result,n,len:integer; d:arr; r:array 1.3,1.4 of integer; infile,outfile:text;procedure print;var i,j:integer;begin assign(outfile,poi24.out); rewrite(outfile); for i:=1 to 3 do begin for j:=1 to 3 do if j2 then write(outfile,ri,j) else case ri,j of 1:write(outfile,+); 2:write(outfile,-); 3:write(outfile,*); 4:write(outfile,/) end; writeln(outfile,=,ri,4) end; close(outfile);end;procedure try(k:integer;d:arr);var a,b,i,j,l,t:integer; e:arr;begin if k=1 then if d1=24 then begin print;halt end else else begin for i:=1 to k-1 do for j:=i+1 to k do begin a:=di; b:=dj; if ab then begin t:=a;a:=b;b:=t end; t:=0; for l:=1 to k do if (li) and (lj) then begin t:=t+1;et:=dl end; r5-k,1:=a; r5-k,3:=b; r5-k,4:=-1; for l:=1 to 4 do begin case l of 1:r5-k,4:=a+b; 2:r5-k,4:=a-b; 3:r5-k,4:=a*b; 4:if b0 then if a mod b=0 then r5-k,4:=a div b end; r5-k,2:=l; if r5-k,4-1 then begin et+1:=r5-k,4; try(k-1,e) end end end end;end;begin assign(infile,poi24.in); reset(infile); for i:=1 to 4 do read(infile,di); close(infile); try(4,d); assign(outfile,poi24.out); rewrite(outfile); writeln(outfile,no answer!); close(outfile);end.练习题彩虹7号（rainbow.pas）X市是一个重要的军事基地，在这个基地中有一支名为“彩虹7号”的特别部队。每个队员都有一个固定独立的编号X(1X215)，他们的职责就是完成部队交给他们的任务，每个任务同样都有固定独立的编号N(1N10)。在执行任务的过程中，为了保证任务的保密性和队员的安全，队员和队员之间的联系将必须由特别部队所提供的一种保密频段交互设备进行。每个队员都需要一个身份验证口令进入系统，由于队员所执行的任务都是涉及国家安全或者极高机密的活动，如果队员使用的口令出现错误，他们将付出无法估计的代价。特别部队的队员都是层层筛选的精英人才，所以不希望发生这样的事情。因此队员必须牢记口令的设置方法。口令S的内容满足：SN=X。显然，S有可能也很有可能是一个无理数，所以限定S为一个实数，它包含整数部分和小数部分，不包含小数点（即0.1将视作01）。口令的长度 M(10M50)，将根据任务的难度而有所不同。 编程任务：给定X，N，M。计算口令的内容S。输入（rainbow .in）：文件输入，文件有且仅有一行包含3个整型数X，N，M，每个数之间以一个空格符隔开。输出（rainbow.out）：文件输出，文件有且仅有一行，为S的结果。样例输入：2 2 10样例输出：1414213652注意：口令的最后一位请使用去尾法保留，不要使用四舍五入法保留。文件请不要包含多余的空格和换行。3.3 递 归 法递归作为一种强有力的数学和算法描述工具在Pascal语言中被广泛使用。一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有定义本身的引用（在过程或自定义函数中，又包含自己调用自己），则称它们是递归的或者是递归定义的。一个递归算法仅使用少量的程序编码就可描述出解题所需要的多次重复计算而不需要设计循环结构。使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的规模较小的问题来求解，进而最终导致原问题的解决。例如：n!的定义，我们知道，在数学中n!一般定义为： 1 若n=0 n!= n(n-1)! 若n0 在n0的公式中，又包含了（n-1）!，这就是递归定义。利用递归方法，可以用有限的语句来定义对象的无限集合。但在递归定义中，应该至少有一条是非递归的，即初始定义。如上面例子中的第一条，否则就变成了循环定义，产生逻辑性错误。 n!的递归定义的程序： program findn； var n：integer； t：longint； procedure find（n：integer）； begin if n0 then t：1 else begin find（n-1）； t：tn end； 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!=32!，必须先求2!，即程序中的f(n-1)，此时系统自动先保存n的原值3，再设n=2，进入第一层递归调用。（3）因为2!=21!，所以系统又保存2，并设n=1，进入第2层调用。（4）因为1!=10!，所以保存1，并设n=0，进入第3层调用。（5）因为n=0，终止调用，t赋值1，返回4的入口点。（6）取出执行4时保存的1，求出t=1t=1，返回3的入口点。（7）取出执行3时保存的2，求出t=2t=2，返回2的入口点。（8）取出执行2时保存的3，求出t=3t=6，返回1的入口点。（9）返回主程序，输出结果：t=6。从上面分析的过程看到，由于递归调用，需用同一变量名n，但值不同，所以在调用前必须先把n的原值保存，再赋以新值，然后进入调用。调用结束后，再把保存的值取出，使n恢复原来的值。在过程中find中又包含find(n-1)，即又调用了它自己，这就是递归调用。包含有递归调用的算法，就叫做递归算法。递归调用会产生无终止运算的可能性，因此必须在适当时候终止递归调用，即在程序中必须要有终止条件。上面程序中，过程find的第一条语句就是终止条件。一般地，根据递归定义设计的递归算法中，非递归的初始定义，就用作程序中的终止 条件。实践证明，不是所有问题都可以用递归的方法处理，用递归算法编写的程序也不一定是好程序。可以看出，执行递归的过程既浪费时间又费存储空间，因此有的语言系统，禁止使用递归，由于计算机存储容量的限制，编译系统也不允许递归。但因递归特别符合人们的思维习惯，递归算法的设计也要比非递归算法设计容易，所以当问题是递归定义，尤其是当涉及的数据结构是递归定义的时候，使用递归算法特别合适。应用递归算法能够求解的问题一般具有两个特点：存在某个特定条件，在此条件下，可得到指定的解，即递归在终止状态。对任意给定的条件，有明确的定义规则，可以产生新的状态并将最终导出终止状态，即存在导致问题求解的递归步骤。递归是用栈来实现的。不过，递归恐怕不像想象得这么简单。首先，它体现了一个数学思想：化归，即把一个问题转化成另一个的方法。递归比较特殊，它是转化成性质相似，但规模更小的问题。 例3 阅读程序NOIp2001_G。program gao7_1; function ack(m,n:integer):integer; begin 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)end;begin writeln(ack(3,4);readln;end.分析：这个程序我们可以用下面的函数表示。在解题时，一般都是用递归的方法去实现的，而递归方法将会计算五千多步，在竞赛时这种方法是不可用的，而递归往往可以用递推去实现，因此，我们在教学过程中就讲解了该函数的递推过程，现将推导过程表示如下：（1）我们在递归过程中发现该函数总是要调用到M=0，M=1及M=2的情况，因此，我们就考虑要推导ACK（3，N）必须首先推导ACK（0，N），ACK（1，N）以及ACK（2，N）的情况。（2）ACK（0，N）可以由函数直接得到，公式为ACK（0，N）=N+1（3）ACK（1，0）=ACK（0，1）=1+1=0+2 ACK（1，1）=ACK（0，ACK（1，0）=ACK（0，1+1）=1+1+1=1+2 ACK（1，2）=ACK（0，ACK（1，1）=ACK（0，1+2）=1+1+2=2+2 因此，我们可以联想到ACK（1，N）=N+2。这个公式可以用数学归纳法证明之。（略）根据上面的方法，我们可以方便地推导出下面一些公式：（4）ACK（2，0）=ACK（1，1）=1+2=3（利用M=1的公式） ACK（2，1）=ACK（1，ACK（2，0）=ACK（1，1+2）=3+2=5（利用M=1的公式及ACK（2，0）ACK（2，2）=ACK（1，ACK（2，1）=ACK（1，5）=5+2=（2+1）*2+1因此，我们可以联想到ACK（2，N）=（N+1）*2+1。同样，这个公式可以用数学归纳法证明之。（略）（5）ACK（3，0）=ACK（2，1）=(1+1)*2+1=5（利用M=2的公式）ACK（3，1）=ACK（2，ACK（3，0）=ACK（2，5）=（(1+1)*2+1+1）*2+1=23+22+1ACK（3，2）=ACK（2，ACK（3，1）=ACK（2，13）=（23+22+1+1）*2+1=24+23+22+1=25-3因此，我们可以联想到ACK（3，N）=2(N+3)-3。例4 仍以例1为例，找n个数的r个数的组合。 输入：n，r =5，3 输出：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组数。首先固定第一位数（如5），其后是在另4个数中再“组合”2个数。这就将“5个数中3个数的组合”推到了“4个数中2个数的组合”上去了。第一位数可以是n，r （如5，3），n个数中r个数组合递推到n-1个数中r-1个数有组合，这是一个递归的算法。即： var i:integer; begin for i:=n downto r do begin 固定i的输出位置 comb(i-1,r-1); 原过程递推到i-1个数的r-1个数组合 end; end;再考虑打印输出格式。程序 var k,n,r:integer; Produrce comb(n,r:integer); var i,temp:integer; begin for i:=n downto r do if (in)and(kr) then k为过程外定义的 begin for temp:=1 to (k-r)*3 do write( ); 确定i的输出位置 end; write(i:3); if i1 then comb(i-1,r-1); 递推到下一情形 else writeln; end; begin main write(n,r=);readln(n,r); if rn then begin writeln(Input n,r error!);halt;end; comb(n,r); 调用递归过程 end;练习题1邮票面值设计（postag.pas）【题目描述】给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+k40) 种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大max ，使得1-max之间的每一个邮资值都能得到。例如，N=3，K=2，如果面值分别为1分、4分，则在l6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在17分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到连续的邮资最大值，所以max=7，面值分别为l分、3分。【样例输入】3 2 输入第一个数N，第二个数K，中间用空格间隔【样例输出】1 3 输出的第一行面值分别为l分、3分max=7 输出的第二连续的邮资最大值2聪明的学生（guess.pas）【题目描述】一位教授逻辑学的教授有三名非常善于推理且精于心算的学生A，B和C。有一天,教授给他们3人出了一道题：教授在每个人脑门上贴了一张纸条并告诉他们，每个人的纸条上都写了一个正整数，且某两个数的和等于第三个。于是，每个学生都能看见贴在另外两个同学头上的整数，但却看不见自己的数。这时，教授先对学生A发问了：“你能猜出自己的数吗？”A回答：“不能。”教授又转身问学生B：“你能猜出自己的数吗？”B想了想，也回答：“不能。”教授再问学生C同样的问题，C思考了片刻后，摇了摇头：“不能。”接着，教授又重新问A同样的问题，再问B和C，经过若干轮的提问之后，当教授再次询问某人时，此人突然露出了得意的笑容，把贴在自己头上的那个数准确无误地报了出来。现在，如果告诉你：教授在第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M，你能推断出另外两个学生的头上贴的是什么数吗？【提示】在没有人猜出自己头上的数之前，大家对教授提问的回答始终都是“不能”；而且除此之外在A，B，C之间是没有进行任何信息交流的。也就是说，每个人推断的依据仅仅是另外两个人的头上数，以及大家对教授的提问所做出的否定回答。教授总是从学生A开始提问的。你可以假定，这3个聪明的学生能够根据已知的条件在最早的轮次猜出自己的数，并且永远都不会猜错。稍经分析和推理，你将得出以下结论：总是头上贴着最大的那个数的人最先猜出自己头上的数。【输入文件】输入文件为guess.in。该文件包括若干组测试数据，其中的每一行代表一组测试数据，由两个整数N和M组成（即在教授第N次提问时，轮到回答问题的那个人猜出了贴在自己头上的数是M）。两个数之间用空格分隔开。最后，由-1 -1组成的一行标志着输入的数据结束。同时要求，0N500; 0M30000。【输出文件】输出文件为guess.out。按照输入文件中的顺序依次给出各组数据的结果。文件中对应每组数据输出的第一行是一个整数p，是可能情况的总数。接下来的p行，每一行包括3个数，分别为贴在A、B、C头上的3个数。输出时，所有解按照A头上的数增序排列；在A头上的数相同的情况下，按照B头上的数增序排列。【样例输入】5 83 22 3-1 -1【样例输出】32 8 65 8 36 8 211 1 212 3 13.4 回 溯 法回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”思想作为其控制结构 例5 再以例1说明，找n个数中r个数的组合。分析：将自然数排列在数组A中。 A1 A2 A3 5 4 3 5 4 2 3 2 1排数时从A1到A2再到A3，后一个至少比前一个数小1，并且应满足ri+Arir。若ri+Arir就要回溯，该关系就是回溯条件。为直观起见，当输出一组组合数后，若最后一位为1，也应作一次回溯（若不回，便由上述回溯条件处理）。程序program zuhe3; type tp=array1.100 of integer; var n,r:integer;procedure comb2(n,r:integer;a:tp); var i,ri:integer; begin ri:=1;a1:=n; repeat if rir then 没有搜索到底 if ri+arir then 判断是否回溯 begin ari+1:=ari-1; ri:=ri+1; 向前搜索 end; else begin ri:=ri-1;ari:=ari-1;end; 回溯 else begin for j:=1 to r do write(aj:3);writeln; 输出组合数 if ar=1 then 是否回溯 begin ri:=ri-1;ari:=ari-1;end; 回溯 else ari:=ari-1; 递推到下一个数 end; until a1r-1; end;begin write(n,r=);readln(n,r); if rn then begin writeln(Input n,r error!);halt;end; comb2(n,r); end.练习题1马拦过河卒（knight.pas）【题目描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时，在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，A点（0, 0）、B点（n, m）（n, m为不超过15的整数），同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。【输入】一行四个数据，分别表示B点坐标和马的坐标。【输出】一个数据，表示所有的路径条数。【样例】knight.in knight.out6 6 3 362走迷宫（maze.pas） 【题目描述】有一个mn格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这mn个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息（用-l表示无路）。【输入】第一行是两个数m，n(1m,n15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。【输出】所有可行的路径，描述一个点时用（x,y）的形式，除开始点外，其他的都要用“”表示方向。如果没有一条可行的路则输出-1。【样例输入】5 61 0 0 1 0 11 1 1 1 1 10 0 1 1 1 01 1 1 1 1 01 1 1 0 1 11 15 6【样例输出】(1,2)(2,1)(2,2)(2,3)(2,4)(2,5)(3,5)(3,4)(3,3)(4,3)(4,4)(4,5)(5,5) (5,6)(1,1)(2,1)(2,2)(2,3)(2,4)(2,5)(3,5)(3,4)(4,4)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(2,4)(2,5)(3,5)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(2,4)(3,4)(3,3)(4,3)(4,4)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(2,4)(3,4)(3,5)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(2,4)(3,4)(4,4)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(3,3)(3,4)(2,4)(2,5)(3,5)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(3,3)(3,4)(3,5)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(3,3)(3,4)(4,4)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(3,3)(4,3)(4,4)(3,4)(2,4)(2,5)(3,5)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(3,3)(4,3)(4,4)(3,4)(3,5)(4,5)(5,5)(5,6)(1,1)(2,1)(2,2)(2,3)(3,3)(4,3)(4,4)(4,5)(5,5)(5,6)3组合的输出（track.pas） 【题目描述】排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素（不分顺序且rn），我们可以简单地将n个元素理解为自然数1,2,n，从中任取r个数。现要求你不用递归的方法输出所有组合。 例如：n5，r3，所有组合为：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(1n21，1rn)。【输出】所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占3个字符的位置，所有的组合也按字典顺序。【样例输入】5 3【样例输出】1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 53.5 递 推递推是迭代算法中一种用若干步可重复的简单运算来描述复杂数学问题的方法，以便于计算机进行处理。它与递推关系的思想完全一致，由边界条件开始往后逐个推算，在一般情况下，效率较高，编程也非常的方便。但是，我们一般只需要求递推关系的第n项，而边界条件与第n项前面之间的若干项的信息是我们不需要的，如果采用递推的方法来求解的话，第n项之前的每一项都必须计算出来，最后才能得到所需要的第n项的值。这是递推无法避免的，从而在一定程度上影响了程序的效率。当然在大多数情况下，采用递推的方法还是可行的，在竞赛中，使用递推的方法编程，通常会在时限内出解。当然，更好的求解方法还有母函数法、迭代归纳法等。例1 青蛙过河（frog.pas）。【题目描述】有一条河，左边一个石墩（A区）上有编号为1，2，3，4，n的n只青蛙，河中有k个荷叶（C区），还有h个石墩（D区），右边有一个石墩（B区），如图3-1所示。n只青蛙要过河（从左岸石墩A到右岸石墩B），规则为：图3-1 青蛙过河示意图（1）石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙（不论大小）。（2）青蛙可以：AB（表示可以从A跳到B，下同），AC，AD，CB，DB，DC，CD。（3）当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1号的青蛙上面。你的任务是对于给出的h、k，计算并输出最多能有多少只青蛙可以根据以上规则顺利 过河？【样例输入】2 3 河中间有2个石礅，3个荷叶【样例输出】16最多有16只青蛙可以按照规则过河【算法分析】从具体到一般，推导过程如下：f(0,0)=1;f(0,k)=k+1;如k=3时，有4只青蛙可以过河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:integer; begin assign(input,frog.in); assign(output,frog.out); reset(input); rewrite(output);readln(h,k);s:=k+1;for i:=1 to h do s:=s*2;writeln(s);close(input);close(output)end.例2 排序集合（sort.pas）。【题目描述】对于集合N=1,2,n的子集，定义一个称之为“小于”的关系