西工大算法复习资料总结(最终修订版)(共26页)

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

2、g(n)|<=c|f(n)|成立，也称函数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(int m) if(m>n) /递归结束条件 output(); /相应的处理(输出结果) else am=0; /设置状态：0表示不要该物品 search(m+1); /递归搜索：继续确定下一个物

4、品 am=1; /设置状态：1表示要该物品 search(m+1); /递归搜索：继续确定下一个物品 搜索排列树的一般模式： void search(int m) if(m>n) /递归结束条件 output(); /相应的处理(输出结果) else for(i=m;i<=n;i+) swap(m,i); /交换am和ai if() if(canplace(m) /如果m处可放置 search(m+1); /搜索下一层 swap(m,i); /交换am和ai(换回来)5. 动态规划的基本思想、基本步骤、基本要素是什么基本思想：将待求解问题分解成若干子问题，先求解子问题，然后从这些子

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

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

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

8、区别：在于它们对当前扩展节点所采用的扩展方式不同。分支限界法：每个节点只有一次成为活结点的机会回溯法：活结点的所有可行子节点被遍历后才被从栈中弹出11. 搜索算法的一般模式搜索算法关键要解决好状态判重的问题：void search()open表初始化为空;起点加入到open表;while( open表非空 )取open表中的一个结点u;从open表中删除u;for( 对扩展结点u得到的每个新结点vi )if(vi是目标结点)输出结果并返回;If(notused(vi)vi进入open表;12.贪心算法的基本思想、基本步骤及基本要素基本思想：贪心算法总是做出在当前看来是最好的选择，即贪心算法并不

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

10、题的最优解。区别：在动态规划算法中，每步所做的选择往往是依赖于相关子问题的解，因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好的选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。 动态规划算法通常以自底向上方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相机的贪心选择以简化问题规模。2 设计题（60分-写出核心代码或伪代码和相关的变量声明）1. 用二分查找算法查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。最直接的做法就是一个一个地扫描L的所有元素，直到找到x为止

11、。这种方法对于有n个元素的线性表在最坏的情况下需要n次比较。一般来说，若没有其他的附加信息，在有n个元素的线性表中查找一个元素在最坏情况都需要n次比较。考虑最简单的情况，该线性表为有序表，设其按照主键的递增顺序从小到大排列。核心伪代码：function BinarySearch(L,a,b,x) begin if a>b then return -1else beginm=(a+b)div 2;if x=Lm then return (m)else if x>Lmthen return BinarySearch(L,m+1,b,x); else return BinarySearc

12、h(L,a,m-1,x); end; end;2. 请采用快速排序算法为下列数字排序，并写出最终结果（21 25 49 25* 16 08）快速排序的基本思想:选定一个基准值元素，对带排序的序列进行分割，分割之后的序列一部分小于基准值元素，另一部分大于基准值元素，再对这两个分割好的子序列进行上述的过程。void swap(int a,int b)int t;t =a ;a =b ;b =t ; int Partition(int arr,int low,int high) int pivot=arrlow;/采用子序列的第一个元素作为基准元素 while (low < high) /从后

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

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

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

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

17、=weight; else if(weight+=wm<=c1)weight+=wm;search(m+1);weight-=wm search(m+1); 5. 01-背包问题(回溯法)关键代码：int n,c;int w1000,v1000;int a1000,max=0;void search(int m)if(m>=n)checkmax(); else am=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)wei

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

19、N * i + j = 2 * n + 1 -arrayN * i + 2 * n - 1 - j; void DownRightCopy(int n, int array) for(int i = n; i < 2 * n; i+) for (int j = n; j < 2 * n;j+) arrayN * i + j = arrayN * (i - n) + j - n; void LeftDownCopy(int n, int array) for (int i = n; i < 2 * n; i+) for (int j = 0; j < n;j+) arra

20、yN * i + j = arrayN * (i - n) + j + n; void turn(int n, int array) if(n = 1) array0 = 1; else turn(n / 2, array); DownRightCopy(n / 2, array); UpRightCopy(n / 2, array); LeftDownCopy(n / 2, array); 7. 最长公共子序列核心代码： char a201,b201; int n1,n2; void search() int List201201;for(int i=0;i<=n1;i+) Listi

21、0=0;for(int j=0;j<=n2;j+) List0j=0;for(int i=1;i<=n1;i+)for(int j=1;j<=n2;j+)if(ai-1=bj-1)Listij=Listi-1j-1+1; else if(Listi-1j>Listij-1) Listij=Listi-1j; else Listij=Listij-1; 8. 矩阵连乘问题核心代码：int n;int p11;void search()int a1111,temp;for(int i=1;i<=n;i+)aii=0; for(int d=1;d<=n-1;d+)

22、 for(int i;i<=n-d;i+)int j=i+d;aij=0+ai+1j+pi-1*pi*pj;for(int k=i+1;k<j;k+)temp=aik+ak+1j+pi-1*pk*pj;if(temp<aij)aij=temp; 9. 用备忘录算法实现计算Fibonacci数列核心代码：int Fib(int n)int resultn=0,0,.,0;int f1,f2;if(n<2)return n; if(resultn-1=0)f1=Fib(n-1);elsef1=resultn-1;if(resultn-2=0)f2=Fib(n-2);else

23、f2=resultn-2;resultn=f1+f2;return (f1+f2);设计一个的高效算法实现Fibonacci数列Version 1(效率最差)1. long Fibonacci(int n)   2.    3.   if (n = 0)   4.       return 0;   5.   else

24、 if (n = 1)   6.       return 1;   7.   else if (n > 1)   8.        return Fibonacci (n - 1) + Fibonac

25、ci (n - 2);   9.   else   10.        return -1;   11.    Version2(效率其次)1. long Fibonacci2(int n)   2.    3.   if (n =

26、60;0)   4.      return 0;   5.   else if (n = 1)   6.     return 1;   7.   else if (n > 1)   8.   

27、;   9.   10.     if(tempResultn != 0)   11.       return tempResultn;   12.     else   13.        14.  &#

28、160;        tempResultn = Fibonacci2 (n - 1) + Fibonacci2 (n - 2);   15.           return tempResultn;   16.   

29、0;     17.       18.   Version 3(效率最高-放弃递归用循环实现)1. long Fibonacci3(int n)   2.    3.   long * temp = new longn + 1;   4.   5.

30、   temp0 = 0;   6.   7.   if (n > 0)   8.      temp1 = 1;   9.   10.    for(int i = 2; i <= n; +i)&

31、#160;  11.      12.      tempi = tempi - 1 + tempi - 2;   13.      14.   15.   long result = tempn;   16. 

32、0; 17.   delete temp;   18.   19.   return result;   20.   10. 活动安排问题问题关键在于：理解什么是相容性活动！若区间s1,f1)与区间s2,f2)不相交，则称活动1与活动2是相容的，即s1>=f2或s2>=f1时，活动1与活动2相容。（区间表示的是活动的起始时间s和结束时间f）核心代码：struct actionint begin;int end;a1

