第5讲 回溯法专题讲座 编程大赛课程.doc

第5章 回溯法5.1 回溯法概述与穷举的“笨拙”搜索相比，回溯法则是一种“聪明”的求解效益更高的搜索法。下面介绍回溯设计及其应用，体会回溯法相对于穷举的特点与优势。5.1.1 回溯的概念有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往使用回溯法。回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。因此，回溯法可以形象地概括为“向前走，碰壁回头”。回溯法的基本做法是试探搜索，是一种组织得井井有条的、能避免一些不必要搜索的穷举式搜索法。回溯法在问题的解空间树中，从根结点出发搜索解空间树，搜索至解空间树的任意一点，先判断该结点是否包含问题的解；如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其父结点回溯；否则，进入该子树，继续搜索。从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。倘若当前候选解除了不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。5.1.2 回溯描述 1回溯的一般方法下面简要阐述回溯的一般方法。回溯求解的问题P，通常要能表达为：对于已知的由n元组(x1,x2,xn)组成的一个状态空间E=(x1,x2,xn)|xisi,i=1,2,n，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中si是分量xi的定义域，且|si|有限，i=1,2,n。称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是穷举法，上面已经作了介绍，即对E中的所有n元组逐一地检验其是否满足D的全部约束，若满足，则为问题P的一个解。显然，其计算量是相当大的。对于许多问题，所给定的约束集D具有完备性，即i元组(x1,x2,xi)满足D中仅涉及到x1,x2,xi的所有约束，意味着j(ji)元组(x1,x2,xj)一定也满足D中仅涉及到x1,x2,xj的所有约束，i=1,2,n。换句话说，只要存在0jn-1，使得(x1,x2,xj)违反D中仅涉及到x1,x2,xj的约束之一，则以(x1,x2,xj)为前缀的任何n元组(x1,x2,xj,xj+1,xn)也一定违反D中仅涉及到x1,x2,xj的一个约束，nij。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组(x1,x2,xj)违反D中仅涉及x1,x2,xj的一个约束，就可以肯定，以(x1,x2,xj)为前缀的任何n元组(x1,x2,xj,xj+1,xn)都不会是问题P的解，因而就不必去搜索它们，即省略了对部分元素(xj+1,xn)的操作与测试。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比穷举法效率更高的算法。2. 4皇后问题的回溯实施为了具体说明回溯的实施过程，先看一个简单实例。如何在44的方格棋盘上放置4个皇后，使它们互不攻击，即任意两个皇后不允许处在同一横排，同一纵列，也不允许处在同一与棋盘边框成45角的斜线上。图5-1所示为应用回溯的实施过程，其中方格中的表示试图在该方格放置一个皇后,但由于受前面已放置的皇后的攻击而放弃的位置。图5-1 4皇后问题回溯实施求解图（a）为在第1行第1列放置一个皇后的初始状态。图（b）中，第2个皇后不能放在第1、2列，因而放置在第3列上。图（c）中，表示第3行的所有各列均不能放置皇后，则返回第2行，第2个皇后需后移。图（d）中，第2个皇后后移到第4列，第3个皇后放置在第2列。图（e）中，第4行的所有各列均不能放置皇后，则返回第3行；第3个皇后后移的所有位置均不能放置皇后，则返回第2行；第2个皇后已无位可退，则返回第1行；第1个皇后需后移。图（f）中，第1个皇后后移至第2格。图（g）中，第2个皇后不能放在第1，2，3列，因而放置在第4列上。图（h）中，第3个皇后放在第1列；第4个皇后不能放置1，2列，于是放置在第3列。这样经以上回溯，得到4皇后问题的一个解：2413。继续以上的回溯探索，可得4皇后问题的另一个解：3142。3回溯算法框架描述(1) 回溯描述对于一般含参量m,n的搜索问题，回溯法框架描述如下： 输入正整数n,m,(nm) i=1;ai=; while (1) for(g=1,k=i-1;k=1;k-) if( ) g=0; / 检测约束条件,不满足则返回 if(g & ) printf(a1-m); / 输出一个解 if(in & g) i+;ai=;continue; while(ai= & i1) i-; / 向前回溯 if(ai=n & i=1) break; / 退出循环，结束 else ai=ai+1; 具体求解问题的试探搜索范围与要求不同，在应用回溯设计时，需根据问题的具体实际确定数组元素的初值、取值点与回溯点，同时需把问题中的约束条件进行必要的分解，以适应上述回溯流程。其中实施向前回溯的循环while(ai= & i1) i-;是向前回溯一步，还是回溯两步或更多步，完全根据ai是否达到回溯点来确定。例如，回溯点是n，i=6，当a6=n时回溯到i=5；若a5=n时回溯到i=4；依此类推，到ai达到回溯点则停止。图5-1所示的4皇后问题迭代回溯过程描述为：n=4;i=1;ai=1; while (1) g=1;for(k=i-1;k=1;k-) if(ai=ak & abs(ai-ak)=i-k) g=0; / 检测约束条件,不满足则返回 if(g & i=4) printf(a1-4); / 输出一个解 if(i1) i-; / 向前回溯 if(ai=n & i=1) break; / 退出循环结束 else ai=ai+1; 以上回溯体现在迭代式i=i-1，因而又称为迭代回溯。此外，递归也能实现回溯。（2） 递归回溯int put(int k) int i,j,u; if( k=问题规模 ) u=0;if( ) u=1; / 当k时不可操作 if(u=0) / 当k时可操作 if(k=规模) / 若已满足规模，则打印出一个解 printf( ); else put(k+1); / 调用 put(k+1) 在调用put(k)时，当检测约束条件知不可操作（记u=1），即再往前不可能得解，此时当然不可能输出解，也不调用put(k+1)，而是回溯，返回调用put(k)之处。这就是递归回溯的机理。如果是主程序调用put(1)，最后返回到主程序调用put(1)的后续语句，完成递归。图5.1所示的4皇后问题迭代回溯过程描述为：int put(int k) int i,j,u; if(k=4) for(i=1;i=4;i+) / 探索第k行从第1格开始放皇后 ak=i; for(u=0,j=1;j=k-1;j+) if(ak=aj | abs(ak-aj)=k-j ) u=1; / 若第k行第i格放不下,则置u=1 if(u=0) / 若第k行第i格可放,则检测是否满4行 if(k=4) / 若已放满到4行时，则打印出一个解 s+; printf( ); for (j=1;j=4;j+) printf(%d,aj); else put(k+1); / 若没放满4行,则放下一行 put(k+1) 4. 回溯法的效益分析应用回溯设计求解实际问题，由于解空间的结构差异，很难精确计算与估计回溯产生的结点数，因此回溯法的复杂度是分析回溯法效率时遇到的主要困难。回溯法产生的结点数通常只有解空间结点数的一小部分，这也是回溯法的计算效率大大高于穷举法的原因所在。回溯求解过程实质上是一个遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立的。回溯算法在搜索过程中，只要所激活的状态结点满足终结条件，应该把它输出或保存。由于在回溯法求解问题时，一般要求输出问题的所有解，因此在得到结点后，同时也要进行回溯，以便得到问题的其他解，直至回溯到状态树的根且根的所有子结点均已被搜索过为止。组织解空间便于算法在求解集时更易于搜索，典型的组织方法是图或树。一旦定义了解空间的组织方法，这个空间即可从开始结点进行搜索。回溯法的时间通常取决于状态空间树上实际生成的那部分问题状态的数目。对于元组长度为n的问题，若其状态空间树中结点总数为n!，则回溯算法的最坏情形的时间复杂度可达O(p(n)n!)；若其状态空间树中结点总数为2n，则回溯算法的最坏情形的时间复杂度可达O(p(n)2n)，其中p(n)为n的多项式。对于不同的实例，回溯法的计算时间有很大的差异。对于很多具有大n的求解实例，应用回溯法一般可在很短的时间内求得其解，可见回溯法不失为一种快速有效的算法。对于某一具体实际问题的回溯求解，常通过计算实际生成结点数的方法即蒙特卡罗方法（Monte carlo）来评估其计算效率。蒙特卡罗方法的基本思想是在状态空间树上随机选择一条路径(x0,x1,xn-1)，设X是这一路径上部分向量(x0,x1,xk-1)的结点，如果在处不受限制的子向量数是mk，则认为与X同一层的其他结点不受限制的子向量数也都是mk。也就是说，若不受限制的x0取值有m0个，则该层上有m0个结点；若不受限制的x1取值有m1个，则该层上有m0m1个结点；依此类推。由于认为在同一层上不受限制的结点数相同，因此，该路径上实际生成的结点数估计为计算路径上结点数m的蒙特卡罗算法描述如下：/ 已知随机路径上取值数据m0,m1,mk-1 m=1;t=1;for(j=0;j=k-1;j+) t=t*mj; m=m+t; printf(“%ld”,m);把所求得的随机路径上的结点数（或若干条随机路径的结点数的平均值）与状态空间树上的总结点数进行比较，由其比值可以初步看出回溯设计的效益。在下面的n皇后问题的回溯求解时将具体应用以上蒙特卡罗算法估计回溯设计的效益。5.2 桥本分数式5.2.1 桥本分数式1案例提出日本数学家桥本吉彦教授于1993年10月在我国山东举行的中日美三国数学教育研讨会上向与会者提出以下填数趣题：把1,2,9这9个数字填入下式的9个方格中(数字不得重复)，使下面的分数等式成立. + = 桥本教授当即给出了一个解答。这一分数式填数趣题究竟共有多少个解答？试求出所有解答。(等式左边两个分数交换次序只算一个解答)。这一填数趣题的解是否唯一？如果不唯一究竟有多少个解? 由人工推算求解难度太大，通过程序设计由计算机来探求更为合适。2回溯设计(1) 设计要点我们采用回溯法逐步调整探求。把式中9个规定一个顺序后，先在第一个中填入一个数字（从1开始递增），然后从小到大选择一个不同于前面的数字填在第二个中，依此类推，把九个都填入没有重复的数字后，检验是否满足等式。若等式成立，打印所得的解。然后第九个中的数字调整增1再试，直到调整为9（不能再增）；返回前一个中数字调整增1再试；依此类推，直至第一个中的数字调整为9时，完成调整探求。可见，问题的解空间是9位的整数组，其约束条件是9位数中没有相同数字且必须满足分式的要求。为此，设置a数组，式中每一位置用一个数组元素来表示：同时，记式中的3个分母分别为m1=a(2)a(3)=a(2)*10+a(3)m2=a(5)a(6)=a(5)*10+a(6)m3=a(8)a(9)=a(8)*10+a(9)所求分数等式等价于整数等式a(1)*m2*m3+a(4)*m1*m3=a(7)*m1*m2成立。这一转化可以把分数的测试转化为整数测试。注意到等式左侧两分数交换次序只算一个解，为避免解的重复，设a(1)a(4)。式中9个各填一个数字，不允许重复。为判断数字是否重复，设置中间变量g：先赋值g=1；若出现某两数字相同(即a(i)=a(k)或a(1)a(4)，则赋值g=0(重复标记)。首先从a(1)=1开始，逐步给a(i)(1i9)赋值，每一个a(i)赋值从1开始递增至9。直至a(9)赋值，判断：若i=9,g=1,a(1)*m2*m3+a(4)*m1*m3=a(7)*m1*m2同时满足，则为一组解，用n统计解的个数后，格式打印输出这组解。若i9且g=1，表明还不到9个数字，则下一个a(i)从1开始赋值继续。若a(9)=9，则返回前一个数组元素a(8)增1赋值(此时，a(9)又从1开始)再试。若a(8)=9，则返回前一个数组元素a(7)增1赋值再试。依此类推，直到a(1)=9时，已无法返回，意味着已全部试毕，求解结束。按以上所描述的回溯的参量：m=n=9元素初值：a1=1，数组元素初值取1。取值点：ai=1，各元素从1开始取值。回溯点：ai=9，各元素取值至9后回溯。约束条件1：ai=ak | a1a4，其中（ik）。约束条件2：i=9 & a1*m2*m3+a4*m1*m3=a7*m1*m2(2) 桥本分数式回溯程序设计/ 桥本分数式回溯实现 / 把1,2,.,9填入/+/=/ #include void main()int g,i,k,s,a10; long m1,m2,m3;i=1;a1=1;s=0;while (1) g=1; for(k=i-1;k=1;k-) if(ai=ak) g=0;break; / 两数相同,标记g=0 if(i=9 & g=1 & a1a4) m1=a2*10+a3;m2=a5*10+a6;m3=a8*10+a9; if(a1*m2*m3+a4*m1*m3=a7*m1*m2) / 判断等式 s+;printf(%2d) ,s);printf(%d/%ld+%d/,a1,m1,a4);printf(%ld=%d/%ld ,m2,a7,m3);if(s%2=0) printf(n); if(i1) i-; / 往前回溯 if(ai=9 & i=1) break;else ai+; / 至第1个数为9结束 printf( 共以上%d个解。n,s);(3) 程序运行结果( 1) 1/26+5/78=4/39 ( 2) 1/32+5/96=7/84( 3) 1/32+7/96=5/48 ( 4) 1/78+4/39=6/52( 5) 1/96+7/48=5/32 ( 6) 2/68+9/34=5/17( 7) 2/68+9/51=7/34 ( 8) 4/56+7/98=3/21( 9) 5/26+9/78=4/13 (10) 6/34+8/51=9/27 共以上10个解。3. 递归设计(1) 设计要点设置桥本分数式递归函数put(k):当k=9时，第k个数字取值ak=i(i=1,2,9)，标记u=0。ak与已取的aj（jk）比较，是否出现重复数字。若ak=aj，则第k个数字取值不成功，标记u=1；重新取值。若保持u=0，第k个数字取值成功：1) 检测k是否到9；若到9且满足等式，输出一个解。2) 若不到9,或不满足等式要求，则调用put(k+1)。若ak已取到9，返回调用put(k)的k-1状态，即回溯到k-1状态重新取值。主程序调用put(1),返回put(1)时，即输出解的个数s，结束。(2) 递归程序实现/ 桥本分数式递归求解 #include int a10,s=0;void main() int put(int k); put(1); / 调用递归函数put(1) printf( 共有以上%d个解。n,s); / 桥本分数式递归函数 #include int put(int k) int i,j,u,m1,m2,m3; if(k=9) for(i=1;i=9;i+) / 探索第k个数字取值i ak=i; for(u=0,j=1;j=k-1;j+) if(ak=aj) u=1; / 出现重复数字,则置u=1 if(u=0) / 若第k个数字可为i if(k=9 & a1a4) / 若已个数字，则检查等式 m1=a2*10+a3;m2=a5*10+a6;m3=a8*10+a9;if(a1*m2*m3+a4*m1*m3=a7*m1*m2) s+; printf( %2d: ,s); / 输出一个解 printf(%d/%d+%d/%d,a1,m1,a4,m2); printf(=%d/%d ,a7,m3); if(s%2=0) printf(n); else put(k+1); / 若不到个数字，则调用 put(k+1) return s; 4. 求解说明以上回溯与递归求解都有回溯功能，所以能快捷地求出所有解。关于桥本分数式求解，已有应用程序设计得到9个解的报导，遗失了一个解。可见在程序设计求解时，如果程序中结构欠妥或参量设置不当，都可能造成增解或遗解。5.2.2 10数字分数式1. 案例提出把0,1,2,.,9这10个数字填入下式的10个方格中,要求： + = （1） 各数字不得重复；（2） 数字“0”不得填在各分数的分子与分母的首位；（3） 式中各分数为最简真分数，即分子分母没有大于1的公因数。这一分数等式填数趣题究竟共有多少个解答? 试应用回溯求出所有解答。2. 回溯设计设置a数组表示式中的10个数字，即同时，记式中的3个分母分别为m1=a(2)a(3)=a(2)*10+a(3)m2=a(5)a(6)a(7)=a(5)*100+a(6)*10+a(7)m3=a(9)a(10)=a(9)*10+a(10)在上述回溯设计基础上修改若干参数：数字从9个增加到10个，因而i9改为i10；i=9改为i=10；数组元素取值修改为从“0”开始，即a1=0；ai=0；数字“0”不得在各分数的分子与分母的首位，即“0”只能在a(3),a(6),a(7)与a(10)这4个数字中，因而在输出解的条件中增加a(3)*a(6)*a(7)*a(10)=0。此外，需增加判断3个分数是否为真分数的测试循环。3. 10数字分数式程序实现/ 10数字分数式#include void main()int g,i,k,s,t,u,a11; long m1,m2,m3;i=1;a1=0;s=0;while (1) g=1; for(k=i-1;k=1;k-) if(ai=ak) g=0;break; / 两数相同,标记g=0 if(i=10 & g=1 & a3*a6*a7*a10=0) m1=a2*10+a3;m2=a5*100+a6*10+a7; m3=a9*10+a10; if(a1*m2*m3+a4*m1*m3=a8*m1*m2) / 判断等式 t=0; for(u=2;u=9;u+) / 测试3个分数是否为真分数 if(a1%u=0 & m1%u=0) t=1;break; if(a4%u=0 & m2%u=0) t=1;break; if(a8%u=0 & m3%u=0) t=1;break; if(t=0) printf( %d/%ld+%d/,a1,m1,a4);printf(%ld=%d/%ldn ,m2,a8,m3); if(i1) i-; / 往前回溯 if(ai=9 & i=1) break;else ai+; / 至第1个数为9结束 4. 程序运行结果与说明 4/19+5/608=7/32以上10数字分数式求解是在9数字分数式设计基础上改动所得，结构完全相同。请比较以上两个回溯设计的参数变化。5.3 逐位整除数本节探索一个新颖有趣的案例逐位整除数，包括高逐位整除数与低逐位整除数。定义高逐位整除数：从其高位开始，前1位能被1整除, 前2位能被2整除，前n位能被n整除。例如10245就是一个5位高逐位整除数。定义低逐位整除数：从其低位（即个位）开始，1位数能被1整除, 2位数能被2整除，n位数能被n整除。例如5111120就是一个7位低逐位整除数。5.3.1 高逐位整除数对于指定的正整数n，共有多少个不同的n位高逐位整除数？对于n位高逐位整除数，n是否存在有最大值？试探索指定的n位高逐位整除数，输出所有n位高逐位整除数。1. 回溯算法设计设置a,数组，存放求解的高逐位整除数。在a数组中，数组元素a1从1开始取值，存放逐位整除数的最高位数，显然能被1整除；a2从0开始取值，存放第2位数，前2位即a1*10+a2能被2整除；。 为了判别已取的i位数能否被i整除，设置循环for(r=0,j=1;j9，则ai=0即该位清“0”后，i=i-1回溯到前一位增值1。直到第1位增值超过9后，退出循环结束。该算法可探索并输出所有n位逐位整除数，用s统计解的个数。若s=0，说明没有找到n位逐位整除数，输出“无解”。2. 求解n位高逐位整除数程序实现/ n位高逐位整除探索 #includevoid main() int i,j,n,r,t,s,a100; printf( 高逐位整除n位，请确定n：); scanf(%d,&n); printf( 所求%d位高逐位整除数：n,n); for(j=1;j=100;j+) aj=0; t=0;s=0; i=1;a1=1; while(a1=9) if(t=0 & in) i+; for(r=0,j=1;j9 & i1) ai=0; i-; / 回溯 ai=ai+1; else t=0; / 余数r=0时,t=0 if(t=0 & i=n) s+;printf( %d: ,s); for(j=1;j25时，无解！这也说明高逐位整除数位数的最大值为25。5.3.2 低逐位整除数探索低逐位整除数，约定除个位数字可为“0”外，其余各位均为正整数。之所以如此约定，避免出现取1000000000为一个10位低逐位整除数这一平凡情形。尽管如此，考虑到低逐位整除数可能存在较多，对指定的n，寻找并输出n位以上的低逐位整除数，每一个n只输出一个解。1. 回溯算法设计设置a,数组，存放求解的低逐位整除数，a1为个位数字，a2为十位数字，。确定数组元素a1=0(当n5时个位必然为“0”),其余数组元素从1开始取值。 为了判别已取的i位数能否被i整除，设置循环for(r=0,j=i;j=1;j-) r=r*10+aj; r=r%i; （1） 若r=0，即该i位数能被i整除，则t=0；此时有两个选择： 若已取了n位，则输出一个n位低逐位整除数；然后n=n+1继续往后探索。若还未到n位，则i=i+1继续探索下一位。（2） 若r0，即前i位数不能被i整除，则t=1。此时ai=ai+1，即第i位增1后继续。若增值至ai9，则ai=0即该位清“0”后，i=i-1回溯到前一位增值1。直到第1位增值为正整数后，即a10时，退出循环结束。该算法可探索并输出所有n位以上低逐位整除数，每一n值只输出一个解。2. n位以上低逐位整除数程序实现 / n位以上低逐位整除数探索 #includevoid main() int i,j,n,r,t,a100; printf( 探索n位以上低逐位整除数，请确定n：); scanf(%d,&n); printf( 所求%d位以上低逐位整除数：n,n); for(j=1;j=100;j+) aj=1; t=0;a1=0;i=1; while(a11) if(t=0 & i=1;j-) / 检测i时是否整除i r=r*10+aj; r=r%i; if(r!=0) ai=ai+1;t=1; / 余数r!=0时ai增1,t=1 while(ai9 & i1) ai=1; i-; / 回溯 ai=ai+1; else t=0; / 余数r=0时,t=0 if(t=0 & i=n ) printf( n=%2d: ,n); for(j=n;j=1;j-) / 输出一个n位低逐位整除数 printf(%d,aj); printf(n); n+; / 探索 printf( 低逐位整除数的位数最大为%d.,n-1); 3. 程序运行示例与说明探索n位以上低逐位整除数，请确定n：11所求11位以上低逐位整除数： n=11: 41615111120 n=12: 141615111120 n=13: 5252615111120 n=14: 55252615111120 n=15: 255252615111120 n=16: 1255252615111120 n=17: 81255252615111120 n=18: 681255252615111120 n=19: 2681255252615111120 n=20: 12681255252615111120 n=21: 222681255252615111120 n=22: 3222681255252615111120 n=23: 43222681255252615111120 n=24: 243222681255252615111120低逐位整除数的位数最大为24.由n=12与n=13所输出的解，可清楚地看到向前回溯了多位。 至n=24后未见解输出，输出低逐位整除数的最高位数为24。5.4 直尺与串珠5.4.1 古尺神奇1. 案例提出有一年代尚无考究的古尺长36寸，因使用日久尺上的刻度只剩下8条,其余刻度均已不复存在。神奇的是，用该尺仍可一次性度量1至36之间任意整数寸长度。 设计程序，确定古尺上 8条刻度的位置。 2. 回溯设计这是一个新颖且有一定难度的实用性较强的案例。我们探索一般尺长s,刻度数为n的完成度量问题。为了寻求实现尺长s完全度量的n条刻度的分布位置，设置以下两个数组：a数组元素a(i)为第i条刻度距离尺左端线的长度，a(0)=0以及a(n+1)=s对应尺的左右端线。注意到尺的两端至少有一条刻度距端线为1(否则长度s-1不能度量)，不妨设a(1)=1，其余的a(i)(i=2,n)在2s-1中取不重复的数。不妨设 2 a(2)a(3).a(7) s-1 从a(2)取2开始,以后a(i)从a(i-1)+1开始递增1取值,直至s-(n+1)+i 为止。这样可避免重复。当i=n时,n条刻度连同尺的两条端线共n+2条，n+2取2的组合数为C(n+2,2),记为m，显然有m种长度赋给b数组元素b(1),b(2),.,b(m)。为判定某种刻度分布位置能否实现完全度量，设置特征量u，对于1ds的每一个长度d,如果在b(1)b(m)中存在某一个等于d,特征量u值增1。最后，若u=s，说明从1至尺长s的每一个整数d都有一个b(i)相对应，即达到完全度量，于是打印出直尺的n条刻度分布位置。若i1时a(i)增1继续,至a(i)=s-(n+1)+i时回溯。 3. 古尺刻度回溯设计/ 尺长s,寻求n条刻度分布回溯探索 #includevoid main()int d,i,j,k,t,u,s,m,n,a30,b300; printf( 尺长s,寻求n条刻度分布,请确定s,n: ); scanf(%d,%d,&s,&n); a0=0;a1=1;an+1=s; m=(n+2)*(n+1)/2; i=2;ai=2; while(1) if(in) i+; ai=ai-1+1; continue; else for(t=0,k=0;k=n;k+) for(j=k+1;j=n+1;j+) t+;bt=aj-ak; / 序列部分和赋值给b数组 for(u=0,d=1;d=s;d+) for(k=1;k=m;k+) if(bk=d) u+=1;k=m; / 检验b数组取1-s 有多少个 if(u=s) / b数组值包括1-s 所有整数 if(an!=s-1) | (an=s-1) & (a2=s-an-1) printf(); / 输出尺的上边 for(k=1;k=s-1;k+) printf(); printf(n); printf(); for(k=1;k=n+1;k+) / 输出尺的数字标注 for(j=1;j=ak-ak-1-1;j+) printf( ); if(kn+1) printf(%2d,ak); else printf(n); printf(); / 输出尺的下边与刻度 for(k=1;k=n+1;k+) for(j=1;j=ak-ak-1-1;j+) printf(); if(kn+1) printf();else printf(n); printf(直尺的段长序列为：); / 输出段长序列 for(k=1;k1) ai+; else break; 4. 程序运行示例尺长s,寻求n条刻度分布,请确定s,n: 36,8 1 3 6 13 20 27 31 35直尺的段长序列为： 1, 2, 3, 7, 7, 7, 4, 4, 1图5-3 古尺刻度示意图5.4.1 数码串珠1. 案例提出在某佛寺遗址考古发掘中意外发现一串奇特的数码珠串，珠串上共串缀有6颗宝珠，每一宝珠上都刻有一个神秘的正整数。专家考证所串6颗宝珠上的整数具有以下奇异特性：（1） 6颗宝珠上的整数互不相同。（2） 这6个整数之和为s，沿珠串相连的若干颗（16颗）珠上整数之和为1，2，s不间断，这一特性象征祥瑞，即可以覆盖区间1,s中的所有整数。（3） 实现（2）的所有情形，这里的和s是最大的。你知道这里的s为多大？请确定珠串上6颗宝珠的整数及其相串的顺序。2. 回溯设计要点问题是要在如图5-2所示圆上的6个小圆圈中各填入一个整数，这6个整数之和为s，且沿圆相连的若干个（16个）小圆圈中整数之和覆盖区间1,s中的所有整数。求s 的最大值。图5-2 佛珠数码示意图问题要求的3点中，抓住核心的（2）（3）设计。在满足（2）（3）的解中去除有整数相同的解即可。首先探讨沿圆圈6个整数组成部分和的个数。部分和为1个整数，共6个；相应部分和为5个相连整数组成，也为6个。部分和为2个相连整数组成，共6个；相应部分和为4个相连整数组成，也为6个。部分和为3个相连整数组成，共6个；部分和为所有6个相连整数组成，共1个。因而部分和的个数为：65+1=31共有31个部分和，要覆盖1，31，意味着31个部分和没有相同的。一般地，求解环上有n个整数，其和为s，沿环的部分和为区间1-s上的所有整数。为叙述方便，称沿圆圈若干个相连整数之和为“部分和”，称部分和为区间1,s中的所有整数为“完全覆盖”。为了确定和为s的n个整数取值及这些整数的分布，使沿环的部分和能完全覆盖1,s，应用以下数学模型：设圆圈的周长为s，在圆圈上划n条刻度，用a数组作标记。起点为a(0)=0，约定a(1)-a(0)为第1个数，a(2)-a(1)为第2个数，一般地a(i)-a(i-1)为第i个数。因共n个数，显然刻度a(n)=s且与起点a(0)重合。因n个数中至少有一个数为1（否则不能覆盖1），不妨设第1个数为1，即a(1)=1。n个数的每一个数都可以与（约定顺时针方向）相连的1，2，n-1个数组成部分和。为构造部分和方便，定义a(n+1)与a(1)重合，即 a(n+1)=s+a(1)；定义a(n+2)与a(2)重合，即a(8)=s+a(2)；最后有a(2n-1)与a(n-1)重合，即a(2n-1)=s+a(n-1)。设置b数组存储部分和，变量u统计b数组覆盖区间1,s中数的个数。若u=s-1，（s本身显然覆盖，除去不计），即完全覆盖，输出和为s时的解。若i1时a(i)增1继续,至a(i)=s-n+i