0

Есть ли какой-то простой алгоритм нахождения: Максимума среди сумм элементов диагоналей, параллельных главной диагонали матрицы? На форуме смотрел темы, программы какие-то слишком сложные По условию: матрица целочисленная, n * n, у меня задан размер 4 * 4 Подскажите, пожалуйста, буду благодарен

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {


    }
}
3
  • Алгоритм простой и фактически буквально описан в самом задании: 1. Найти суммы, 2. Выбрать максимум. Ничего другого тут быть не может. 27 янв 2019 в 15:06
  • @AnT ну я не знаю как пройтись по параллельным диагоналями, поэтому и спросил
    – DGonzo
    27 янв 2019 в 16:16
  • Диагонали - это у которых и строка и столбец при переходе к следующей клетке увеличиваются на 1 :)
    – Mikhajlo
    28 янв 2019 в 11:28

1 ответ 1

2

Да при таком размере матрицы просто считайте все диагонали и не заморачивайтесь.

Все равно вам придется суммировать все элементы матрицы (не в одну сумму, понятно), так что меньше, чем O(N^2) вы все равно не получите. Больше тоже :)

Код примерно такой (v - матрица):

int max = v[0][N-1];
for(int k = -N+1; k < N; ++k)
{
    int sum = 0;
    for(int i = std::max(0,k), j = std::max(-k,0); j < std::min(N,N-k); i++, j++)
            sum += v[i][j];
    if (max < sum) max = sum;
}
cout << max << endl;
6
  • а можешь как-то упростить код, как-нибудь без длинного for? И можешь пояснить вкратце? Буду очень благодарен
    – DGonzo
    27 янв 2019 в 8:55
  • Это и так предельно упрощенный код. Разделите его на два цикла - для отрицательных k и для положительных - и посмотрите, как он работает (например, вместо sum += v[i][j]; выводите пары cout << " ("<<i<<","<<j<<")";) - и все станет понятно.
    – Harry
    27 янв 2019 в 9:49
  • а не подскажешь как решить проблема max и min не являются членов namespace std?
    – DGonzo
    27 янв 2019 в 16:10
  • #include <algorithm> или написать свои :)
    – Harry
    27 янв 2019 в 16:34
  • Да, спасибо) А зачем в программе находить мин и макс?
    – DGonzo
    27 янв 2019 в 19:21

Ваш ответ

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

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