试题、程序及解题报告山东noip2007讲义提高二7

1、回文素数：1位：2 3 5 72位：11，此外，没有其它的位数为偶数的回文素数。2*k+1位：枚举最高位上的数字1,3,7,9枚举2.k位上的数字000.999枚举中间位置上的数字0.9求得回文数如果是素数，则输出。数环：搜索过程中频繁用到素数的判断，可以事先建立3.2*n*n-1的素数表来作素数的判断，减少重复运算。前n-1个分数之和为t1/t2,如果存在第n个分母x，使得T1/t2+1/x=1,则t1=t2-1,x=t2.证明：因为t1/t2+1/x=1，所以x=t2/(t2-t1)设k=t2-t1，则 t2=kxk=kx-t1t1=k(x-1)t1、t2有公因子k，同时t1/t2为即约分

2、数故k=1,原问题得证。剪枝：假设当前要搜Xi，而和已经是t1/t2,1.若以后的(n-i+1)个数都取最大值，即1/Xi-1，也不可能达到1,则必然是无解的；2.同理，如果后面的(n-i+1)个数中，最后一个分数无穷小，另外（n-i）个都取最小值，即1/m，它们的和也会大于1,则必然也是无解的。如果t1/t2加上其余各项的最大值之和仍小于1,不必继续搜索；如果t1/t2加上其余各项的最小值之和仍超过1,不必继续搜索。算法实现：Procedure search( p)；Var i:integer;Begin If n=step then begin if t1+1=t2 then inc(to

3、t); exit; end; If t21e10 then exit; for i:=p to m do search(step+1,i,t1*i+t2,t2*i);End;主程序：begin readln(n,m); Tot:=0; for i:=2 to m do search(2,i,1,i); writeln(tot);end.If (n-step+1)/p+t1/t21 then exit;Procedure reduce(var p);埃及分数在古埃及，人们使用单位分数的和（形如1/a的，a是自然数）表示一切有理数。例如：2/31/2+1/6，但不允许2/3=1/3+1/3，因为加

4、数中有相同的。对于一个分数a/b，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：19/45=1/3+1/12+1/18019/45=1/3+1/15+1/4519/45=1/3+1/18+1/3019/45=1/4+1/6+1/18019/45=1/5+1/6+1/18最好的是最后一种，因为1/18比1/180,1/45,1/30都大。输入：a，b输出：若干个数，从小到大排列，依次是单位分数的分母。输入样例：19 45输出样例：5 6 18记忆化搜索 如果解答树中存在一些性质相同的子树，那么，只要我们知道了其中一棵子树的性质，就可以

5、根据这个信息，导出其它子树的性质。这就是自顶向下记忆化搜索的基本思想。序关系计数问题用关系和=将3个数a、b和C依次排列有13种不同的关系：abC， ab=C， aCb， a=bC， a=b=C， a=Cb， baC， ba=C， bCa， b=Ca， Cab， Ca=b， Cb=Open;If Closed=Open then 输出无解。分油问题：设有大小不等的3个无刻度的油桶，分别能够存满，X，Y，Z公升油（例如X=80，Y=50，Z=30）。初始时，第一个油桶盛满油，第二、三个油桶为空。编程寻找一种最少步骤的分油方式，在某一个油桶上分出targ升油（例如targ=40）。若找到解，则将分

6、油方法打印出来；否则打印信息“UNABLE”等字样，表示问题无解。算法设计 分油程序的算法主要是，每次判断当前油桶是不是可以倒出油，以及其他某个油桶是不是可以倒进油。如果满足以上条件，那么当前油桶的油或全部倒出，或将另一油桶倒满，针对两种不同的情况作不同的处理。广度搜索 Node(节点类型)Record Situtation:TSituation（当前节点状态）; Level:Integer(当前节点深度); Last :Integer(父节点); End List(节点表):Array1.Max(最多节点数) of Node(节点类型); open(总节点数):Integer; close(

7、待扩展节点编号):Integer; New-S:TSituation;(新节点) List-0; open-1; close-0; List1.Situation- 初始状态; List1.Level:=1; List1.Last:=0; While (closeopen(还有未扩展节点) and (openMax(空间未用完) and (未找到目标节点) do Begin close:=close+1; For I:=1 to TotalExpendMethod do（扩展一层子节点） Begin New-S:=ExpendNode(Listclose.Situation,I); If No

8、t (New-S in List) then (扩展出的节点从未出现过) Begin open:=open+1; Listopen.Situation:=New-S; Listopen.Level:=Listclose.Level+1; Listopen.Last:=close; End-If End-For; End-While;聪明的打字员阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0，S

9、wap1，Up，Down，Left，Right。为了说明这6个键的作用，我们先定义录入区的6个位置编号，从左到右依次为1，2，3，4，5，6。下面列出每个键的作用：Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置的数字交换。如果光标已经处在录入区的1号位置，则按Swap0键之后，录入区的数字不变；Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号位置的数字交换。如果光标已经处在录入区的6号位置，则按Swap1键之后，录入区的数字不变；Up：按Up，光标位置不变，将光标所在位置的数字加1（除非该数字是9）；如果该处数字是9，则按Up之后，数字

10、不变，光标位置也不变；Down：按Down，光标位置不变，将光标所在位置的数字减1（除非该数字是0）；如果该处数字为0，则按Down之后，数字不变，光标位置也不变；Left：光标左移一个位置，如果光标已经在录入区的1号位置，则光标不动；Right：光标右移一个位置，如果光标已经在录入区的6号位置，则光标不动。当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为6的初始密码，而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。输入：两个长

11、度为6的数，前者使初始密码，后者是目标密码，中间用一个空格隔开；输出：一个正整数：最少需要的击键次数。输入样例：123456 654321输出样例：11两机器加工问题有n个部件需在A,B机器上加工，每个工件都必须经过先A后B两道工序。已知：部件i在A、B机器上的加工时间分别为ai，bi。问：如何安排n个工件的加工顺序，才能使得总加工时间最短？输入示例：N=5工件I12345Ai358710Bi62149输出：最少的加工时间：34最小加工时间的加工顺序：15423洗牌问题：有一摞扑克牌共N张（N为偶数），自上而下编号依次为1，2，3，N。将它等分成上下两摞，分别记为A、B，按以下规则洗牌，使之重新成为一摞：A摞的第一张牌夹在B摞的第一、二张牌之间；A摞的第二张牌夹在B摞的第二、三张牌之间；，A摞的最后一张牌放在B摞最后一张牌的下面。求对于给定的扑克牌数N（N为偶数，N3-8-7-