在n个二维数组中搜索
在n个二维数组中搜索
提问于 2011-05-17 13:09:24
帮助实现在n个二维数组上的搜索。更具体地说:如果我有6个表，我把它们放到一个2维数组中，我会提供一个值，比如10，就像这里的how val=0。我需要从这些表中搜索组成10的所有组合值。该值将通过从所有这些表中获取值来计算。
public static int Main() {
int[] a = {2,1,4,7};
int[] b = {3,-3,-8,0};
int[] c = {-1,-4,-7,6};
int sum;
int i; int j; int k;
int val = 0;
for(i = 0; i < 4; i++) {
for(j = 0;j<4;j++) {
for(k = 0;k<4;k++) {
sum = a[i]* b[j]* c[k];
if(sum == val)
System.out.printf("%d %d %d\n",a[i],b[j],c[k]);
}
}
}
}回答 2
Stack Overflow用户
回答已采纳
发布于 2011-05-17 18:42:55
您可以将表视为值列表。然后，如果你有N个表，你的问题是找到N个整数的列表(每个整数取自N个表中的一个)，它们的乘积等于一个值p。你可以递归地解决这个问题：
如果给定表的非空列表和产品值，您可以在t1中查找每个值的值，您必须查找具有产品值p / v和表{t2, t3, ...}的子问题的解决方案(这里假设<
- >d12v >，因为我们处理的是integers
- etc.
下面是一些java代码：
public class SO6026472 {
public static void main(String[] args) {
// define individual tables
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};
// build list of tables
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));
// find solutions
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])));
}
}
/**
* Computes the ways of computing p as a product of elements taken from
* every table in tables.
*
* @param p the target product value
* @param tables the list of tables
* @return the list of combinations of elements (one from each table) whose
* product is equal to p
*/
public List<List<Integer>> find(int p, List<List<Integer>> tables) {
List<List<Integer>> solutions = new ArrayList<List<Integer>>();
// if we have no tables, then we are done
if (tables.size() == 0)
return solutions;
// if we have just one table, then we just have to check if it contains p
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;
}
// if we have several tables, then we take the first table T, and for
// every value v in T we search for (p / v) in the rest of the tables;
// we do this only if p % v is equal to 0, because we're dealing with
// ints
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]这些解决方案适用于任何数量的表。有一些方法可以改进算法，例如使用记忆化和动态编程。但我认为递归解决方案更清晰。
Stack Overflow用户
发布于 2011-05-17 13:32:02
以下是您需要的代码：
(解决方案包括使您的问题变得更容易的递归)
private ArrayList numbers = new ArrayList();
public void CalculateSum(int tableNumber)
{
if(!Tables.isLast(tableNumber))
{
int[][] a = Tables.Get(tableNumber);
for(int y = 0; y < a.length; y++)
{
for(int x = 0; x < a[y].length; x++)
{
numbers.add(a[y][x]);
CalculateSum(tableNumber + 1);
numbers.remove(tableNumber - 1);
}
}
}else
{
int[][] a = Tables.Get(tableNumber);
for(int y = 0; y < a.length; y++)
{
for(int x = 0; x < a[y].length; x++)
{
if((sum(numbers) + a[y][x]) == checkValue)
{
PrintNumbers(numbers);
System.out.print(a[y][x]);
System.out.println();
}
}
}
}
}您需要实现一个类(我的解决方案是‘Tables’)编写方法：
boolean isLast(int tableNo)：检查给定表是否是您的表列表中的最后一个表
int Get(int tableNo)：获取具有指定索引的表
另外，方法sum应该对数字ArrayList中的值求和。PrintNumbers方法应在一行中打印数字ArrayList中的数字。checkValue是您要检查的值。
希望这能帮上忙。
如果你想要澄清这个算法，请写信给我。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/6026472
复制相关文章
相似问题
腾讯云开发者
