Суммировать целые числа в 2d массиве с помощью рекурсии?

Question

Мне нужна помощь с этой проблемой. Я должен сложить все целые числа в 2d массиве с помощью рекурсии. Ниже то, что мне удалось сделать самостоятельно, но я застрял. Этот код генерирует сумму 14, которая должна быть 18.

public class tablerecursion {
    public static void main(String[] args) {
        int[][] tabell = new int[][] { { 1, 2, 3 }, { 3, 2, 1 }, { 1, 2, 3 } };
        int sum = rec(tabell, 2, 2);
        System.out.println(sum);
    }

    static int rec(int[][] table, int n, int m) {
        if (m == 0)
            return table[n][0];
        if (n == 0)
            return table[0][m];
        System.out.println("n:" + n + "  m:" + m);

        return rec(table, n - 1, m) + rec(table, n, m - 1);
    }
}

Есть предложения? Базовый случай не так? Или рекурсивный метод неправильный?

Answer 1

Я бы решил это, используя две функции.Сначала создайте функцию, которая может рекурсивно суммировать один (1d) массив.Функция write, которая рекурсивно суммирует предыдущую функцию по внешнему массиву.

Помните, что таблица [N] сама по себе является массивом.Вам не нужно обращаться ко всему этому за один раз.

Answer 2

Ваша логика рекурсии неверна.

Вы получаете 14, потому что вы звоните

f (2,2) = f (2,1) + f (1,2) = (f(2,0) + f (1,1)) + (f (1,1) + f (0,2))

f (0,2) - ваш базовый случай, 3 f (0), 2) ваш базовый случай, 1 f (1,1) = f (0,1) + f (1,0) = 2 + 3 = 5

Таким образом, сумма составляет 3 + 1 + 5+ 5 = 14

Правильная логика для рекурсивного преобразования: одна рекурсивная функция:

Сумма массива 2x2, начинающаяся с координат (x, y) иокончание (z, w) представляет собой сумму из 3 вещей:

  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  yyyyyyyyyN

• Сумма массива, состоящего из ВСЕХ строк, кроме последней (в примере xxxx-s)выше) Так (x, y) - (z, 2-1).

• Сумма массива, состоящего из строки LAST (кроме правого нижнего угла - yyyyy-s в примере)Итак, (x, w) - (z-1, w)

• Число в координатах (z, w)

• базовые случаи: если y> w (ноль строк), сумма равна нулю;если x

Это действительно ДВОЙНАЯ рекурсия, в идеале .Одним из них является рекурсивное вычисление суммы всех строк с помощью вспомогательной функции «добавить строку», которая, конечно, также рекурсивно реализуется.

Answer 3

public int sumarmatriz(int matriz[][],int i,int j)
{
    if(i==0 && j==0){
        return matriz[i][j];
    }
    else if(j==0){
        return sumarmatriz(matriz,i-1,matriz.length-1)+matriz[i][j];
    }
    else{
        return sumarmatriz(matriz,i,j-1)+matriz[i][j];
    }
}

Answer 4

Вот пример возможного решения. Если бы Java-компилятор мог оптимизировать хвостовую рекурсию , то это было бы так же эффективно, как итеративное решение. Теперь он очень агрессивно ест стэк.

public static long countSum (int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    return countSum (matrix, 0, 0, 0, matrix.length, matrix[0].length);
}

private static long countSum (int[][] matrix, long acc, int curI, int curJ, int maxI, int maxJ) {
    if (curI >= maxI) {
        return acc;
    }
    if (curJ >= maxJ) {
        return countSum(matrix, acc, curI + 1, 0, maxI, maxJ);
    }
    return countSum(matrix, acc + matrix[curI][curJ], curI, curJ + 1, maxI, maxJ);

}

Answer 5

Посмотрите, вот что я хотел бы отметить, и укажите, что рекурсивное решение не применимо:

public static void Main()
{
        var a = new int[][] {  new int[] {1,2,3},
                               new int[] {3,2,1},
                               new int[] {1,2,3}  }; 
        int result = a.Sum(row => row.Sum());
        Console.WriteLine(result);
}

Лучше быть правым, чем просто считаться правильным.

Answer 6

Несколько других ответов предлагают использовать 1D процедуру для суммирования столбца и строки, смежной с элементом в углу 2D-массива

НО

Это было бы так же верноразрезать 2D-массив на четыре меньшие 2D-массивы и выполнить рекурсивный анализ.Условие остановки, конечно, когда вход представляет собой двумерный массив 1x1, где ответ тривиален.

продолжение

Это приводит к затруднению, если только размеры массива2 ^ mx 2 ^ m;Что-нибудь еще, и рано или поздно вы встретите вход Nx1 или 1xN, и вы просто не сможете разрезать это на четыре подмассива.Таким образом, вам все равно придется иметь дело с 1D-вводом.