从递归算法到迭代算法

Question

我必须将这个递归算法转换为一个迭代算法：

  int alg(int A[], int x, int y, int k){
    int val = 0;

    if (x <= y){
      int z = (x+y)/2;

      if(A[z] == k){
        val = 1;
      }

      int a = alg(A,x,z-1,k);

      int b;

      if(a > val){
        b = alg(A,z+1,y,k);
      }else{
        b = a + val;
      }

      val += a + b;
  }

  return val;
 }

我尝试使用while循环，但无法计算出"a“和"b”变量，因此我执行了以下操作：

  int algIterative(int A[], int x, int y, int k){
   int val = 0;

   while(x <= y){
     int z = (x+y)/2;

     if(A[z] == k){
        val = 1;
     }

     y = z-1;
   }
  }

但实际上我不知道这个算法是做什么的。我的问题是：

这个算法是做什么的？如何将其转换为迭代？我需要用堆栈吗？

任何帮助都将不胜感激。

Answer 1

一个简单的方法可以是这样的smt，借助一个二维数组：

int n = A.length;
int[][]dp = new int[n][n];
for(int i = n - 1;i >= 0; i--){
    for(int j = i; j < n; j++){
        // This part is almost similar to the recursive part.
        int z = (i+j)/2;
        int val = 0;
        if(A[z] == k){
          val = 1;
        }

        int a = z > i ?  dp[i][z - 1] : 0;

        int b;

        if(a > val){
           b = (z + 1 <= j) ? dp[z + 1][j] : 0;
        }else{
           b = a + val;
        }

        val += a + b;
        dp[i][j] = val; 
    }
}
return dp[0][n - 1];

Explanation：

注意，对于i，它是递减的，而j是在增加，所以在计算dp[x][y]时，您需要dp[x][z - 1] (with z - 1 < j)和dp[z + 1][j] (with z >= i)，并且应该已经填充了这些值。

Answer 2

我不确定alg是否能计算出任何有用的东西。

它处理数组A在索引x和y之间的部分，并计算一种计数器。

如果间隔为空，则返回值(val)为0。否则，如果该子数组的中间元素等于k，则val设置为1，然后添加左、右子数组的值，并返回总计。在某种程度上，它计算了数组中k的个数。

但是，如果发现左侧的计数不大于val，即如果val =0，即0或val =1时，则右边的值被计算为左侧+ val上的值。

在没有堆栈的情况下，可能会出现脱毒。如果您查看遍历的子间隔序列，您可以从N的二进制表示中重构它，那么函数的结果就是沿着后置处理收集的部分结果的积累。

如果可以将后置顺序转换为无序，这将减少到一个线性通过A，这有点技术性。