33、000;int n;/n表示活动的总数int sum=0;/sum表示能参加的活动的数量void search()sum=1;int temp=a0.end;/temp表示第一个活动结束的时间for(int i=1;i<n;i+)if(ai.begin>=temp)sum+;temp=ai.end;void selection_sort()for(int i=0;i<n;i+)int k=i;for(int j=i+1;j<n;j+)if(aj.end<ak.end)k=j; struct action temp=ai; ai=ak; ak=temp;11. 最优

34、服务次序问题思路是最短服务时间优先，先将服务时间排序，然后注意后面的等待服务时间既包括等待部分，也包括服务部分。  贪心策略：对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时间最短的顾客进行服务，即做完第一次选择后，原问题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(

35、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.    

36、; vector<int>su(s+1,0);    5.     int n=x.size();    6.     sort(x.begin(),x.end();    7.     int i=0,j=0;    8.     wh

37、ile(i<n)  9.         stj+=xi;     10.         suj+=stj;     11.         i+;  12.     &#

38、160;   j+;     13.         if(j=s)j=0;   14.        15.     double t=0;  16.     for(i=0;i<s;i+)  

39、0;17.         t+=sui;   18.     t/=n;   19.     return t;  20. 第二种方法： 1. int x10000;   2. int main()  3.      

40、 4.     int n;  5.     cin >> n;  6.     int temp;  7.     for(int j = 0; j< n; j+)  8.     

41、0;  9.        scanf("%d",&xj);  10.         11.      sort(x,x+n);      12.     for(int i = 1; i&

42、#160;< n; i+)  13.         xi+=xi-1;            14.     double t = 0;  15.     for(int i = 0;

43、0;i < n; i+)  16.         t+=xi;          17.     t/=n;  18.     cout.setf(ios:fixed);     19.   

44、  cout << setprecision(2)  << t << endl;        20.     system("pause");  21.     return 0;  22. 12. 最短路径问题Dijkstra算法是解单源最

45、短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合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是一

46、个二维数组，cij表示边(i,j)的权。当(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到图上其余各点

47、vi的当前最短路径长度的初值为：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. const int N = 5;  2. con

48、st int M = 1000;   3. template<class Type>  4. void Dijkstra(int n,int v,Type dist,int prev,Type cN+1);  5. void Traceback(int v,int i,int prev);/输出最短路径 v源点，i终点  6. int&

49、#160;main()  7.   8.     int v = 1;/源点为1  9.     int distN+1,prevN+1,cN+1N+1;  10.   11.     cout<<"有向图权的矩阵为："<<endl;  12.   

50、60; for(int i=1; i<=N; i+)  13.       14.         for(int j=1; j<=N; j+)  15.           16.     

51、60;       fin>>cij;      17.             cout<<cij<<" "    18.           

52、;19.         cout<<endl;  20.       21.     Dijkstra(N,v,dist,prev,c);  22.     for(int i=2; i<=N; i+)  23.     

53、0; 24.         cout<<"源点1到点"<<i<<"的最短路径长度为:"<<disti<<"，其路径为"  25.         Traceback(1,i,prev);  26.       

54、;  cout<<endl;  27.       28.   29.     return 0;  30.   31. template<class Type>  32. void Dijkstra(int n,int v,Type dist,int prev,Type c

55、N+1)  33.   34.     bool sN+1;  35.     for(int i=1; i<=n; i+)  36.       37.         disti = cvi;/disti表示当前从源到顶点i的最短

56、特殊路径长度  38.         si = false;  39.         if(disti = M)  40.           41.        

57、     previ = 0;/记录从源到顶点i的最短路径i的前一个顶点  42.           43.         else  44.           45.    

58、;         previ = v;  46.           47.       48.     distv = 0;  49.     sv = true;&

59、#160; 50.     for(int i=1; i<n; i+)  51.       52.         int temp = M;  53.         int u = v;/

60、上一顶点  54.         /取出V-S中具有最短特殊路径长度的顶点u  55.         for(int j=1; j<=n; j+)  56.           57.     

61、60;       if(!sj) && (distj<temp)  58.               59.                 u =

62、60;j;  60.                 temp = distj;  61.               62.          &#

63、160;63.         su = true;  64.         /根据作出的贪心选择更新Dist值  65.         for(int j=1; j<=n; j+)  66.     

64、;      67.             if(!sj) && (cuj<M)  68.               69.        &#

65、160;        Type newdist = distu + cuj;  70.                 if(newdist < distj)  71.       

66、            72.                     distj = newdist;  73.           &#

67、160;         prevj = u;  74.                   75.               76.  

68、         77.       78.   79. /输出最短路径 v源点，i终点  80. void Traceback(int v,int i,int prev)  81.   82.     if(v = i)  83.

69、60;     84.         cout<<i;  85.         return;  86.       87.     Traceback(v,previ,prev);  88.  

70、0;  cout<<"->"<<i;  89.   13. 霍夫曼编码问题（要求画出霍夫曼树）哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。其构造步骤如下：     (1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。     (2)算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。     (3)假设编码字符集中每一字符c的频率是f(

71、c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。构造过程如图所示：算法中用到的类定义：1. template<class Type>   2. class Huffman  3.   4.     friend BinaryTree<i

72、nt> HuffmanTree(Type,int);  5.     public:  6.         operator Type() const   7.           8.        

73、     return weight;  9.           10.     /private:  11.         BinaryTree<int> tree;  12.     

74、60;   Type weight;  13. ;  算法HuffmanTree描述如下：1. template<class Type>  2. BinaryTree<int> HuffmanTree(Type f,int n)  3.   4.     /生成单节点树  5.     Huff

75、man<Type> *w = new Huffman<Type>n+1;  6.     BinaryTree<int> z,zero;  7.   8.     for(int i=1; i<=n; i+)  9.       10.  

76、0;      z.MakeTree(i,zero,zero);  11.         wi.weight = fi;  12.         wi.tree = z;  13.       14.  &

77、#160;  /建优先队列  15.     MinHeap<Huffman<Type>> Q(n);  16.     for(int i=1; i<=n; i+) Q.Insert(wi);  17.     /反复合并最小频率树  18.     Huf

78、fman<Type> x,y;  19.     for(int i=1; i<n; i+)  20.       21.         x = Q.RemoveMin();  22.         

79、;y = Q.RemoveMin();  23.         z.MakeTree(0,x.tree,y.tree);  24.         x.weight += y.weight;  25.         x.tree = z

80、;  26.         Q.Insert(x);  27.       28.     x = Q.RemoveMin();  29.     delete w;  30.     return x.tree;&#

81、160; 31.  32.14. 用贪心算法解决搬桌子问题关键思想：把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。算法代码：#include<stdio.h>int main()structint start;int end;a100;int i,j;int n,m,min,num,temp,used100=0;scanf("%d%d",&m,&n);for(i=0;i<n;i+)scanf("%d%d",&ai.start,&ai.end);/sort(a,n); /按s

82、tart从小到大对数组a排序min=0;num=0;while(num<n)temp=0;for(i=0;i<n;i+)if(usedi=0&&ai.start>=temp)temp=ai.end;usedi=1;num+;min+;printf("%d",min);15. 八数码难题核心代码：12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667

83、6869#include <stdio.h>#include<memory.h>#define len          /状态共有种，数组稍微开大点#define le 9               /每种状态有9个数据,也可看为每种状态下又有9种状态typedef int statele;        /状态：表示九个格子state stlen,goal;           /st为状态数组