f(A,i,mid) 是做什么的？

Question

f(A, i, j) {
    print("f", i, j);
    n: = j - i + 1;
    mid: = floor((i + j) / 2);
    if (n > 1) {
        f(A, i, mid);
        f(A, mid + 1, j);
        g(A, i, j);
    }
}
g(A, i, j) {
    print("g", i, j);
    n: = j - i + 1;
    if (n == 2) {
        if (A[i] > A[j]) swap A[i] and A[j];
    } else {
        for (k: = 0 to n / 4 - 1) swap A[i + n / 4 + k] with A[i + n / 2 + k];
        // swap 2nd and 3rd quarters
        g(A, i, i + n / 2 - 1); // recurse on 1st and 2nd quarters
        g(A, i + n / 2, j); // recurse on 3rd and 4th quarters
        g(A, i + n / 4, i + 3n / 4 - 1); // recurse on 2nd and 3rd quarters
    }

所以我假设 f(A,0,3) 和 A= [ 4,2,3,1] 通过代码后，我可以看到 mid = 1 并且 n=4 这意味着 n > 1 所以这就是我感到困惑的地方 f(A,i,mid) 究竟做了什么？什么是 f 和 g？

Answer 1

你的主要功能是f(A, i, j) { ... }。

在该函数内部，语句 f(A, i, mid) 是同一个函数的 recursive call，带有参数A、i 和 mid。

要更详细地查看发生的情况，您只需插入更多 print 语句即可。

这是将 f() 函数翻译成 Javascript，增加了打印内容，删除了 g()，并添加了深度跟踪和文本缩进：

function f(A, i, j, depth) {
  const indent = "   ".repeat(depth);
  console.log(indent + "f called with A=[" + A.toString() + "], i=" + i + ", j=" + j + ", depth=" + depth + ".");
  let n = j - i + 1;
  let mid = Math.floor((i + j) / 2);
  console.log(indent + "n=" + n + ", mid=" + mid + ".");
  if (n > 1) {
    console.log(indent + "We found n is > 1 --> Enter recursion");
    console.log(indent + "Start 1st recursive call:");
    f(A, i, mid, depth + 1);
    console.log(indent + "After 1st recursive call.");
    console.log(indent + "Start 2nd recursive call:");
    f(A, mid + 1, j, depth + 1);
    console.log(indent + "After 2nd recursive call.");
  }
}

const A = [4, 2, 3, 1];
f(A, 0, 3, 0); // Added a 0 parameter for initial recursion depth value

Answer 2

f和g都是简单的递归函数，f(A,i,mid)只是对原函数f(A,i,j)的调用。取一些值，例如 f(A,0,3) 和 A= [ 4,2,3,1] 并仔细检查代码。

我只是把它转换成java，我发现输出如下：

输入：

int[] A = { 4, 2, 3, 1 };
f(A, 0, 3);

输出：

f: 0, 3
f: 0, 1
f: 0, 0
f: 1, 1
g: 0, 1
f: 2, 3
f: 2, 2
f: 3, 3
g: 2, 3
g: 0, 3
g: 0, 1
g: 2, 3
g: 1, 2

如果你需要完整的代码，就在这里，你可以使用任何你喜欢的输入，

public class SomeRecursion
{
   static void f(int[] A, int i, int j)
   {
      System.out.println("f: " + i + ", " + j);
      int n = j - i + 1;
      int mid = (i + j) / 2;
      if (n > 1)
      {
         f(A, i, mid);
         f(A, mid + 1, j);
         g(A, i, j);
      }
   }

   static void g(int[] A, int i, int j)
   {
      System.out.println("g: " + i + ", " + j);
      int n = j - i + 1;
      if (n == 2)
      {
         if (A[i] > A[j])
         {
            // swap A[i] and A[j];
            int t = A[i];
            A[i] = A[j];
            A[j] = t;
         }
      }
      else
      {
         for (int k = 0; k < n / 4; k++)
         { // swap 2nd and 3rd quarters
           // swap A[i + n / 4 + k] with A[i + n / 2 + k];
            int t = A[i + n / 4 + k];
            A[i + n / 4 + k] = A[i + n / 2 + k];
            A[i + n / 2 + k] = t;

         }
         g(A, i, i + n / 2 - 1); // recurse on 1st and 2nd quarters
         g(A, i + n / 2, j); // recurse on 3rd and 4th quarters
         g(A, i + n / 4, i + 3 * n / 4 - 1); // recurse on 2nd and 3rd quarters
      }
   }

   public static void main(String[] args)
   {
      int[] A = { 4, 2, 3, 1 };

      f(A, 0, 3);

   }
}

f(A,i,mid) 是做什么的？

what does f(A,i,mid) do?

algorithm

recursion

pseudocode