西工大算法复习资料总结材料

1、笔试部分一简答题(40分)1算法的基本概念、性质及其与程序的联系与区别算法：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法性质：输入-有零个或者多个外部量作为算法的输入；输出-算法产生至少一个量最为输出；确定性：组成算法的每条指令是清晰的、无歧义的；有限性：算法中指令的执行次数有限和执行的时间有限。程序：是算法用某种设计语言的具体实现，程序可以不满足算法的有限性。2大O表示法的含义和渐进时间复杂度(要会计算复杂度)大O表示法：称一个函数 g(n)是O(f(n)，当且仅当存在常数 c>0和n0>=1 ，对一切 n>n0 均有|g(n)|<=c|f(n)|

2、成立，也称函数g(n)以f(n)为界或者称 g(n)囿于f(n)。记作g(n)=O(f(n)。定义：如果一个问题的规模是n ,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数。T(n)称为这一算法的"时间复杂度"。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。3分治法的基本思想是什么分治法的基本思想是：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题 的解。4回溯算法的基本思想及其一般模式（子集树+排列树）基本思想：在包含问题的所有解的解空间树中，按照

3、深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结 束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。搜索子集树的一般模式：void search（i nt m）if(m>n)output。；elseam=0;search(m+1);am=1;search(m+1);搜索排列树的一般模式：void search(i nt m)/递归结束条件/相应的处理（

4、输出结果）/设置状态：0表示不要该物品/递归搜索：继续确定下一个物品/设置状态：1表示要该物品/递归搜索：继续确定下一个物品if(m>n)/递归结束条件output。；/相应的处理(输出结果)elsefor(i=m;i<=n ;i+)swap(m,i);/ 交换 am和 aiif()if(canplace(m)/如果m处可放置search(m+1); / 搜索下一层swap(m,i);/ 交换 am和 ai(换回来)5动态规划的基本思想、基本步骤、基本要素是什么基本思想：将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。基本步骤：找出最优解的性质，并刻

5、画其结构特征； 递归地定义最优值； 以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造最优解。基本要素：最优子结构性质和子问题重叠问题6什么是最优子结构性质和子问题重叠性质最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重 要线索。子问题重叠性质：指在用递归演算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠 性质，对每一个子问题只计算一次， 然后将其计算结果保存在一个表格中，当再次需要计算已经计算

6、过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。7分治法与动态规划的联系与区别联系：基本思想相同，即将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。区别：适用于动态规划法求解的问题， 经分解得到的子问题往往不是相互独立的。 分治 法子问题被重复计算多次，而动态规划子问题可用一个表来记录已解决子问题的答案，避免了子问题重复计算的问题。8动态规划的变形（备忘录方法）与动态规划的联系与区别联系：都用表格保存已解决的子问题的答案区别：备忘录方法的递归方式是自顶向下的，而动态规划的递归方式是自底向上的。9分支限界法（广度优先搜索）的基本思想是什么分支限

7、界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展节点。活结点一旦成为扩展节点，就一次性产生所有儿子节点。在这些儿子节点中，导致不可行解或导致非最优解的儿子节点被舍弃，其余儿子节点被加入活结点表中。此后，从活结点表中取下一节点成为当前扩展节点，并重复上述节点扩展过程，这个过程一直持续到找到所需的解或活结点表为空时为止。10. 分支限界法与回溯法的区别1.搜索方式不同：分支限界法使用广度优先或最小消耗优先搜索，而回溯法使用深度优先搜索。2主要区别：在于它们对当前扩展节点所采用的扩展方式不同。分支限界法：每个节点只有一次成为活结点

8、的机会回溯法：活结点的所有可行子节点被遍历后才被从栈中弹出11. 搜索算法的一般模式搜索算法关键要解决好状态判重的问题：void search。open表初始化为空；起点加入到 open表；while（ open 表非空）取open表中的一个结点 u;从open表中删除u;for(对扩展结点u得到的每个新结点vi ）if（vi是目标结点）输出结果并返回；lf(n otused(vi)vi进入open 表;12. 贪心算法的基本思想、基本步骤及基本要素基本思想：贪心算法总是做出在当前看来是最好的选择，即贪心算法并不从整体最优上加以考虑，所做的选择只是在某种意义上的局部最优选择，即贪心选择。基本步

9、骤：从问题的某个初始解出发； 采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个局部最优解缩小问题的规模； 将所有局部最优解综合起来，得到原问题的解。基本要素：贪心选择性质：指所求问题的整体最优解可以通过一系列的局部最优的选择，即贪心选择来达到。贪心选择策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态，只与当前状态有关。最优子结构性质：一个问题的最优解包含其子问题的最优解。13. 贪心算法与动态规划算法联系与区别联系：都要求问题具有最优子结构性质，即一个问题的最优解包含其子问题的最优解。区别：在动态规划算法中， 每步所做的选择往往是依赖于相关子问题的解，因而只有

10、在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好的选择， 即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。动态规划算法通常以自底向上方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相机的贪心选择以简化问题规模。二设计题(60分-写出核心代码或伪代码和相关的变量声明)1用二分查找算法查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L,输出为x在L中的位置或者x不在L中的信息。最直接的做法就是一个一个地扫描L的所有元素，直到找到x为止。这种方法对于有n个元素的线性表在最坏的情况下需要n次比较。一般来说，若没有其他的附加信息，

11、 在有n个元素的线性表中查找一个元素在最坏情况都需要n次比较。考虑最简单的情况，该线性表为有序表，设其按照主键的递增顺序从小到大排列。核心伪代码：fun ctio n Bin arySearch(L,a,b,x)beginif a>b the n retur n -1else begi nm=(a+b)div 2;if x=Lm the n retur n (m)else if x>Lmthe n return Bin arySearch(L,m+1,b,x);elsereturn Bin arySearch(L,a,m-1,x); en d;en d;2请采用快速排序算法为下列数

12、字排序，并写出最终结果(21 25 49 25* 16 08)快速排序的基本思想：选定一个基准值元素，对带排序的序列进行分割，分割之后的序 列一部分小于基准值元素，另一部分大于基准值元素，再对这两个分割好的子序列进行上述 的过程。void swap(i nt a,i nt b) int t;t =a ;a =b ;b =t ;int Partiti on (i nt arr,i nt low,i nt high)in t pivot=arrlow;采用子序列的第一个元素作为基准元素while (low < high)/从后往前在后半部分中寻找第一个小于基准元素的元素while (low

13、< high && arrhigh >= pivot)-high;/将这个比枢纽元素小的元素交换到前半部分swap(arrlow, arrhigh);/从前往后在前半部分中寻找第一个大于基准元素的元素while (low <high &&arr low <=pivot )+low ;/将这个基准元素大的元素交换到后半部分swap (arr low ,arr high );return low ;/ 返回基准元素所在的位置void QuickSort(i nt a,i nt low,i nt high)if (low <high )i

14、nt n=Partiti on (a ,low ,high );QuickSort (a ,low ,n );QuickSort (a ,n+1,high );3写出对下面的序列进行归并排序的过程(从小到大)(63 14 9 98 23 48 15 70)核心代码：void MergeSort(i nt low,i nt high)if(low>=high)每个子列表中剩下一个元素时停止return;/将列表划分成相等的两个子列表，若有奇数个元素，则在左边子列表大于右边子列 表elseint mid=(low+high)/2;MergeSort(low,mid);递归划分子列表Merge

15、Sort(mid+1,high);/递归划分子列表/新建一个数组b用于存放归并的元素in t b=new in thigh-low+1;/两个子列表进行排序归并，直到两个子列表中的一个结束for(i nt i=low,j=mid+1,k=low;i<=mid&&j<=high;k+)if(arri<=arrj)bk=arri;elsebk=arrj;j+； for(;j<=high;j+,k+)/如果第二个子列表中仍然有元素，则追加到新列表bk=arrj; for(;i<=mid;i+,k+)/如果第一个子列表中仍然有元素，则追加到新列表bk=ar

16、ri;for(i nt z=0;z<high-low+1;z+)/将排序的数组b的所有元素复制到原始数组arr中arrz=bz;4装载问题问题关键在于：首先将第一艘船尽可能装满且c1<最大值max，然后将剩余的部分装上第二艘船c2，若:总重量-c1<c2则能装入两艘船。关键代码：int c1,c2 ,n ,w10;int weight=O,max=O;void search(i nt m)if(m=n)if(weight<=c1) if(weight>max) max=weight;elseif(weight+=wm<=c1) weight+=wm;sear

17、ch(m+1);weight-=wmsearch(m+1);5.01-背包问题(回溯法)关键代码：int n,c;int w1000,v1000;int a1000,max=0;void search(i nt m)if(m>=n)checkmax();elseam=0;search(m+1);am=1;search(m+1)void checkmax()int i;int weight=0,value=0;for(i=0;i <n ;i+)if(ai=1)weight+=wi; value+=vi; if(weight<=c) if(value>max) max=va

18、lue;6循环赛日程表(递归与分治)设计思想：按分治策略，可以将所有选手对分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割， 直至只剩下两个选手时，比赛日程表的指定就很简单了。核心代码：int N = 1;void UpRightCopy(i nt n, int array)for(i nt i = 0; i < n; i+)for(i nt j = n; j < 2 * n ;j+)arrayN * i + j = 2 * n + 1 -arrayN * i + 2 * n - 1 - j;void Down

19、RightCopy(i nt n, int array)for(i nt i = n; i < 2 * n; i+)for (int j = n; j < 2 * n ;j+)arrayN * i + j = arrayN * (i - n) + j - n;void LeftDow nCopy(i nt n, int array)for (i nt i = n; i < 2 * n; i+)for (int j = 0; j < n ;j+)arrayN * i + j = arrayN * (i - n) + j + n;void turn (i nt n, int

20、 array)if(n = 1)array0 = 1;elseturn(n / 2, array);Dow nRightCopy( n / 2, array);UpRightCopy(n / 2, array);LeftDow nCopy (n / 2, array);7最长公共子序列核心代码：char a201,b201;int n1, n2;void search()int List201201;for(i nt i=0;i<=n 1;i+)ListiO=O;for(i nt j=O;j<=n 2;j+)ListOj=O;for(i nt i=1;i<=n 1;i+)fo

21、r(i nt j=1;j<=n 2;j+)if(ai-1=bj-1)Listi j=Listi-1j-1+1;elseif(Listi-1 j>Listij-1)Listi j=Listi-1j;elseListi j=Listi j-1;8矩阵连乘问题核心代码：int n;in t p11;void a1111,temp;for(i nt i=1;i<=n ;i+)aii=O；for(i nt d=1;d<=n _1;d+)for(i nt i;i<=n_ d;i+)int j=i+d;aij=0+ai+1j+pi-1*pi*pj;for(

22、i nt k=i+1;k<j;k+)temp=aik+ak+1j+pi-1*pk*pj;if(temp<ai j)ai j=temp;9用备忘录算法实现计算Fibo nacci数列核心代码：int Fib(i nt n)int result n =0,0,.,0;int f1,f2;if(n <2)return n;if(result n-1=0)f1=Fib( n-1);elsef1=result n-1;if(result n-2=0)f2=Fib( n-2);elsef2=result n-2; result n=f1+f2; return (f1+f2);设计一个的高

23、效算法实现Fibo nacci数列Version 1(效率最差)1. long Fibonacci( int n)2. 3. if (n = 0)4. return 0;5. else if (n = 1)6. return 1;7. else if (n > 1)8. return Fibonacci (n -1) + Fibonacci (n -2);9. else10. return -1;11. Version2(效率其次)1. long Fibonacci2( int n)2. 3. if (n = 0)4. return 0;5. else if (n =1)6. retur

24、n 1;7. else if (n > 1)8. 9.9. if (tempResultn !=0)10. return tempResultn;11. else12. 13. tempResultn = Fibonacci2 (n -1) + Fibonacci2 (n -15.return tempResultn;16.17.18.Version 3（效率最高-放弃递归用循环实现）1.long Fibonacci3( int n)2.3.long * temp = new long n + 1;4.5.temp 0 = 0;6.7.if (n > 0)8.temp 1 = 1;

25、9.10.for (int i = 2; i <= n; +i)11.12.tempi = tempi -1 + tempi -2;13.14.15.long result = tempn;17. delete temp;18.18. return result;19. 10. 活动安排问题问题关键在于：理解什么是相容性活动！ 若区间s1,f1）与区间s2,f2）不相交，则称活动 1与活动2是相容的，即s1>=f2或s2>=f1时，活动1与活动2相容。（区间表示的是活 动的起始时间s和结束时间f）核心代码：struct actio nint begi n;int en d;a

26、1000;int n;/n表示活动的总数int sum=0;/sum表示能参加的活动的数量void search。sum=1;int temp=aO.e nd;/temp 表示第一个活动结束的时间 for(i nt i=1;i< n;i+)if(ai.begi n>=temp)sum+;temp=ai.e nd;void selecti on _sort()for(i nt i=0;i< n;i+)int k=i;for(i nt j=i+1;j <n ;j+)if(a j.end<ak.end)k=j;struct actio n temp=ai;ai=ak;a

27、k=temp;11. 最优服务次序问题思路是最短服务时间优先，先将服务时间排序，然后注意后面的等待服务时间既包括等 待部分，也包括服务部分。贪心策略：对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T'。新问题和原问题相同，只是问题规模由n减小为n-1。基于此种选择策略，对新问题T'，选择n-1顾客中选择服务时间最短的先进行服务，如此进行下去，直至所有服务都完成为 止。每个客户需要的等待时间为：T(1)=t(1);T( 2)=t(1)+t(2);T(n )=t(1)+t (2)+.+t

28、( n);总等待时间为：T=n *t(1)+( n-1)*t (2)+( n-2)*t(3)+.+( n+1-i)*t(i)+.+2*t( n-1)+1*t (n)注：st是服务数组，Stj为第j个队列上的某一个顾客的等待时间；su是求和数组,suj的值为第j个队列上所有顾客的等待时间；第一种代码：1. double greedy(vector< int >x, int s)2. 3. vector< int >st(s+1,0);4.vectorv int >su(s+1,0);5.int n=x.size();6.sort(x.begi n( ),x.e nd

29、();7.int i=0,j=0;8.while (i<n)9.st j+=xi;10.suj+=stj;11.i+;12.j+;13.if (j=s)j=0;14.15.double t=0;16.for (i=0;i<s;i+)17.t+=sui;18.t/=n;19.return t;20.第二种方法:1. int x10000;2. int main()4.int n;5.cin >> n;6.int temp;7.for (int j = 0; j< n; j+)8.9.scanf( "%d"，&xj);10.11.sort(

30、x,x+ n);12.for (int i = 1; i < n; i+)13.xi+=xi-1;14.double t = 0;15.for (int i = 0; i < n; i+)16.t+=xi;17.t/=n;18.cout.setf(ios:fixed);19.cout << setprecisi on(2) << t << en dl;20.system( "pause");21.return 0;22. 12. 最短路径问题Dijkstra算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断

31、地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把 从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组 dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。Dijkstra算法可描述如下，其中输入带权有向图是 G=(V,E) , V=1,2,，n，顶点v是源。 c是一个二维数组，cij表示边(i,j)的权。当(

32、i,j)不属于E时，cij是一个大数。disti表 示当前从源到顶点i的最短特殊路径长度。 在Dijkstra算法中做贪心选择时， 实际上是考虑 当S添加u之后，可能出现一条到顶点的新的特殊路，如果这条新特殊路是先经过老的S到达顶点u,然后从u经过一条边直接到达顶点 i,则这种路的最短长度是 distu+cui。 如果distu+cui<disti，则需要更新 disti的值。步骤如下：(1) 用带权的邻接矩阵 c来表示带权有向图，cij表示弧<vi,vj>上的权值。设S为已 知最短路径的终点的集合，它的初始状态为空集。从源点 v经过S到图上其余各点vi的当前 最短路径长度的

33、初值为：disti=cvi, vi 属于V.(2) 选择vu,使得distu=Mindisti | vi 属于V-S,vj就是长度最短的最短路径的终点。 令 S=S U u.(3) 修改从v到集合V-S上任一顶点vi的当前最短路径长度：如果distu+cuj< distj 则修改 distj= distu+cuj.(4) 重复操作(2),(3)共n-1次.1. con st int N = 5;2. const int M = 1000;3. template < class Type4. void Dijkstra( int n, int v,Type dist, int pre

34、v,Type cN+1);5. void Traceback( int v,int i,int prev); / 输出最短路径 v 源点，i 终点6. int main()7. 8. int v = 1; / 源点为 19. int distN+1,prevN+1,cN+1N+1;10.10. cout<<"有向图权的矩阵为："<<e ndl;11. for (int i=1; i<=N; i+)12. 13. for (int j=1; j<=N; j+)14. 15. fin>>cij;16. cout<<ci

35、j<<""17. 18. cout<<e ndl;19. 20. Dijkstra(N,v,dist,prev,c);21. for (int i=2; i<=N; i+)23.24.cout<< "源点1到点"<<i<< "的最短路径长度为："<<disti<<"，其路径为”；25.Traceback(1,i,prev);26.cout<<e ndl;27.28.29.return 0;30.31.template <

36、; class Type>32.void Dijkstra( int n, int v,Type dist, int prev,Type cN+1)33.34.bool sN+1;35.for (int i=1; i<=n; i+)36.37.disti = cvi;disti表示当前从源到顶点i的最短特殊路径长度38.si = false ;39.if (disti = M)40.41.previ = 0;/记录从源到顶点i的最短路径i的前一个顶点42.43.else44.标准实用0.61

37、.5.66.文案大全previ = v;distv = 0;sv = true ;for (int i=1; i<n; i+)int temp = M;int u = v; / 上一顶点/取出V-S中具有最短特殊路径长度的顶点ufor (int j=1; j<=n; j+)if (!s j) && (dist j<temp)u = j;temp = distj;su = true ;/根据作出的贪心选择更新Dist值for (int j=1; j<=n; j+)标准实用6.77.

38、7.88.文案大全Type n ewdist = distu + cuj;if (n ewdist < distj)dist j = n ewdist;prevj = u;/输出最短路径v源点，i终点void Traceback( int v,int i,int prev)if (v = i)cout<<i;return ;Traceback(v,previ,prev);cout<< "->" <<i;89. 13. 霍夫曼编码问题(要求画出霍夫曼树)哈夫曼提出构造最优前

39、缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤 如下:(1) 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。(2) 算法以|C|个叶结点开始，执行|C| 1次的“合并”运算后产生最终所要求的树T。(3) 假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列 Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n 1次的合并后，优先队列中只剩下一棵树，即所要求的树To构造过程如图所示:算法中用到的类定义:1. template < cl

40、ass Type2. class Huffman3. 4. friendBinaryTree< int > HuffmanTree(Type,int );5. public :6. operator Type()const7. 8. return weight;9. 10. /private:11. BinaryTree<int > tree;12. Type weight;13. ;算法HuffmanTree 描述如下：1. template < class Type>2. BinaryTree< int > HuffmanTree(Type

41、f,int n)3. 4. /生成单节点树5. Huffman<Type> *w = new Huffman<Type>n+1;6. BinaryTree< int > z,zero;8.29.for (int i=1; i<=n; i+)乙M akeTree(i,zero,zero);wi.weight = fi;wi.tree = z;/建优先队列MinH eap<Huffma n< Type>> Q(n

42、);for (int i=1; i<=n; i+) Q.lnsert(wi);/反复合并最小频率树Huffma n< Type> x,y;for (int i=1; i<n; i+)x = Q.RemoveMi n();y = Q.RemoveMi n();z.MakeTree(O,x.tree,y.tree);x.weight += y.weight;x.tree = z;Q.l nsert(x);x = Q.RemoveMi n();delete w;30. return x.tree;31. 32.14. 用贪心算法解决搬桌子问题关键思想：把课桌按起点从小到大排序

43、，每次都是搬离当前位置最近的课桌。算法代码：#in clude<stdio.h>int mai n()structint start;int end;a100;int i,j;int n,m,min,nu m,temp,used100=0;scan f("%d%d",&m,&n);for(i=0;i< n;i+)scan f("%d%d",&ai.start,&ai.e nd);/ sort(a,n);/按start从小到大对数组 a排序mi n=0;num=0;while( num<n)temp=

44、O;for(i=0;i <n ;i+)if(usedi=O&&ai.start>=temp)temp=ai.e nd;usedi=1;nu m+;mi n+;prin tf("%d",mi n);15. 八数码难题核心代码：1 #in clude <stdio.h>2 #in clude<memory.h>9种状态3 #define len 362888/状态共有 362880 种，数组稍微开大点4 #define le 9/ 每种状态有9个数据，也可看为每种状态下又有5 typedef int statele;/状态：表

45、示九个格子6 state stlen,goal;/st为状态数组 goal为目标数组/dis为每7 int dislen,factle,headlen,vislen,der42= -1,0,1,0,0,-1,0,1;8种状态的已走的步骤 /der为方向：上，下，左，右9 void encode()/ 编码10int i;1 for (i=fact0=1; i<le; i+)1 facti=facti-1*i;12 int decode( int s)/ 解码13 int i,j,code,cnt;1 for (i=code=0; i<le; i+)4 1 for (cnt=O,j=

46、i+1; j<le; j+)5 if (stsi>stsj)1 cn t+;6 code+=cnt*fact8-i;1 7 if (viscode)1 return 0;8 else1 retur n viscode=1;9 2int bfs()0 2 int front=1,rear=2,i,x,y,z,nx,ny,nz;1 en code();2 while (front<rear)2 2 state & s=stfro nt;3 if (memcmp (s,goal, sizeof (s)=0)/ 对 front 状态和目标状态进行比较2 return fron

47、 t;4 for (i=0; i<le; i+)/找到为0的元素，即空的那个格子，这里选取空2的那个格子是应为相对于1,2,3,8这样的数据，0作为判断依据简单于用数据作为判断5依据2 if (si=0) break ;6 x=i/3;2 y=i%3;7 z=i;/记录空的格子的行标，列表，和所在位置，这里的位置按照从左到右2从上到下依次递增8 for (i=0; i<4; i+)/按照上，下，左，右四个方向进行搜索2 93 nx=x+deriO;0n y=y+deri1;3 nz=nx*3+ny;1 if (nx>=0&&n x<3&&

48、n y>=0&&n y<3)3 2 state & t=strear;3 memcpy (&t,&s, sizeof (s);/记录此时的状态即九个格子的数值3 tz=s nz;3 tn z=sz;4 disrear=disfr on t+1;3 if (decode(rear)/判断strear这种状态是否已经出现过5 rear+;3 6 3fron t+;7 3 return 0;8 3int main( void )4 int i,oj;0 for (i=0; i<le; i+)scanf (”d"，&st1i)

49、;/按从左到右从上到下的顺序存储数据for (i=0; i<le; i+)scanf ("%d"，&goali);oj=bfs();if (oj)printf ("%dn" ,disoj);elseputs ("Impossible" );4142434445464748495051return 0;52535455565758596061626364656667686916.图的M着色问题考虑所有的图，讨论在至多使用m种颜色的情况下，可对一给定的图着色的所有不同方法。通过回溯的方法，不断的为每一个节点着色，在前面n-1

50、个节点都合法的着色之后，开始对第n个节点进行着色，这时候枚举可用的m个颜色，通过和第n个节点相邻的节点的颜色，来判断这个颜色是否合法，如果找到那么一种颜色使得第n个节点能够着色，那么说明m种颜色的方案是可行的。用m种颜色为无向图 G=(V,E)着色，其中，V的顶点个数为n,可以用一个n元组 x=(x1,x2,xn)来描述图的一种可能着色，其中， xi 1,2,m , (1 <i <n)表示赋予顶点 i的颜色。例如，5元组(1,2, 2, 3, 1)表示对具有5个顶点的无向图(a)的一种着色，顶点 A着颜色1，顶点B着颜色2，顶点C着颜色2，如此等等。如果在n元组X中，所有相邻 顶点都不会着相同颜色，就称此 n元组为可行解，否则为无效解。容易看出，每个顶点可 着颜色有m种选择，n个顶点就有mn种不同的着色方案，问题的解空间是一棵高度为n的完全m叉树，这里树高度的定义为从根节点到叶子节点的路径的长度。每个分支结点， 都有m个儿子结点。最底层有mn个叶子结点。例如，表示用3种颜色为3个顶点的图着色的状态空间树。如图所示，对第i (i>=1 )层上的每个顶点，从其父节点到该节点的边上的标号表示顶点i着色的颜色编号。1. #i nclude "stdafx.h"2. #i nclude <iostream>3.