Форум » Обработка числовых последовательностей » №4848 (27.93) ошибка в решении » Ответить
№4848 (27.93) ошибка в решении
beep: Здравствуйте. В решении Д. Муфаззалова (27-93 mufazzalov.py) есть ошибка в логике. Дело в том, что current_min вычисляется с запозданием на один шаг, поэтому получается 2 варианта проблем. Первый вариант, это когда минимальный хвост подсчитывается неверно и берется предпоследнее минимальное значение: Данные [pre2] 5 3 -3 -1 -3 -3 -3 [/pre2] Ответ будет - 10, а правильный -9. Проблема в том, что минимум для первого отрезка {-3, -1} вычислится как -3, а не -4, ведь current_min отстает на шаг и если нужный шаг стоит рядом с магическим числом, то алгоритм просто не успевает проверить последний вариант current_sub_sum. Второй вариант проблем заключается в том, что по дефолту для current_min задается значение 0 для каждой новой итерации и если магические числа будут стоять рядом, то из-за того, что current_min запаздывает на шаг, в current_min не будет попадать начало отрезка с магическим числом и значение current_min так и будет оставаться равным нулю. Тогда для данных [pre2] 5 3 -10 -3 -3 -3 -3 [/pre2] ответ будет -12, а правильный -9. Происходит это потому, что current_min из-за отставания на шаг не успевает обновиться и вместо 3 магических чисел на отрезке у нас получается 4 магических числа - хвост, который каждый раз должен содержать магическое число, это магическое число не содержит, потому что не успевает обновиться.
Ответов - 2
beep: ап
Поляков: Спасибо, автор обновил свое решение.
полная версия страницы