Алгоритмы и псевдокод

Самый дорогой дефис в истории

• 22 июля 1962 года ракета Mariner 1, летевшая к Венере, была уничтожена через 293 секунды после запуска.
• Причиной стал один пропущенный знак над символом в уравнениях навигации. Компьютер точно следовал написанным инструкциям, а написанные инструкции были неверны.
• Компьютер никогда не додумывает за вас. Каждый шаг, который вы ему даете, должен иметь ровно одно значение.
• Именно поэтому этот урок посвящен написанию шагов, которым может следовать машина: алгоритмам.

Что такое алгоритм

• Алгоритм — это решение проблемы, выраженное в виде последовательности определенных шагов.
• Каждый шаг однозначен (имеет одно значение), детерминирован (одинаковый вход → одинаковый выход), конечен (шаги заканчиваются) и эффективен (каждый шаг реально выполним).
• Он говорит что делать, независимо от языка программирования, и каждый следует схеме вход → обработка → выход.

У каждого алгоритма одна и та же структура: вход, обработка, выход

Разобранный пример: таблица идентификаторов

*Таблица идентификаторов называет все элементы данных перед написанием кода

Три конструкции

IF … THEN … ELSE … ENDIF

• Присваивание сохраняет значение со стрелкой, Total ← Total + Value; = используется для сравнения. DIV — целочисленное деление, а MOD — остаток, поэтому 17 MOD 5 = 2.

INPUT Age                      # sequence
IF Age >= 18 THEN
    # selection
ENDIF
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF
FOR Count <- 1 TO 10           # iteration
    OUTPUT Count
NEXT Count

*Три строительных блока любого алгоритма

Какой цикл?

• FOR … NEXT когда вы знаете, сколько раз повторять: петля с управляемым счетчиком.
• WHILE … ENDWHILE проверяет условие перед каждой итерацией, поэтому тело может выполниться ноль раз: петля с предусловием.
• REPEAT … UNTIL проверяет после каждой итерации, поэтому тело всегда выполняется как минимум один раз: петля с постусловием. Валидация ввода — классический случай.
• Ответ «опишите конструкцию итерации» должен называть петлю, указывать где проверяется условие и приводить последствия.

*Цикл WHILE проверяет до выполнения тела; цикл REPEAT … UNTIL проверяет после него

Разобранный пример: от слов к псевдокоду

DECLARE Count, Total, NextNumber : INTEGER
Total <- 0
FOR Count <- 1 TO 100
    INPUT NextNumber
    IF NextNumber > 0 THEN
        Total <- Total + NextNumber
    ENDIF
NEXT Count
OUTPUT Total

Распознавание конструкций в отрывке

• Любимый вопрос показывает пять отрывков псевдокода и просит отметить, какую из присваивания, выбора, итерации использует каждый.
• Result ← CalculateTotal() — это присваивание. WHILE IsClosed — это итерация. REPEAT … INPUT Value … UNTIL Sales[4] > Value — это итерация и присваивание (INPUT сохраняет значение). IF Sales[Current] <= 150 THEN Discount ← TRUE ENDIF
• Смотрите на каждую строку отрывка, а не только на первую. Строка может требовать двух отметок.

Блок-схемы

• Блок-схема иллюстрирует тот же алгоритм, что и псевдокод. Овалы обозначают START и END, прямоугольники — процессы, параллелограммы — INPUT/OUTPUT, а ромб — условие выбора.
• Ромб используется для выбора (условия), а линия потока, идущая вверх по схеме, обозначает цикл.
• На экзамене встречаются оба формата: псевдокод по блок-схеме и блок-схема по псевдокоду или структурированному английскому языку. Каждый нарисованный вами символ должен соответствовать одной строке псевдокода.

Каждый символ блок-схемы соответствует одному типу оператора псевдокода

Разбор примера: игра в угадайку

DECLARE Target, Guess : INTEGER
Target <- INT(RAND(100)) + 1
REPEAT
    INPUT Guess
    IF Guess < Target THEN
        OUTPUT "Too low"
    ELSE
        IF Guess > Target THEN
            OUTPUT "Too high"
        ENDIF
    ENDIF
UNTIL Guess = Target
OUTPUT "Correct"

Игра в угадайку как блок-схема: цикл возвращается к вводу до тех пор, пока попытка не совпадет с ответом

Пошаговое уточнение

• Пошаговое уточнение означает начало с общего плана и последовательную детализацию каждого шага до более мелких действий снова и снова, пока каждый шаг не можно будет записать напрямую в виде псевдокода.
• «Обработать заказ» → «Получить товары», «Рассчитать итоговую сумму», «Принять оплату» → «Рассчитать итоговую сумму» превращается в «Для каждого товара добавьте цену × количество; примените скидку, если есть».
• Каждый уровень является уточнением предыдущего, и законченные уровни вместе составляют проект. Задание «Опишите пошаговое уточнение» требует изложения плана, его детализации и правила остановки.

Уточняйте каждый шаг до состояния, когда его можно закодировать напрямую

Логические выражения

• Части решения определяются логическими выражениями: условиями, построенными из сравнений (=, <>, <, >, <=, >=), соединенных операторами AND, OR и NOT.
• Пример корректной оценки: Mark >= 0 AND Mark <= 100. Скидка применяется, если клиент является членом клуба или тратит более 50: IsMember OR Total > 50.
• NOT (Mark < 40) означает то же самое, что и Mark >= 40. Запишите выражение, а затем протестируйте его со значениями с обеих сторон границы.

Сравнения, соединенные через AND, OR и NOT, образуют условия, необходимые алгоритму

Потерянные баллы

Вы поняли