| Кандидаты должны уметь: | Примечания и рекомендации |
|---|---|
| 1 Понимание цикла разработки программ, ограниченного: анализом, проектированием, написанием кода и тестированием | • Включает определение каждого этапа и выполнение соответствующих задач: – анализ: абстрагирование, декомпозиция задачи, identification of the problem and requirements (выявление проблемы и требований) – проектирование: декомпозиция, структурные диаграммы, блок-схемы, псевдокод – написание кода: написание программного кода и итеративное тестирование – тестирование: тестирование программного кода с использованием тестовых данных |
| 2 (a) Понимание того, что каждая компьютерная система состоит из подсистем, которые в свою очередь состоят из дальнейших подсистем (b) Понимание того, как задача может быть декомпозирована на составные части | • Включая: – входные данные – процессы – выходные данные – хранение |
| (c) Использование различных методов для проектирования и создания решения задачи | • Включая: – структурные диаграммы – блок-схемы – псевдокод |
| 3 Объяснение назначения заданного алгоритма | • Включая: – указание назначения алгоритма – описание процессов, участвующих в алгоритме |
| 4 Понимание стандартных методов решения | • Ограничено: – линейный поиск – сортировка пузырьком – суммирование – подсчет – нахождение максимального, минимального и среднего значений |
| 5 (a) Понимание необходимости проведения проверок корректности (валидации) входных данных и различных видов таких проверок | • Включая: – проверка диапазона – проверка длины – проверка типа – проверка наличия – проверка формата – контрольная цифра |
| (b) Понимание необходимости проведения проверок верификации входных данных и различных видов таких проверок | • Включая: – визуальная проверка – двойной ввод |
| 6 Предложение и применение подходящих тестовых данных | • Ограничено: – нормальные – нестандартные (неправильные) – экстремальные – граничные • Экстремальные данные — это наибольшее/наименьшее допустимое значение • Граничные данные — это наибольшее/наименьшее допустимое значение и соответствующее наименьшее/наибольшее отклоняемое значение |
| 7 Заполнение таблицы трассировки для документирования ручного прогона алгоритма | • Включая, на каждом шаге алгоритма: – переменные – выходные данные – запросы пользователя |
| 8 Выявление ошибок в заданных алгоритмах и предложения по их исправлению | |
| 9 Написание и редактирование алгоритмов для заданных задач или ситуаций, используя: псевдокод, программный код и блок-схемы | • Требуется точность при написании алгоритмов, например, x > y допустимо, но «x больше y» недопустимо • См. раздел 4 для символов блок-схем • См. раздел 4 для псевдокода |
Проектирование алгоритмов и решение задач
IGCSE Computer Science · Тема 7
9:16
Жизненный цикл разработки программ
Каждое приложение на вашем телефоне было написано кем-то вроде этого. Но они не начинали с набора кода. До первой строки проблема изучалась, решение разрабатывалось…
Озвучивание на английском · переключаемые субтитры на английском и китайском языках
Программа
Источник: Программа Cambridge International
7.1
Цикл разработки программного обеспечения
Цикл разработки программного обеспечения — это набор этапов, используемых для создания программы. Существует четыре этапа.

| Этап | Что нужно делать |
|---|---|
| анализ | изучить проблему и определить, что требуется |
| проектирование | спланировать, как будет работать программа |
| написание кода | написать код программы и тестировать его по мере создания |
| тестирование | запустить готовую программу с тестовыми данными для выявления ошибок |


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

