Задача - это вход и требование к выходу

Что такое алгоритм, разобрала первая глава. Эта начинается с того, что алгоритм должен сделать. Причина простая: почти все споры «работает или не работает» на самом деле споры о том, что именно требовалось. Пока требование не записано, проверить программу нечем, и доказать про неё тоже нечего.

Как думаешь, что здесь непонятно

«Найди максимум в списке чисел». Формулировка кажется исчерпывающей. На самом деле она не отвечает на четыре вопроса:

• что вернуть, если список пуст;
• вернуть само число или его номер;
• если максимумов два, какой из них считается ответом;
• гарантируется ли, что числа целые.

Четыре программы, отвечающие на эти вопросы по-разному, будут одинаково «правильно находить максимум» и при этом давать разные ответы на одном и том же входе. Спор между их авторами неразрешим, потому что спорят они не о коде.

Спецификация: три части

Задача - это описание того, какой выход считается верным для каждого допустимого входа. Записывается она тремя частями:

• вход и предусловие - что подаётся и что про это гарантируется;
• выход - что требуется вернуть;
• постусловие - какое свойство связывает выход со входом.

Для максимума это выглядит так:

вход:          список a из n чисел
предусловие:   n ≥ 1, элементы - числа (целые или дробные)
выход:         индекс i
постусловие:   0 ≤ i < n и a[i] ≥ a[j] для всех j, 0 ≤ j < n

Спецификация тут сняла все четыре вопроса из начала урока, и каждый - своей частью: пустой список запретило предусловие (n ≥ 1), «число или номер» решил выход (индекс), вопрос о целых снят предусловием - годятся любые числа, а свободу при равных максимумах оставило постусловие - подойдёт любой из них. Свобода в постусловии это не небрежность, а решение: чем оно слабее, тем больше программ его выполняют.

Экземпляр задачи - это один конкретный вход. Задача «отсортировать список» одна, а экземпляров у неё бесконечно много, и алгоритм обязан справляться с каждым, а не с тем, на котором его проверяли.

Разбор: одна задача, два алгоритма

Постусловие ничего не говорит о способе. Максимум можно искать одним проходом:

a = [3, 8, 5, 8]
luchshij = 0
for i in range(1, len(a)):
    if a[i] > a[luchshij]:
        luchshij = i
print(luchshij)

А можно перебором пар: для каждого i проверить, не больше ли его кто-нибудь. Оба выполняют постусловие, то есть оба решают задачу. Различаются они только ценой: первый делает n-1 сравнений, второй - около n². Задача не выбирает между ними; выбирать будем мы, и в следующем разделе появится инструмент, которым это делают.

Разбор: спецификация, которая пропускает мусор

Вот постусловие, которое выглядит верным, но задачу «отсортировать» не описывает:

выход: список b, в котором b[0] ≤ b[1] ≤ ... ≤ b[n-1]

Ему удовлетворяет программа, возвращающая на любом входе список из n нулей: на [5, 3, 1, 4, 2] она вернёт [0, 0, 0, 0, 0]. Упорядоченность есть, а исходных чисел нет. Не хватает второго требования:

и b - перестановка a

Такой пропуск - самая частая ошибка в постановке задачи: описано желаемое свойство результата и забыта его связь со входом. Проверять программу по дырявой спецификации бесполезно: она честно пройдёт проверку и честно окажется бесполезной.

Зачем это в работе

Тестовый набор - это спецификация, записанная примерами, и примеров всегда меньше, чем случаев. Когда сформулировано предусловие («на вход приходит непустой список»), становится видно, кто отвечает за его выполнение: вызывающий или сама функция. Когда сформулировано постусловие, появляется, что писать в проверке и о чём спорить на ревью.

Теперь сам

Запиши спецификацию для задачи «в отсортированном списке a найти, сколько раз встречается число x». Что попадёт в предусловие, а что в постусловие?