Множественный выбор

Множественный выбор – это алгоритмическая конструкция, позволяющая выбрать и выполнить ровно одну (иногда – несколько, по специально оговорённым правилам) из множества альтернатив на основе значения выражения или предикатов. В традиционных языках он реализуется как case-of/switch-case (Pascal/C/C++/Go/Java), как цепочка elif (Python), или как сопоставление с образцом (match в современных диалектах). Для подготовки к ЕГЭ по информатике владение множественным выбором критично при:

• трассировке программ и анализе ветвлений;
• построении блок-схем и таблиц решений;
• доказательстве полноты/корректности разбиения диапазонов;
• оптимизации кода (замена длинных цепочек условий).

Ниже приведены строгие определения, семантические модели, эквивалентные преобразования, правила корректности и практические шаблоны. В конце – 5 упражнений именно экзаменационного формата.

Формальная модель и семантика

1. Синтаксическая схема
   

   Пусть E – выражение со значением в домене D. Определён набор «ветвей» C1, C2, …, Ck и (необязательная) ветвь default. Каждая ветвь задаётся образцом Pi ⊆ D и телом Si.

   Форма записи (абстрактно):

   switch E:

     case P1: S1

     case P2: S2

     ...

     case Pk: Sk

     default: Sdef

2. Инвариант корректности (общий случай)
   

   (1) Полнота: ( ⋃_{i=1..k} Pi ) ∪ Pdef = D_использования,

       где D_использования – все возможные значения E в данной программе.

   (2) Однозначность: ∀x∈D_использования: |{ i | x∈Pi }| ≤ 1,

       если язык/реализация не допускает намеренного «проваливания» (fallthrough).

   (3) Терминируемость: выполнение любой выбранной ветви завершается (нет бесконечных циклов без условий выхода, если это не задуманная логика).

   Замечания:

   • В частном случае Pi – точечные значения (например, x=1, x=2); либо интервалы/множества (x ∈ [10..20] ∪ {42}).

   • В языках с «проваливанием» (C/C++/Go с fallthrough) пункт (2) заменяется на явную спецификацию: либо запрещать пересечение (и ставить break), либо документировать «комбинированное» выполнение.

Нормальные формы и эквивалентные преобразования

1. Эквивалентность с цепочкой if-elseif-else
   

   Для попарно непересекающихся Pi:

   switch E:

     case P1: S1

     case P2: S2

     ...

     default: Sdef

   эквивалентно

   if   E∈P1 then S1

   elif E∈P2 then S2

   ...

   else Sdef

   Важно: при пересекающихся Pi порядок имеет значение; нормальная форма требует явного приоритета:

   if   E∈P1 then S1

   elif E∈(P2 \ P1) then S2

   ...

2. Решётка предикатов и дизъюнктивная нормальная форма (ДНФ)
   

   Если Pi выражаются логическими формулами над сравнениями, корректность удобно проверять через покрытие и непересечение:

   Полнота:        (P1 ∨ P2 ∨ ... ∨ Pk ∨ Pdef) ≡ True

   Однозначность:  ¬∃x: (Pi ∧ Pj) при i≠j, если запрещено пересечение

   Это позволяет механически выявлять «дыры» в покрытии и коллизии условий.

Стоимость выполнения и выбор реализации

1. Модель стоимости
   

   Пусть k – число ветвей.

   • Цепочка if-elif: в среднем O(k) сравнений, в лучшем O(1) (попадание в первую), в худшем O(k).

   • Дискретный switch (целые/enum), реализованный как jump table: амортизированно O(1).

   • Разреженные случаи: компиляторы используют деревья сравнения (почти O(log k)) или хеш-диспетчеризацию.

2. Практическое правило выбора
   

   - Плотные диапазоны целых/enum → switch (jump table).

   - Разреженные ключи/строки → словарь/хеш-таблица (ассоциативный массив).

   - Сложные предикаты/интервалы → упорядоченные диапазоны + двоичный поиск либо каскад if-elif с документированным приоритетом.

Правила корректности (чек-лист разработчика и решающего ЕГЭ)

Правило 1. Полнота покрытия.
Докажите, что каждая возможная ветвь значения E попадает в case или default. При использовании интервалов используйте пограничные проверки:

∀x∈[L..R]: x попадает в ⋃ Pi  ∪ Pdef

Правило 2. Непересечение (или явный приоритет).
Либо делайте Pi попарно непересекающимися, либо фиксируйте приоритет ветвей (порядок в if-elif или документированный fallthrough).

Правило 3. Константность проверок для jump table.
В языках с switch по целым/enum не допускайте вычислительных выражений в метках (только константы), иначе таблица прыжков невозможна и компилятор деградирует до цепочки сравнений.

Правило 4. default обязателен при «открытом» домене.
Если E может принимать значения вне перечисления (ввод пользователя, внешний файл), ветвь по умолчанию должна корректно обрабатывать такие случаи.

Правило 5. Числовые диапазоны – без «дыр».
Согласовывайте границы: используйте полузамкнутые интервалы [a, b) системно, чтобы избежать наложений/пробелов.

Правило 6. Строки и регистры.
При множественном выборе по строкам нормализуйте регистр/локаль заранее (например, s := lower(trim(s))).

Правило 7. Пред- и постусловия.
Фиксируйте контракт:
{P: допустимые значения E}  switch(E)  {Q: инварианты данных и побочные эффекты ветви}

Правило 8. Тестовое покрытие.
Минимальный набор тестов – по одному значению на каждую ветвь + значения на границах интервалов, + «нестандартные» (ошибочные) данные для default.

Типовые шаблоны

