40 задач на Python
Джеймс Девис
Книга призвана помочь читателю развить свои математические навыки, улучшить логическое мышление, освоить использование языка программирования Python для решения задач. Она подходит как для самостоятельного изучения, так и в качестве учебного пособия для студентов и учителей, желающих более глубоко погрузиться в мир языка Python и его приложений с использованием современных инструментов.В книге представлены задачи из разных областей: геометрические, комбинаторные, задачи на вероятности и статистику, логические, арифметические, задачи на движение и скорость и задачи на рекурсию и последовательности.
Джеймс Девис
40 задач на Python
Глава 1: Задачи на логику и сообразительность
1. Задача о пастухе и волках
Условие:
Пастух охраняет стадо овец на лугу. На лугу также находятся волки. Луг можно представить в виде сетки (N \times M) клеток. Каждая клетка может быть либо пустой, либо содержать овцу, либо волка, либо пастуха.
Пастух может двигаться на одну клетку вверх, вниз, влево или вправо (но не по диагонали). Волки также могут двигаться на одну клетку в любом из четырех направлений. В каждом ходу все волки и пастух делают один шаг одновременно. Если волк попадает на клетку с овцой, он съедает овцу. Если волк попадает на клетку с пастухом, волк останавливается, и пастух побеждает в этом раунде.
Ваша задача – написать программу, которая моделирует передвижения пастуха и волков на лугу, чтобы пастух мог спасти как можно больше овец.
Входные данные:
– Размер луга (N \times M)
– Позиции овец, волков и пастуха на лугу
– Количество ходов, которые нужно смоделировать
Выходные данные:
– Позиции всех овец, волков и пастуха после заданного количества ходов
– Количество спасённых овец
Пример входных данных:
5 5
Пастух: 2 2
Овцы: 1 1, 3 3, 4 4
Волки: 0 0, 4 0
Ходы: 5
Пример выхода:
Пастух: 3 3
Овцы: 1 1, 3 3
Волки: 0 1, 4 1
Спасённые овцы: 2
Пояснение:
1. На вход подаются размеры луга (5x5), стартовые позиции пастуха (2,2), овец (1,1), (3,3), (4,4), волков (0,0), (4,0) и количество ходов (5).
2. Программа моделирует передвижение пастуха и волков в течение 5 ходов и выводит финальные позиции и количество спасённых овец.
Примечания:
– Считайте, что пастух и волки могут двигаться на одну клетку в одном направлении за один ход.
– Волки преследуют овец или пастуха, выбирая направление, которое минимизирует расстояние до ближайшей овцы или пастуха.
– Овцы остаются на месте.
– Если несколько волков попадают на одну клетку одновременно, один волк съедает овцу, остальные остаются на этой клетке.
Идея решения задачи о пастухе и волках
1. Представление поля
Представим луг в виде двумерного массива (списка списков). Каждая клетка может содержать одну из следующих сущностей:
– Пустая клетка (`.`)
– Пастух (`P`)
– Овца (`S`)
– Волк (`W`)
2. Чтение и обработка входных данных
Читаем размеры луга, позиции пастуха, овец и волков, а также количество ходов. Инициализируем двумерный массив для представления луга и заполняем его исходными данными.
3. Логика движения
– Пастух движется в направлении ближайшей овцы, чтобы защитить её.
– Можно использовать алгоритм поиска кратчайшего пути, например, алгоритм A* или простейший жадный алгоритм, чтобы определить направление движения пастуха к ближайшей овце.
– Волки движутся в направлении ближайшей овцы или пастуха.
– Для каждого волка определяем кратчайший путь до ближайшей цели и движемся в этом направлении.
– На каждом шагу все волки и пастух совершают по одному движению одновременно. Важно учесть, что сначала нужно рассчитать новые позиции всех сущностей, а затем обновить поле.
4. Обработка столкновений
– Если волк попадает на клетку с овцой, овца съедается.
– Если волк попадает на клетку с пастухом, волк останавливается и считается побеждённым, и пастух побеждает в этом раунде.
5. Моделирование ходов
– Повторяем процесс движения и обновления поля для заданного количества ходов.
– Отслеживаем количество спасённых овец.
6. Вывод результатов
– По завершении всех ходов выводим конечные позиции пастуха, овец и волков.
– Выводим количество спасённых овец.
Пример реализации на Python
```python
from collections import deque
# Чтение входных данных
N, M = map(int, input().split())
pastukh = tuple(map(int, input().split()))
sheep_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]
wolf_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]
K = int(input())
# Инициализация поля
field = [['.' for _ in range(M)] for _ in range(N)]
field[pastukh[0]][pastukh[1]] = 'P'
for x, y in sheep_positions:
field[x][y] = 'S'
for x, y in wolf_positions:
field[x][y] = 'W'
# Вспомогательные функции
def is_valid(x, y):
return 0 <= x < N and 0 <= y < M
def bfs(start, goals):
queue = deque([start])
visited = set()
visited.add(start)
dist = {start: 0}
while queue:
x, y = queue.popleft()
if (x, y) in goals:
return dist[(x, y)], (x, y)
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if is_valid(nx, ny) and (nx, ny) not in visited:
queue.append((nx, ny))
visited.add((nx, ny))
dist[(nx, ny)] = dist[(x, y)] + 1
return float('inf'), None
# Основная логика движения и моделирования
for _ in range(K):
# Движение пастуха
_, nearest_sheep = bfs(pastukh, sheep_positions)
if nearest_sheep:
px, py = pastukh
sx, sy = nearest_sheep
if px < sx: px += 1
elif px > sx: px -= 1
elif py < sy: py += 1
elif py > sy: py -= 1
pastukh = (px, py)
# Движение волков
new_wolf_positions = []
for wx, wy in wolf_positions:
_, target = bfs((wx, wy), sheep_positions + [pastukh])
if target:
tx, ty = target
if wx < tx: wx += 1
elif wx > tx: wx -= 1
elif wy < ty: wy += 1
elif wy > ty: wy -= 1
new_wolf_positions.append((wx, wy))
wolf_positions = new_wolf_positions
# Обновление поля и проверка столкновений
field = [['.' for _ in range(M)] for _ in range(N)]
field[pastukh[0]][pastukh[1]] = 'P'
new_sheep_positions = []
for x, y in sheep_positions:
if (x, y) not in wolf_positions:
field[x][y] = 'S'
new_sheep_positions.append((x, y))
sheep_positions = new_sheep_positions
for x, y in wolf_positions:
if field[x][y] == 'P':
field[x][y] = 'P'
else:
field[x][y] = 'W'
# Вывод результатов
print(f"Пастух: {pastukh[0]} {pastukh[1]}")
print("Овцы:", ', '.join(f"{x} {y}" for x, y in sheep_positions))
print("Волки:", ', '.join(f"{x} {y}" for x, y in wolf_positions))
print(f"Спасённые овцы: {len(sheep_positions)}")
```
Давайте разберем код более подробно на каждом этапе.
Чтение входных данных
```python
N, M = map(int, input().split())
pastukh = tuple(map(int, input().split()))
sheep_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]
wolf_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]
K = int(input())
```
1. `N, M = map(int, input().split())`: Считываем размеры луга (количество строк и столбцов).
2. `pastukh = tuple(map(int, input().split()))`: Считываем координаты пастуха и сохраняем их как кортеж.
3. `sheep_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]`: Считываем позиции всех овец. Каждая позиция считывается как кортеж координат, и все позиции сохраняются в список.
4. `wolf_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]`: Считываем позиции всех волков аналогично овцам.
5. `K = int(input())`: Считываем количество ходов.
Инициализация поля
```python
field = [['.' for _ in range(M)] for _ in range(N)]
field[pastukh[0]][pastukh[1]] = 'P'
for x, y in sheep_positions:
field[x][y] = 'S'
for x, y in wolf_positions:
field[x][y] = 'W'
1. `field = [['.' for _ in range(M)] for _ in range(N)]`: Создаем двумерный массив, представляющий луг, заполняя его пустыми клетками (`.`).
2. `field[pastukh[0]][pastukh[1]] = 'P'`: Размещаем пастуха на лугу в начальной позиции.
3. `for x, y in sheep_positions: field[x][y] = 'S'`: Размещаем овец на их начальных позициях.
4. `for x, y in wolf_positions: field[x][y] = 'W'`: Размещаем волков на их начальных позициях.
Вспомогательные функции
Проверка валидности координат
```python
def is_valid(x, y):
return 0 <= x < N and 0 <= y < M
```
1. `def is_valid(x, y): return 0 <= x < N and 0 <= y < M`: Функция проверяет, находятся ли координаты в пределах луга. Если координаты выходят за границы, возвращается False, иначе True.
Поиск кратчайшего пути (BFS)
```python
from collections import deque
def bfs(start, goals):
queue = deque([start])
visited = set()
visited.add(start)
dist = {start: 0}
while queue:
x, y = queue.popleft()
if (x, y) in goals:
return dist[(x, y)], (x, y)
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if is_valid(nx, ny) and (nx, ny) not in visited:
queue.append((nx, ny))
visited.add((nx, ny))
dist[(nx, ny)] = dist[(x, y)] + 1
return float('inf'), None
```
1. `from collections import deque`: Импортируем deque для реализации очереди.
2. `def bfs(start, goals):`: Определяем функцию для поиска кратчайшего пути от `start` до ближайшей цели из `goals`.
3. `queue = deque([start])`: Инициализируем очередь с начальной позицией.
4. `visited = set()`: Создаем множество для отслеживания посещённых клеток.
5. `visited.add(start)`: Добавляем начальную позицию в множество посещённых.
6. `dist = {start: 0}`: Инициализируем словарь для хранения расстояний от начальной точки.
7. `while queue: …`: Запускаем цикл, пока есть элементы в очереди.
8. `x, y = queue.popleft()`: Извлекаем текущую позицию из очереди.
9. `if (x, y) in goals: …`: Если текущая позиция является целью, возвращаем расстояние и координаты.
10. `for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: …`: Перебираем все возможные направления движения (вверх, вниз, влево, вправо).
11. `nx, ny = x + dx, y + dy`: Вычисляем новые координаты.
12. `if is_valid(nx, ny) and (nx, ny) not in visited: …`: Если новые координаты валидны и не были посещены, добавляем их в очередь и множество посещённых, обновляем расстояние.
Основная логика движения и моделирования
Основной цикл для моделирования ходов
```python
for _ in range(K):
```
1. `for _ in range(K):`: Запускаем цикл для моделирования каждого хода.
Движение пастуха
```python
_, nearest_sheep = bfs(pastukh, sheep_positions)
if nearest_sheep:
px, py = pastukh
sx, sy = nearest_sheep
if px < sx: px += 1
elif px > sx: px -= 1
elif py < sy: py += 1
elif py > sy: py -= 1
pastukh = (px, py)
1. `_, nearest_sheep = bfs(pastukh, sheep_positions)`: Ищем ближайшую овцу для пастуха.
2. `if nearest_sheep: …`: Если найдена овца, определяем направление движения пастуха.
3. `px, py = pastukh`: Текущие координаты пастуха.
4. `sx, sy = nearest_sheep`: Координаты ближайшей овцы.
5. `if px < sx: px += 1 …`: Если пастух находится левее овцы, он движется вправо. Аналогично для других направлений.
6. `pastukh = (px, py)`: Обновляем координаты пастуха.
Движение волков
```python
new_wolf_positions = []
for wx, wy in wolf_positions:
_, target = bfs((wx, wy), sheep_positions + [pastukh])
if target:
tx, ty = target
if wx < tx: wx += 1
elif wx > tx: wx -= 1
elif wy < ty: wy += 1
elif wy > ty: wy -= 1
new_wolf_positions.append((wx, wy))
wolf_positions = new_wolf_positions
1. `new_wolf_positions = []`: Создаем список для обновленных позиций волков.
2. `for wx, wy in wolf_positions: …`: Перебираем текущие позиции всех волков.
3. `_, target = bfs((wx, wy), sheep_positions + [pastukh])`: Ищем ближайшую цель (овца или пастух) для волка.
4. `if target: …`: Если найдена цель, определяем направление движения волка.
5. `tx, ty = target`: Координаты ближайшей цели.
6. `if wx < tx: wx += 1 …`: Если волк находится левее цели, он движется вправо. Аналогично для других направлений.
7. `new_wolf_positions.append((wx, wy))`: Добавляем обновленные координаты волка в список.
8. `wolf_positions = new_wolf_positions`: Обновляем позиции волков.
Обновление поля и проверка столкновений
```python
field = [['.' for _ in range(M)] for _ in range(N)]
field[pastukh[0]][pastukh[1]] = 'P'
new_sheep_positions = []
for x, y in sheep_positions:
if (x, y) not in wolf_positions:
field[x][y] = 'S'
new_sheep_positions.append((x, y))
sheep_positions = new_sheep_positions
for x, y in wolf_positions:
if field[x][y] == 'P':
field[x][y] = 'P'
else:
field[x][y] = 'W'
1. `field = [['.' for _ in range(M)] for _ in range(N)]`: Пересоздаем поле, заполняя его пустыми клетками.
2. `field[pastukh[0]][pastukh[1]] = 'P'`: Обновляем позицию пастуха на поле.
3. `new_sheep_positions = []`: Создаем список для обновленных позиций овец.
4. `for x, y in sheep_positions: …`: Перебираем текущие позиции овец.
5. `if (x, y) not in wolf_positions: …`: Если овца не съедена волком, добавляем её в обновленное поле
В данной задаче была успешно смоделирована ситуация на лугу, где пастух старается спасти овец от волков. Мы рассмотрели основные этапы решения задачи, включая чтение входных данных, инициализацию игрового поля, реализацию вспомогательных функций для проверки валидности координат и поиска кратчайшего пути, а также логику движения пастуха и волков.
2. Пересечения кругов
Условие задачи: Даны координаты центров и радиусы двух кругов на плоскости. Необходимо определить, пересекаются ли эти круги.
Входные данные:
– Четыре вещественных числа: ( x_1, y_1, r_1, r_2 )
– ( x_1, y_1 ) – координаты центра первого круга.
– ( r_1 ) – радиус первого круга.
– ( x_2, y_2 ) – координаты центра второго круга.
– ( r_2 ) – радиус второго круга.
Выходные данные:
– Одно слово "YES", если круги пересекаются, и "NO" в противном случае.
Примеры:
Пример 1:
Входные данные: 0 0 5 3 0 0 3
Выходные данные: YES
Пример 2:
Входные данные: 0 0 2 6 0 0 3
Выходные данные: NO
Решение: Для того чтобы определить, пересекаются ли два круга, можно воспользоваться следующими правилами:
1. Вычислим расстояние ( d ) между центрами кругов.
2. Если ( d ) меньше суммы радиусов ( r_1 ) и ( r_2 ) и больше разности радиусов ( |r_1 – r_2| ), то круги пересекаются.
3. Если ( d ) равно сумме радиусов, то круги касаются друг друга внешне.
4. Если ( d ) равно разности радиусов, то круги касаются друг друга внутренне.
5. Во всех других случаях круги не пересекаются.
Формула для вычисления расстояния между центрами кругов:
[ d = \sqrt{(x_2 – x_1)^2 + (y_2 – y_1)^2} \]
Псевдокод:
ввод x1, y1, r1, x2, y2, r2
вычислить d = sqrt((x2 – x1)^2 + (y2 – y1)^2)
если d <= r1 + r2 и d >= |r1 – r2| тогда
вывод "YES"
иначе
вывод "NO"
```
Псевдокод – это упрощенный язык описания алгоритмов, который используется для представления логики решения задачи без привязки к конкретному языку программирования. Он обычно используется для описания шагов алгоритма на естественном языке, что облегчает понимание и написание кода.
В псевдокоде часто используются ключевые слова, похожие на те, что применяются в реальных языках программирования, такие как "если", "то", "цикл", "вывод" и т. д. Однако синтаксис псевдокода более гибкий и менее строгий, чем у конкретного языка программирования.
Псевдокод позволяет описать алгоритм более наглядно и понятно, не углубляясь в детали реализации на определенном языке. Он используется в образовании, при разработке алгоритмов и при описании решения задач до того, как приступить к программированию на конкретном языке.
Реализация на Python:
```python
import math
# Чтение входных данных
x1, y1, r1 = map(float, input().split())
x2, y2, r2 = map(float, input().split())
# Вычисление расстояния между центрами кругов
d = math.sqrt((x2 – x1) ** 2 + (y2 – y1) ** 2)
# Проверка пересечения кругов
if d <= r1 + r2 and d >= abs(r1 – r2):
print("YES")
else:
print("NO")
```
Эта задача помогает понять, как использовать простую геометрию и математические формулы для определения пересечения геометрических фигур. Решение данной задачи иллюстрирует применение расстояний и неравенств для определения условий пересечения кругов.
3. Задача о пяти домиках
Условие задачи: На улице расположены пять домов, пронумерованных от 1 до 5. Каждый дом занят каким-то жителем. Дома расположены вдоль прямой, и между некоторыми соседними домами есть заборы. Необходимо определить минимальное количество переездов, чтобы жители домов удовлетворили следующим условиям:
1. Житель дома 1 не должен жить с жителем дома 2.
2. Житель дома 2 не должен жить с жителем дома 3.
3. Житель дома 3 не должен жить с жителем дома 4.
4. Житель дома 4 не должен жить с жителем дома 5.
Каждый переезд стоит одну единицу. В начальный момент времени все жители уже живут в соответствии с условиями задачи.
Входные данные:
– Пять чисел от 1 до 5, представляющих номера домов, в которых в настоящее время живут жители.
Выходные данные:
– Одно целое число – минимальное количество переездов, которое необходимо совершить.
Примеры:
Пример 1:
Входные данные: 1 2 3 4 5
Выходные данные: 0
Пример 2:
Входные данные: 1 3 2 4 5
Выходные данные: 1
Решение:
Для решения этой задачи мы можем проанализировать текущее расположение жителей и определить, сколько переездов необходимо, чтобы выполнить все условия. Мы можем выявить промежутки, где два соседних дома заселены, и для каждого такого промежутка определить минимальное количество переездов, которое необходимо совершить.
Псевдокод:
ввод номера_домов
подсчет_переездов = 0
если номера_домов[0] == 1 и номера_домов[1] == 2, тогда подсчет_переездов += 1
если номера_домов[1] == 2 и номера_домов[2] == 3, тогда подсчет_переездов += 1
если номера_домов[2] == 3 и номера_домов[3] == 4, тогда подсчет_переездов += 1
если номера_домов[3] == 4 и номера_домов[4] == 5, тогда подсчет_переездов += 1
вывод подсчет_переездов
Реализация на Python:
```python
# Чтение входных данных
house_numbers = list(map(int, input().split()))
# Подсчет минимального количества переездов
moves_count = 0
for i in range(4):
if house_numbers[i] == i + 1 and house_numbers[i + 1] == i + 2:
moves_count += 1
# Вывод результата
print(moves_count)
```
Эта задача демонстрирует, как использовать простую логику для определения минимального количества операций, необходимых для достижения определенной цели. Решение основано на анализе текущего расположения жителей и выявлении промежутков, где требуются переезды для выполнения условий задачи.
4. Логическая цепочка чисел
Условие задачи: Дана последовательность чисел. Необходимо определить, является ли эта последовательность логической цепочкой. Логическая цепочка – это последовательность чисел, где каждое последующее число в последовательности является результатом выполнения определенной логической операции над предыдущим числом.
Входные данные:
– Последовательность целых чисел, разделенных пробелами.
Выходные данные:
– Если последовательность является логической цепочкой, вывести "YES". Иначе вывести "NO".
Примеры:
Пример 1:
Входные данные: 1 3 6 10 15
Выходные данные: YES
Пример 2:
Входные данные: 2 4 7 12 18
Выходные данные: NO
Решение:
Для определения, является ли последовательность логической цепочкой, мы можем проверить, выполняется ли для каждой пары чисел в последовательности логическое условие, которое связывает предыдущее и следующее число. Например, в логической цепочке каждое следующее число может быть равно предыдущему числу плюс индекс текущего числа в последовательности.
Псевдокод:
ввод последовательности_чисел
для каждого i от 1 до длины(последовательности_чисел) – 1:
если последовательность_чисел[i] != последовательность_чисел[i – 1] + i:
вывод "NO"
завершить выполнение
вывод "YES"
Реализация на Python:
```python
# Чтение входных данных
sequence = list(map(int, input().split()))
# Проверка на логическую цепочку
for i in range(1, len(sequence)):
if sequence[i] != sequence[i – 1] + i:
print("NO")
break
else:
print("YES")
```
Эта задача иллюстрирует способ проверки последовательности чисел на соответствие логической цепочке. Мы можем пройтись по всей последовательности и проверить выполнение условия для каждой пары чисел. Если условие не выполняется хотя бы для одной пары чисел, мы можем сразу вывести "NO".
5. Тайна древнего лабиринта
Условие задачи: Группа исследователей отправилась исследовать древний лабиринт, о котором ходят легенды. Они обнаружили, что лабиринт состоит из комнат, соединенных таинственными проходами. Каждая комната имеет уникальный номер, а проходы между комнатами двунаправленные. Они обнаружили, что вход в лабиринт находится в комнате с номером 1, а выход – в комнате с номером N.
Каждый проход имеет определенную стоимость прохождения, которая может быть как положительной, так и отрицательной. Исследователи хотят найти путь с минимальной суммарной стоимостью прохождения из комнаты 1 в комнату N.
Напишите программу, которая поможет исследователям найти минимальную стоимость прохождения лабиринта.
Входные данные:
– Первая строка содержит два целых числа: N (2 <= N <= 10^5) – количество комнат, и M (1 <= M <= 2*10^5) – количество проходов между комнатами.
– Следующие M строк содержат описание проходов. Каждая строка содержит три целых числа: a, b и w (1 <= a, b <= N, -10^3 <= w <= 10^3), где a и b – номера комнат, соединенных проходом, а w – стоимость прохождения этого прохода.
Выходные данные:
– Одно целое число – минимальная суммарная стоимость прохождения из комнаты 1 в комнату N. Если путь не существует, вывести -1.
Примеры:
Пример 1:
Входные данные:
5 7
1 2 4
1 3 2
2 3 5
2 4 10
3 4 -3
3 5 3
4 5 4
Выходные данные: 6
Пример 2:
Входные данные:
3 2
1 2 1
2 3 1
Выходные данные: 2
Решение:
Для нахождения минимальной суммарной стоимости прохождения лабиринта из комнаты 1 в комнату N мы можем воспользоваться алгоритмом поиска кратчайшего пути в графе. Мы будем использовать алгоритм Дейкстры для нахождения кратчайшего пути от вершины 1 до вершины N.
Псевдокод:
ввод N, M
инициализация графа G
для каждого i от 1 до M:
ввод a, b, w
добавить ребро (a, b) со стоимостью w в граф G
вызвать алгоритм Дейкстры для поиска кратчайшего пути от вершины 1 до вершины N в графе G
вывод результат
Реализация на Python:
```python
import heapq
def dijkstra(graph, start, end):
pq = [(0, start)]
distances = {v: float('inf') for v in graph}
distances[start] = 0
while pq:
dist, node = heapq.heappop(pq)
if node == end:
return dist
if dist > distances[node]:
continue
for neighbor, weight in graph[node]:
if (new_dist := dist + weight) < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return -1
# Чтение входных данных
N, M = map(int, input().split())
graph = {i: [] for i in range(1, N + 1)}
for _ in range(M):
a, b, w = map(int, input().split())
graph[a].append((b, w))
graph[b].append((a, w))
# Вызов алгоритма Дейкстры для нахождения кратчайшего пути
min_cost = dijkstra(graph, 1, N)
# Вывод результата
print(min_cost)
```
Эта задача демонстрирует применение алгоритма Дейкстры для нахождения минимального пути в графе. Мы строим граф, где вершинами являются комнаты, а ребрами – проходы между комнатами с их стоимостью прохождения. Затем мы вызываем алгоритм Дейкстры для нахождения кратчайшего пути от комнаты 1 до комнаты N.
Глава 2: Задачи на числа и арифметику
1. Загадка о числовых ребусах
Условие задачи: Для решения числовых ребусов требуется найти, какие буквы представляют собой какие цифры. Каждая буква соответствует уникальной цифре от 0 до 9. Задача состоит в том, чтобы найти такие значения для каждой буквы, чтобы выполнялось правило "одна буква – одна цифра", а также чтобы все равенства в ребусе были верны.
Пример:
Ребус: SEND + MORE = MONEY
Возможное решение: 9567 + 1085 = 10652
Входные данные: Ребус в виде строки, в которой могут быть использованы буквы латинского алфавита в верхнем регистре и знаки арифметических операций (+, -, *, /), а также пробелы.
Выходные данные: Вывести решение ребуса в виде равенства, где буквы заменены на соответствующие им цифры.
Пример:
Входные данные: SEND + MORE = MONEY
Выходные данные: 9567 + 1085 = 10652
Замечание: В решении ребуса необходимо учитывать, что ведущие нули запрещены, и каждая буква соответствует уникальной цифре.
Для решения задачи о числовых ребусах можно использовать метод перебора всех возможных комбинаций цифр для каждой буквы, учитывая правила замены букв на цифры и удовлетворяя условиям ребуса.
План решения:
1. Идентификация уникальных букв: Необходимо определить все уникальные буквы, которые встречаются в ребусе. Это поможет определить количество букв, для которых нужно найти соответствующие им цифры.
2. Перебор всех возможных комбинаций: Для каждой буквы нужно перебрать все возможные цифры от 0 до 9. Можно использовать рекурсивную функцию для генерации всех возможных комбинаций.
3. Проверка условий ребуса: Для каждой комбинации цифр нужно проверить, удовлетворяют ли они условиям ребуса. Например, сумма двух чисел должна давать третье число.
4. Вывод решения: Если найдены цифры, удовлетворяющие условиям ребуса, необходимо вывести их вместе с соответствующими буквами, образуя равенство.
5. Оптимизация: Можно использовать различные оптимизации, такие как исключение неподходящих комбинаций на ранних этапах, чтобы ускорить поиск решения.
Один из возможных способов решения задачи о числовых ребусах на основе предложенного плана:
```python
# Функция для проверки, что цифры в числе уникальны
def are_digits_unique(num):
return len(set(num)) == len(num)
# Функция для решения числового ребуса
def solve_rebus(rebus):
# Извлекаем уникальные буквы из ребуса
unique_chars = set(char for char in rebus if char.isalpha())
# Генерируем все возможные комбинации цифр для уникальных букв
for digits in itertools.permutations('0123456789', len(unique_chars)):
digits_str = ''.join(digits)
# Проверяем, что ведущие нули отсутствуют и цифры уникальны
if digits_str[0] != '0' and are_digits_unique(digits_str):
# Заменяем буквы на соответствующие цифры в ребусе
rebus_with_digits = rebus.translate(str.maketrans({char: digit for char, digit in zip(unique_chars, digits_str)}))
# Разделяем ребус на левую и правую части
left, right = rebus_with_digits.split('=')
# Проверяем, удовлетворяет ли решение ребусу
if eval(left) == eval(right):
return rebus_with_digits
return None
# Пример использования
rebus = "SEND + MORE = MONEY"
solution = solve_rebus(rebus)
if solution:
print(solution)
else:
print("Решение не найдено.")
```
Этот код генерирует все возможные комбинации цифр для уникальных букв в ребусе, заменяет буквы на соответствующие цифры в ребусе и проверяет, удовлетворяет ли полученное выражение условиям ребуса. Если находится решение, оно выводится на экран.
Объяснения к коду:
1. Функция `are_digits_unique`:
– Эта функция принимает строку `num`, представляющую число в виде строки.
– Внутри функции используется `set`, чтобы преобразовать строку в множество уникальных символов.
– Функция возвращает `True`, если количество символов в строке `num` совпадает с количеством уникальных символов, что означает, что все цифры в числе уникальны. В противном случае функция возвращает `False`.
2. Функция `solve_rebus`:
– Эта функция принимает строку `rebus`, представляющую собой числовой ребус.
– Она начинается с извлечения уникальных букв из ребуса с помощью функции `set` и условия `char.isalpha()`. Таким образом, `unique_chars` содержит все уникальные буквы, встречающиеся в ребусе.
– Затем функция перебирает все возможные перестановки цифр от 0 до 9 с помощью функции `itertools.permutations`, указывая количество цифр, соответствующее количеству уникальных букв в ребусе.
– Для каждой перестановки цифр функция проверяет, что ведущий ноль отсутствует, вызывая `digits_str[0] != '0'`, и что все цифры уникальны, вызывая функцию `are_digits_unique`.
– Если эти условия выполнены, функция заменяет буквы на соответствующие цифры в ребусе с помощью метода `str.translate` и словаря, созданного с помощью `zip`.
– Затем ребус разбивается на левую и правую части с помощью метода `split('=')`.
– После этого проверяется, является ли результат левой части равенства (`eval(left)`) равным результату правой части (`eval(right)`).
– Если это так, то функция возвращает ребус с замененными буквами на цифры. Если не найдено ни одного решения, функция возвращает `None`.
3. Пример использования:
– В примере использования задается ребус `"SEND + MORE = MONEY"`.
– Функция `solve_rebus` вызывается с этим ребусом.
– Если найдено решение, оно выводится на экран. Если решение не найдено, выводится сообщение "Решение не найдено."
2. Магические квадраты
Описание задачи: Магический квадрат – это квадратная матрица размером (n \times n), заполненная числами от 1 до (n^2) таким образом, что суммы чисел в каждой строке, каждом столбце и обеих диагоналях равны.
Ваша задача – написать программу, которая проверяет, является ли данная матрица магическим квадратом.
Формат ввода:
– В первой строке задается одно целое число (n) ((1 leq n leq 100)) – размерность матрицы.
– В следующих (n) строках содержится по (n) целых чисел, разделенных пробелами, – элементы матрицы.
Формат вывода:
– Выведите `YES`, если матрица является магическим квадратом.
– Выведите `NO` в противном случае.
Пример 1:
Ввод:
3
8 1 6
3 5 7
4 9 2
Вывод: YES
Пример 2:
Ввод:
3
2 7 6
9 5 1
4 3 8
Вывод: NO
Пример 3:
Ввод:
2
1 2
3 4
Вывод: NO
Решение:
1. Считать размерность матрицы (n) и её элементы.
2. Проверить, что все числа от 1 до (n^2) присутствуют в матрице.
3. Вычислить сумму первой строки (или любого другого ряда) как эталонную сумму.
4. Проверить, что суммы всех строк, столбцов и диагоналей равны эталонной сумме.
5. Вывести результат проверки.
Пример кода на Python:
```python
def is_magic_square(matrix):
n = len(matrix)
# Проверка, что все числа от 1 до n^2 присутствуют
all_numbers = set(range(1, n*n + 1))
numbers_in_matrix = set(num for row in matrix for num in row)
if all_numbers != numbers_in_matrix:
return False
# Вычисление эталонной суммы
magic_sum = sum(matrix[0])
# Проверка строк
for row in matrix:
if sum(row) != magic_sum:
return False
# Проверка столбцов
for col in range(n):
if sum(matrix[row][col] for row in range(n)) != magic_sum:
return False
# Проверка диагоналей
if sum(matrix[i][i] for i in range(n)) != magic_sum:
return False
if sum(matrix[i][n-i-1] for i in range(n)) != magic_sum:
return False
return True
# Чтение данных
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
# Проверка и вывод результата
if is_magic_square(matrix):
print("YES")
else:
print("NO")
```
Этот код считывает входные данные, проверяет, является ли матрица магическим квадратом, и выводит соответствующий результат.
Подробное объяснение кода проверки магического квадрата
Шаг 1: Считывание размерности матрицы и её элементов
– Код: `n = int(input())`
– Здесь используется функция `input()` для чтения входного значения, представляющего размерность матрицы. Функция `int()` преобразует строку в целое число.
– Код: `matrix = [list(map(int, input().split())) for _ in range(n)]`
– Этот код считывает ( n ) строк, каждая из которых содержит ( n ) чисел.
– `input().split()` считывает строку и разбивает её по пробелам, возвращая список строк.
– `map(int, …)` преобразует каждую строку в целое число.
– `list(…)` собирает эти числа в список.
– Внешний цикл `for _ in range(n)` выполняется ( n ) раз, собирая все строки в список списков (матрицу).
Шаг 2: Проверка уникальности чисел от 1 до ( n^2 )
– Код: `all_numbers = set(range(1, n*n + 1))`
– `range(1, n*n + 1)` создает последовательность чисел от 1 до ( n^2 ).
– `set(…)` преобразует эту последовательность в множество для удобства проверки уникальности.
– Код: `numbers_in_matrix = set(num for row in matrix for num in row)`
– Вложенный генератор `num for row in matrix for num in row` проходит по всем элементам матрицы и собирает их в множество `numbers_in_matrix`.
– Эта строка кода проверяет, что все числа от 1 до ( n^2 ) присутствуют в матрице и являются уникальными.
– Код: `if all_numbers != numbers_in_matrix: return False`
– Сравнение множеств `all_numbers` и `numbers_in_matrix`. Если они не равны, то матрица не может быть магическим квадратом, и функция возвращает `False`.
Шаг 3: Вычисление эталонной суммы
– Код: `magic_sum = sum(matrix[0])`
– `sum(matrix[0])` вычисляет сумму чисел в первой строке матрицы.
– Эта сумма принимается за эталонную, с которой будут сравниваться суммы остальных строк, столбцов и диагоналей.
Шаг 4: Проверка сумм строк
– Код: `for row in matrix: if sum(row) != magic_sum: return False`
– Цикл проходит по каждой строке `row` в матрице.
– `sum(row)` вычисляет сумму чисел в текущей строке.
– Если сумма строки не равна `magic_sum`, функция возвращает `False`.
Шаг 5: Проверка сумм столбцов
– Код: `for col in range(n): if sum(matrix[row][col] for row in range(n)) != magic_sum: return False`
– Внешний цикл проходит по каждому столбцу `col`.
– Внутренний генератор `matrix[row][col] for row in range(n)` собирает все элементы столбца.
– `sum(…)` вычисляет сумму элементов текущего столбца.
– Если сумма столбца не равна `magic_sum`, функция возвращает `False`.
Шаг 6: Проверка сумм диагоналей
– Главная диагональ:
– Код:`if sum(matrix[i][i] for i in range(n)) != magic_sum: return False`
– Генератор `matrix[i][i] for i in range(n)` собирает элементы главной диагонали (где индексы строки и столбца равны).
– `sum(…)` вычисляет сумму этих элементов.
– Если сумма главной диагонали не равна `magic_sum`, функция возвращает `False`.
– Побочная диагональ:
– Код: `if sum(matrix[i][n-i-1] for i in range(n)) != magic_sum: return False`
– Генератор `matrix[i][n-i-1] for i in range(n)` собирает элементы побочной диагонали (где сумма индексов строки и столбца равна \( n-1 \)).
– `sum(…)` вычисляет сумму этих элементов.
– Если сумма побочной диагонали не равна `magic_sum`, функция возвращает `False`.
Шаг 7: Вывод результата
– Код: `if is_magic_square(matrix): print("YES") else: print("NO")`
– Если функция `is_magic_square(matrix)` возвращает `True`, программа выводит "YES".
– В противном случае выводится "NO".
Итог
Код последовательно проверяет все необходимые условия для магического квадрата, от уникальности чисел до сумм строк, столбцов и диагоналей. Если все условия выполняются, матрица признается магическим квадратом.
3. Проблемы с делением и умножением
Описание задачи: Напишите программу, которая будет выполнять деление и умножение двух чисел, но с учетом некоторых специальных случаев.
Условия:
1. Если второе число равно нулю, программа должна вывести сообщение "Ошибка: деление на ноль" и завершиться.
2. Если первое число равно нулю, результатом умножения будет 0, независимо от значения второго числа.
3. Если второе число больше первого, программа должна вывести результат деления в виде десятичной дроби с двумя знаками после запятой.
4. В остальных случаях программа должна выполнять деление и умножение обычным образом.
Формат ввода: Два целых числа, разделенных пробелом: (a) и (b) \((-10^9 leq a, b leq 10^9)).
Формат вывода:
– Если второе число равно нулю, вывести сообщение "Ошибка: деление на ноль".
– В остальных случаях вывести результат деления и умножения, учитывая указанные условия.
Примеры:
Ввод: 5 2
Вывод: 10 2.50
Ввод: 0 7
Вывод: 0 0
Ввод: 4 8
Вывод: 0 0.50
Ввод: 3 0
Вывод: Ошибка: деление на ноль
Примечание:
Результат деления и умножения должен выводиться через пробел в том же порядке, в котором они перечислены в формате вывода.
Идея решения этой задачи включает следующие шаги:
1. Считывание двух целых чисел (a) и (b).
2. Проверка, равно ли второе число нулю. Если да, вывести сообщение об ошибке и завершить программу.
3. Проверка, равно ли первое число нулю. Если да, результат умножения будет 0, иначе обычное умножение.
4. Проверка, больше ли второе число первого. Если да, результат деления будет десятичной дробью, иначе обычное деление.
5. Вывод результатов умножения и деления.
Код, который реализует описанную выше идею:
```python
# Чтение входных данных
a, b = map(int, input().split())
# Проверка деления на ноль и вывод ошибки
if b == 0:
print("Ошибка: деление на ноль")
else:
# Проверка на случай, когда первое число равно нулю
if a == 0:
mul_result = 0
else:
mul_result = a * b
# Проверка на случай, когда второе число больше первого
if b > a:
div_result = "{:.2f}".format(a / b)
else:
div_result = a // b
# Вывод результатов
print(mul_result, div_result)
```
Этот код сначала считывает два целых числа, разделенных пробелом. Затем он проверяет, равно ли второе число нулю. Если да, выводится сообщение об ошибке. В противном случае код проверяет, равно ли первое число нулю, и вычисляет результат умножения. После этого он проверяет, больше ли второе число первого, и в зависимости от этого вычисляет результат деления. Наконец, он выводит оба результата в нужном формате.
Давайте разберем подробно каждую часть кода:
1. Чтение входных данных:
```python
a, b = map(int, input().split())
```
– `input()` считывает строку ввода от пользователя.
– `split()` разделяет эту строку на список строк, используя пробел как разделитель.
– `map(int, …)` применяет функцию `int()` к каждой строке списка, преобразуя их в целые числа.
– `a, b = …` присваивает первое и второе числа переменным `a` и `b`.
2. Проверка деления на ноль:
```python
if b == 0:
print("Ошибка: деление на ноль")
```
– Этот блок кода проверяет, равно ли второе число `b` нулю. Если да, выводится сообщение об ошибке "Ошибка: деление на ноль".
3. Проверка случая, когда первое число равно нулю:
```python
if a == 0:
mul_result = 0
else:
mul_result = a * b
```
– Если первое число `a` равно нулю, результат умножения `mul_result` будет 0, потому что любое число, умноженное на ноль, равно нулю.
– В противном случае, результат умножения будет равен `a * b`.
4. Проверка случая, когда второе число больше первого:
```python
if b > a:
div_result = "{:.2f}".format(a / b)
else:
div_result = a // b
```
– Если второе число `b` больше первого `a`, результат деления `div_result` будет десятичной дробью, округленной до двух знаков после запятой.
– В противном случае, результат деления будет целым числом, полученным с помощью оператора целочисленного деления `//`.
5. Вывод результатов:
```python
print(mul_result, div_result)
```
– Этот код выводит результаты умножения и деления, разделенные пробелом, используя функцию `print()`. Если было выброшено исключение, результат деления не будет выводиться.
В задаче реализован алгоритм, который выполняет умножение и деление двух чисел с учетом специальных случаев. Если второе число равно нулю, программа выводит сообщение об ошибке "Ошибка: деление на ноль". В остальных случаях программа выполняет умножение двух чисел и проверяет несколько условий:
1. Если первое число равно нулю, результат умножения будет 0.
2. Если второе число больше первого, результат деления будет десятичной дробью с двумя знаками после запятой.
3. В остальных случаях программа выполняет деление и умножение обычным образом.
После вычислений программа выводит результаты умножения и деления, разделенные пробелом. Такой подход позволяет корректно обрабатывать различные сценарии, включая случаи деления на ноль и особые случаи с числами равными или различающимися по значению.
4. Задача о двух шляпах и трех числах
Описание задачи: Представьте, что перед вами стоит 3 человека, каждый из которых надевает на себя либо красную, либо синюю шляпу. Они не могут видеть цвет своей собственной шляпы, но видят шляпы других.
Ваша задача – написать программу, которая определяет минимальное количество человек, которые могут быть уверены в цвете своей шляпы.
Условия:
1. У каждого человека есть только два варианта цвета шляпы: красный или синий.
2. Люди могут смотреть только вперед, не знают количество людей за собой и не могут общаться друг с другом.
Формат ввода:
– Три целых числа, разделенных пробелом: (a), (b), (c), где (a), (b), (c) – 0 (красная шляпа) или 1 (синяя шляпа), представляющие цвета шляп каждого человека в порядке их стояния.
Формат вывода:
– Одно целое число, представляющее минимальное количество человек, которые могут быть уверены в цвете своей шляпы.
Примеры:
Ввод: 0 0 1
Вывод: 2
Ввод: 1 1 1
Вывод: 0
Ввод: 0 1 0
Вывод: 3
Примечание: В этой задаче каждый человек смотрит на шляпы тех, кто стоит перед ним. Например, первый человек смотрит на шляпы второго и третьего человека, второй человек смотрит на шляпы третьего человека, а третий человек не видит шляп никого.
Решение: Для решения этой задачи нужно взглянуть на последнего человека в очереди и рассмотреть, сколько человек перед ним надели шляпы того же цвета, что и он.
Если количество человек с шляпами такого же цвета, что и шляпа последнего человека, нечетное, то этот последний человек уверен в цвете своей шляпы. В противном случае, он не может быть уверен в цвете своей шляпы.
Следовательно, мы можем рассматривать только последний человек в очереди, и на основе цвета его шляпы решить, уверен он в своем цвете или нет.
Давайте реализуем этот подход в коде.
```python
def min_people_to_be_certain(a, b, c):
# Подсчет количества людей с шляпами того же цвета, что и шляпа последнего человека
count_same_color = sum([a, b, c]) – max(a, b, c)
# Если количество таких людей нечетное, последний человек уверен в цвете своей шляпы
if count_same_color % 2 != 0:
return 0
else:
return 1
# Чтение входных данных
a, b, c = map(int, input().split())
# Вывод результата
print(min_people_to_be_certain(a, b, c))
```
В этом коде функция `min_people_to_be_certain` принимает три целых числа (a), (b) и (c), представляющих цвета шляп каждого человека в очереди. Она сначала считает количество людей с шляпами того же цвета, что и шляпа последнего человека, а затем проверяет, нечетное ли это число. Если да, то последний человек уверен в цвете своей шляпы, и функция возвращает 0, иначе возвращает 1.
После считывания входных данных программа вызывает эту функцию и выводит результат.
В данной задаче минимальное количество человек, которые могут быть уверены в цвете своей шляпы, зависит от того, сколько человек перед последним надели шляпы того же цвета, что и он сам.
Если количество людей с шляпами такого же цвета, что и шляпа последнего человека, нечетное, то последний человек уверен в цвете своей шляпы, так как он видит нечетное количество шляп такого же цвета, как у него.
Если количество людей с шляпами такого же цвета, что и шляпа последнего человека, четное, то последний человек не может быть уверен в цвете своей шляпы, так как он видит четное количество шляп такого же цвета, как у него.
Таким образом, ответ на задачу зависит только от количества людей с шляпами того же цвета, что и шляпа последнего человека. Если это количество нечетное, то минимальное количество людей, которые могут быть уверены в цвете своей шляпы, равно 0, иначе 1.
Вывод программы представляет собой это минимальное количество человек, которые могут быть уверены в цвете своей шляпы.
5. Числовые последовательности и их секреты
Описание задачи: Представьте, что перед вами задача – найти секрет в числовой последовательности. Ваша задача – написать программу, которая будет искать этот секрет в последовательности чисел.
Условия:
1. В числовой последовательности может быть скрыт секрет, который представляет собой подпоследовательность чисел, образующих определенный узор.
2. Секрет может быть разным: это может быть арифметическая прогрессия, геометрическая прогрессия или какой-то другой узор.
Формат ввода:
– Последовательность целых чисел, разделенных пробелом.
Формат вывода:
– Описание найденного секрета в виде строки, например, "Арифметическая прогрессия с разностью 3", "Геометрическая прогрессия с множителем 2", или "Нет секрета".
Примеры:
Ввод: 1 3 5 7 9
Вывод: Арифметическая прогрессия с разностью 2
Ввод: 2 4 8 16 32
Вывод: Геометрическая прогрессия с множителем 2
Ввод: 1 2 4 7 11
Вывод: Нет секрета
Примечание: В этой задаче ваша программа должна определить, является ли найденный узор арифметической прогрессией, геометрической прогрессией или если в последовательности нет никакого узора.
Для решения этой задачи нужно пройти по всей последовательности чисел и проверить, является ли она арифметической прогрессией, геометрической прогрессией или не содержит никакого узора.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «Литрес».
Прочитайте эту книгу целиком, купив полную легальную версию (https://www.litres.ru/chitat-onlayn/?art=70712785) на Литрес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.