| Кандидаты должны уметь: | Примечания и рекомендации |
|---|---|
| Проявить понимание абстракции | Необходимость и преимущества использования абстракции Описать цель абстракции Создать абстрактную модель системы, включив только существенные детали |
| Описать и использовать декомпозицию | Разбивать задачи на подзадачи, ведущие к понятию модуля программы (процедура / функция) |
Проектирование алгоритмов и решение задач
A-Level Computer Science · Тема 9
14:28
Вычислительное мышление
Вот задача: создать систему для управления всем складом магазина — каждым товаром, каждой продажей, каждой поставкой, каждым отчетом. Как одна огромная проблема, она слишком велика, чтобы…
English narration · English and 中文 subtitles you can switch
9.1
Вычислительное мышление
Программа
Источник: Программа Cambridge International
Вычислительное мышление — это набор ментальных инструментов для анализа проблемы и проектирования решения, которое может выполнить компьютер. Два ключевых из них — абстракция и декомпозиция.

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

Декомпозиция
Декомпозиция означает разбиение большой задачи на более мелкие подзадачи, каждую из которых проще решить, и решение их по очереди.
- найдите основные части задачи.
- разбейте каждую на более мелкие подзадачи.
- продолжайте, пока каждая не станет достаточно маленькой для непосредственного проектирования.
- решите мелкие задачи и объедините результаты.
Для контроля запасов: "управление запасами" → "фиксация продаж", "фиксация поставок", "составление отчетов" → ("фиксация продаж") "поиск товара", "уменьшение количества товара", "сохранение транзакции". Декомпозиция делает большие задачи выполнимыми, позволяет команде разделить работу и дает модульный код — каждый модуль становится процедурой или функцией.
Вопрос "Объясните, почему используется декомпозиция" имеет фиксированную структуру и оценивается в три балла. Назовите три отдельных преимущества: каждая подзадача настолько мала, что ее можно спроектировать, закодировать и протестировать отдельно; разные программисты могут работать над разными модулями одновременно; существующий модуль (или библиотечная процедура) можно переиспользовать, а ошибку легче найти, так как она находится внутри одного модуля. Структурная схема (тема 12) — это диаграмма декомпозиции: программа сверху, её модули снизу и данные, передаваемые между ними.

Решение задачи вычислительным способом
Пройдите через четыре основы в том порядке, в каком их следует применять — разбейте задачу на части, найдите повторяющиеся элементы, отбросьте несущественное, затем запишите шаги.
| English | Русский |
|---|---|
| computational thinking/ˌkɒmpjuːˈteɪʃənl ˈθɪŋkɪŋ/ | computational thinking |
| abstraction/əbˈstrækʃn/ | abstraction |
| decomposition/ˌdiːkɒmpəˈzɪʃn/ | decomposition |
| sub-problem/sʌb ˈprɒbləm/ | sub-problem |
| procedure/prəˈsiːdʒə/ | procedure |
| modules/ˈmɒdjuːlz/ | Модули |
| algorithm/ˈælɡərɪθəm/ | algorithm |
| sequence/ˈsiːkwəns/ | sequence |
| unambiguous/ʌnæmˈbɪɡjuːəs/ | Неоднозначный |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | deterministic |
9.2
Алгоритмы
Программа
| Кандидаты должны уметь: | Примечания и рекомендации |
|---|---|
| Проявить понимание того, что алгоритм — это решение задачи, выраженное в виде последовательности определенных шагов | |
| Использовать подходящие имена идентификаторов для представления данных, используемых задачей, и отображать их с помощью таблицы идентификаторов | |
| Написать псевдокод, содержащий ввод, обработку и вывод | |
| Писать псевдокод, используя три основных конструкта: последовательность, выбор и итерация (повторение) | |
| Документировать простой алгоритм с помощью структурированного английского описания, блок-схемы или псевдокода | |
| Написать псевдокод на основе: • структурированного английского описания • блок-схемы | |
| Нарисовать блок-схему на основе: • структурированного английского описания • псевдокода | |
| Описать и использовать процесс пошаговой детализации для выражения алгоритма до уровня детализации, достаточного для программирования задачи | |
| Использовать логические высказывания для определения частей решения алгоритма |
Источник: Программа Cambridge International
Алгоритм — это решение, выраженное последовательностью определенных шагов. Каждый шаг однозначен (имеет одно значение), детерминирован (одинаковый вход → одинаковый выход), конечен (шаги завершаются) и осуществим (каждый можно выполнить). Алгоритм говорит что делать, независимо от используемого языка программирования для его реализации.
Выбор: следуйте веткам IF / ELSE
Перетащите счет и посмотрите, какая ветка выполняется. Выбор последовательно проверяет каждое условие и выбирает ПЕРВОЕ истинное — именно так работает конструкция IF … ELSE IF … ELSE.
9.2
Таблица идентификаторов
При начале алгоритма перечислите все данные в таблице идентификаторов — их идентификатор (название переменной), тип данных и описание. Таблица в экзамене содержит ровно эти три столбца:
| Идентификатор | Тип данных | Описание |
|---|---|---|
Category |
STRING |
категория продукта |
SaleDate |
DATE |
дата продажи товара |
ItemCost |
REAL |
стоимость товара |
InStock |
BOOLEAN |
TRUE если есть в наличии |
Sales |
ARRAY[1:30] OF REAL |
последние 30 суточных итогов продаж |
Используйте описательные имена (ItemCost, а не x): идентификатор начинается с буквы, не содержит пробелов и пишется одинаково при каждом появлении. Распространенные типы — INTEGER, REAL, STRING, CHAR, BOOLEAN, DATE, а также массивы. Таблица заставляет вас назвать каждое данные перед написанием кода, а вопрос "дополнить таблицу идентификаторов" дает один балл за правильный тип данных или описание, поэтому указывайте тип точно так, как в руководстве по псевдокоду.
*Таблица идентификаторов называет все элементы данных перед написанием кода
| English | Русский |
|---|---|
| identifier table/aɪˈdentɪfaɪə ˈteɪbl/ | identifier table |
| identifier/aɪˈdentɪfaɪə/ | идентификатор |
| Boolean/ˈbuːlɪən/ | Булева величина |
9.2
Псевдокод — три основных конструкции
Псевдокод — это структурированный, независимый от языка способ описания алгоритмов.

1. Последовательность
Шаги выполняются друг за другом (последовательность):
INPUT Name
INPUT Age
OUTPUT "Hello", Name
2. Выбор
Выбор того, какие шаги выполнять, на основе условия (выбор):
IF Age >= 18 THEN
OUTPUT "Adult"
ELSE
OUTPUT "Minor"
ENDIF
Для большего количества вариантов используйте CASE OF ... ENDCASE.
3. Итерация
Повторение блока (итерация, цикл):
FOR i ← 1 TO 10
OUTPUT i
NEXT i
Цикл WHILE проверяет условие перед каждым проходом (может выполниться ноль раз); цикл REPEAT...UNTIL проверяет условие после каждого прохода (всегда выполняется хотя бы один раз).
WHILE Total < 100 DO
INPUT Value
Total ← Total + Value
ENDWHILE
REPEAT
INPUT Mark
UNTIL Mark >= 0 AND Mark <= 100

Выбор цикла сам по себе является оценочным моментом: FOR когда вы знаете количество повторений (цикл с управляемым счетчиком); WHILE когда цикл может не выполниться вообще (цикл с предусловием); REPEAT ... UNTIL когда он должен выполниться хотя бы один раз, как при проверке ввода (цикл с постусловием). Ответ "опишите конструкцию итерации" называет конструкцию, указывает, где проверяется условие, и приводит следствие (ноль раз или хотя бы один раз).
Распространенные операции
- присваивание:
x ← 5(стрелка;=используется для сравнения). - ввод/вывод:
INPUT variable,OUTPUT expression. - сравнения
=,<>,<,>,<=,>=; логикаAND,OR,NOT. - арифметика
+ - * /, сложениеDIV(целочисленное деление) иMOD(остаток от деления). - строки:
LENGTH,LEFT,RIGHT,MIDи&для конкатенации (объединения).
Псевдокод, который ожидается на экзамене
Каждый ответ по псевдокоду оценивается в соответствии с опубликованным руководством Cambridge. Пишите эти формы точно:
| Конструкция | Псевдокод |
|---|---|
| Переменная | DECLARE Total : INTEGER |
| Массив | DECLARE Marks : ARRAY[1:30] OF REAL |
| Константа | CONSTANT MaxTries = 3 |
| Присваивание | Total ← Total + Value |
| Ввод / вывод | INPUT NameOUTPUT "Hello ", Name |
| Выбор | CASE OF Choice1 : OUTPUT "Add"OTHERWISE OUTPUT "Error"ENDCASE |
| Цикл FOR | FOR i ← 1 TO 10 STEP 2 ... NEXT i |
| Цикл WHILE | WHILE Total < 100 DO ... ENDWHILE |
| Цикл REPEAT | REPEAT ... UNTIL Mark >= 0 |
| Целочисленная арифметика | 17 DIV 5 = 317 MOD 5 = 2 |
| Строки | LENGTH(S), LEFT(S, 3), RIGHT(S, 2)MID(S, 2, 4), TO_UPPER(S), TO_LOWER(S) |
| Преобразования | INT(3.7) = 3, NUM_TO_STR(12)STR_TO_NUM("4.5"), ASC('A') = 65, CHR(66) = 'B' |
| Случайное число | RAND(100)INT(RAND(100)) + 1 |
RAND(100) дает вещественное число от 0 до (но не включая) 100. INT(RAND(100)) + 1 дает целое число от 1 до 100.
Два навыка приносят баллы за каждый вопрос: декларировать каждую используемую переменную, указывая тип из таблицы идентификаторов, и инициализировать каждый счетчик и сумму (Count ← 0, Total ← 0) перед циклом, который их изменяет.
Ввод → Обработка → Вывод
Каждая программа имеет эту структуру:
INPUT Length
INPUT Width
Area ← Length * Width
OUTPUT "Area = ", Area
Перечисление входов и выходов делает алгоритм чище.
Разобранный пример. Напишите псевдокод, который вводит 100 целых чисел и выводит, сколько из них, и общую сумму тех, что находятся в диапазоне от 10 до 20 включительно.
Таблица идентификаторов: Count : INTEGER (счетчик цикла), Value : INTEGER (только что введенное целое число), InRange : INTEGER (сколько было в диапазоне), Total : INTEGER (их сумма).
DECLARE Count, Value, InRange, Total : INTEGER
InRange ← 0
Total ← 0
FOR Count ← 1 TO 100
INPUT Value
IF Value >= 10 AND Value <= 20 THEN
InRange ← InRange + 1
Total ← Total + Value
ENDIF
NEXT Count
OUTPUT InRange, Total
Если затем вопрос просит "определить две конструкции и указать, как используется каждая", отвечайте в той же форме: итерация — цикл FOR повторяет ввод 100 раз; выбор — оператор IF добавляет значение только тогда, когда оно находится в диапазоне.
Разобранный пример. Программа выбирает секретное целое число от 1 до 100. Пользователь угадывает до тех пор, пока не угадает; после каждой неверной попытки программа говорит "Слишком мало" или "Слишком много", а в конце выводит, сколько попыток было сделано.
Таблица идентификаторов: Secret : INTEGER (число, которое нужно угадать), Guess : INTEGER (ввод пользователя), Tries : INTEGER (сколько попыток было сделано на данный момент).
DECLARE Secret, Guess, Tries : INTEGER
Secret ← INT(RAND(100)) + 1
Tries ← 0
REPEAT
INPUT Guess
Tries ← Tries + 1
IF Guess < Secret THEN
OUTPUT "Too low"
ELSE
IF Guess > Secret THEN
OUTPUT "Too high"
ENDIF
ENDIF
UNTIL Guess = Secret
OUTPUT "You took ", Tries, " guesses"
Цикл REPEAT ... UNTIL является правильным выбором, так как пользователь должен угадать хотя бы один раз. Баллы начисляются за: случайное число в правильном диапазоне, цикл, завершающийся на верном угадывании, счетчик, начинающийся с нуля и увеличивающийся внутри цикла, два сообщения при правильных условиях и финальный вывод.

Разобранный пример. Вывести два различных случайных целых числа, каждое между $-10$ и $10$ включительно.
Существует 21 возможных значений, поэтому INT(RAND(21)) дает результат от 0 до 20, а вычитание 10 смещает диапазон на значения от $-10$ до $10$. Второе число необходимо генерировать повторно, пока оно не станет отличным от первого:
DECLARE First, Second : INTEGER
First ← INT(RAND(21)) - 10
REPEAT
Second ← INT(RAND(21)) - 10
UNTIL Second <> First
OUTPUT First, Second

IF … ELSE (выбор)
Измените значение и посмотрите, какой ветвь выполнит программа — как программа принимает решение.
| English | Русский |
|---|---|
| variable/ˈveərɪəbl/ | variable |
| data type/ˈdeɪtə taɪp/ | data type |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocode |
| flowchart/ˈfləʊtʃɑːt/ | Блок-схема |
| selection/sɪˈlekʃn/ | Выбор (разветвление) |
| iteration/ˌɪtəˈreɪʃn/ | Итерация |
| loop/luːp/ | цикла |
| count-controlled loop/kaʊnt kənˈtrəʊld luːp/ | Счётный цикл |
| pre-condition loop/priː kənˈdɪʃn luːp/ | Цикл с предварительной проверкой |
| post-condition loop/pəʊst kənˈdɪʃn luːp/ | Цикл с последующей проверкой |
| assignment/əˈsaɪnmənt/ | assignment |
| concatenation/kənˌkætəˈneɪʃn/ | конкатенация |
| initialise/ɪˈnɪʃəlaɪz/ | Инициализация |
| counter/ˈkaʊntə/ | Счётчик |
| structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ | Структурированный английский язык |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | Постепенное уточнение |
| logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ | Логическое утверждение |
| precedence/ˈpresɪdəns/ | Приоритет (порядок выполнения операций) |
| De Morgan's law/də ˈmɔːɡənz lɔː/ | Законы де Моргана |
9.2
Три нотации
Один и тот же алгоритм можно записать тремя способами.
- структурированный английский — естественный язык с отступами и фиксированными ключевыми словами; подходит для описания высокого уровня.
- блок-схема — диаграмма со стандартными формами:
| Форма | Значение |
|---|---|
| Закругленный прямоугольник | Старт / Стоп |
| Параллелограмм | Ввод / Вывод |
| Прямоугольник | Обработка |
| Ромб | Решение |
| Стрелка | Поток управления |
- псевдокод — нотация с ключевыми словами выше; ближе всего к коду.
Вы должны уметь преобразовывать между любой парой: каждый IF — это ромб решения, каждый цикл — стрелка назад, а последовательность — стопка прямоугольников.
IF ... THEN ... ELSE ... ENDIF

