Обозначения, пошаговая декомпозиция и логика
| English | Русский |
|---|---|
| notation/nəʊˈteɪʃn/ | нотация |
| structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ | структурированный английский |
| pseudocode/ˈsuːdəʊkəʊd/ | псевдокод |
| flowchart/ˈfləʊtʃɑːt/ | блок-схема |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | пошаговое уточнение |
| logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ | логическое выражение |
| Boolean/ˈbuːlɪən/ | Boolean |
| precedence/ˈpresɪdəns/ | приоритет |
| De Morgan's law/də ˈmɔːɡənz lɔː/ | закон де Моргана |
Первый алгоритм не имел языка программирования для записи
- В 1843 году Ада Лавлейс опубликовала шаги вычисления чисел Бернулли на аналитической машине Бэббиджа, которая так и не была построена.
- Поскольку языка программирования не существовало, она записала алгоритм в виде нумерованной таблицы операций: собственной нотации.
- Любой алгоритм по-прежнему начинается таким образом. Вы записываете его в некоторой нотации, проверяете и только затем преобразуете в код.
- Этот урок посвящен трем нотациям, используемым на экзамене, способам перехода между ними и написанию условий внутри них.
Три нотации
- Структурированный английский язык: обычные предложения с отступами и несколькими фиксированными словами, такими как
IF,FOR EACH,REPEAT. Подходит для первого наброска. - Псевдокод: нотация ключевых слов (
IF … ENDIF,WHILE … ENDWHILE,FOR … NEXT), наиболее близкая к реальному коду и оцениваемая согласно руководству Cambridge. - Блок-схема: диаграмма стандартных фигур. Овальная рамка для
START/STOP, параллелограмм для ввода и вывода, прямоугольник для процесса, ромб для принятия решения, стрелки для потока.
Блок-схема усреднения списка чисел, нарисованная с использованием стандартных фигур
В блок-схеме какая фигура обозначает принятие решения?
Ромб — это принятие решения; скругленный прямоугольник = начало/конец, параллелограмм = ввод/вывод, прямоугольник = процесс.
Сопоставьте каждую фигуру блок-схемы с её значением.
Параллелограмм = ввод/вывод, прямоугольник = процесс, скругленный прямоугольник = начало/конец, ромб = принятие решения.
Сопоставьте каждое обозначение с его описанием.
Все три описывают один и тот же алгоритм на разных расстояниях от кода.
Разбор примера: структурированный английский язык в псевдокод
- Структурированный английский язык: Задайте итоговой сумме значение нуля. Для каждого из N чисел добавьте его к итоговой сумме. Разделите итоговую сумму на N и выведите результат.
- Каждое предложение становится одной конструкцией: оператор присваивания, цикл
FORс оператором присваивания внутри него, затем оператор присваивания и вывод.
Total <- 0
FOR Index <- 1 TO N
Total <- Total + Number[Index]
NEXT Index
Average <- Total / N
OUTPUT Average
- Порядок предложений соответствует порядку операторов. Ничего не добавляется и ничего не пропускается.
В алгоритме усреднения цикл FOR, который добавляет каждое число к общей сумме, является примером конструкта ____.
Повторение блока для каждого числа — это итерация. Присваивание внутри него сохраняет текущую сумму.
Разбор примера: псевдокод в блок-схему
- Возьмите тот же алгоритм.
STARTпомещается в закругленный прямоугольник,Total ← 0иIndex ← 1— в прямоугольники. - Цикл
FORпреобразуется в ромб, содержащий проверкуIndex <= N?. Выход Да ведет к прямоугольникуTotal ← Total + Number[Index], затем кIndex ← Index + 1, и стрелка возвращается вверх к ромбу. - Выход Нет продолжается к
Average ← Total / N, параллелограмму вывода иSTOP. - Подпишите оба выхода каждого ромба. Ромб с одним неподписанным выходом не является элементом принятия решений.
Пошаговое уточнение
- Поэтапная детализация означает написание алгоритма в виде краткого плана, затем расширение каждого шага на более подробные подшаги и повторение этого процесса до тех пор, пока каждый шаг нельзя будет напрямую закодировать.
- Каждый уровень сохраняет структуру предыдущего уровня и добавляет детали. План не выбрасывается: он становится структурой программы.
- Проектирование прекращается, когда шаг представляет собой одну строку псевдокода или один модуль, который у вас уже есть.
Поэтапная детализация расширяет каждый шаг до состояния, когда его можно закодировать
Постепенное уточнение — это техника:
Вы уточняете высокоуровневый план уровень за уровнем, добавляя детали, сохраняя при этом структуру.
Разбор примера: три уровня
- Уровень 1: Обработать результаты экзамена.
- Уровень 2: Ввести каждую оценку. Вычислить среднее. Подсчитать количество сдавших. Вывести отчет.
- Уровень 3, уточнение «подсчитать количество сдавших»:
Passes ← 0, затем для каждой оценкиFOR,IF Mark >= 40 THEN Passes ← Passes + 1. - На вопрос «опишите поэтапную детализацию» ответьте тремя идеями: начните с плана, расширьте каждый шаг на более мелкие шаги, остановитесь, когда каждый шаг можно запрограммировать.
Пошаговая декомпозиция: от плана коду
Спускайтесь по уровням. Вы начинаете со всей задачи в одной строке и постоянно расширяете каждый шаг на меньшие — пока каждый шаг не станет простым для прямого кодирования.
При постепенном уточнении каждый новый уровень заменяет предыдущий, поэтому исходный план отбрасывается.
Каждый уровень сохраняет структуру вышестоящего и добавляет детали. План становится формой готовой программы.
Логические выражения
- Логическое выражение — это булево условие: оно может принимать значение
TRUEилиFALSE, и управляет цикломIF, условным операторомWHILEили структурой данныхUNTIL. - Оно строится из сравнений (
=,<>,<,>,<=,>=), соединенных логическими операторамиAND,ORиNOT. Mark >= 0 AND Mark <= 100истинно только для оценок в заданном диапазоне.Age < 12 OR Age >= 65истинно для детей и пенсионеров.
Сравнения, соединенные AND, OR и NOT, образуют одно условие
Приоритетность и скобки
- Операторы применяются в фиксированном порядке приоритетности: сначала
NOT, затемAND, затемOR. - Поэтому
A OR B AND CозначаетA OR (B AND C), а не(A OR B) AND C. Для выражений со скобкамиA = TRUE,B = FALSE,C = FALSEпервое значение равноTRUE, а второе —FALSE. - Используйте скобки, когда условие сочетает
ANDиOR. Они ничего не стоят и устраняют неоднозначность.
Расставьте логические операторы по приоритету, от наивысшего (вычисляется первым) к наименьшему.
NOT связывает сильнее всего, затем AND, затем OR — используйте скобки при сомнениях.
Без скобок, что означает A OR B AND C?
AND имеет приоритет выше, чем OR, поэтому он вычисляется первым. Тем не менее обведите условие в скобки, чтобы никто не забыл.
Законы де Моргана
- Закон де Моргана:
NOT (A AND B)эквивалентно(NOT A) OR (NOT B), аNOT (A OR B)эквивалентно(NOT A) AND (NOT B). - Простыми словами: «не (зарегистрирован и оплатил)» означает «не зарегистрирован или не оплатил».
- Используйте его для упрощения условия или проверки: выберите значения для
AиB, вычислите обе стороны, и они должны совпадать во всех случаях.
По закону де Моргана, NOT (A AND B) эквивалентен (NOT A) OR (NOT B).
NOT применяется к содержимому скобок и меняет AND↔OR; аналогично NOT (A OR B) = (NOT A) AND (NOT B).
Разбор примера: условие из словесного описания
- Правило: студент может сдать экзамен, если он зарегистрирован и либо оплатил, либо имеет стипендию, но не если он отстранен.
- Назовите булевы переменные:
Registered,Paid,Bursary,Suspended. - Условие:
Registered AND (Paid OR Bursary) AND NOT Suspended. - Скобки вокруг
Paid OR Bursaryобязательны. Без них приоритетный операторANDприменится первым, и студент со стипендией, но без регистрации, был бы допущен.
Какие условия эквивалентны NOT (Registered AND Paid)? Выберите все подходящие варианты.
Закон де Моргана превращает NOT от AND в OR от отрицаний. Версия с AND слишком строгая: студент, который зарегистрирован, но не оплатил, должен делать исходное условие TRUE, а версия с AND делает его FALSE.
Потерянные баллы
a = 1 OR 2не является условием. Запишитеa = 1 OR a = 2: каждая сторонаORдолжна быть полным сравнением.NOTприменяется только к следующему за ним элементу.NOT A AND Bозначает(NOT A) AND B.- Ромб требует двух подписанных выходов, а цикл — стрелки, ведущей вверх. Блок-схема без стрелки возврата не является циклом.
- Структурированный английский все еще точен. «Обработать оценки» — не шаг; «добавить оценку к общей сумме» — да.
Чтобы проверить, является ли a равным 1 или 2, правильное условие выглядит так:
Каждая часть операции OR должна быть полным сравнением: a = 1 OR a = 2. Запись a = 1 OR 2 является распространенной ошибкой.
Вы поняли
- Три нотации для одного алгоритма: структурированный английский, псевдокод, блок-схема (ромб = решение, стрелка назад = цикл).
- поэтапная детализация: план → расширение каждого шага → остановка, когда шаг можно закодировать
- логическое выражение — это булево условие; приоритетность NOT → AND → OR, поэтому берите скобками всё, что их смешивает
- де Морган:
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B