算法导论中文版答案.pdf

算法导论参考答案算法导论参考答案 第第 2 章章 第第 3 章章 第第 4 章章 第第 5 章章 第第 6 章章 第第 7 章章 第第 8 章章 第第 9 章章 第第 15 章章 第第 16 章章 第第 24 章章 第第 25 章章 第 2 章 第 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;i using namespace std; int find(int *a,int len,int n)/修改后的二分查找，若返回值为 x，则 ax=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.