搜索与回溯四大问题

搜索与回溯四大问题制作者：depthfirst问题一邮票问题(youpiao.pas/c/cpp)[问题描述]设有已知面额的邮票m种，每种有n张。用总数不超过n张的邮票进行组合，能组合的邮票面额中可以连续出现面额数最多是多少？(1=m=100,1=n=100,1=邮票面额=255)输入:第一行：n和m的值，中间用一空格隔开。第二行：a[1..m](面额)，每个数中间用一空格隔开。输出:连续面额数的最大值[样例输入](youpiao.in)43124[样例输出](youpiao.out)14[问题分析]这是一道对已知数进行组合的问题。常规方法是从最低面额开始，将所有的数的组合探求一遍，同时将所得到的值记录下来，然后对连续出现地数值进行统计，最后找出最值。从算法复杂度的角度来讲并不麻烦，但m和n值的大小始终是制约搜索速度的主要因素。因此如果在搜索过程中不加一定的优化，程序必然超时，因此我们必须要充分挖掘出其内含的限制条件，必要时还要用数学方法帮助解决。优化一：如果是通过小面额的组合来求得总的面额值，不仅解题难度较大，而且对较大的M和N而言，程序必然超时。但如果倒过来，将给定的面值进行拆分，解题的难度就大大减少。试以面额值为8为例（等式说明：4*2表示面值为4的邮票有2张）：8＝4*2＝4*1+2*1+1*2＝4*1+2*2＝2*4优化二：在构成邮票面额时，难免出现同一个面额不同的组合的情况，根据题目要求只要某种面额出现一种组合就可以了，所以我们可以采用一些数学技巧来减少多余的组合。这样就可以加快程序运行速度。结合刚才对8进行拆分的例子，我们可以注意到最容易实现的的用邮票数最少的方案。给我们的启示是：对邮票组合面值的探求可以从大面值的邮票开始。优化三：根据题意，有一个很明显的限制条件就是所用邮票总数不超过n张，这个条件可以带来两个方面的信息：一是指出了邮票面额的最大值为n*a[m]或是题目给出的255；另一就是限定了总张数的最值为n，结合优化一的方法，可以最大限度地“剪枝”。[参考过程]：a：array[1..100]ofinteger；{记录m种不同的面值，并由低到高排列}b:array[1..255]ofinteger；{记录可能出现的面额}n,m:integer；maxlong:integer；{记录面额连续出现的最多数}proceduresearch(k,n,x:integer)；{k表示第k个已知面额，n表示可用已知面额的最多数量，x表示目前已构成的面额值}vari:integer；beginif(n=0)or(k=0)thenexit；fori:=ndownto0dobeginx:=x+a[k]*i；n:=n-i；b[x]:=b[x]+1；search(k-1,n,x)；n:=n+i；x:=x-a[k]*i；end；end；问题二N皇后问题(nqueen.pas/c/cpp)[问题描述]在N*N的棋盘上放置N（1=n=100）个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法和方法总数。[输入样例](nqueen.in)8[输出样例](nqueen.out)115863724216837425……90825317469183162574928413627592[问题分析]显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在／斜线上的行列值之和相同；如果同在＼斜线上的行列值之差相同；从下图可验证（以八皇后为例）：１２３４５６７８１２３４５６７８｜／＼｜／＼｜／＼｜／－－－▲－－－－／｜＼／｜＼／｜＼考虑每行有且仅有一个皇后，设一维数组a[1..n]表示皇后的放置：第i行皇后放在第j列，用a[i]＝j来表示，即下标是行数，内容是列数。例如：a[3]=5就表示第3个皇后在第3行第5列上。判断皇后是否安全，即检查同一列、同一对角线是否已有皇后，建立标志数组b控制同一列只能有一个皇后，若两皇后在同一对角线上，则其行列坐标之和或行列坐标之差相等，故亦可建立标志数组c、d控制同一对角线上只能有一个皇后。如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。在这种方式下，要表示两个皇后I和J不在同一列或斜线上的条件可以描述为：a[i]a[j]andabs(i-j)abs(a[i]-a[j])[参考过程]vara:array[1..100]ofinteger;b,c,d:array[-100..200]ofboolean;t,i,j,k,n:integer;procedureprint;begint:=t+1;write(t);fork:=1tondowrite(a[k]);writeln;end;proceduretry(i:integer);varj:integer;beginifinthenbeginprint;exit;end;forj:=1tondoifb[j]andc[i+j]andd[i-j]thenbegina[i]:=j;b[j]:=false;c[i+j]:=false;d[i-j]:=false;ifinthentry(i+1)elseprint;b[j]:=true;c[i+j]:=true;d[i-j]:=true;end;end;问题三自然数的拆分(chaifen.pas/c/cpp)[问题描述]输入自然数n（1=n=30），然后将其拆分成由若干数相加的形式，参与加法运算的数可以重复。输入：待拆分的自然数n输出：若干数的加法式子[样例输入](chaifen.in)7[样例输出](chaifen.out)1+61+1+51+1+1+41+1+1+1+31+1+1+1+1+21+1+1+1+1+1+11+1+1+2+21+1+2+31+2+41+2+2+21+3+32+52+2+33+4[问题分析]简单的搜索回溯，只是不断拆分最后一个数再回溯。等式中后一个数必须大于等于前一个数，因为这个可以避免重复和提高效率。我们用一个数组a[i]来记录拆分的数字，用b[i]记录剩下的数字。k记录第几个拆分的数字。每次拆分都可以把a[i]都打印出来。把剩下的数字b[i]在进行拆分，并且是从i开始拆分的[参考过程]proceduresearch(start,m,k:integer);vari,j:integer;beginfori:=startto(mdiv2)dobegina[k]:=i;b[k]:=m-i;forj:=1tokdowrite(a[j],'+');writeln(b[k]);search(i,b[k],k+1);end;end;问题四校园迷宫[问题描述]李华被教育局分配到了红星学校，当然是陪着很多人的。不知转了多少次车，总算到了。可惜的是，学校像个迷宫一样，只在门口贴了张学校地图。李华就开始研究地图了，但是学校错综复杂，等找到目的地，早就开考了。为此，李华取出随身携带的微型电脑。注：只能往4个方向走：上、下、左、右。输入格式第1行，二个数，N，M。接下来是一个N*M的矩阵，表示这个学校。（有N行，M列）。矩阵由2个数字组成。0：路；1：墙。路能走，墙不能走（这是基本常识,不过还是提醒一下，不然哪个牛又要飞檐走壁了）。再是2行，第1行2个数X1，Y1表示校门口的坐标（即校门口在矩阵的第X1行，第Y1列）。第2行2个数X2，Y2表示鄙人的考场的坐标（即校门口在矩阵的第X2行，第Y2列）。数据范围：0M，N=2000。0〈X1，X2〈=N，0〈Y1，Y2〈=M。输出格式一个数，表示最少要走的步数。如果走不到，则输出NoAnswer![样例输入]5511111111001000100100111014154[样例输出]6注意：本ppt内容确实非本人原创，系本人由everyknower文件改编而来，但everyknower是本人曾用账号，因此不存在侵权问题。如在网络上发现作者名为“depthfirst”“everyknower”或“编者”，此三者都是本人，都不属于侵权问题。版权说明