递归正常循环转换

我已经在下面给出的是实际上是计数someValues.The方法的方法。递归正常循环转换

public static double sum(int z, int x, int y) 
    { 
     double count = 0.0; 
     if (x == 0) 
     { 
      if (z <= 0) return 1.0; 
      return 0.0; 
     } 
     for (int i = 1; i <= y; i++) 
     { 
      count += sum(z - i, x - 1, y); 
     } 
     return count; 
    }

我只是想将此方法从递归转换为正常迭代。或者，如果可能的话，一些一线方程。请帮帮我。

来源

2017-01-09 kaushik

你能举一个输入和输出的例子吗？ – Gatusko

肯定..总和（2,2,4）= 16，和（4,1,4）= 1 – kaushik

这是一个棘手的问题，使用z <= x中的答案为y^x的，但随着生长z中的结果变小。 – fafl

所以这不是很漂亮，但它的工作原理没有递归。此外，我从双变的返回类型的，因为考虑到INT：

public static int sum(int z, int x, int y) 
{ 
    // Compute number of calls 
    int[][] calls = new int[x+1][x*y+1]; 
    calls[0][0] = 1; 
    for (int i = 0; i < x; i++) { 
     for (int j = 0; j <= x*y; j++) { 
      for (int target = j+1; target <= j+y && target <= x*y; target++) { 
       calls[i+1][target] += calls[i][j]; 
      } 
     } 
    } 

    // Return count of last column where z <= 0 
    int result = 0; 
    for (int j = x*y; z-j <= 0; j--) { 
     result += calls[x][j]; 
    } 
    return result; 
}

要了解，看看在这个高科技的Excel工作表：

这个图表显示的呼叫sum(3, 3, 3)。横向上你看到x和垂直你看到z都变小了。 y是3并且没有改变。

左上角的1意味着一个呼叫sum(3, 3, 3)。这个电话然后产生三个子电话（因为y = 3）：sum(2, 2, 3),sum(1, 2, 3)和sum(0, 2, 3)。这三个调用可以在下一列找到（其中x = 2）。

每个这三个呼叫然后产卵再次三次呼叫，为x = 1的行中示出。这9个调用与z有重叠。然后，这九个呼叫中的每一个再次产生三个呼叫，导致x = 0列中的27个呼叫。

要获得结果，只需计算x = 0列中的所有调用，其中z < = 0。在此示例中，这是每个调用，因此您得到的结果为27.对于更大的z，结果将会更小。

来源

2017-01-10 13:23:43 fafl

public static double sum(int z, int x, int y) { 
    int num = 0;  
    for (int i = 0; i <= y; i++) { 
     if (z - x - i > 0) { 
      num++; 
     } 
    } 

    return (double) (Math.pow(y, x) - num); 
}

说明：您的方法最多会启动递归调用y^x。递归的最后一级，x == 0，你要确定的z最大值在所有的通话和检查有多少这些电话确实具有z > 0，因此调用返回0，你不必考虑它。现在，在递归的最后一级，最大值z由z - x给出。您现在只需对for循环中的所有实例进行计数，其中z - x保持为正值，因此它不会影响您的总和。在计算该数字后，从结果的初始近似中减去该数字，即y^x。

来源

2017-01-09 22:59:15 Polb

这给出了总和为79（6,4,3），其中正确的结果是76 – fafl

递归正常循环转换

回答

相关问题