В верхнем блоке размещается вся система. Каждый блок на следующем уровне обозначает одну задачу системы; блок можно разделить и дальше (оплата разделяется на наличные и карту). Читайте блоки одного уровня слева направо в порядке выполнения задач. Структурная схема показывает части, а не порядок принятия решений или циклы: для этого используются блок-схема или псевдокод.
Написание кода и тестирование
При написании кода вы пишете код программы. Вы используете итеративное тестирование — тестируете маленькие части снова и снова по мере их создания. При тестировании вы запускаете всю программу с тестовыми данными, чтобы проверить её работоспособность.
| English | Русский |
|---|---|
| program development life cycle/ˈprəʊɡræm dɪˈveləpmənt laɪf ˈsaɪkl/ | жизненный цикл разработки программ |
| analysis/əˈnæləsɪs/ | анализ |
| design/dɪˈzaɪn/ | проектирование |
| coding/ˈkəʊdɪŋ/ | написание кода |
| testing/ˈtestɪŋ/ | тестирование |
| abstraction/əbˈstrækʃn/ | абстракция |
| decomposition/ˌdiːkɒmpəˈzɪʃn/ | декомпозиция |
| sub-systems/sʌb ˈsɪstəmz/ | подсистемы |
| structure diagram/ˈstrʌktʃə ˈdaɪəɡræm/ | диаграмма структуры |
| iterative testing/ˈɪtərətɪv ˈtestɪŋ/ | итеративное тестирование |
| test data/test ˈdeɪtə/ | тестовые данные |
| flowchart/ˈfləʊtʃɑːt/ | блок-схема |
7.2
Инструменты проектирования
Вы можете спланировать решение тремя основными способами.
- диаграмма структуры — показывает части системы и то, как они связаны друг с другом;
- блок-схема — диаграмма, использующая прямоугольники и стрелки для показа шагов по порядку;
- псевдокод — шаги, записанные простым языком, похожим на код (не настоящим языком программирования).

7.3
Алгоритмы
Алгоритм — это набор шагов, выполненных в правильном порядке, которые решают проблему. Любой алгоритм можно разделить на три части:
- входные данные — данные, которые поступают;
- обработка — работа, выполняемая над данными;
- выходные данные — результат, который получается.
Это называется декомпозицией на входные данные, обработку и выходные данные. Например, для задачи «найти среднее трёх оценок»: входные данные — три оценки; обработка — их сложение и деление на 3; выходные данные — среднее значение.

| English | Русский |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | пузырьковая сортировка |
| totalling/ˈtəʊtəlɪŋ/ | накопление суммы |
| counting/ˈkaʊntɪŋ/ | подсчёт |
7.4
Валидация и верификация
При вводе данных вы проверяете их, чтобы сократить количество ошибок.
Валидация проверяет, что данные разумны и соответствуют правилам. Она не может проверить истинность данных, только то, допустимы ли они.
| Проверка валидации | Что проверяется |
|---|---|
| проверка диапазона | значение находится между минимально и максимально допустимыми значениями |
| проверка длины | количество символов допустимо (например, пароль ≥ 8) |
| проверка типа | данные имеют правильный тип (например, число, а не буквы) |
| проверка наличия | действительно введено что-либо (а не оставлено пустым) |
| проверка формата | данные находятся в правильном формате (например, дата как dd/mm/yyyy) |
| Контрольная цифра | дополнительный вычисленный символ помогает обнаруживать ошибки при вводе числа |
Верификация проверяет, что данные были скопированы или введены правильно (без ошибок при наборе). Два метода:
- визуальная проверка — человек сравнивает набранные данные с оригиналом;
- двойной ввод — данные вводятся дважды, и две копии сравниваются.

Написание процедуры проверки допустимости
На экзамене часто просят написать код проверки. Используйте цикл, который повторяет запрос до тех пор, пока ввод не станет допустимым, и выводите сообщение пользователю, если ввод недопустим.
Разобранный пример. Напишите псевдокод для ввода оценки за тест, которая должна быть целым числом от 0 до 100 (проверка диапазона), и повторяйте запрос, пока не будет введена допустимая оценка.
DECLARE Mark : INTEGER
REPEAT
OUTPUT "Enter a mark from 0 to 100"
INPUT Mark
IF Mark < 0 OR Mark > 100
THEN
OUTPUT "Invalid: the mark must be from 0 to 100"
ENDIF
UNTIL Mark >= 0 AND Mark <= 100
Условие UNTIL задаёт допустимый диапазон, а условие IF противоположно ему. Обратите внимание на OR в IF: оценка не может быть одновременно меньше 0 и больше 100, поэтому AND в этом месте никогда не будет истинным.
Остальные проверки строятся по тому же образцу, но с другим условием:
| Проверка | Условие допустимости значения |
|---|---|
| проверка длины (пароль не менее 8 символов) | LENGTH(Password) >= 8 |
| проверка наличия (имя должно быть введено) | Name <> "" |
| проверка диапазона (возраст от 16 до 65) | Age >= 16 AND Age <= 65 |
Проверку типа обычно выполняет сам язык, например когда введённое значение сохраняется в переменной типа INTEGER.
| English | Русский |
|---|---|
| pseudocode/ˈsuːdəʊkəʊd/ | псевдокод |
| algorithm/ˈælɡərɪθəm/ | алгоритм |
| input/ˈɪnpʊt/ | входные данные |
| processing/ˈprəʊsesɪŋ/ | обработка данных |
| output/ˈaʊtpʊt/ | выходные данные |
| validation/ˌvælɪˈdeɪʃn/ | валидация |
| range check/reɪndʒ tʃek/ | проверка диапазона |
| length check/leŋθ tʃek/ | проверка длины |
| type check/taɪp tʃek/ | проверка типов |
| presence check/ˈprezəns tʃek/ | проверка наличия |
| format check/ˈfɔːmæt tʃek/ | проверка формата |
| check digit/tʃek ˈdɪdʒɪt/ | контрольная цифра |
| verification/ˌverɪfɪˈkeɪʃn/ | верификация |
| visual check/ˈvɪʒuːəl tʃek/ | визуальная проверка |
| double entry/ˈdʌbl ˈentri/ | двойной ввод |
7.5
Таблицы трассировки
Таблица трассировки фиксирует значение каждой переменной по мере выполнения алгоритма шаг за шагом. Она помогает вам:

