CODEWITHSUNDEEP
c++calgorithm
Andrew21111
Andrew21111

Reputation: 908

From recursive algorithm to an iterative one

I have to convert this recursive algorithm into an iterative one:

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

I tried with a while loop, but I can't figure out how I can calculate "a" and "b" variables, so I did this:

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

But actually I couldn't figure out what this algorithm does. My questions are:

What does this algorithm do? How can I convert it to iterative? Do I need to use stacks?

Any help will be appreciated.

Upvotes: 0

Views: 136

Answers (2)

user1196549
user1196549

Reputation:

I am not sure that alg computes anything useful.

It processes the part of the array A between the indexes x and y, and computes a kind of counter.

If the interval is empty, the returned value (val) is 0. Otherwise, if the middle element of this subarray equals k, val is set to 1. Then the values for the left and right subarrays are added and the total is returned. So in a way, it counts the number of k's in the array.

But, if the count on the left side is found to be not larger than val, i.e. 0 if val = 0 or 0 or 1 if val = 1, the value on the right is evaluated as the value on the left + val.

Derecursivation might be possible without a stack. If you look at the sequence of subintervals that are traversed, you can reconstruct it from the binary representation of N. Then the result of the function is the accumulation of partials results collected along a postorder process.

If the postorder can be turned to inorder, this will reduce to a single linear pass over A. This is a little technical.

Upvotes: 2

Pham Trung
Pham Trung

Reputation: 11284

A simple way could be smt like this with the aid of a two dimensional array:

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:

Notice that for i, it is decreasing, and j, it is increasing, so, when calculate dp[x][y], you need dp[x][z - 1] (with z - 1 < j) and dp[z + 1][j] (with z >= i), and those values should already be populated.

Upvotes: 1

Related Questions