Информатик: Помощник с нейросетью онлайн

Решение

Это типичная задача на динамическое программирование или на рекуррентную формулу.

Нужно посчитать количество двоичных строк длины 12, в которых нигде не встречается подстрока 11.

Идея

Обозначим f(n) — количество допустимых строк длины n.

Рассмотрим последнюю цифру:

• если строка оканчивается на 0, то перед ней может быть любая допустимая строка длины n-1;
• если строка оканчивается на 1, то перед ней обязательно стоит 0, значит последние две цифры — 01, а до них может быть любая допустимая строка длины n-2.

Отсюда:

f(n) = f(n-1) + f(n-2)

Это очень похоже на числа Фибоначчи.

База

• f(1) = 2 → строки: 0, 1
• f(2) = 3 → строки: 00, 01, 10

Дальше считаем по формуле:

f(3) = 5
f(4) = 8
f(5) = 13
f(6) = 21
f(7) = 34
f(8) = 55
f(9) = 89
f(10) = 144
f(11) = 233
f(12) = 377

Ответ

Количество таких строк длины 12 равно 377.

Как это записать в решении ЕГЭ

Можно кратко так:

Пусть f(n) — число двоичных строк длины n без двух единиц подряд. Если строка оканчивается на 0, получаем f(n-1) вариантов. Если строка оканчивается на 1, то перед ней должен стоять 0, значит получаем f(n-2) вариантов. Следовательно, f(n)=f(n-1)+f(n-2). При f(1)=2, f(2)=3 получаем f(12)=377.

Если хочешь проверить программно

n = 12
f = [0] * (n + 1)
f[1] = 2
f[2] = 3

for i in range(3, n + 1):
 f[i] = f[i - 1] + f[i - 2]

print(f[12]) # 377

Полезный прием

Если в задаче есть фраза вроде:

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

то почти всегда стоит попробовать:

1. разбить по последнему символу;
2. получить рекуррентную формулу;
3. посчитать вручную или через таблицу.

Короткий ответ

Для невзвешенного лабиринта нужен BFS (поиск в ширину). Он гарантированно находит кратчайший путь по числу шагов, если все ходы стоят одинаково.

Идея

Мы рассматриваем каждую клетку как вершину графа:

• можно идти вверх, вниз, влево, вправо;
• стены # проходить нельзя;
• старт S, финиш F.

Что делает BFS

• сначала посещает все клетки на расстоянии 1;
• потом на расстоянии 2;
• потом 3 и так далее.

Поэтому первый раз, когда мы дошли до F, путь уже кратчайший.

Как восстановить маршрут

Нужно запоминать, из какой клетки мы пришли в каждую новую клетку.

Для этого удобно хранить:

• dist[x][y] — расстояние от старта;
• prev[x][y] — предыдущая клетка на кратчайшем пути.

Когда нашли финиш, идем назад по prev, а потом разворачиваем список.

Пример кода на Python

from collections import deque

def bfs_path(grid):
 n = len(grid)
 m = len(grid[0])

 # Ищем старт и финиш
 for i in range(n):
 for j in range(m):
 if grid[i][j] == 'S':
 start = (i, j)
 if grid[i][j] == 'F':
 finish = (i, j)

 dist = [[-1] * m for _ in range(n)]
 prev = [[None] * m for _ in range(n)]

 q = deque()
 q.append(start)
 dist[start[0]][start[1]] = 0

 directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

 while q:
 x, y = q.popleft()

 if (x, y) == finish:
 break

 for dx, dy in directions:
 nx, ny = x + dx, y + dy

 if 0 <= nx < n and 0 <= ny < m:
 if grid[nx][ny] != '#' and dist[nx][ny] == -1:
 dist[nx][ny] = dist[x][y] + 1
 prev[nx][ny] = (x, y)
 q.append((nx, ny))

 if dist[finish[0]][finish[1]] == -1:
 return None, None

 # Восстановление пути
 path = []
 cur = finish
 while cur is not None:
 path.append(cur)
 cur = prev[cur[0]][cur[1]]

 path.reverse()
 return dist[finish[0]][finish[1]], path

grid = [
 "S..#",
 ".#..",
 "..#F"
]

length, path = bfs_path(grid)

print("Длина пути:", length)
print("Маршрут:", path)

Как это работает на примере

Если ответ такой:

Длина пути: 5
Маршрут: [(0, 0), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2)]

это значит, что от S до F нужно сделать 5 шагов.

Важные моменты для ЕГЭ и задач

• BFS подходит только для невзвешенного графа.
• Если у ребер есть веса, нужен уже Дейкстра.
• Для восстановления пути всегда сохраняй prev.
• Если нужно только расстояние, достаточно dist.

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

• BFS — кратчайший путь в лабиринте без весов.
• Очередь (deque) — обязательна.
• dist — чтобы не ходить по клеткам повторно.
• prev — чтобы восстановить маршрут.

Если хочешь, я могу еще показать, как решать такую задачу на ЕГЭ в виде таблицы без кода.