- убедиться, что алгоритм работает корректно;
- определить что делает алгоритм, проследив его выполнение на заданных данных.
Пример: выполните трассировку этого алгоритма с входным значением 5.
INPUT N
Total ← 0
FOR I ← 1 TO N
Total ← Total + I
NEXT I
OUTPUT Total
| i | total | ВЫХОД |
|---|---|---|
| 1 | 1 | |
| 2 | 3 | |
| 3 | 6 | |
| 4 | 10 | |
| 5 | 15 | 15 |
Трассировка показывает, что алгоритм суммирует числа от 1 до n. При входном значении 5 выход равен 15.
Разобранный пример. Выполните трассировку этого алгоритма и укажите результат.
X ← 20
Count ← 0
WHILE X > 1
X ← DIV(X, 2)
Count ← Count + 1
ENDWHILE
OUTPUT Count
DIV дает только целую часть деления. Запишите одну строку за каждую итерацию: x становится равным 10 (счетчик 1), затем 5 (счетчик 2), затем 2 (счетчик 3), затем 1 (счетчик 4). Теперь x > 1 ложно, поэтому цикл останавливается, и результат составляет 4. Две привычки защищают эти баллы: проверяйте условие перед каждой итерацией, а не после, и записывайте новую строку для каждой итерации — попытка удерживать значения в голове приводит к ошибкам в трассировках.
Поиск и исправление ошибок
В распространённом типе заданий приводится алгоритм с ошибками, которые нужно найти и исправить. Читайте его построчно и спрашивайте себя: каждой ли переменной присвоено начальное значение? Верное ли число раз выполняется каждый цикл? Правильно ли направлено каждое сравнение? В нужном ли месте находится вывод?
Разобранный пример. Этот алгоритм должен вводить 10 чисел и выводить наибольшее. Найдите три ошибки и исправьте их.
Largest ← 1000
FOR Count ← 1 TO 9
INPUT Number
IF Number < Largest
THEN
Largest ← Number
ENDIF
OUTPUT Largest
NEXT Count
- Строка 1: начальное значение
Largest ← 1000слишком велико, поэтому ни одно число его не заменит. Исправление:Largest ← -1000(или введите первое число и используйте его как начальное значение). - Строка 2: цикл выполняется только 9 раз. Исправление:
FOR Count ← 1 TO 10. - Строка 4:
<находит наименьшее значение. Исправление:IF Number > Largest.
Есть также проблема с OUTPUT: внутри цикла он выводит наибольшее из введённых значений после каждого ввода. Если перенести его после NEXT Count, будет выведен только окончательный ответ. Для каждой ошибки укажите строку, объясните, что не так, и полностью запишите исправленную строку.
Таблица трассировки
Пройдите по циклу и заполните таблицу трассировки, по одной строке на каждый проход.
| English | Русский |
|---|---|
| trace table/treɪs ˈteɪbl/ | таблица трассировки |
| normal/ˈnɔːml/ | нормальный |
| abnormal/əbˈnɔːml/ | аномальный |
| extreme/ekˈstriːm/ | экстремальный |
| boundary/ˈbaʊndəri/ | граничный |
7.6
Тестовые данные
Тестовые данные — это данные, которые вы используете для тестирования программы. Вы должны знать четыре их типа.
| Тип | Значение | Пример (допустимый возраст 0–120) |
|---|---|---|
| нормальные | разумные данные, которые должны быть приняты | 25 |
| недопустимые | неверные данные, которые должны быть отклонены | -4 или «кот» |
| экстремальные | наибольшее и наименьшее значения, которые все еще допустимы | 0 и 120 |
| граничные | значения по обе стороны от предела (одно допустимо, другое нет) | 120 и 121 |
Разобранный пример. Программа принимает число людей, бронирующих столик, от 1 до 12. Приведите тестовые данные каждого типа и ожидаемый результат.
| Тип | Тестовые данные | Ожидаемый результат |
|---|---|---|
| обычные | 5 | принимаются |
| недопустимые | 20 (или «шесть») | отклоняются с сообщением об ошибке |
| крайние | 1 и 12 | принимаются |
| граничные | 12 и 13 (или 0 и 1) | 12 принимается, 13 отклоняется |
Всегда указывайте ожидаемый результат вместе с данными: тест полезен, только если известно, что должно произойти. Крайнее значение находится на самой границе; граничные данные — это пара значений по обе стороны от границы.

