资源描述
算法导论参考答案 第 2 章 第 3 章 第 4 章 第 5 章 第 6 章 第 7 章 第 8 章 第 9 章 第 15 章 第 16 章 第 24 章 第 25 章 第2章 2.1-1 2.1-2 2.1-3 2.1-4 2.2-1 2.2-2 2.2-3 2.2-4 2.3-1 2.3-2 void Merge(int *A,int p,int q,int r) /构建左半部分和右半部分的辅助数组 int n1=q-p+1; int n2=r-q; int *L=new intn1; int *R=new intn2; for (int i=0;in1;i+) Li=Ap+i-1; for(int j=0;jn2;j+) Rj=Aq+j; int i=0; int j=0; int k=p-1; while(i=n1-1) i+; else Ak=Rj; j+; k+; while(i=n1-1) Ak=Li; i+; k+; while(j=n int left=0,right=len,mid=(left+right)/2; while(leftamid) left=mid+1; else if(nn) for(i=0;iai; b0=1; c0=-1; c1=a0; len=1;/此时只有 c1求出来,最长递增子序列的长度为 1. for(i=1;ilen)/要更新 len,另外补充一点:由二分查找可知 j 只可能比 len 大 1 len=j;/更新 len coutlenendl; return 0; 15.5-1 15.5-2 15.5-3 15.5-4 第 16 章 16.1-1 16.1-2 16.1-3 16.1-4 16.2-1 16.2-2 16.2-3 16.2-4 16.2-5 16.2-6 16.2-7 16.3-1 16.3-2 16.3-3 16.3-4 16.3-5 16.3-6 那就推广到树的结点有三个孩子结点,证明过程同引理 16.3 的证明。 16.3-7 16.3-8 第 24 章 24.1-1 同源顶点 s 的运行过程,见图 24-4 24.1-2 24.1-3 24.1-4 24.1-5* 24.1-6 修改 Bellman-Ford 算法,先找到负环上的一个节点,再依次找到负环上的一个节点,再依 次找到负环上的其他节点。 24.2-1 见图 24-5 24.2-2 最后一次不影响结果 24.2-3 24.2-4 24.3-1 见图 24-6 24.3-2 24.3-3 24.3-4 24.3-5 24.3-6 24.3-7 24.3-8 这种情况下不会破坏已经更新的点的距离。 24.4* 24.5* 第 25 章 25.1-1 见图 25-1 25.1-2 为了保证递归定义式 25.2 的正确性 25.1-3 25.1-4 25.1-5 25.1-6 25.1-7 25.1-8 25.1-9 25.1-10 25.2-1 见图 25-4 25.2-2 25.2-3 25.2-4 25.2-5 25.2-6 25.2-7 25.2-8 25.2-9 25.3-1 25.3-2 25.3-3 25.3-4 25.3-5 25.3-6
展开阅读全文