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

第一章算法与程序设计概述主要内容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.2】统计分母在区间[a,b]的最简真分数(分子小于分母，且分子分母无公因数)共有多少个,并求最简真分数升序序列中的第k项(正整数a,b,k从键盘输入)。

算法设计:为排序方便，设置数组c存储分子，数组d存储分母。真分数升序排序后的第k项为c(k)/d(k)。在[a,b]内穷举分数i/j的分母j:a,a+1,…,b；对每一个分母j穷举分子i:1,2,…,j-1。若分子i与分母j存在大于1的公因数,说明i/j非最简,忽略不计；否则赋值得一个最简真分数c(n)/d(n)。数组下标n统计最简真分数的个数。应用冒泡法排序后即可打印出指定的第k项c(k)/d(k)。5【例2.3】已知集合A定义如下:

1∈A，2∈A；x,y∈A=>2x+3y∈A试求集合A元素从小到大排列的序列的前n项。（1）按第n项的大小循环设计

x,y可以是已产生的所有已有项中的任意两项，已产生项越多，递推生成的新项也就越多。穷举循环变量k从3开始递增1取值,到第n项时k的终值尚无法确定，可约定一个较大的终值（例如10000）。若k可由已有的项a(j)，a(i)(j<i)推得，即若k满足条件k=2*a[j]+3*a[i]或k=2*a[i]+3*a[j]，说明k是a数列中的一项，赋值给a(t)。当项数t达到规定项数n时,则退出穷举。6（２）按项数循环设计已知前2项，t循环从3开始递增1取值到指定的项数n。第一项的值k从2开始递增取值，对每一个k取值，标记h=0赋值；若k可由已有的项a(j)，a(i)(j<i)推得，即若k满足条件k=2*a[j]+3*a[i]或k=2*a[i]+3*a[j]，说明k是a数列中的一项，赋值给a(t)，同时标记h=1赋值。对某项数t若h=0时，则t减1后循环，即对于原t使k增值后继续，直到达到规定项数n为止。72.2.1优选穷举对象选择合适的穷举对象是穷举优化的首要条件。【例2.4】把一个6位整数分为前后两个3位数,若该数等于所分两个3位数和的平方,则称该数为6位分段和平方数。试求出所有6位分段和平方数。（1)对所有6位数穷举（2)对3位数穷举2.2穷举设计的优化8大家有疑问的，可以询问和交流可以互相讨论下，但要小声点92.2.2优化穷举循环参量优化穷举循环参量可减少无效循环，提高穷举效率。【例2.6】求解高斯八皇后问题。在国际象棋的8×8方格的棋盘上如何放置8个皇后,使得这8个皇后不能相互攻击。算法设计：高斯八后问题的一个解用一个八位数表示,八位数解的第k个数字为j,表示棋盘上的第k行的第j格放置一个皇后。两个皇后不允许处在同一横排,同一纵列，要求八位数中数字1—8各出现一次，不能重复。因而解的范围区间应为[12345678，87654321]。注意到数字1—8的任意一个排列的数字和为9的倍数，即数字1—8的任意一个排列均为9的倍数，因而穷举a循环的穷举范围定为[12345678，87654321]，其循环步长可定为9。10

2.2.3精简穷举循环精简一些不必要的循环，可大大提高穷举的效率。【例2.7】整币兑零求解。计算把一张1元整币兑换成1分,2分,5分,1角,2角,5角共6种零币的不同兑换种数。（1）穷举设计求解设面值为1，2，5，10，20，50单位零币的个数分别为p1,p2,p3,p4,p5,p6。设置穷举的6重循环。（2）精简穷举循环设计在上述程序的6重循环中，我们可精简p1循环。（3）穷举设计的进一步优化在循环设置中，p3循环从0—n/5可改进为0—(n-2*p2)/5。112.3回溯法及其描述2.3.1回溯的基本概念回溯法找出求解问题的线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。回溯法可以形象地概括为“向前走，碰壁回头”。与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。应用回溯设计求解实际问题，由于解空间的结构差异，而且很难计算与估计回溯产生的结点数，因此回溯计算复杂度是分析回溯法效率时遇到的主要困难。回溯法产生的结点数通常不足解空间结点数的3%，这也是回溯法的计算效率大大高于穷举法的原因所在。

122.3.2回溯法描述1.回溯的一般方法132.回溯算法框架描述

