Вопросы по алгоритмам
SPL:
Здравствуйте) Уже довольно долго не могу сдать лабу из-за того что не получается выполнить задание) В моей программе (на Си) необходимо написать функцию, которая определяет сумму всех элементов подматрицы с большей суммой элементов на периметре. Матрица квадратная, динамическая.
Никак не могу придумать алгоритм. Мб у кого-то есть идеи - буду благодарен)
Артем:
А подматрицы должны выделятся как на рис.1 или как на рис.2 ? Подматрицы тоже должны быть квадратными ?
SPL:
Вершины должны лежать на диагонали и антидиагонали, т.е. как на рисунке 1, тоже должны быть квадратными)
Артем:
1) Определяем сколько у нас должно быть подматриц:
2x2, 3x3 - 1 подматрица
4x4, 5x5 - 2 п.
6x6, 7x7 - 3 п.
Код:
int size, submatrix;
// ввод размерности матрицы и выделение памяти
submatrix = size / 2; // дробная часть если и будет, то отбросится и получится целое кол-во подматриц
2) Для того чтобы выделять подматрицы введем переменные, которые будут хранить индексы по периметру:
Код:
int left, top, right, bottom;
Также введем переменные, которые будут хранить индексы для подматрицы с максимальной суммой элементов по периметру:
Код:
int max_left, max_top, max_right, max_bottom;
3) Ищем подматрицу с максимальной суммой элементов по периметру. В коде нужно будет использовать индексацию массива через указатель *(A+i*n+j), так как память выделялась через одинарный указатель и обычная индексация A[ i ][ j ] вызовет ошибку компиляции. Но для лучшей читабельности кода и поонятности алгоритма, я решил оставить вариант с A[ i ][ j ].
Код:
int i, j, sub, sum, max_sum = -1000;
max_left = left = 0;
max_top = top = 0;
max_right = right = size-1;
max_bottom = bottom = size-1;
for(sub=0; sub<submatrix; sub++)
{
sum = 0;
for(i=top; i<=bottom; i++)
sum += a[i][left] + a[i][right];
for(i=left+1; i<right; i++)
sum += a[top][i] + a[bottom][i];
if(sum > max_sum)
{
max_left = left;
max_top = top;
max_right = right;
max_bottom = bottom;
max_sum = sum;
}
left ++;
top++;
right--;
bottom--;
}
Ну а дальше, зная крайние индексы подматрицы с максимальной суммой элементов по периметру, уже не составит труда найти сумму элементов этой подматрицы. Желаю удачи ! :)
ЗЫ: работоспособность кода я конечно же не проверял, но думаю логика программы правильная)))
SPL:
Оргомное спасибо :) Разобрался, лаба сделана и работает, даже правильно :)
Навигация