1. Дискретный выбор по целому/enum
   

   # Псевдокод

   switch grade:

     case 5: print("отлично")

     case 4: print("хорошо")

     case 3: print("удовлетворительно")

     case 2: print("неудовлетворительно")

     default: print("ошибка ввода")

   Инвариант: каждая оценка из {2,3,4,5} ведёт к ровно одному действию.

2. Интервальные правила (оценка по баллам)
   

   if   s ∈ [90..100] then A

   elif s ∈ [75..89]  then B

   elif s ∈ [60..74]  then C

   elif s ∈ [0..59]   then D

   else ошибка

   Правило границ: интервалы непересекающиеся и покрывают [0..100].

3. Выбор по строковому ключу с нормализацией
   

   key := lower(trim(input))

   switch key:

     case "sum":   ...

     case "avg":   ...

     case "min":   ...

     case "max":   ...

     default:      ...

4. Таблица решений (decision table)
   

   Для сложных критериев (несколько булевых условий) строим таблицу истинности и объединяем строки, ведущие к одному действию – это минимизирует количество ветвей и устраняет пересечения.

Связь с ЕГЭ по информатике

• Трассировка: умение пошагово следить за значением выражения и правильной ветвью.
• Блок-схемы: корректное изображение множественного выбора (ромб с множественными дугами/узел case).
• Анализ границ: частые задания на интервалы (температуры, баллы, диапазоны дат).
• Минимизация логики: перевод «длинных if» в структурированный выбор, доказательство полноты/непересечения.
• Сложность: аргументация «почему это работает быстрее»: jump table vs линейная цепочка.

Типичные ошибки и способы профилактики

1. Перекрывающиеся интервалы. Лекарство: единый стиль [a..b] или [a..b) и таблица границ.
2. Отсутствие default. Для «грязного» ввода – обязательно.
3. Регистрозависимость строк. Нормализация ввода.
4. Неявный приоритет. Явно документируйте порядок, если допускается пересечение условий.
5. Локализация побочных эффектов. В каждой ветви однотипные действия (например, return), чтобы избежать «проваливания» логики.
6. Случайная деградация производительности. Избегайте сложных вычислений в «метках» – выносите в вычисление E.

Мини-шпаргалка

Полнота покрытия:

(P1 ∨ P2 ∨ ... ∨ Pk ∨ Pdef) ≡ True

Непересечение (при запрете пересечений):

∀i≠j: (Pi ∧ Pj) ≡ False

Проверка границ интервалов:

[0..100] = [0..59] ∪ [60..74] ∪ [75..89] ∪ [90..100]

и попарные пересечения пусты.

Оценка трудоёмкости:

цепочка if-elif → O(k), jump table → O(1), дерево сравнений → O(log k)

Пять упражнений (формат ЕГЭ)

Упражнение 1. Полное покрытие и границы
Дана функция присвоения категории по возрасту a∈[0..120]:

• «дети»: a∈[0..13],
• «подростки»: a∈[14..17],
• «взрослые»: a∈[18..59],
• «пенсионеры»: a∈[60..120].

a) Запишите множественный выбор с доказуемо полным покрытием и непересечением.
b) Укажите тестовый набор минимального покрытия (границы каждой группы + два внутренних значения).
c) Объясните, что произойдёт при ошибке границы, например, [60..119] – как это отловить тестами?

Упражнение 2. Эквивалентность switch и if-elif
Имеется switch по коду операции op∈{1,2,3,4}. Требуется переписать в if-elif-else без изменения семантики, учитывая, что ветвь 3 должна выполняться последней по приоритету в случае пересечений.
a) Запишите эквивалентную последовательность if-elif-else с явным приоритетом.
b) Обоснуйте, почему выбранный порядок гарантирует сохранение поведения.
c) Оцените изменение трудоёмкости в худшем/среднем случае.

Упражнение 3. Таблица решений для совокупности предикатов
Есть три булевых предиката над целым x:
A: x<0, B: x чётно, C: |x|≤100. Действия:

• D1, если A∧B;
• D2, если ¬A∧B∧C;
• D3, если ¬B;
• D4 – иначе.

a) Постройте таблицу истинности и покажите, какие строки можно объединить.
b) Выведите минимизированный множественный выбор (без пересечений).
c) Подготовьте набор тестов, покрывающих все ветви (укажите конкретные x).

Упражнение 4. Производительность и структура данных
Имеются 10 000 различных строковых команд. Требуется выбрать действие по команде как можно быстрее.
a) Сравните три подхода: цепочка elif, switch по строкам (если поддерживается), ассоциативный массив dict/map.
b) Обоснуйте выбор с точки зрения асимптотики и реальной константы времени.
c) Укажите, какие пред- и постусловия нужно документировать (нормализация регистра, удаление пробелов, обработка неизвестных команд).

Упражнение 5. Интервальные кейсы и отсутствие «дыр»
Дано разбиение температур t (целые, диапазон [−50..50]) на классы:

• «мороз»: t∈[−50..−1],
• «ноль»: t=0,
• «тепло»: t∈[1..20],
• «жарко»: t∈[21..50].

a) Запишите множественный выбор в интервалной форме.
b) Проверьте полноту и непересечение формально (логические равенства из раздела 8).
c) Предложите автоматическую генерацию тестов по границам (перечислите набор значений).

Заключение

Множественный выбор – дисциплинированный способ выразить разбиение пространства значений на альтернативы. Его корректность опирается на полноту покрытия, непересечение условий (или явный приоритет), а эффективность – на подбор структуры реализации (jump table, дерево сравнений, хеш-диспетчеризация). Для ЕГЭ это означает умение:

• формально проверять границы и отсутствие «дыр»;
• трассировать выполнение и правильно выбирать ветвь;
• аргументировать сложность и корректность.

Следуя приведённым правилам и проработав упражнения, вы получите устойчивые навыки, необходимые для уверенного решения экзаменационных задач.