Задача, договор и доказательство решения

Сервис получает список заявок и должен найти первую заявку с нужным номером. В примере из пяти строк всё работает. На пустом списке программа паникует, а при двух одинаковых номерах возвращает случайный результат. Перед выбором алгоритма нужно определить, какой ответ вообще считается правильным.

Этот курс рассчитан на человека, который уже умеет писать функции, циклы, структуры и тесты на Go. Если эти конструкции пока незнакомы, сначала пройдите основы Go. Не нужны олимпиадный опыт или университетский курс математики. Нужны готовность пройти маленький пример руками и объяснить, почему следующий шаг сохраняет правильность.

Что будет результатом обучения

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

Важны четыре части каждого решения: договор входа и выхода, реализация, объяснение корректности, оценка времени и памяти. Код без последних двух частей ещё не показывает, что решение выдержит новый пример. А красивое доказательство без обработки пустого входа не спасает приложение.

Подготовка среды

Скачайте комплект лабораторий, распакуйте его в собственную папку. Нужен Go 1.22 или новее, внешние библиотеки не используются. Установку и базовый запуск показывает официальная инструкция Go.

go version
go test ./reference
go test ./exercises -run TestLowerBound

Первую команду выполняйте где угодно, следующие — в корне распакованного algorithm-labs. Эталонные тесты должны пройти. Тест упражнения в исходной заготовке завершается ошибкой implement LowerBound: эту функцию предстоит написать. Ошибка здесь ожидаема и не означает неисправную установку. Папка reference содержит открытый разбор; сначала попробуйте решить самостоятельно.

Формулируем договор

Пусть функция получает срез целых номеров и искомое число. Уточним: номера могут повторяться; список пока не отсортирован; ответ — индекс самого первого совпадения, отсутствие обозначается −1; функция не меняет вход. Для [7, 2, 7] и цели 7 ответ равен 0, для пустого среза — −1.

func FirstIndex(a []int, target int) int {
    for i, value := range a {
        if value == target { return i }
    }
    return -1
}

Это законченная функция, но не отдельная программа с main. Создайте файл first.go с package exercises в папке exercises и добавьте функцию. Файлы одного пакета Go собираются вместе. Для запуска отдельного примера понадобится package main, импорт fmt и main; не копируйте декларацию функции в терминал как shell-команду.

Почему цикл правильный

Перед каждой проверкой все элементы с индексом меньше i уже просмотрены и не равны цели. Это утверждение, сохраняющееся от шага к шагу, называют инвариантом цикла. До первого шага просмотренных элементов нет, поэтому утверждение верно. Если текущий элемент подходит, более раннего совпадения нет. Если не подходит, просмотренный префикс увеличивается на один элемент. Когда цикл закончился, просмотрен весь список.

Такое объяснение полезнее фразы «очевидно, цикл ищет». Оно отдельно показывает начальное состояние, сохранение свойства, смысл завершения. Далее мы будем применять те же вопросы к двоичному поиску, очереди обхода и таблице динамики.

Самостоятельная практика

Добавьте TestFirstIndex с пустым входом, одним совпадением, отсутствием и повторяющимися значениями. Затем измените договор: вернуть последний индекс. Сначала запишите, какое утверждение теперь должно быть верно после просмотра префикса; только затем меняйте код.

Критерии готовности: исходный срез не изменился; отрицательные числа допустимы; индекс не перепутан со значением; выбранное обозначение отсутствия одинаково во всех тестах. Время практики — около 25 минут.

Разбор

Для последнего индекса храните answer = -1 и обновляйте его при каждом совпадении. После просмотра префикса answer обозначает последнее совпадение в этом префиксе. Ранний возврат теперь нарушил бы договор. Сделайте контрпример [7, 2, 7]: оба решения находят значение, но только одно возвращает нужный индекс.

В следующей главе сравним, сколько действий требуют решения, когда данных становится больше. Методика курса опирается на открытые программы MIT 6.006 и Princeton Algorithms; задачи и объяснения здесь самостоятельные.