Раздел 1 — Задача, модель, алгоритм

Программа пишется не с первой строки кода. Между словами «надо посчитать, сколько краски купить» и работающей программой лежат этапы, и ошибка, пропущенная на раннем этапе, дорожает на каждом следующем.

В этом разделе — первые три этапа. Программы по готовым алгоритмам начнутся в разделе 4, когда будут изучены основы языка C++. Требования к программе целиком, оформленные документом, — техническое задание — разбираются в разделе 13, когда за плечами будет достаточно написанных программ.

Постановка задачи отвечает на три вопроса: что дано (исходные данные), что нужно получить (результат) и при каких условиях задача имеет смысл (ограничения). Разберём сквозной пример раздела.

Ограничения — не формальность. Именно они определяют, что программа должна ответить на ввод «длина −5 м»: такая комната не существует, и честный ответ — сообщение об ошибке, а не отрицательное число банок.

Математическая модель — описание задачи на языке величин и формул. Она начинается с таблицы величин: у каждой есть обозначение, смысл, единица измерения, тип значения и допустимый диапазон.

Тип «целое» или «вещественное» здесь — свойство величины в задаче, а не в языке программирования: число слоёв бывает только целым, длина — любой. В разделе 3 этой таблице будут соответствовать типы C++ int и double.

Связи между величинами записываются формулами — по одной на каждую промежуточную величину и результат.

Sст = 2 · (a + b) · h − Sпр          [м²]    площадь четырёх стен без проёмов
Q   = Sст · k · r · 1,1             [л]     1,1 — запас 10 %
N   = ⌈ Q / V ⌉                    [шт.]   ⌈x⌉ — округление вверх до целого

Проверка единиц: м · м = м²; м² · л/м² = л; л / л — безразмерное число. Совпадает.

Допущение — упрощение реальности, принятое сознательно. Модель без допущений не бывает: реальная стена неровная, краска впитывается по-разному, часть остаётся на валике. Допущения нужно не избегать, а записывать, чтобы их можно было обсудить и заменить.

Модель проверяют контрольным примером — расчётом вручную на конкретных числах:

a = 5 м, b = 4 м, h = 2,7 м, Sпр = 3,5 м², r = 0,12 л/м², k = 2, V = 2,5 л

Sст = 2 · (5 + 4) · 2,7 − 3,5 = 48,6 − 3,5 = 45,1 м²
Q   = 45,1 · 2 · 0,12 · 1,1   = 11,9064 л
N   = ⌈ 11,9064 / 2,5 ⌉ = ⌈ 4,76 ⌉ = 5 банок

Не каждую задачу описывает одна формула. Встречаются ещё два вида моделей — они потом станут ветвлениями и циклами программы.

Кусочная модель: формула зависит от условия

         ⎧ 150 + 30 · d,                   если 0 < d ≤ 10
C(d) =   ⎨
         ⎩ 150 + 30 · 10 + 20 · (d − 10),  если d > 10

Контрольные примеры:
  d = 7   →  C = 150 + 210             = 360 ₽
  d = 10  →  C = 150 + 300             = 450 ₽   (граница: обе формулы дают 450)
  d = 15  →  C = 150 + 300 + 20 · 5    = 550 ₽

На границе условий — здесь d = 10 — обе формулы должны давать одно значение, если в условии нет скачка цены. Проверка границы находит ошибки вида «< вместо ≤» ещё до программы.

Итерационная модель: результат получается повторением шага

S0 = P                              P — начальная сумма, ₽
Si = Si−1 · (1 + p / 1200)          p — ставка, % годовых; 1200 = 12 мес. · 100 %
Найти наименьшее n, при котором Sn ≥ T   T — целевая сумма, ₽

Ограничения: P > 0, T > P, p > 0

Здесь нет формулы «n = …», которую можно сразу вычислить: результат получается повторением одного и того же шага, пока не выполнится условие. Ограничение p > 0 обязательно: при нулевой ставке сумма никогда не вырастет, и повторение не закончится.

Алгоритм — конечная последовательность точных предписаний исполнителю, которая приводит от исходных данных к результату. Модель говорит, что связано с чем; алгоритм — в каком порядке действовать.