9.2
Пошаговое уточнение
Пошаговое уточнение начинается с высокоуровневого плана и раскрывает каждый шаг до тех пор, пока он не станет достаточно малым для кодирования. Для среднего значения $n$ чисел:
Уровень 1:
Read in the numbers
Compute the average
Output the average
Уровень 2:
INPUT n
total ← 0
FOR i ← 1 TO n
INPUT value
total ← total + value
NEXT i
average ← total / n
OUTPUT average
Каждое уточнение сохраняет предыдущую структуру и добавляет детали.
Вопрос на шесть баллов «применить пошаговое уточнение» дает вам высокоуровневый план и требует расширить каждый шаг до конкретных команд, которые мог бы написать программист. Сохраняйте порядок шагов, называйте данные, которые каждый шаг читает или производит, и останавливайтесь, когда каждая строка представляет собой отдельный ввод, присваивание, вывод, цикл или условие. Например, «проверить пароль» превращается в: ввести пароль; проверить, что его длина не менее 8; проверить, что он содержит хотя бы одну цифру; вывести «accepted», если оба условия выполнены, иначе вывести «rejected».

Пошаговая декомпозиция: от плана коду
Спускайтесь по уровням. Вы начинаете со всей задачи в одной строке и постоянно расширяете каждый шаг на меньшие — пока каждый шаг не станет простым для прямого кодирования.
9.2
Логические выражения
Логическое выражение — это булево условие, управляющее ветвлением, состоящее из сравнений (x > 10), логических связок (AND, OR, NOT) и скобок. Используйте его как условие для IF, WHILE или REPEAT...UNTIL:
WHILE attempts < 3 AND NOT loggedIn DO
INPUT password
IF password = correctPassword THEN
loggedIn ← TRUE
ELSE
attempts ← attempts + 1
ENDIF
ENDWHILE
Приоритет (от наивысшего к наименьшему): NOT, затем AND, затем OR. При сомнениях используйте скобки. Частые ошибки:
a = 1 OR 2неверно — пишитеa = 1 OR a = 2.NOT a > 5означаетNOT (a > 5), то естьa <= 5.NOT (A AND B)равно(NOT A) OR (NOT B)(закон де Моргана) — удобно для упрощения условий.
Перевод предложения в логическое выражение — навык, который проверяют напрямую. «Билет бесплатный для всех, кому меньше 5 или больше 65» превращается в Age < 5 OR Age > 65. «Отметка действительна, если это целое число от 0 до 100» превращается в Mark >= 0 AND Mark <= 100. «Цикл останавливается, когда файл закончен или прочитано десять записей» превращается в UNTIL EOF(File) OR Count = 10. Записывайте каждое сравнение полностью: Age > 65 и Age < 5, никогда не Age > 65 OR < 5.
*Приоритет: NOT связывается с loggedIn сначала, затем AND объединяет две стороны
Разобранная задача. Составьте таблицу идентификаторов и псевдокод для чтения 10 чисел и вывода наибольшего. Таблица идентификаторов называет каждую переменную, указывая её тип данных и назначение: Count : INTEGER (счетчик цикла), Num : REAL (только что прочитанное число), Max : REAL (наибольшее на данный момент).
Max ← -999999
FOR Count ← 1 TO 10
INPUT Num
IF Num > Max THEN
Max ← Num
ENDIF
NEXT Count
OUTPUT Max
Ключевое решение, приносящее баллы, — инициализация Max: она должна начинаться ниже любого возможного ввода — или, еще безопаснее, устанавливаться равным первому прочитанному числу. Инициализация его значением 0 приведет к тому, что алгоритм ошибочно вернет 0 для списка отрицательных чисел; эта ошибка выявляется трассировкой только тогда, когда тестовые данные содержат отрицательные значения.
Программные требования для вопросов об алгоритмах
Перед написанием или трассировкой алгоритмов используйте выражения и встроенные функции на листах 11.1.1–11.1.2. TO_UPPER и TO_LOWER принимают целые строки; UCASE и LCASE в руководстве работают с одним символом. Следуйте инструкциям задания по вставке.
Объединяйте строки с помощью &; преобразуйте число в строку с помощью NUM_TO_STR перед объединением. Вызовите процедуру с помощью CALL Name(arguments); используйте функцию как выражение. SETDATE(day, month, year) конструирует значение DATE. Проверяйте типы перед вычислением: некорректное выражение вызывает ошибку ERROR, а не догадывается о преобразовании.
Для блок-схемы с несколькими суммами инициализируйте каждый аккумулятор перед циклом. Обновляйте их на правильных ветках, увеличивайте счетчик, затем проверяйте условие завершения. Вычисляйте среднее значение после цикла, используя фактическое количество включенных значений.
9.2
Определения, принимаемые экзаменатором
Вопросы на определение оцениваются по фиксированной формулировке. Выучите их точно и дайте только один ответ.
| Термин | Определение |
|---|---|
| абстракция | сохранение существенных деталей задачи и исключение несущественных |
| декомпозиция | разбиение задачи на более мелкие подзадачи, каждая из которых может решаться отдельно |
| алгоритм | решение задачи, выраженное последовательностью определенных шагов |
| таблица идентификаторов | таблица, перечисляющая каждый идентификатор, используемый в алгоритме, с указанием его типа данных и описания назначения |
| псевдокод | структурированный, независимый от языка способ записи шагов алгоритма |
| блок-схема | диаграмма, показывающая шаги и решения алгоритма с использованием стандартных символов, соединенных стрелками |
| последовательность | инструкции, выполняемые одна за другой в указанном порядке |
| выбор (выборочный оператор) | выбор того, какие инструкции выполнять, согласно условию |
| итерация (цикл) | повторение группы инструкций, пока выполняется условие или до тех пор, пока оно истинно |
| постепенное уточнение | разбиение каждого шага плана на более мелкие шаги, многократно, пока каждый шаг нельзя будет закодировать напрямую |
| логическое выражение | условие, составленное из сравнений и операторов AND, OR и NOT, которое вычисляется как TRUE или FALSE |
9.2
Советы для экзамена
- Определите алгоритм как неоднозначную, конечную, детерминированную последовательность шагов, независимую от языка программирования.
- Правильно используйте три конструкции — последовательность, выбор, итерацию — и ведите таблицу идентификаторов с типами данных.
- Разбивайте задачу с помощью декомпозиции и абстракции, затем применяйте постепенное уточнение.
- Пишите псевдокод, который мог бы реально работать: объявляйте переменные и следуйте стилю псевдокода экзамена.
Распространенные ошибки
- Использование
=для присваивания значения. Присваивание обозначается как←;=является сравнением. - Забывание
ENDIF,ENDWHILE,ENDCASEилиNEXT. Каждая конструкция закрывается, и закрывающее слово — это место, где проверяется балл за конструкцию. - Неинициализация суммы или счетчика перед циклом, из-за чего алгоритм прибавляет к значению, которого никогда не существовало.
- Использование цикла
FOR, когда количество повторений неизвестно. Чтение до специального значения или получения правильного ответа требуетWHILEилиREPEAT ... UNTIL. - Написание
Age > 65 OR < 5. Каждая сторонаORиANDдолжна быть полным сравнением. - Ответ на вопрос «объясните, почему используется декомпозиция» одним преимуществом, написанным тремя способами. Три балла требуют трех разных преимуществ.
Интерактивные уроки по этой теме
Пройдите его шаг за шагом с упражнениями мгновенной проверки.