/*输入正整数n,m,(n≥m)*/i=1;a[i]=<元素初值>;while(1){g=1;for(k=i-1;k>=1;k--)if(<约束条件1>)g=0;/*检测,不满足则返回*/if(g&&<约束条件2>)printf(a[1-m]);/*输出一个解*/if(i<n&&g){i++;a[i]=<取值点>;continue;}while(a[i]==<回溯点>&&i>1)i--;/*向前回溯*/if(a[i]==n&&i==1)break;/*退出循环，结束*/elsea[i]=a[i]+1;}142.3.3回溯法的效益分析回溯法的时间通常取决于状态空间树上实际生成的那部分问题状态的数目。对于元组长度为n的问题，若其状态空间树中结点总数为n!，则回溯算法的最坏情形的时间复杂度可达O(p(n)n!)；对于某一具体实际问题的回溯求解，常通过计算实际生成结点数的方法即蒙特卡罗方法（Montecarlo）来评估其计算效率。把所求得的随机路径上的结点数（或若干条随机路径的结点数的平均值）与状态空间树上的总结点数进行比较，由其比值可以初步看出回溯设计的效益。152.4回溯设计应用

2.4.1桥本分数式1.问题提出日本数学家桥本吉彦教授于1993年10月在我国山东举行的中日美三国数学教育研讨会上向与会者提出以下填数趣题:把1,2,...,9这9个数字填入下式的九个方格中(数字不得重复),使下面的分数等式成立

□□□──+──=──□□□□□□桥本教授当即给出了一个解答。这一分数式填数趣题究竟共有多少个解答?试求出所有解答。(等式左边两个分数交换次序只算一个解答)。161.回溯算法设计设置a数组,式中每一□位置用一个数组元素来表示.为判断数字是否重复,设置中间变量g：若出现某两数字相同(即a(i)=a(k))或a(1)>a(4),则赋值g=0(重复标记)。首先从a(1)=1开始,逐步给a(i)(1≤i≤9)赋值,每一个a(i)赋值从1开始递增至9。直至a(9)赋值,判断：若i=9,g=1,等式同时满足,则为一组解,用n统计解的个数后,格式打印输出这组解。若i<9且g=1,表明还不到九个数字,则下一个a(i)从1开始赋值继续。若a(9)=9,则返回前一个数组元素a(8)增1赋值(此时,a(9)又从1开始)再试。若a(8)=9,则返回前一个数组元素a(7)增1赋值再试。依此类推，直到a(1)=9时,已无法返回,意味着已全部试毕,求解结束。17２．算法描述输入正整数n,m,(n≥m);i=1;a[i]=<元素初值>;while(1){g=1;for(k=i-1;k>=1;k--)if(<约束条件1>)g=0;/*检测,不满足返回*/if(g&&<约束条件2>)printf(a[1-m]);/*输出一个解*/if(i<n&&g){i++;a[i]=<取值点>;continue;}while(a[i]==<回溯点>&&i>1)i--;/*回溯*/if(a[i]==n&&i==1)break;/*退出循环，结束*/elsea[i]=a[i]+1;}18２．算法描述输入n=m=9;i=1;a[i]=1;while(1){g=1;for(k=i-1;k>=1;k--)if(a[i]==a[k]||a[1]>a[4]

)g=0;/*检测,不满足返回*/if(g&&i=9&&a[1]*m2*m3+a[4]*m1*m3=a[7]*m1*m2

)printf(a[1-m]);/*输出一个解*/if(i<n&&g){i++;a[i]=1;continue;}while(a[i]==n&&i>1)i--;/*回溯*/if(a[i]==n&&i==1)break;/*退出循环，结束*/elsea[i]=a[i]+1;}192.4.2排列组合1.实现排列A(n,m)对指定的正整数m,n(约定1<m<=n),具体实现排列A(n,m)。（1）回溯算法设计设置一维数组a，a(i)（i=1,2,…,m）在1—n中取值。首先从a(1)=1开始,逐步给a(i)(1≤i≤m)赋值,每一个a(i)赋值从1开始递增至n。为判断数字是否重复,设置中间变量g：先赋值g=1；若出现某两数字相同(即a(i)=a(j)),则赋值g=0(重复标记)。若i=m与g=1同时满足,则为一组解,用s统计解的个数后,格式打印输出这组解。若i<m且g=1,表明不到m个数字,下一个a(i)从1开始赋值，继续。若a(i)=n,则返回前一个数组元素a(i-1)增1赋值。直到a(1)=9时,已无法返回,意味着已全部试毕,求解结束。