7.7
Стандартные методы решения
Вы должны знать эти распространенные алгоритмы.
Линейный поиск
Линейный поиск сравнивает каждый элемент с целевым, начиная с начала. Остановитесь, когда значение найдено или список закончился. Список не обязательно должен быть отсортирован. Приведённый ниже пример использует позиции 1 до 4.
DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, SearchValue : INTEGER
DECLARE Found : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
INPUT SearchValue
Found ← FALSE
I ← 1
WHILE I <= 4 AND NOT Found
IF List[I] = SearchValue
THEN
Found ← TRUE
ENDIF
I ← I + 1
ENDWHILE
OUTPUT Found
Разобранное сравнение. Поиск значения 5 выполняет сравнения 8, 3, а затем 5: три сравнения, при этом Found становится равно TRUE. Четвёртый элемент не проверяется. Поиск значения 9 сравнивает все четыре значения; Found остаётся равным FALSE. Остановка происходит перед попыткой чтения позиции 5, которая выходит за пределы этого массива.

Пузырьковая сортировка
Пузырьковая сортировка упорядочивает список. Сравниваются соседние значения, и они меняются местами, если левое значение больше правого. Обычно одного прохода недостаточно. Эта полная версия повторяет проходы, пока какой-либо полный проход не завершится без обменов.
DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Temp : INTEGER
DECLARE Swapped : BOOLEAN
List[1] ← 8
List[2] ← 3
List[3] ← 5
List[4] ← 1
REPEAT
Swapped ← FALSE
FOR I ← 1 TO 3
IF List[I] > List[I + 1]
THEN
Temp ← List[I]
List[I] ← List[I + 1]
List[I + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT I
UNTIL NOT Swapped
OUTPUT List[1], ", ", List[2], ", ", List[3], ", ", List[4]
Разобранные проходы. Начните со значения 8, 3, 5, 1. В первом проходе список преобразуется в 3, 8, 5, 1, затем в 3, 5, 8, 1, затем в 3, 5, 1, 8. Это помещает наибольшее значение в конец, но оставляет остальные неупорядоченными. Второй проход заканчивается на позиции 3, 1, 5, 8; третий — на позиции 1, 3, 5, 8. Четвёртый проход не совершает обменов и подтверждает, что эту версию можно остановить. Сбрасывайте значение Swapped на FALSE в начале каждого прохода; устанавливайте его на TRUE при любом обмене.

Подсчет суммы и подсчет количества
Подсчёт суммы прибавляет каждое требуемое значение к текущей сумме: Total ← Total + Value. Подсчёт количества прибавляет 1 за каждый требуемый элемент: Count ← Count + 1. Инициализируйте оба значения нулём перед обработкой данных.
Разобранное решение. Четыре попытки ввода: −20, 4, 50 и 6. Значение принимается только если оно больше −20 и меньше 50. В этом примере обрабатывается четыре попытки, а не четыре принятых значения.
DECLARE I, Count : INTEGER
DECLARE Value, Total : REAL
Total ← 0
Count ← 0
FOR I ← 1 TO 4
INPUT Value
IF Value > -20 AND Value < 50
THEN
Total ← Total + Value
Count ← Count + 1
ENDIF
NEXT I
IF Count > 0
THEN
OUTPUT Total, ", ", Count, ", ", Total / Count
ELSE
OUTPUT "No accepted values"
ENDIF
| Попытка ввода | Сумма после попытки | Количество после попытки |
|---|---|---|
| −20 | 0 | 0 |
| 4 | 4 | 1 |
| 50 | 4 | 1 |
| 6 | 10 | 2 |
Строгие границы отклоняют −20 и 50. Оба обновления находятся внутри теста на приемлемость, поэтому отклоненные попытки не изменяют ни сумму, ни количество. Среднее значение принятых значений равно:
Не делите на четыре: было добавлено только два значения. Если ни одно значение не принято, количество равно нулю, и среднее вычислить нельзя; вместо деления на ноль выведите сообщение об ошибке.
Переход к фиксированному числу принятых значений. Если задача требует 50 принятых значений вместо четырех попыток, замените фиксированный цикл FOR на WHILE Count < 50 и закройте его ENDWHILE. Сохраните тот же ввод и тест на приемлемость внутри него. Отклоненный ввод не меняет Count, поэтому запрашивается следующий ввод. По завершении Count равен 50, хотя число попыток может быть больше. Выведите сумму и вычислите среднее как Total / Count.
Максимум, минимум и среднее
Максимум — это наибольшее значение, а минимум — наименьшее. Среднее — это сумма, деленная на количество значений. Для непустого списка инициализируйте оба значения его первым элементом. Для каждого последующего элемента заменяйте максимум, если новое значение больше, и минимум, если оно меньше.
Разобранное решение. Список содержит −8, −3, −12, −5. Начинать поиск максимума с нуля невозможно: ни один элемент списка не больше нуля, поэтому алгоритм выведет число, которого нет в списке. Начинание с −8 работает без предположения о положительности данных.
| Только что рассмотренное значение | Максимум на данный момент | Минимум на данный момент |
|---|---|---|
| −8 (инициализация) | −8 | −8 |
| −3 | −3 | −8 |
| −12 | −3 | −12 |
| −5 | −3 | −12 |
DECLARE List : ARRAY[1:4] OF INTEGER
DECLARE I, Maximum, Minimum, Total : INTEGER
List[1] ← -8
List[2] ← -3
List[3] ← -12
List[4] ← -5
Maximum ← List[1]
Minimum ← List[1]
Total ← List[1]
FOR I ← 2 TO 4
IF List[I] > Maximum
THEN
Maximum ← List[I]
ENDIF
IF List[I] < Minimum
THEN
Minimum ← List[I]
ENDIF
Total ← Total + List[I]
NEXT I
OUTPUT Maximum, ", ", Minimum, ", ", Total / 4
Максимум равен −3, а минимум равен −12. Среднее вычисляется по всем четырем значениям:
Среднее значение находится между минимумом и максимумом; это полезная проверка, но не доказательство правильности вычисления. Инициализация с первого элемента требует непустого списка. Обработайте пустой список отдельно перед попыткой чтения этого элемента.
| English | Русский |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | линейный поиск |
| maximum/ˈmæksɪməm/ | максимум |
| minimum/ˈmɪnɪməm/ | минимум |
| average/ˈævrɪdʒ/ | среднее значение |
7.8
Советы для экзамена
- Четыре этапа жизненного цикла: анализ → проектирование → кодирование → тестирование. Абстрагирование оставляет только главное; декомпозиция разбивает задачу на части.
- Валидация проверяет, что данные разумны (проверки диапазона, длины, типа, наличия, формата); верификация проверяет, что они были скопированы правильно (визуальная проверка или двойной ввод).
- Изучите четыре типа тестовых данных: нормальные (принимается), неправильные (отклоняется), экстремальные (наибольшее/наименьшее из допустимых значений), граничные (с обеих сторон от порога).
- Таблица трассировки (значения каждой переменной на каждом шаге) показывает, как работает алгоритм.
- Чтобы написать процедуру проверки допустимости, поместите ввод в цикл
REPEAT … UNTIL, условиеUNTILкоторого задаёт допустимые данные. - Исправляя ошибку, укажите строку и полностью запишите исправленную строку.
- Знать стандартные алгоритмы: линейный поиск (проверка каждого элемента по очереди) и пузырьковая сортировка (обмен соседних пар до тех пор, пока обмен не потребуется больше).
Интерактивные уроки по этой теме
Пройдите его шаг за шагом с упражнениями мгновенной проверки.