поиск в n 2-мерных массивах

Question

Помогите с тем, как реализовать поиск по n 2-мерным массивам. Чтобы быть более конкретным: Если у меня есть 6 таблиц, и я помещаю их в двумерный массив. Я предоставлю значение, скажем, 10, например, как 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]);
      }
    }
  }
}

Answer 1

Ниже приведен код, который вам требуется:

(Решение включает в себя рекурсию, облегчающую вашу проблему)

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' как мое решение) методы записи:

логическое значение isLast (int tableNo): проверить, является ли данная таблица последней таблицей в списке таблиц

int [] [] Get (int tableNo): получить таблицу с указанным индексом

Также метод sum должен суммировать значения в числах ArrayList. Метод PrintNumbers должен печатать числа в ArrayList чисел подряд. checkValue - это значение, которое вы хотите проверить.

Надеюсь, это поможет ....

Пожалуйста, напишите, если хотите получить разъяснения по этому алгоритму.

Answer 2

Вы можете рассматривать таблицу как список значений.Затем, если у вас есть N таблиц, ваша проблема состоит в том, чтобы найти списки из N целых чисел (каждое из которых взято из одной из N таблиц), произведение которых равно значению p.Вы можете решить эту проблему рекурсивно:

• с непустым списком таблиц {t1, t2, t3, ...}
• с учетом значения продукта p, которое вы ищете
• для каждого значения v в t1 вы должны искать решения подзадачи со значением продукта p / v и таблицами {t2, t3, ...} (предполагается, что p % v == 0, поскольку мы имеем дело с целыми числами
• и т. Д.

Ниже приведен код 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]

Решения работают для любого количества таблиц. Существуют способы улучшить алгоритм, например, с помощью запоминания и динамического программирования. Но я думаю, что рекурсивное решение более понятно.