Сумма элементов матрицы с заданной суммой индексов

      Комментарии к записи Сумма элементов матрицы с заданной суммой индексов отключены

Главная Форумы Программирование Помощь с решением задач на Prolog Задачи на списки Обработка матриц на Prolog Сумма элементов матрицы с заданной суммой индексов

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 10 мес. назад.

  • Автор
    Сообщения
  • #2016

    questioner
    Участник

    Нужно написать программу на Prolog:

    Матрица задается как список списков. Для данного натурального m ≤ n найти сумму тех элементов данной действительной квадратной матрицы порядка n, сумма индексов которых равна m.

    На рисунке показана такая матрица (в клетках записаны суммы индексов).

  • #2033

    Для решения задачи нам потребуется считать индексы, которым надо присвоить начальное значение – для этого можно написать вспомогательную функцию:

    sum_indexes(Matrix, SumIndexes, Sum):-
      sum_indexes(Matrix, SumIndexes, 0, 0, Sum).

    Начальное значение индексов равно нулю, т.к. для получения элементов матрицы используется стандартная функция nth0.

    Вычисление суммы должно заключаться в получении элемента с заданными индексами, рекурсивной обработке остальных элементов, соединении результатов. Это общий принцип “разделяй и властвуй”.

    sum_indexes(Matrix, SumIndexes, RowIndex, ColumnIndex, Sum):-
      get_matrix_element(Matrix, RowIndex, ColumnIndex, Element),
      tail_matrix_processing(Matrix, SumIndexes, RowIndex, ColumnIndex, TailSum),
      element_processing(SumIndexes, RowIndex, ColumnIndex, Element, TailSum, Sum).

    Функция получения элемента получает строку с заданным номером, в ней выделяет требуемый столбец. Правило может завершиться неудачей если переданы некорректные значения индексов.

    get_matrix_element(Matrix, RowIndex, ColumnIndex, Element):-
      nth0(RowIndex, Matrix, Row),
      nth0(ColumnIndex, Row, Element).

    В силу того, правило принимает те же значения, что и получает функция вычисления суммы – в этом случае логично завершить работу с ошибкой. Такая ситуация возникнет, например, при попытке обработки пустой матрицы.

    Обработка “хвоста” матрицы изменяет индексы и пытается выполнить рекурсивный вызов (используется косвенная рекурсия):

    tail_matrix_processing(Matrix, SumIndexes, RowIndex, ColumnIndex, Sum):-
      NextColumnIndex is ColumnIndex + 1, 
      sum_indexes(Matrix, SumIndexes, RowIndex, NextColumnIndex, Sum), !;
      NextRowIndex is RowIndex + 1, 
      sum_indexes(Matrix, SumIndexes, NextRowIndex, 0, Sum), !.
    tail_matrix_processing(_Matrix, _SumIndexes, _RowIndex, _ColumnIndex, 0).

    Если не удается обработать следующий элемент строки, то обработка переходит на следующую строку матрицы. Если строки матрицы закончились – то сумма необработанных элементов равна нулю.

    При соединении результатов необходимо проверить условие (сумму индексов) и на его основании либо добавить текущий элемент к результату рекурсивной обработки – либо нет:

    element_processing(SumIndexes, RowIndex, ColumnIndex, Element, TailSum, Sum):-
      SumIndexes is RowIndex + ColumnIndex, !, Sum is TailSum + Element.
    element_processing(_SumIndexes, _RowIndex, _ColumnIndex, _Element, TailSum, TailSum).

Для ответа в этой теме необходимо авторизоваться.