# Исправление ошибок в функции `maxpath` для нахождения максимальной суммы пути в треугольной матрице

Delphi , Синтаксис , Массивы

Исправление ошибок в функции maxpath для нахождения максимальной суммы пути в треугольной матрице

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

Описание проблемы

Проблема заключается в двух ошибках в коде функции maxpath. Первая ошибка связана с индексацией, где вместо использования переменной p используется p + 1. Однако, если внимательно подумать, можно заметить, что значение p переносится из предыдущей строки, и для каждой строки после первой p + 1 гарантированно определен. Это значит, что можно начать суммирование с первого элемента, переходя к второй строке и далее, и даже условие проверки на границы не потребуется.

Вторая ошибка менее значительна, но вычислять длину строки каждый раз не требуется. Длина строки всегда равна ее индексу (с учетом нулевого начала) плюс один, следовательно, можно сравнивать непосредственно с x.

Исправленный код

Вот как выглядит исправленный код:

def maxpath(triangle):
    p = 0
    total = triangle[0][0]
    for x in range(1, len(triangle)):
        if triangle[x][p] < triangle[x][p + 1]:
            p += 1
        total += triangle[x][p]
    return total

Дополнительно, можно еще больше оптимизировать функцию, убрав проверку x < p, так как это условие становится избыточным после первого исправления.

Пример работы функции

maxpath([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]) # Пример из сайта Euler

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

Заключение

В данной статье мы рассмотрели, как важно внимательно анализировать код, даже если на первый взгляд кажется, что все работает корректно. Небольшие ошибки в индексации и лишние проверки могут привести к некорректному результату работы функции. Использование Object Pascal (Delphi) для подобных задач также возможно, но для упрощения понимания примера был использован Python.

program MaxPath;
{$APPTYPE CONSOLE}
uses
  System.SysUtils;

function MaxPath(const Triangle: TArray<TArray<Integer>>): Integer;
var
  P, X: Integer;
  Total: Integer;
begin
  P := 0;
  Total := Triangle[0][0];
  for X := 1 to Length(Triangle) - 1 do
    if Triangle[X][P] < Triangle[X][P + 1] then
      Inc(P);
  for X := Length(Triangle) - 1 downto 1 do
    Total := Total + Triangle[X][P];
  Result := Total + Triangle[0][0]; // для первой строки, так как она не участвует в цикле выше
end;

var
  Triangle: TArray<TArray<Integer>>;
begin
  Triangle := TArray<TArray<Integer>>.Construct(4, Default<TArray<Integer>>);
  Triangle[0] := TArray<Integer>.Construct(1, 3);
  Triangle[1] := TArray<Integer>.Construct(2, 7, 4);
  Triangle[2] := TArray<Integer>.Construct(3, 2, 4, 6);
  Triangle[3] := TArray<Integer>.Construct(4, 8, 5, 9, 3);
  Writeln(MaxPath(Triangle));
  Readln;
end.

Приведенный выше код на Object Pascal (Delphi) демонстрирует, как можно реализовать функцию MaxPath для треугольной матрицы, аналогичную исправленному Python-варианту. Важно отметить, что для первой строки треугольника (которая не участвует в первом цикле) необходимо отдельно добавить ее элемент к итоговой сумме.

Создано по материалам из источника по ссылке.

Исправление ошибок в функции `maxpath` для нахождения максимальной суммы пути в треугольной матрице.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Массивы ::