admin管理员组

文章数量:1572326

算法导论（第三版）参考答案：练习2.3-1，练习2.3-2，练习2.3-3，练习2.3-4，练习2.3-5，练习2.3-6，练习2.3-7

Exercise 2.3-1

Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A=⟨3,41,52,26,38,57,9,49⟩ .

Exercise 2.3-2

Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A .

MERGE(A, p, q, r)
  n1 = q - p + 1
  n2 = r - q
  let L[1..n₁] and R[1..n₂] be new arrays
  for i = 1 to n₁
      L[i] = A[p + i - 1]
  for j = 1 to n₂
      R[j] = A[q + j]
  i = 1
  j = 1
  for k = p to r
      if i > n₁  //判断L中是否取完
          A[k] = R[j]
          j = j + 1
      else if j > n₂  //判断R中是否取完
          A[k] = L[i]
          i = i + 1
      else if L[i] ≤ R[j]
          A[k] = L[i]
          i = i + 1
      else
          A[k] = R[j]
          j = j + 1

C code

#include <stdio.h>

void merge(int A[], int p, int q, int r) {
    int i, j, k;

    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1];
    int R[n2];

    for (i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (j = 0; j < n2; j++)
        R[j] = A[q + j + 1];

    for(i = 0, j = 0, k = p; k <= r; k++) {
        if (i == n1) {
            A[k] = R[j++];
        } else if (j == n2) {
            A[k] = L[i++];
        } else if (L[i] <= R[j]) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }
}

void merge_sort(int A[], int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

Exercise 2.3-3

Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

>T(n)=>{ >2,>2T(n/2)+n,if n=2,if n=2k,for k>1.>>

is T(n)=nlgn

令:</

本文标签： 第二章导论算法参考答案

版权声明：本文标题：《算法导论》第二章-第3节_练习（参考答案） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dianzi/1725880481a1046797.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。