从递归算法到迭代算法

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;
 }

我尝试了一段时间的循环，但是我不知道如何计算" A"one_answers" 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

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

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

如果间隔为空，则返回的值（val）为0。否则，如果此子阵列的中间元素等于K，则将val设置为1退回。因此，从某种意义上说，它计算数组中的K数。

但是，如果发现左侧的计数不大于val，即如果val = 0或0或1，如果val = 1，则将右侧的值评估为左 的值val。

---

没有堆栈，

可能是可能的。如果您查看遍历遍历的子间隔的序列，则可以从N的二进制表示中重建它。那么该函数的结果是沿邮寄过程收集的部分结果的积累。

。

如果可以将帖子列入订单，这将减少到A上的单个线性通行证。这是有点技术的。

Answer 2

借助二维数组的帮助可以是这样的简单方法：

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];

说明：

请注意，对于i，它正在减少，并且j正在增加，因此，当计算dp[x][y]时，您需要dp[x][z - 1] (with z - 1 < j)和dp[z + 1][j] (with z >= i)，并且应该已经填充这些值。