Подложка суммы матрицы путем рекурсии в C#
Я пытаюсь решить проблему без использования цикла, но не могу найти способ ...
Возьмем, например, этот массив: (предположим, что есть рандомизированные значения)
1, 2, 3, 4, 5
2, 3, 4, 5, 6
3, 4, 5, 6, 7
4, 5, 6, 7, 8
5, 6, 7, 8, 9
Отправив (строка: 2, столбец: 1), я хочу получить сумму:
1, 2
2, 3
3, 4
Я пишу эту функцию рекурсии, чтобы решить эту проблему:
static int Func(int[,] matrix, int row, int column)
{
if (row == -1 || column == -1)
return 0;
int result = 0;
for (int i = 0; i <= column; i++)
{
result += matrix[row, i];
}
return result + Func(matrix, row - 1, column);
}
Это работает, но я хочу заменить цикл дополнительным вызовом функции ...
@ pm100 Просто для обучения ...
Почему бы не изучить сценарии, в которых рекурсия действительно является правильным инструментом? Решение этой проблемы с помощью рекурсии не кажется даже хорошей идеей ...
ну, это не похоже на естественно рекурсивную вещь, если вы хотите научиться писать рекурсивные вещи, перейдите к более естественным рекурсивным операциям (факториал, фибрилляция, поиск по дереву, ...)
вам нужно добавить немного innerFunc(matrix, row, col, originalrow, originalcol) с еще двумя аргументами, которые будут охранять для column и row, и для каждого вызова рекурсии вы будете делать что-то вроде этого return matrx[row,col] + innerFunc(matrix, newrow, newcol, originalrow, originalcol) для newrow и newcol, вы решите, что изменить, на основе значений защиты
@InBetween Umm Я понимаю, но это возможно? (без изменения аргументов функции)
@ ЕгорЛебедев Спасибо, но я попросил решить эту проблему без изменения аргументов Func, я попытался проследить поток с множеством комбинаций, и я не могу найти решение.
Вы имеете в виду только рекурсивный вызов Func с его текущей подписью и при этом заставить его работать без каких-либо циклов? Я бы сказал нет, невозможно
Вы, кажется, тратите время на довольно бесполезную проблему. Это своего рода интернет-вызов или вы упрощаете реальную проблему, которую, кажется, собираетесь решить, и которая кажется излишне сложной?
@InBetween есть проблема в Интернете, возможно, я зря трачу время, но я еще этого не знаю, поэтому я прошу вас, ребята ...
Что ж, если есть проблема, то вполне вероятно, что есть решение, но, честно говоря, есть лучшие способы потратить время на обучение, чем пытаться решить эту. Но удачи.
@Hazan: можно ли использовать вторичную функцию для решения этой проблемы или ее следует решить с помощью только одной функции?
Ответы 1
Вы всегда можете попробовать упростить такие рекурсии, подумав о функциях, которые обрабатывать одну запись, а затем оставьте остальные записи равными обрабатывается следующим рекурсивным вызовом.
Основная идея, которая может решить ваш случай: попробуйте суммировать числа от правого нижнего угла к верхнему левому углу матрицы (таким образом вы можете использовать отрицательные индексы для строк / столбцов, чтобы проверить, когда вы достигли границ матрицы).
Итак, в вашем конкретном случае есть три ключевых момента в этой идее:
- (A) Функция должна возвращать число, расположенное в данной позиции (строка, столбец) матрицы, плюс сумму последовательности, начинающейся с следующий номер в суммирующей последовательности: то есть сумма (строка, столбец) = мат [строка, столбец] + сумма (строка, столбец-1).
- (B) Выполняя (A) рекурсивный вызов несколько раз, в какой-то момент столбец будет отрицательным ... Когда это произойдет, мы должны перейти к строке выше текущей обрабатываемой строки и просуммировать все столбцы в этой строке. линия.
- (C) В какой-то момент вся матрица будет просуммирована, и число ряд станет отрицательным. Это когда алгоритму необходимо завершить рекурсию, поскольку программа вычислила все входные данные, необходимые для вычисления.
Итак, вы можете написать это так:
static int Func(int[,] matrix, int row, int column, int maxColumn)
{
// (C) All rows have been processed successfully: stop the recursion.
if (row < 0)
return 0;
// (B) All columns in the current line have been processed: go to the next row
// which you need to sum
if (column < 0)
return Func(matrix, row - 1, maxColumn, maxColumn);
// (A) The basic definition of your recursion
return matrix[row, column] + Func(matrix, row, column - 1, maxColumn);
}
В вашем примере ввода вы можете просто назвать это как:
Func(yourMatrix, 2, 1, 1);
Обратите внимание, что для того, чтобы этот алгоритм работал, вам необходимо передать дополнительную переменную maxColumn, чтобы функция знала номер столбца, который она должна использовать при переходе к следующей строке, которую необходимо обработать. Очевидно, что параметры maxColumn и column всегда должны быть равны при первом вызове функции Func().
OP заявляет в комментариях, что изменение подписи метода не является вариантом.
@InBetween Я вижу, я только что прочитал ваши комментарии по этому поводу, и я также думаю, что это невозможно, по крайней мере, с дополнительным аргументом, так как функция должна знать, к какой строке или столбцу она должна вернуться во время рекурсии
мы можем спросить почему?