20２．算法描述输入正整数n,m,(n≥m);i=1;a[i]=1;while(1){g=1;for(j=1;j<i;j++)if(a[j]==a[i]

)g=0;/*检测,不满足返回*/if(g&&i==m)printf(a[1-m]);/*输出一个解*/if(i<n&&g){i++;a[i]=1;continue;}while(a[i]==n&&i>1)i--;/*回溯*/if(a[i]==n&&i==1)break;/*退出循环，结束*/elsea[i]=a[i]+1;}213.程序变通注意到组合与组成元素的顺序无关，约定组合中的组成元素按递增排序。因而，把以上程序中的约束条件1（a[j]==a[i]）修改为a[j]>=a[i]，即可实现从n个不同元素中取m个(约定1<m<n)的组合。把以上程序中的输出语句printf("%d",a[j])改为printf("%c",a[j]+64);排列(或组合)输出由前n个正整数改变为前n个大写英文字母输出。把以上程序中的输出语句printf("%d",a[j])改为printf("%c",n+65-a[j]);排列(或组合)输出由前n个正整数改变为前n个大写英文字母逆序输出。

22

1.问题提出由2n个0或1组成的数环，形成的由相连n个数字组成的2n个二进制数恰好在环序列中都出现一次。这个序列被称作n阶德布鲁金（Debrujin）环序列。为构造与统计方便，约定n阶德布鲁金环序列由n个0开头。二阶德布鲁金环序列非常简单，显然只有0011这一个解，2个数字组成的二进制数依次为00,01,11,10（因为是环，尾部0即开头的0，下同），共4个，每个各出现一次。三阶德布鲁金环序列也不复杂，由000开头,第4个数字与第8个数字显然都为1(否则会出现0000出界)。余下三个数字组合只能为011,110,101三种情形。而未出现111,且有110,011等重复，显然不满足三阶德布鲁金环序列条件。因而三阶德布鲁金环序列有与两个解：随着阶数的增加，求解德布鲁金序列难度也相应增大。

2.4.3德布鲁金环序列232.回溯求解n阶德布鲁金环序列在n阶德布鲁金环序列中，共有m=2^n个二进制数字。设置一维a数组，约定a(n)=1，a(m-1)=1，其余数组元素为0。应用回溯法探求a(n)——a(m-2)，这些元素取0或1。问题的解空间是由数字0或1组成的m-n-2位整数组，其约束条件是0的个数为m/2-n个，且没有相同的由相连n个数字组成的二进制数。当i≤m-2时，a(i)从0取值；当i>n+1且a(i)=1时回溯；当i=n+1且a(i)=1时退出。当a(n)——a(m-2)已取数字时，设置h统计其中0的个数，若h≠m/2-n，则返回；若h=m/2-n，判断是否有相同的由n个数字组成的二进制数。若存有相同的，标注t=1；若不存在有相同的，保持t=0,作打印输出。

243．算法描述输入正整数n,计算m=2^n;a[n]=1;a[m-1]=1;i=n+1;while(1){if(a[j]==a[i]

)g=0;/*检测,不满足返回*/if(i=m-2&&h=m/2-n&&m1≠m2)printf(a[0—m-1]);/*输出一个解*/if(i<n&&g){i++;a[i]=0;continue;}while(a[i]==1&&i>n+1)i--;/*回溯*/if(a[i]==1&&i==n+1)break;/*退出，结束*/elsea[i]=a[i]+1;}251.n皇后问题要求在n×n方格棋盘放置n个皇后使它们不相互攻击(即任意两个皇后不允许处在同一横排,同一纵列,也不允许处在同一与棋盘边框成45度角的斜线上。正整数n从键盘输入,n>2)。2.回溯探求设计设置数组a(n),数组元素a(i)表示第i行的皇后位于第a(i)列.求n皇后问题的一个解,即寻求a数组的一组取值,该组取值中每一元素的值互不相同(即没有任两个皇后在同一列),且第i个元素与第k个元素相差不为abs(i-k),(即任两个皇后不在同一45度角的斜线上)。2.4.4高斯皇后问题及其拓广26

首先a(1)从1开始取值。然后从小到大选择一个不同于a(1)且与a(1)相差不为1的整数赋给a(2)。再从小到大选择一个不同于a(1),a(2)且与a(1)相差不为2,与a(2)相差不为1的整数赋给a(3)。依此类推,至a(n)也作了满足要求的赋值,打印该数组即为找到的一个n皇后的解。为了检验a(i)是否满足上述要求,设置标志变量g,g赋初值1。若不满足上述要求,则g=0。按以下步骤操作:

令x=abs(a(i)-a(k))(k=1,2,...,i-1)

判别:若x=0或x=i-k,则g=0。若出现g=0,则表明a(i)不满足要求,a(i)调整增1后再试,依此类推。若i=n且g=1,则满足要求,用s统计解的个数后，格式打印输出这组解。若i<n且g=1，表明还不到n个数，则下一个a(i)从1开始赋值继续。

27

3．算法描述输入正整数n;i=1;a[i]=1;while(1){g=1;for(k=i-1;k>=1;k++){x=absf(a[i]-a[k]