ЕГЭ по информатике · задание 1

Граф и таблица

Программа находит соответствие.
Остальное решаешь сам

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

11 класс · нужны только список, строка и цикл for

с чего всё начинается

Схема без чисел, числа без букв

На схеме видно, что с чем соединено, но длин на ней нет.

В таблице есть длины, но пункты в ней названы номерами, а не буквами.

договоримся сразу

Что делает программа, а что — ты

1Программа

Подбирает соответствие букв и номеров и печатает одну строчку:

АЕБВДЖГ

Первая буква — это П1, вторая — П2, и так до последней. Больше программа ничего не делает: длин она не знает и вопроса задачи не видит.

2Ты

Подписываешь номера на схеме и дальше решаешь как всегда:

смотришь длину в клетке таблицы;
складываешь строку, если спросили сумму;
выбираешь самую длинную или короткую;
считаешь путь, если прямой дороги нет.

Это и проверяют на экзамене. Программа снимает не решение, а самую механическую его часть — сопоставление букв с номерами.

шаг 1

Схему записываем парами букв

Девять линий, ни одной подписи. Больше со схемы ничего и не нужно.

Идём по рисунку и на каждую линию пишем две буквы, которые она соединяет. Порядок букв внутри пары любой: 'АГ' и 'ГА' — одна и та же дорога.

graph = ['АГ', 'ГБ', 'БВ', 'ВЖ', 'ЖЕ',
         'ЕА', 'ДА', 'ДБ', 'ЕД']

Порядок пар тоже любой

Список — это просто перечень, программа переберёт его весь. Удобно обойти сначала внешний контур по кругу, а потом дописать линии внутри него: так труднее пропустить дорогу.

Проверка: сколько линий на рисунке — столько пар в списке. Здесь девять.

шаг 2

Таблицу — парами номеров

Строка П1: числа в столбцах 2, 5 и 7 — пишем (1,2), (1,5), (1,7). Строка П2: столбцы 5 и 6, первый столбец уже посчитан.

Таблица симметрична: клетка П1–П2 и клетка П2–П1 — это одна и та же дорога. Поэтому берём только клетки выше диагонали, они подсвечены. Сами числа не нужны — важно лишь, что клетка не пустая.

table = [(1,2), (1,5), (1,7),
         (2,5), (2,6),
         (3,4), (3,5), (3,7),
         (4,6)]

Сразу проверь себя. Пар в table должно выйти ровно столько же, сколько в graph. Здесь и там девять. Не сошлось — пропущена линия или клетка, и искать это лучше сейчас, а не после запуска.

единственный новый инструмент

permutations — все способы расставить буквы

Соответствие — это расстановка: какая буква стоит на месте П1, какая на П2 и так далее. Расстановок конечное число, и Python выдаёт их все сам.

from itertools import *

for p in permutations('АБВ'):
    print(''.join(p))

АБВ
АВБ
БАВ
БВА
ВАБ
ВБА

Что здесь что

from itertools import *: подключает permutations. После этой строки имя пишется коротко, без точки
''.join(p): склеивает буквы в слово: ('А','Б','В') превращается в 'АБВ'

Сколько их выходит

3 буквы — 6 расстановок
7 букв — 5 040
8 букв — 40 320

Компьютеру на такой перебор нужны доли секунды.

как отсеиваются лишние

Проверяем каждую пару из таблицы

letters = 'АБВГДЕЖ'

for p in permutations(letters):
    p = ''.join(p)
    ok = True
    for a, b in table:
        x = p[a-1]
        y = p[b-1]
        if x + y not in graph and y + x not in graph:
            ok = False
            break
    if ok:
        print(p)

Почему проверки две подряд. Дорогу А—Г в списке graph можно было записать и как 'АГ', и как 'ГА'. Программа не знает, как именно ты её написал, поэтому смотрит оба варианта.

Построчно

letters: буквы, какие есть на схеме — выписываем с рисунка
p: очередная расстановка, например 'АЕБВДЖГ'
p[a-1]: буква на месте Па. Минус один потому, что Python считает места с нуля: П1 лежит на месте 0
not in graph: такой дороги на схеме нет — расстановка не подходит
break: одна пара не сошлась, остальные смотреть незачем

что вывелось

Строчка букв — и дальше обычное решение

АЕБВДЖГ

П1	П2	П3	П4	П5	П6	П7
А	Е	Б	В	Д	Ж	Г

Читается слева направо: первая буква стоит на месте П1, вторая — П2, и так до конца. Подпиши эти номера прямо на схеме карандашом — и схема с таблицей станут одним рисунком.

Клетка П4 — П6 подсвечена: 86 километров.

если вывелось не одно слово

Две строки — это норма. Ноль строк — опечатка

2Напечаталось две строки

БВДЖАЗЕГ
БЗДЖАВЕГ

Значит, на схеме есть два пункта с совершенно одинаковыми связями. Различить их нечем, и это не изъян условия, а замысел задачи.

Сравни строки: различаются они ровно в двух местах — здесь на П2 и П6. Спросили «какие номера могут соответствовать» этой паре — ответ 26.

Спросили про дорогу, которой эта пара не касается, — ответ одинаков по любой из строк, бери любую.

0Не напечаталось ничего

Такого не бывает: раз задачу составили, расстановка существует. Значит, схема или таблица переписаны с ошибкой. Ищи по порядку:

пар в graph и в table должно быть поровну;
букв в letters — столько же, сколько кружков на схеме;
номера в table не больше числа пунктов;
перечитай таблицу построчно: чаще всего теряется одна клетка.

Пустой вывод — это не поломка, а подсказка: данные переписаны неверно. При решении на бумаге такой подсказки нет.

шаблон целиком

Шаблон, который набирают на экзамене

from itertools import *

# 1. схема: пары соединённых букв
graph = ['АГ', 'ГБ', 'БВ', 'ВЖ', 'ЖЕ', 'ЕА', 'ДА', 'ДБ', 'ЕД']
# 2. таблица: непустые клетки выше диагонали
table = [(1,2), (1,5), (1,7), (2,5), (2,6), (3,4), (3,5), (3,7), (4,6)]
# 3. буквы со схемы
letters = 'АБВГДЕЖ'

# эти два числа обязаны совпасть
print(len(graph), len(table))

for p in permutations(letters):
    p = ''.join(p)
    ok = True
    for a, b in table:
        x = p[a-1]
        y = p[b-1]
        if x + y not in graph and y + x not in graph:
            ok = False
            break
    if ok:
        print(p)

3

строки меняются от задачи к задаче:
graph, table, letters

Всё остальное

переписывается без единой правки. Ни длин, ни вопроса задачи в коде нет — он ищет только соответствие. Значит, годится для любой формулировки задания 1.

памятка

Порядок действий

Выпиши линии схемыпарами букв — в graph
Выпиши непустые клеткипарами номеров — в table, только выше диагонали
Впиши буквы схемыв letters
Запусти и прочитай словопервая буква — П1, вторая — П2, и так далее
Подпиши номера на схемеи дальше решай как обычно

Программа отвечает на один вопрос: кто есть кто. Ответ на вопрос задачи — по-прежнему твой.