0

Добрый день. Есть задача написать процедуру, на вход которой будет подаваться двумерный массив рандомной размерности. Требуется вывести все возможные суммы элементов с условием, что за одну итерацию из одномерного массива (строки) берется только одно значение. Сам алгоритм выглядит следующим образом.

Пример:

на входе:

123  
456  
789  

на выходе:

1+4+7 1+4+8 1+4+9  
1+5+7 1+5+8 1+5+9  
1+6+7 1+6+8 1+6+9  

2+4+7 2+4+8 2+4+9  
2+5+7 2+5+8 2+5+9  
2+6+7 2+6+8 2+6+9  

3+4+7 3+4+8 3+4+9  
3+5+7 3+5+8 3+5+9  
3+6+7 3+6+8 3+6+9  

Вопрос: как реализовать данный алгоритм для массива nxn(array [n][n])?

5
  • 1
    Для каждой имеющейся строки достаточно брать первый элемент в сумму. А затем сдвигать элемент последней строки, как дойдет до конца - сдвинуть элемент предпоследней строки, у последней вернув "указатель" на первый элемент. Когда дойдем до конца предпоследней строки - сдвигать элемент строки перед ней. И так далее, пока в первой строке не дойдем до конца, и сдвинуть дальше элемент первой строки будет нельзя. Т.к. язык, исполнитель (какое-то устройство или, может быть, крепостной?) не указан, этот комментарий - решение для русского языка.
    – Arkady
    29 сен 2014 в 12:32
  • Спасибо. Язык исполнитель будет java.
    – photozaz
    29 сен 2014 в 12:57
  • Вам нужно обойти все перестановки конечного множества [1 .. n], где n — количество столбцов. Для каждой перестановки τ нужно подсчитать сумму Σ array[i][τ(i)]. Надеюсь, таблицы квадратные?
    – VladD
    29 сен 2014 в 13:36
  • Таблицы также рандомной размерности.
    – photozaz
    29 сен 2014 в 13:41
  • @photozaz: А, понял. Тогда всё гораздо проще — вам нужны не перестановки, просто n циклов по каждой координате.
    – VladD
    29 сен 2014 в 13:43

2 ответа 2

1

Попробуйте вот так.

bool Next(int[] indices) {
    int currPos = 0;
    while (currPos < n) {
        indices[currPos]++;
        if (indices[currPos] < m)
            return true;
        indices[currPos] = 0;
        currPos++;
    }
    return false;
}

int[] indices = new int[n];
// initilialized with 0

do {
    outputSum(indices);
} while (Next(indices));

void outputSum(int[] indices) {
    for (int line = 0; line < n; line++) {
        if (line != 0) System.out.write(" + ");
        int col = indices[line];
        System.out.write(matrix[col][line]);
    }
    System.out.writeln();
}
1

реализовал следующим образом:

    /**
 * Find highest sums in jagged array
 * @param lists is a jagged array to be processed
 * @param n is a number of highest sums to be found
 * @return
 */
public List<Integer> findSums(int[][] lists, int n) {

    ArrayList<Integer> allSums = new ArrayList<Integer>();

    for (int i=0; (i<lists[0].length)&(i<n); i++)   // get the first list of elements of lists[][]; cut list to n size
        allSums.add(lists[0][i]);

    if (lists.length>1) {

         for (int r=1; r<lists.length; r++) {
             ArrayList<Integer> sums = new ArrayList<Integer>();
             for(int c=0; (c<lists[r].length)&(c<n); c++) {
                 sumElements(allSums,lists[r][c], sums);
             }

             sums = ArrayOperations.arraySortDescending(sums);
             allSums.clear();
             allSums.addAll(sums);  // store sorted sums into allSums list
             sums.clear();      // clear sums list              
         }

     } else {
            if (allSums.size()>n)
                allSums.subList(n, allSums.size()).clear();
     }

    return allSums;
}

/**
 * Count sums for every element in row with elements of previous row
 * @param array
 * @param nlv is the next list value
 * @param sums is a temporary storage for sums between two lists 
 */
private void sumElements(ArrayList<Integer> list, int nlv, ArrayList<Integer> sums) {
    for (int i=0; i<list.size(); i++) {
        sums.add(list.get(i) + nlv);
    }
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.