计算机常用算法与程序设计教程 第2章 穷举与回溯

《计算机常用算法与程序设计教程 第2章 穷举与回溯》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章穷举与回溯1常用算法与程序设计主要内容2.1穷举及其应用2.2穷举设计的优化2.3回溯法及其描述2.4回溯设计应用2.5回溯设计的优化2常用算法与程序设计2.1穷举及其应用2.1.1穷举概述穷举法又称列举法，其基本思想是逐一列举问题所涉及的所有情况。穷举法常用于解决“是否存在”或“有多少种可能”等问题。应用穷举法时应注意对问题所涉及的有限种情形须一一列举，既不能重复，又不能遗漏。穷举通常应用循环结构来实现。在循环体中，应用选择结构实施判断筛选，求得所要求的解。3常用算法与程序设计穷举法的框架描述：n=0;for(k=<区间下限>;k<=<区间上限>;k++)/*据指定范围实施穷举*/i

2、f(<约束条件>)/*据约束条件实施筛选*/{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非最简,忽略不计；否则赋值得一个最简真分

3、数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

4、是a数列中的一项，赋值给a(t)。当项数t达到规定项数n时,则退出穷举。6常用算法与程序设计（２）按项数循环设计已知前2项，t循环从3开始递增1取值到指定的项数n。第一项的值k从2开始递增取值，对每一个k取值，标记h=0赋值；若k可由已有的项a(j)，a(i)(j

5、一个6位整数分为前后两个3位数,若该数等于所分两个3位数和的平方,则称该数为6位分段和平方数。试求出所有6位分段和平方数。（1)对所有6位数穷举（2)对3位数穷举2.2穷举设计的优化8常用算法与程序设计2.2.2优化穷举循环参量优化穷举循环参量可减少无效循环，提高穷举效率。【例2.6】求解高斯八皇后问题。在国际象棋的8×8方格的棋盘上如何放置8个皇后,使得这8个皇后不能相互攻击。算法设计：高斯八后问题的一个解用一个八位数表示,八位数解的第k个数字为j,表示棋盘上的第k行的第j格放置一个皇后。两个皇后不允许处在同一横排,同一纵列，要求八位数中数字1—8各出现一次，不能重复。因而解的范围区间应为

6、[12345678，87654321]。注意到数字1—8的任意一个排列的数字和为9的倍数，即数字1—8的任意一个排列均为9的倍数，因而穷举a循环的穷举范围定为[12345678，87654321]，其循环步长可定为9。9常用算法与程序设计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重循环中，我们可精

7、简p1循环。（3）穷举设计的进一步优化在循环设置中，p3循环从0—n/5可改进为0—(n-2*p2)/5。10常用算法与程序设计2.3回溯法及其描述2.3.1回溯的基本概念回溯法找出求解问题的线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。回溯法可以形象地概括为“向前走，碰壁回头”。与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步