что делает 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, и g - простые рекурсивные функции, f (A, i, mid) - это просто вызов исходной функции f (A, i, j). Возьмите некоторые значения, такие как f (A, 0,3) и A = [4,2,3,1] и аккуратно go через код.

Я просто преобразовал его в 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);

   }
}

Answer 2

Ваша основная функция: f(A, i, j) { ... }.

Внутри этой функции оператор f(A, i, mid) является рекурсивным вызовом . та же функция, с параметрами 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