你可以将一个表格视为值的列表。然后,如果你有N个表格,你的问题就是找到N个整数列表(每个整数来自于N个表格中的一个),其乘积等于一个值p。你可以递归地解决这个问题:
- 给定一个非空的表格列表
{t1、 t2、 t3、...}
- 给定要查找的乘积值
p
- 对于
t1
中的每个值v
,您必须寻找具有乘积值p/v
和表格{t2、 t3、...}
的子问题的解决方案(这假设p%v==0
,因为我们处理整数
- 等等。
一些Java代码如下:
public class SO6026472 {
public static void main(String[] args) {
Integer[] t1 = new Integer[] {2,-2,4,7};
Integer[] t2 = new Integer[] {3,-3,-8,0};
Integer[] t3 = new Integer[] {-1,-4,-7,6};
Integer[] t4 = new Integer[] {1,5};
List<List<Integer>> tables = new ArrayList<List<Integer>>();
tables.add(Arrays.asList(t1));
tables.add(Arrays.asList(t2));
tables.add(Arrays.asList(t3));
tables.add(Arrays.asList(t4));
SO6026472 c = new SO6026472();
List<List<Integer>> solutions = c.find(36, tables);
for (List<Integer> solution : solutions) {
System.out.println(
Arrays.toString(solution.toArray(new Integer[0])));
}
}
public List<List<Integer>> find(int p, List<List<Integer>> tables) {
List<List<Integer>> solutions = new ArrayList<List<Integer>>();
if (tables.size() == 0)
return solutions;
if (tables.size() == 1) {
if (tables.get(0).contains(p)) {
List<Integer> solution = new ArrayList<Integer>();
solution.add(p);
solutions.add(solution);
return solutions;
} else
return solutions;
}
List<Integer> table = tables.remove(0);
for (Integer value : table) {
if (value != 0 && p % value == 0) {
List<List<Integer>> subSolutions = find(p / value, tables);
if (! subSolutions.isEmpty()) {
for (List<Integer> subSolution : subSolutions) {
subSolution.add(0, value);
}
solutions.addAll(subSolutions);
}
}
}
tables.add(0, table);
return solutions;
}
}
这段代码打印了一个稍微修改过的示例的解决方案:
[2, 3, 6, 1]
[-2, -3, 6, 1]
这些解决方案适用于任意数量的表格。有一些方法可以改进算法,例如使用记忆化和动态规划。但我认为递归解决方案更加清晰。