第一章-算法与程序设计概述-PPT.ppt

第一章第一章 算法与程序设计概述算法与程序设计概述2.1 穷举及其应用穷举及其应用2.2 穷举设计的优化穷举设计的优化2.3 回溯法及其描述回溯法及其描述2.4 回溯设计应用回溯设计应用2.5 回溯设计的优化回溯设计的优化22.1 穷举及其应用穷举及其应用2.1.1 穷举概述穷举概述 穷举法又称列举法，其基本思想是逐一列举问穷举法又称列举法，其基本思想是逐一列举问题所涉及的所有情况。题所涉及的所有情况。穷举法常用于解决穷举法常用于解决“是否存在是否存在”或或“有多少种有多少种可能可能”等问题。等问题。应用穷举法时应注意对问题所涉及的有限种情应用穷举法时应注意对问题所涉及的有限种情形须一一列举，既不能重复，又不能遗漏。形须一一列举，既不能重复，又不能遗漏。穷举通常应用循环结构来实现。在循环体中，穷举通常应用循环结构来实现。在循环体中，应用选择结构实施判断筛选，求得所要求的解。应用选择结构实施判断筛选，求得所要求的解。3穷举法的框架描述：穷举法的框架描述：n=0;for(k=;k=;k+)/*据指定范围实施穷举据指定范围实施穷举*/if()/*据约束条件实施筛选据约束条件实施筛选*/printf();/*输出解输出解*/n+;/*统计解的个数统计解的个数*/4【例【例【例【例2.22.22.22.2】统计分母在区间】统计分母在区间】统计分母在区间】统计分母在区间a,ba,ba,ba,b的最简真分数的最简真分数的最简真分数的最简真分数(分子小于分分子小于分分子小于分分子小于分母，且分子分母无公因数母，且分子分母无公因数母，且分子分母无公因数母，且分子分母无公因数)共有多少个共有多少个共有多少个共有多少个,并求最简真分数升序并求最简真分数升序并求最简真分数升序并求最简真分数升序序列中的第序列中的第序列中的第序列中的第k k k k项项项项(正整数正整数正整数正整数a,b,ka,b,ka,b,ka,b,k从键盘输入从键盘输入从键盘输入从键盘输入)。算法设计算法设计算法设计算法设计:为排序方便，设置数组为排序方便，设置数组为排序方便，设置数组为排序方便，设置数组c c c c存储分子，数组存储分子，数组存储分子，数组存储分子，数组d d d d存储分母。真存储分母。真存储分母。真存储分母。真分数升序排序后的第分数升序排序后的第分数升序排序后的第分数升序排序后的第k k k k项为项为项为项为c(k)/d(k)c(k)/d(k)c(k)/d(k)c(k)/d(k)。在在在在a,ba,ba,ba,b内穷举分数内穷举分数内穷举分数内穷举分数i/ji/ji/ji/j的分母的分母的分母的分母j:a,a+1,bj:a,a+1,bj:a,a+1,bj:a,a+1,b；对每一个分母对每一个分母对每一个分母对每一个分母j j j j穷举分子穷举分子穷举分子穷举分子i:1,2,j-1i:1,2,j-1i:1,2,j-1i:1,2,j-1。若分子若分子若分子若分子i i i i与分母与分母与分母与分母jjjj存在大于存在大于存在大于存在大于1 1 1 1的公因数的公因数的公因数的公因数,说明说明说明说明i/ji/ji/ji/j非最简非最简非最简非最简,忽忽忽忽略不计；否则赋值得一个最简真分数略不计；否则赋值得一个最简真分数略不计；否则赋值得一个最简真分数略不计；否则赋值得一个最简真分数c(n)/d(n)c(n)/d(n)c(n)/d(n)c(n)/d(n)。数组下标数组下标数组下标数组下标n n n n统计最简真分数的个数。应用冒泡法排序后即可打印出指统计最简真分数的个数。应用冒泡法排序后即可打印出指统计最简真分数的个数。应用冒泡法排序后即可打印出指统计最简真分数的个数。应用冒泡法排序后即可打印出指定的第定的第定的第定的第k k k k项项项项c(k)/d(k)c(k)/d(k)c(k)/d(k)c(k)/d(k)。5【例【例2.32.3】已知集合已知集合A A定义如下定义如下:1A1A，2A2A；x,yA=2x+3yAx,yA=2x+3yA试求集合试求集合A A元素从小到大排列的序列的前元素从小到大排列的序列的前n n项。项。（1 1）按第按第n n项的大小循环设计项的大小循环设计x,yx,y可以是已产生的所有已有项中的任意两项，已产生可以是已产生的所有已有项中的任意两项，已产生项越多，递推生成的新项也就越多。项越多，递推生成的新项也就越多。穷举循环变量穷举循环变量k k从从3 3开始递增开始递增1 1取值取值,到第到第n n项时项时k k的终值尚的终值尚无法确定，可约定一个较大的终值（例如无法确定，可约定一个较大的终值（例如1000010000）。）。若若k k可由已有的项可由已有的项a(j)a(j)，a(i)(ji)a(i)(ji)推得，即若推得，即若k k满足条满足条件件k=2*aj+3*ai k=2*aj+3*ai 或或 k=2*ai+3*ajk=2*ai+3*aj，说明，说明k k是是a a数列数列中的一项，赋值给中的一项，赋值给a(t)a(t)。当项数当项数t t达到规定项数达到规定项数n n时时,则退出穷举。则退出穷举。6（）（）按项数循环设计按项数循环设计已知前已知前2 2项，项，t t循环从循环从3 3开始递增开始递增1 1取值到指定的取值到指定的项数项数n n。第一项的值第一项的值k k从从2 2开始递增取值，对每一个开始递增取值，对每一个k k取值，取值，标记标记h=0h=0赋值；赋值；若若k k可由已有的项可由已有的项a(j)a(j)，a(i)(ji)a(i)(ji)推得，即若推得，即若k k满足条件满足条件k=2*aj+3*ai k=2*aj+3*ai 或或 k=2*ai+3*ajk=2*ai+3*aj，说明，说明k k是是a a数列中的一项，赋数列中的一项，赋值给值给a(t)a(t)，同时标记，同时标记h=1h=1赋值。赋值。对某项数对某项数t t若若h=0h=0时，则时，则t t减减1 1后循环，即对于原后循环，即对于原t t使使k k增值后继续，直到达到规定项数增值后继续，直到达到规定项数n n为止。为止。7 2.2.1 2.2.1 2.2.1 2.2.1 优选穷举对象优选穷举对象优选穷举对象优选穷举对象 选择合适的穷举对象是穷举优化的首要条件。【例【例【例【例2.42.42.42.4】把一个把一个把一个把一个6 6 6 6位整数分为前后两个位整数分为前后两个位整数分为前后两个位整数分为前后两个3 3 3 3位数位数位数位数,若若若若该数等于所分两个该数等于所分两个该数等于所分两个该数等于所分两个3 3 3 3位数和的平方位数和的平方位数和的平方位数和的平方,则称该数为则称该数为则称该数为则称该数为6 6 6 6位分位分位分位分段和平方数。试求出所有段和平方数。试求出所有段和平方数。试求出所有段和平方数。试求出所有6 6 6 6位分段和平方数。位分段和平方数。位分段和平方数。位分段和平方数。（1)1)1)1)对所有对所有对所有对所有6 6 6 6位数穷举位数穷举位数穷举位数穷举（2)2)2)2)对对对对3 3 3 3位数穷举位数穷举位数穷举位数穷举2.2 穷举设计的优化穷举设计的优化8大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点9 2.2.2 2.2.2 优化穷举循环参量优化穷举循环参量优化穷举循环参量可减少无效循环，提高穷举效率。优化穷举循环参量可减少无效循环，提高穷举效率。【例【例2.62.6】求解高斯八皇后问题。求解高斯八皇后问题。在国际象棋的在国际象棋的8888方格的棋盘上如何放置方格的棋盘上如何放置8 8个皇后个皇后,使得这使得这8 8个皇后不能相互攻击。个皇后不能相互攻击。算法设计：算法设计：高斯八后问题的一个解用一个八位数表示高斯八后问题的一个解用一个八位数表示,八位数解的第八位数解的第k k个数字为个数字为j,j,表示棋盘上的第表示棋盘上的第k k行的第行的第j j格放置一个皇后。格放置一个皇后。两个皇后不允许处在同一横排两个皇后不允许处在同一横排,同一纵列，要求八位数中同一纵列，要求八位数中数字数字1818各出现一次，不能重复。各出现一次，不能重复。因而解的范围区间应为因而解的范围区间应为1234567812345678，8765432187654321。注意到数。注意到数字字1818的任意一个排列的数字和为的任意一个排列的数字和为9 9的倍数，即数字的倍数，即数字1818的任意一个排列均为的任意一个排列均为9 9的倍数，因而穷举的倍数，因而穷举a a循环的穷举范围循环的穷举范围定为定为1234567812345678，8765432187654321，其循环步长可定为，其循环步长可定为9 9。10 2.2.3 2.2.3 精简穷举循环精简穷举循环精简一些不必要的循环，可大大提高穷举的效率。精简一些不必要的循环，可大大提高穷举的效率。【例【例2.72.7】整币兑零求解。整币兑零求解。计算把一张计算把一张1 1元整币兑换成元整币兑换成1 1分分,2,2分分,5,5分分,1,1角角,2,2角角,5,5角共角共6 6种种零币的不同兑换种数。零币的不同兑换种数。（1 1）穷举设计求解穷举设计求解设面值为设面值为1 1，2 2，5 5，1010，2020，5050单位零币的个数分别为单位零币的个数分别为p1,p2,p3,p4,p5,p6p1,p2,p3,p4,p5,p6。设置穷举的。设置穷举的6 6重循环。重循环。（2 2）精简穷举循环设计精简穷举循环设计在上述程序的在上述程序的6 6重循环中，我们可精简重循环中，我们可精简p1p1循环。循环。（3 3）穷举设计的进一步优化穷举设计的进一步优化在循环设置中，在循环设置中，p3p3循环从循环从0n/50n/5可改进为可改进为0(n-2*p2)/50(n-2*p2)/5。112.3 回溯法及其描述2.3.1 2.3.1 回溯的基本概念回溯的基本概念回溯法找出求解问题的线索往前试探，若试探成功，回溯法找出求解问题的线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。再往前试探。回溯法可以形象地概括为回溯法可以形象地概括为“向前走，碰壁回头向前走，碰壁回头”。与穷举法相比，回溯法的与穷举法相比，回溯法的“聪明聪明”之处在于能适时之处在于能适时“回头回头”，若再往前走不可能得到解，就回溯，退一步，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。另找线路，这样可省去大量的无效操作。应用回溯设计求解实际问题，由于解空间的结构差异，应用回溯设计求解实际问题，由于解空间的结构差异，而且很难计算与估计回溯产生的结点数，因此回溯计而且很难计算与估计回溯产生的结点数，因此回溯计算复杂度是分析回溯法效率时遇到的主要困难。算复杂度是分析回溯法效率时遇到的主要困难。回溯法产生的结点数通常不足解空间结点数的回溯法产生的结点数通常不足解空间结点数的3%3%，这，这也是回溯法的计算效率大大高于穷举法的原因所在。也是回溯法的计算效率大大高于穷举法的原因所在。122.3.2 2.3.2 回溯法描述回溯法描述 1.1.回溯的一般方法回溯的一般方法132.回溯算法框架描述回溯算法框架描述/*/*输入正整数输入正整数n,m,(nm)*/n,m,(nm)*/i=1;ai=i=1;ai=;while(1)while(1)g=1;for(k=i-1;k=1;k-)g=1;for(k=i-1;k=1;k-)if(if()g=0;/*1)g=0;/*检测检测,不满足则返回不满足则返回 */*/if(g&if(g&)2)printf(a1-m);/*printf(a1-m);/*输出一个解输出一个解 */*/if(in&g)i+;ai=if(in&g)i+;ai=;continue;continue;while(ai=while(ai=&i1)i-;/*&i1)i-;/*向前回溯向前回溯 */*/if(ai=n&i=1)break;/*if(ai=n&i=1)break;/*退出循环，结束退出循环，结束 */*/else ai=ai+1;else ai=ai+1;142.3.3 回溯法的效益分析回溯法的效益分析回溯法的时间通常取决于状态空间树上实际生成的那回溯法的时间通常取决于状态空间树上实际生成的那部分问题状态的数目。对于元组长度为部分问题状态的数目。对于元组长度为n n的问题，若其的问题，若其状态空间树中结点总数为状态空间树中结点总数为n!n!，则回溯算法的最坏情形，则回溯算法的最坏情形的时间复杂度可达的时间复杂度可达O(p(n)n!)O(p(n)n!)；对于某一具体实际问题的回溯求解，常通过计算实际对于某一具体实际问题的回溯求解，常通过计算实际生成结点数的方法即蒙特卡罗方法（生成结点数的方法即蒙特卡罗方法（Monte carloMonte carlo）来）来评估其计算效率。评估其计算效率。把所求得的随机路径上的结点数（或若干条随机路径把所求得的随机路径上的结点数（或若干条随机路径的结点数的平均值）与状态空间树上的总结点数进行的结点数的平均值）与状态空间树上的总结点数进行比较，由其比值可以初步看出回溯设计的效益。比较，由其比值可以初步看出回溯设计的效益。152.4 回溯设计应用 2.4.1 2.4.1 桥本分数式桥本分数式1.1.问题提出问题提出日本数学家桥本吉彦教授于日本数学家桥本吉彦教授于19931993年年1010月在我国山东举行月在我国山东举行的中日美三国数学教育研讨会上向与会者提出以下填数的中日美三国数学教育研讨会上向与会者提出以下填数趣题趣题:把把1,2,.,91,2,.,9这这9 9个数字填入下式的九个方格中个数字填入下式的九个方格中(数字不得重复数字不得重复),),使下面的分数等式成立使下面的分数等式成立 +=+=桥本教授当即给出了一个解答。这一分数式填数趣题究桥本教授当即给出了一个解答。这一分数式填数趣题究竟共有多少个解答竟共有多少个解答?试求出所有解答。试求出所有解答。(等式左边两个等式左边两个分数交换次序只算一个解答分数交换次序只算一个解答)。161.回溯算法设计回溯算法设计设置设置a a数组数组,式中每一式中每一位置用一个数组元素来表示位置用一个数组元素来表示 .为判断数字是否重复为判断数字是否重复,设置中间变量设置中间变量g g：若出现某两数字相同：若出现某两数字相同(即即a(i)=a(k)a(i)=a(k)或或a(1)a(4),a(1)a(4),则赋值则赋值g=0(g=0(重复标记重复标记)。首先从首先从a(1)=1a(1)=1开始开始,逐步给逐步给a(i)(1i9)a(i)(1i9)赋值赋值,每一个每一个a(i)a(i)赋值从赋值从1 1开始递增至开始递增至9 9。直至。直至a(9)a(9)赋值赋值,判断：判断：若若i=9,g=1,i=9,g=1,等式同时满足等式同时满足,则为一组解则为一组解,用用n n统计解的个数后统计解的个数后,格式打印输出这组解。格式打印输出这组解。若若i9 i9 且且g=1,g=1,表明还不到九个数字表明还不到九个数字,则下一个则下一个a(i)a(i)从从1 1开始赋开始赋值继续。值继续。若若a(9)=9,a(9)=9,则返回前一个数组元素则返回前一个数组元素a(8)a(8)增增1 1 赋值赋值(此时此时,a(9),a(9)又从又从1 1开始开始)再试。若再试。若a(8)=9,a(8)=9,则返回前一个数组元素则返回前一个数组元素a(7)a(7)增增1 1 赋值再试。赋值再试。依此类推，直到依此类推，直到a(1)=9a(1)=9时时,已无法返回已无法返回,意味着已全部试毕意味着已全部试毕,求解结束。求解结束。17算法描述算法描述输入正整数输入正整数n,m,(nm);n,m,(nm);i=1;ai=i=1;ai=;while(1)while(1)g=1;for(k=i-1;k=1;k-)g=1;for(k=i-1;k=1;k-)if(if()g=0;/*1)g=0;/*检测检测,不满足返回不满足返回 */*/if(g&if(g&)2)printf(a1-m);/*printf(a1-m);/*输出一个解输出一个解 */*/if(in&g)i+;ai=if(in&g)i+;ai=;continue;continue;while(ai=while(ai=&i1)i-;/*&i1)i-;/*回溯回溯 */*/if(ai=n&i=1)break;/*if(ai=n&i=1)break;/*退出循环，结束退出循环，结束 */*/else ai=ai+1;else ai=ai+1;18算法描述算法描述输入输入n=m=9;n=m=9;i=1;ai=1;i=1;ai=1;while(1)while(1)g=1;for(k=i-1;k=1;k-)g=1;for(k=i-1;k=1;k-)if(ai=ak|a1a4 if(ai=ak|a1a4)g=0;)g=0;/*/*检测检测,不满足返回不满足返回 */*/if(g&i=9&a1*m2*m3+a4*m1*m3=a7*m1*m2 if(g&i=9&a1*m2*m3+a4*m1*m3=a7*m1*m2)printf(a1-m);/*printf(a1-m);/*输出一个解输出一个解 */*/if(in&g)if(i1)i-;/*while(ai=n&i1)i-;/*回溯回溯 */*/if(ai=n&i=1)break;/*if(ai=n&i=1)break;/*退出循环，结束退出循环，结束 */*/else ai=ai+1;else ai=ai+1;192.4.2 2.4.2 排列组合排列组合1.1.实现排列实现排列A(n,m)A(n,m)对指定的正整数对指定的正整数m,n(m,n(约定约定1m=n),1m=n),具体实现排列具体实现排列A(n,m)A(n,m)。（1 1）回溯算法设计回溯算法设计设置一维数组设置一维数组a a，a(i)a(i)（i=1,2,mi=1,2,m）在）在1n1n中取值。首先从中取值。首先从a(1)=1a(1)=1开始开始,逐步给逐步给a(i)(1im)a(i)(1im)赋值赋值,每一个每一个a(i)a(i)赋值从赋值从1 1开始开始递增至递增至n n。为判断数字是否重复为判断数字是否重复,设置中间变量设置中间变量g g：先赋值：先赋值g=1g=1；若出现某两数；若出现某两数字相同字相同(即即a(i)=a(j),a(i)=a(j),则赋值则赋值g=0(g=0(重复标记重复标记)。若若i=mi=m与与g=1g=1同时满足同时满足,则为一组解则为一组解,用用s s统计解的个数后统计解的个数后,格式打印格式打印输出这组解。输出这组解。若若im im 且且g=1,g=1,表明不到表明不到m m个数字个数字,下一个下一个a(i)a(i)从从1 1开始赋值，继续。开始赋值，继续。若若a(i)=n,a(i)=n,则返回前一个数组元素则返回前一个数组元素a(i-1)a(i-1)增增1 1赋值。直到赋值。直到a(1)=9a(1)=9时时,已无法返回已无法返回,意味着已全部试毕意味着已全部试毕,求解结束。求解结束。20算法描述算法描述输入正整数输入正整数n,m,(nm);n,m,(nm);i=1;ai=1;i=1;ai=1;while(1)while(1)g=1;for(j=1;ji;j+)g=1;for(j=1;ji;j+)if(aj=ai if(aj=ai)g=0;/*)g=0;/*检测检测,不满足返回不满足返回 */*/if(g&i=m)if(g&i=m)printf(a1-m);/*printf(a1-m);/*输出一个解输出一个解 */*/if(in&g)i+;ai=1;continue;if(i1)i-;/*while(ai=n&i1)i-;/*回溯回溯 */*/if(ai=n&i=1)break;/*if(ai=n&i=1)break;/*退出循环，结束退出循环，结束 */*/else ai=ai+1;else ai=ai+1;213.3.程序变通程序变通注意到组合与组成元素的顺序无关，约定组合中的组成元素注意到组合与组成元素的顺序无关，约定组合中的组成元素按递增排序。因而，把以上程序中的约束条件按递增排序。因而，把以上程序中的约束条件1 1（aj=aiaj=ai）修改为）修改为aj=aiaj=ai，即可实现从，即可实现从n n个不同元个不同元素中取素中取m m个个(约定约定1mn)1mn+1in+1且且a(i)=1a(i)=1时回溯；时回溯；当当i=n+1i=n+1且且a(i)=1a(i)=1时退出。时退出。当当a(n)a(m-2)a(n)a(m-2)已取数字时，设置已取数字时，设置h h统计其中统计其中0 0的个数，的个数，若若hm/2-nhm/2-n，则返回；，则返回；若若h=m/2-nh=m/2-n，判断是否有相同的由，判断是否有相同的由n n个数字组成的二进制数。个数字组成的二进制数。若存有相同的，标注若存有相同的，标注t=1t=1；若不存在有相同的，保持；若不存在有相同的，保持t=0,t=0,作作打印输出。打印输出。243算法描述算法描述输入正整数输入正整数n,n,计算计算m=2n;m=2n;an=1;am-1=1;i=n+1;an=1;am-1=1;i=n+1;while(1)while(1)if(aj=ai if(aj=ai)g=0;/*)g=0;/*检测检测,不满足返回不满足返回 */*/if(i=m-2&h=m/2-n&m1m2)if(i=m-2&h=m/2-n&m1m2)printf(a0 m-1);/*printf(a0 m-1);/*输出一个解输出一个解 */*/if(in&g)i+;ai=0;continue;if(in+1)i-;/*while(ai=1&in+1)i-;/*回溯回溯 */*/if(ai=1&i=n+1)break;/*if(ai=1&i=n+1)break;/*退出，结束退出，结束 */*/else ai=ai+1;else ai=ai+1;251.n1.n皇后问题皇后问题 要求在要求在nnnn方格棋盘放置方格棋盘放置n n个皇后使它们不相互攻击个皇后使它们不相互攻击(即即任意两个皇后不允许处在同一横排任意两个皇后不允许处在同一横排,同一纵列同一纵列,也不允许处在也不允许处在同一与棋盘边框成同一与棋盘边框成4545度角的斜线上。正整数度角的斜线上。正整数n n从键盘输入从键盘输入,n2),n2)。2.2.回溯探求设计回溯探求设计 设置数组设置数组a(n),a(n),数组元素数组元素a(i)a(i)表示第表示第i i行的皇后位于第行的皇后位于第a(i)a(i)列列.求求nn皇后问题的一个解皇后问题的一个解,即寻求即寻求a a数组的一组取值数组的一组取值,该该组取值中每一元素的值互不相同组取值中每一元素的值互不相同(即没有任两个皇后在同一即没有任两个皇后在同一列列),),且第且第i i个元素与第个元素与第k k个元素相差不为个元素相差不为abs(i-k),(abs(i-k),(即任两个即任两个皇后不在同一皇后不在同一4545度角的斜线上度角的斜线上)。2.4.4 高斯皇后问题及其拓广高斯皇后问题及其拓广26 首先首先a(1)a(1)从从1 1 开始取值。然后从小到大选择一个不同于开始取值。然后从小到大选择一个不同于a(1)a(1)且与且与a(1)a(1)相差不为相差不为1 1的整数赋给的整数赋给a(2)a(2)。再从小到大选择。再从小到大选择一个不同于一个不同于a(1),a(2)a(1),a(2)且与且与a(1)a(1)相差不为相差不为2,2,与与a(2)a(2)相差不为相差不为1 1的整数赋给的整数赋给a(3)a(3)。依此类推。依此类推,至至a(n)a(n)也作了满足要求的赋值也作了满足要求的赋值,打印该数组即为找到的一个打印该数组即为找到的一个n n皇后的解。皇后的解。为了检验为了检验a(i)a(i)是否满足上述要求是否满足上述要求,设置标志变量设置标志变量g,gg,g赋初赋初值值1 1。若不满足上述要求。若不满足上述要求,则则g=0g=0。按以下步骤操作。按以下步骤操作:令令 x=abs(a(i)-a(k)(k=1,2,.,i-1)x=abs(a(i)-a(k)(k=1,2,.,i-1)判别判别:若若x=0 x=0 或或 x=i-k,x=i-k,则则g=0g=0。若出现若出现g=0,g=0,则表明则表明a(i)a(i)不满足要求不满足要求,a(i),a(i)调整增调整增1 1后再后再试试,依此类推。依此类推。若若i=ni=n且且g=1,g=1,则满足要求则满足要求,用用s s统计解的个数后，格式统计解的个数后，格式打印输出这组解。打印输出这组解。若若ini=1;k+)g=1;for(k=i-1;k=1;k+)x=absf(ai-ak);x=absf(ai-ak);if(ak=ai&x=i-k if(ak=ai&x=i-k)g=0;)g=0;/*/*检测检测,不满足返回不满足返回 */*/if(g&i=n)if(g&i=n)printf(a1-n);/*printf(a1-n);/*输出一个解输出一个解 */*/if(in&g)i+;ai=1;continue;if(i1)i-;/*while(ai=n&i1)i-;/*回溯回溯 */*/if(ai=n&i=1)break;/*if(ai=n&i=1)break;/*退出，结束退出，结束 */*/else ai=ai+1;else ai=ai+1;284.时间测试292.5 回溯设计的优化回溯设计的优化回溯算法在搜索执行的同时产生解空间，是一种系回溯算法在搜索执行的同时产生解空间，是一种系统地搜索问题解答的方法。回溯算法避免了生成那统地搜索问题解答的方法。回溯算法避免了生成那些不可能产生解的状态，不断去除那些实际上不可些不可能产生解的状态，不断去除那些实际上不可能产生所需解的结点，以减少问题的计算量。能产生所需解的结点，以减少问题的计算量。回溯算法的改进途径如下：回溯算法的改进途径如下：(1)(1)根据树分支设计优先策略根据树分支设计优先策略,结点少的分支优结点少的分支优先，解多的分支优先；先，解多的分支优先；(2)(2)根据求解问题调整与改进搜索数组元素的取根据求解问题调整与改进搜索数组元素的取值点与回溯点；值点与回溯点；(3)(3)根据求解问题调整与改进搜索的约束条件。根据求解问题调整与改进搜索的约束条件。30【例【例2.82.8】实现组合实现组合C(n,m)C(n,m)设计优化。设计优化。算法改进要点：算法改进要点：注意到组合与元素的顺序无关，约定组合中的元素按注意到组合与元素的顺序无关，约定组合中的元素按升序排序。升序排序。回溯实现从回溯实现从1n1n这这n n个数中每次取个数中每次取m m个数的组合，设置个数的组合，设置a a数组，数组下标数组，数组下标i i从从1 1开始取值。开始取值。约定约定a(1),.,a(i),.,a(m)a(1),.,a(i),.,a(m)按递增顺序排列，按递增顺序排列，a(i)a(i)后有后有m-im-i个大于个大于a(i)a(i)的元素的元素,其中最大取值为其中最大取值为n n，显然，显然a(i)a(i)最多取最多取n-m+in-m+i，即，即a(i)a(i)回溯的条件是回溯的条件是a(i)=n-m+ia(i)=n-m+i。当当 imim时，时，i i增增1 1，a(i)a(i)从从a(i-1)+1a(i-1)+1开始取值；直至开始取值；直至i=mi=m时输出结果。时输出结果。当当a(i)=n-m+ia(i)=n-m+i时时i=i-1i=i-1回溯回溯,直至直至i=0i=0时结束。时结束。31【例【例2.92.9】探索复杂排列算法的改进。探索复杂排列算法的改进。前面应用回溯法探索从前面应用回溯法探索从n n个不同元素中取个不同元素中取m m（约定（约定1m=n1m=n）个元素与另外）个元素与另外n-mn-m个相同元素组成的复杂排列。个相同元素组成的复杂排列。事实上，这一回溯设计可进行进一步改进。事实上，这一回溯设计可进行进一步改进。算法设计改进要点：算法设计改进要点：设计基础上设计基础上,引入了一个变量引入了一个变量k k来控制来控制0 0的个数，当的个数，当kn-mkn-m时时,ai=0,ai=0，元素需从，元素需从0 0开始取值；否则，开始取值；否则，0 0的个数已的个数已达达n-mn-m个，个，ai=1ai=1，即从，即从1 1开始取值。这样处理，使开始取值。这样处理，使0 0的个的个数不超过数不超过n-mn-m，减少一些无效操作，提高了回溯效率。，减少一些无效操作，提高了回溯效率。取值点：当取值点：当kn-mkn-m时时,ai=0,ai=0，需从，需从0 0开始取值；否则，开始取值；否则，ai=1ai=1，即从，即从1 1开始取值。开始取值。32