Подматрица с наименьшим средним

Question

поэтому у меня есть это школьное задание Мне нужна помощь.

Мне нужно написать программу, которая позволит вводить двумерную матрицу и выводить, какая из подматриц имеет наименьшее среднее значение. Так, например, этот 4x4 matrix

four 3x3 matrices содержит

и для каждого из этих подматриц я должен вычислить среднее, и выход наименьшее среднее значение. Итак, в моем примере средние значения подматриц составляют 5,6,9,10, а выход будет равен 5.

Вход в программу выглядит следующим образом: количество строк, количество столбцов, размеры подматрицы , и матричные значения. Так, например, если я введу 2 в размерах подматрицы, мне нужно будет найти наименьшее среднее значение всех подматриц 2x2 и распечатать его. Теперь я знаю, как вводить и заполнять матрицу числами, вычислять средние значения, сравнивать их и распечатывать самые маленькие, однако я не могу придумать способ найти все подматрицы заданного размера, а я Там было что-то похожее.

Answer 1

Скажем, ваша большая матрица M имеет R ряды и C столбцы. Вы хотите найти все подкатегории Mm0, m1, m2, ... которые имеют r ряды и c столбцы. (Предположим, что c <= C && r <= R).

Если вы сделаете это вручную, как вы это сделаете? Вы начинаете с матрицы r x c в левом верхнем углу, затем перемещаетесь вправо на 1 столбец и продолжаете двигаться, пока не дойдете до конца. Затем вы переходите к следующей строке и повторяете. Вы переходите к следующей строке, пока ваши подматрицы не достигнут дна.

Практически достаточно вычислить позиции возможных левых верхних углов ваших подматриц. Таким образом, учитывая приведенные выше цифры:

for(int row = 0; row < (R - r + 1); row++) { 
    for(int col = 0; col < (C - c + 1); col++) { 
     // left top corner is at [row,col] 
     // access your submatrix and calculate your average 
    } 
} 

Обратите внимание, что вы не перебирать в R (или C), потому что для последнего действительного левого верхнего угла точки, подматрица (будучи r x c размера) по-прежнему необходимо, чтобы вписаться в вашей матрицы. Но левый верхний угол «находится» в подматрице, следовательно, +1.

Answer 2

Поскольку это домашнее задание, я не думаю, что вы выиграете, если я это выработаю для вас. Вместо этого я предлагаю вам сделать это следующим образом:

Обратите внимание, что n представляет длину матрицы. В этом случае n равно 3. Числа на сторонах - это индексы. Вычеркивание этого должно помочь выяснить показатели подматриц. Если вы работаете с 4x4 и 5x5, вы можете увидеть шаблон и написать обобщенный алгоритм.