Способов записать алгоритм три: словами, блок-схемой и псевдокодом. Словесная запись удобна для обсуждения, но легко становится неоднозначной. Блок-схема наглядна для ветвлений и циклов. Псевдокод ближе всего к будущей программе.

Словесная запись алгоритма покраски:

1. Ввести a, b, h, Sпр, r, k, V.
2. Если хотя бы одно значение недопустимо — сообщить об ошибке и закончить.
3. Вычислить площадь стен Sст = 2 · (a + b) · h − Sпр.
4. Вычислить объём краски Q = Sст · k · r · 1,1.
5. Вычислить N = Q / V, округлив вверх до целого.
6. Вывести N.

Символы блок-схем в России установлены стандартом ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем». Для алгоритмов курса нужны семь символов.

Правила построения: поток идёт сверху вниз и слева направо — в этих направлениях стрелки можно не рисовать; в остальных стрелка обязательна. У схемы один вход и один выход. Линии не пересекаются без необходимости. Текст в символе — короткий: формула или условие, а не абзац.

Схема алгоритма покраски — на странице символы нарисованы упрощённо, соответствие — в таблице выше:

                 ( Начало )
                     │
      / Ввод a, b, h, Sпр, r, k, V /
                     │
         < данные допустимы? >──── нет ─────┐
                     │ да                   │
   [ Sст = 2 · (a + b) · h − Sпр ]          │
                     │                      │
   [ Q = Sст · k · r · 1,1 ]                │
                     │                      │
   [ N = ⌈Q / V⌉ ]                / Вывод «ошибка во     /
                     │            /  входных данных»     /
               / Вывод N /                  │
                     │◄─────────────────────┘
                 ( Конец )

Любой алгоритм можно составить из трёх базовых структур — это утверждение доказано (теорема Бёма — Якопини, 1966). Схемы, построенные только из них, называют структурными.

  Следование           Ветвление                   Цикл с предусловием

  [ действие 1 ]       < условие? >─ нет ─┐        ┌──►< условие? >─ нет ─┐
        │                   │ да          │        │        │ да           │
  [ действие 2 ]       [ действие 1 ]  [ действие 2 ]      [ тело ]        │
        │                   │             │        └────────┘              │
                            ├◄────────────┘                    ┌◄──────────┘
                            │                                  │

Схема итерационной модели вклада — цикл с предусловием:

               ( Начало )
                   │
         / Ввод P, p, T /
                   │
     < P > 0, T > P, p > 0 ? >──── нет ──────┐
                   │ да                      │
          [ S = P;  n = 0 ]                  │
                   │                         │
     ┌──────►< S < T ? >── нет ──┐           │
     │             │ да          │    / Вывод «ошибка» /
     │   [ S = S · (1 + p/1200) ]│           │
     │             │             │           │
     │        [ n = n + 1 ]      │           │
     └─────────────┘             │           │
                          / Вывод n /        │
                                 │◄──────────┘
                             ( Конец )

Псевдокод — запись алгоритма ключевыми словами на естественном языке. У него нет строгого стандарта; важно, чтобы запись была однозначной и последовательной. В курсе используется такая форма:

ВВОД P, p, T
ЕСЛИ P ≤ 0 ИЛИ T ≤ P ИЛИ p ≤ 0 ТО
    ВЫВОД «ошибка во входных данных»
ИНАЧЕ
    S ← P
    n ← 0
    ПОКА S < T ВЫПОЛНЯТЬ
        S ← S · (1 + p / 1200)
        n ← n + 1
    КОНЕЦ ПОКА
    ВЫВОД n
КОНЕЦ ЕСЛИ

Стрелка ← означает присваивание: «вычислить правую часть и записать в переменную слева». Запись n ← n + 1 — не уравнение, а действие: увеличить n на единицу.

Трассировка — выполнение алгоритма вручную с записью значений всех переменных после каждого шага. Трассировка на контрольном примере P = 100 000, p = 12, T = 110 000:

Результат: 10 месяцев. Проверка другим способом: 1,01⁹ ≈ 1,0937 < 1,1, а 1,01¹⁰ ≈ 1,1046 ≥ 1,1 — совпадает.

Один контрольный пример не доказывает правильность алгоритма. Минимальный набор тестовых примеров для любой задачи курса — три вида: