Задание 5 ЕГЭ по информатике

1. 1. N=5 — нечётное. Двоичная запись: 101.
2. 2. Приписываем справа 1 (число нечётное): 1011.
3. 3. Переводим обратно: 1·8+0·4+1·2+1·1 = 11.
4. 4. Результат R = 11.

Ответ: R = 11

1. 1. Шаг 1. «Формально исполнить» значит не думать наперёд, а честно выполнять команды и записывать состояние. Заводим таблицу из двух столбцов: текущее число и номер шага. Ничего в уме не держим — вся суть навыка именно в этом.
2. 2. Шаг 2. Начало: число 6, сделано 0 шагов. Проверяем условие цикла: 6 не равно 1, значит цикл выполняется.
3. 3. Шаг 3. Число 6 чётное → делим пополам: 3, шагов 1. Проверка: 3 не равно 1, продолжаем.
4. 4. Шаг 4. Число 3 нечётное → 3 × 3 + 1 = 10, шагов 2. Здесь и проявляется характер такого исполнителя: число не только уменьшается, но иногда растёт, и предсказать длину пути заранее невозможно.
5. 5. Шаг 5. 10 чётное → 5, шагов 3. 5 нечётное → 5 × 3 + 1 = 16, шагов 4. 16 чётное → 8, шагов 5.
6. 6. Шаг 6. 8 чётное → 4, шагов 6. 4 чётное → 2, шагов 7. 2 чётное → 1, шагов 8. Условие цикла нарушено: число равно 1, исполнитель останавливается. Ответ: 8 шагов, вся цепочка — 6, 3, 10, 5, 16, 8, 4, 2, 1.
7. 7.

   Шаг 7. Та же трассировка программой:

   ```python

   chislo = 6
   shagov = 0
   put = [chislo]
   while chislo != 1:
       if chislo % 2 == 0:
           chislo = chislo // 2
       else:
           chislo = 3 * chislo + 1
       shagov += 1
       put.append(chislo)

   print(shagov, put) ```

   Вывод: 8 [6, 3, 10, 5, 16, 8, 4, 2, 1] — ровно наша таблица.

8. 8. Шаг 8. Обратите внимание на целочисленное деление //. Обычное деление / вернуло бы 3.0 — вещественное число, и уже на следующем сравнении chislo % 2 == 0 начнутся сюрпризы, а в выводе появятся точки. В задачах про исполнителей над целыми числами / не используют никогда.
9. 9. Шаг 9. Второе, что стоит заметить: список put не нужен для ответа, он нужен для проверки себя. Распечатанная цепочка позволяет мгновенно сверить программу с ручной трассировкой. Если бы в коде стояло 3 * chislo - 1, расхождение вылезло бы на втором элементе, а не после получаса поисков.
10. 10. Шаг 10. И главный вывод про формальное исполнение: исполнитель не понимает смысла. Он не знает, что «цепочка когда-нибудь дойдёт до единицы»; он просто проверяет условие и выполняет команду. Ваша задача при трассировке — стать таким же: выполнять буквально и записывать каждое состояние.

Ответ: 8 шагов

1. 1.

   Шаг 1. Переводим условие в функцию дословно, по пунктам:

   ```python

   def preobrazovat(n):
       zapis = bin(n)[2:]
       if n % 3 == 0:
           zapis = zapis + '00'
       else:
           zapis = zapis + '11'
       return int(zapis, 2)

   n = 1
   while preobrazovat(n) < 200:
       n += 1

   print(n, preobrazovat(n)) ```

2. 2. Шаг 2. Разберём две незнакомые конструкции. Функция bin(n) возвращает строку вида '0b1101', и срез [2:] отрезает префикс 0b, оставляя чистую двоичную запись. Обратно строку в число переводит int(zapis, 2) — второй аргумент говорит, что запись читается в двоичной системе. Эти две строчки закрывают всю линию 5 и половину линии 14.
3. 3. Шаг 3. Важнейшая деталь: кратность проверяется у исходного числа N, а не у его записи и не у результата. В условии написано «если N кратно 3» — значит, в коде n % 3 == 0. Подмена проверяемого объекта — самая частая ошибка в этой линии, и она даёт правдоподобный неверный ответ, который не вызывает подозрений.
4. 4. Шаг 4. Проследим первые значения. N = 1: запись 1, единица не кратна трём → дописываем 11, получается 111 = 7. Меньше 200, идём дальше. N = 2: запись 10 → 1011 = 11. N = 3: запись 11, тройка кратна трём → 1100 = 12.
5. 5. Шаг 5. N = 4: 100 → 10011 = 19. N = 5: 101 → 10111 = 23. N = 6: 110, кратно трём → 11000 = 24. Заметна закономерность: дописывание двух разрядов умножает число примерно на четыре, и добавка 11 даёт на 3 больше, чем добавка 00.
6. 6. Шаг 6. Дальше перебор идёт быстро: N = 16 даёт 67, N = 25 даёт 103, N = 40 даёт 163. Всё ещё меньше 200, цикл продолжается.
7. 7. Шаг 7. N = 49: запись 110001, 49 не кратно трём → 11000111 = 199. Досадно близко, но условие «не меньше 200» не выполнено, и цикл делает ещё один шаг.
8. 8. Шаг 8. N = 50: запись 110010 → 11001011 = 203. Условие выполнено, цикл останавливается, программа печатает 50 203. Ответ — 50.
9. 9. Шаг 9. Пара 49 и 50 показывает, зачем нужен перебор: граница проходит между соседними числами, и никакой «оценкой сверху» её не угадать. Заодно видно, почему нельзя перебирать через десять — пропустили бы ровно то значение, которое требуется.
10. 10. Шаг 10. Что менять, если спросят иначе? «Наибольшее N, при котором R меньше 200» — перебираем for n in range(1, 1000) и запоминаем последнее подошедшее (это будет 49). «R — степень двойки» — меняется только условие в while. Сам перевод алгоритма в функцию остаётся тем же, и именно поэтому его стоит писать аккуратно: он переиспользуется во всех вариантах формулировки.

Ответ: 50 (при N = 49 получается 199 — на единицу меньше порога)

1. 1. Шаг 1. У исполнителя Робот среда — клетчатое поле со стенами, а система команд состоит из перемещений и проверок обстановки вроде «справа свободно». Попытка шагнуть в стену или за край поля называется отказом: исполнитель не выполняет команду и останавливает программу. Цикл «пока свободно» именно для того и нужен, чтобы до отказа не доводить.
2. 2.

   Шаг 2. Запишем поле строками, где точка — свободно, а решётка — стена:

   • • ```python
   • • pole = ['..#.',
   • • '....',
   • • '#...',
   • • '....']

   stroka, stolbec = 0, 0 zakrasheno = {(stroka, stolbec)}

   def svobodno(r, c):
       return 0 <= r < 4 and 0 <= c < 4 and pole[r][c] == '.'

   while svobodno(stroka, stolbec + 1):
       stolbec += 1
       zakrasheno.add((stroka, stolbec))

   while svobodno(stroka + 1, stolbec):
       stroka += 1
       zakrasheno.add((stroka, stolbec))

   print(stroka, stolbec, len(zakrasheno)) ```

3. 3. Шаг 3. Функция svobodno проверяет сразу две вещи: что клетка существует (координаты внутри поля) и что в ней нет стены. Порядок условий важен: если сначала обратиться к pole[r][c], а потом проверять границы, программа упадёт при выходе за край. Python вычисляет and слева направо и до первого ложного — это и спасает.
4. 4. Шаг 4. Множество zakrasheno хранит посещённые клетки. Именно множество, а не счётчик: если Робот пройдёт по клетке дважды, закрашенной она останется одной, а счётчик насчитал бы два. Стартовая клетка добавляется сразу — Робот стоит на ней и закрашивает её.
5. 5. Шаг 5. Трассируем первый цикл. Робот в (0, 0). Справа клетка (0, 1) — точка, свободно → шаг вправо, теперь (0, 1), закрашено две клетки.
6. 6. Шаг 6. Снова проверка: справа клетка (0, 2) — там стена. Условие ложно, первый цикл заканчивается. Робот остался в (0, 1), и это ключевой момент: цикл «пока» остановился сам, отказа не произошло. Если бы вместо цикла стояли три команды «вправо», третья вызвала бы отказ.
7. 7. Шаг 7. Второй цикл. Снизу от (0, 1) клетка (1, 1) — свободна → (1, 1), закрашено три. Снизу (2, 1) — свободна → (2, 1), закрашено четыре. Заметьте: стена (2, 0) находится слева от этой клетки и никак не мешает — Робот идёт вниз, а не влево.
8. 8. Шаг 8. Снизу (3, 1) — свободна → (3, 1), закрашено пять. Следующая проверка смотрит на строку 4, которой не существует: функция svobodno возвращает ложь по проверке границ. Второй цикл заканчивается.
9. 9. Шаг 9. Итог: Робот в клетке (3, 1) — третья строка сверху, второй столбец слева; закрашено 5 клеток: (0,0), (0,1), (1,1), (2,1), (3,1). Программа печатает 3 1 5.
10. 10. Шаг 10. Чему учит этот разбор. Во-первых, состояние исполнителя — это не только его положение, но и всё, что он изменил в среде (закрашенные клетки). Во-вторых, граница поля ведёт себя как стена, и забыть об этом — классическая ошибка. В-третьих, цикл «пока свободно» — единственный способ написать программу, которая сработает на любом поле, а не только на нарисованном: ровно этого и требуют формулировки вида «программа должна работать при любом расположении стен».

Ответ: Робот в клетке (3, 1), закрашено 5 клеток

1. 1.

   def R(N):
       s = bin(N)[2:]        # двоичная запись без '0b'
       if N % 3 == 0:
           s = s + '00'      # правило условия для чисел, кратных 3
       else:
           s = s + '11'      # правило для всех остальных
       return int(s, 2)      # полученную запись читаем как двоичное число
   # перебираем N по возрастанию и берём первое подходящее
   for N in range(1, 1000):
       if R(N) >= 200:
           print(N)
           break

Ответ: Цикл печатает минимальное N, при котором R(N) ≥ 200