0

我想通过将每列中的一个值乘以乘积来以“所有可能的方式”计算一个包含值的表。我最好用Java解决这个问题。该表的大小为 n*m。例如，它的大小可能为 3*5，并包含：

0.5, 3.0, 5.0, 4.0, 0.75
0.5, 3.0, 5.0, 4.0, 0.75
0.5, 9.0, 5.0, 4.0, 3.0

获得产品的一种方法是：

0.5 * 3.0 * 5.0 * 4.0 * 0.75

当表的大小为 n * m 时，如何以“所有可能的方式”计算它？我想编写一个适用于每个 n*m 表的程序（可能包含循环）。

4

2 回答 2

0

创建一个递归方法，进行两次调用，一次调用在最终产品的列中使用数字，一次调用不使用。在您不使用它的呼叫中，您再拨打两个电话，一个使用列中的下一个号码，一个不使用，依此类推。当您确实使用数字时，您会转到下一列，有效地创建一个递归树，其中每个叶子都是查找产品的不同组合。

除了您的表格之外，您不需要任何数据结构，它可以容纳任何大小的表格。如果您不理解我所描述的方法，我可以提供一些简短的示例代码，但它相当简单。

method findProducts(int total, pos x, pos y) 
if(inbounds of table)
findProducts(total + column[x]row[y] value, 0, y+1) 
findProducts(total, x+1, y) 
else 
print(total)

像这样的东西，计数器会很有用，所以你只能打印那些是 y 数字组合的值，即行数。

于 2013-06-13T21:12:41.380 回答
0

正如另一个答案所提到的，您可以递归地执行此操作，但总的来说，我发现 Java 对递归有些不满意。另一种方法是跟踪您在表中的位置的“签名”（即，m每个值为的长度数组0 <= val < m）。每个签名唯一地指定通过表的路径，您可以很容易地计算给定签名的值：

double val = 1.;
for (int j=0; j<m; j++)
     val *= table[j][signature[j];

要遍历所有签名，请将它们视为（最多）m 位数的基数n并简单地递增，确保在超过 时携带n。这是一些未经测试、未经优化、可能索引错误的示例代码：

int[] sig = new int[m];
double[] values = new double[m*n];
while (sig[m-1] < n) {
     values = getValue(table, sig);
     int carry = 1, j = 0;
     while (carry > 0 && j < n) {
         sig[j] += carry;
         carry = 0;
         while (sig[j] >= n) {
              sig[j] -= n;
              carry += 1;
         }
      }
 }
于 2013-06-13T21:19:39.143 回答