40 задач на Python
Шрифт:
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: …`: Если овца не съедена волком, добавляем её в обновленное поле
В данной задаче была успешно смоделирована ситуация на лугу, где пастух старается спасти овец от волков. Мы рассмотрели основные этапы решения задачи, включая чтение входных данных, инициализацию игрового поля, реализацию вспомогательных функций для проверки валидности координат и поиска кратчайшего пути, а также логику движения пастуха и волков.
Условие задачи: Даны координаты центров и радиусы двух кругов на плоскости. Необходимо определить, пересекаются ли эти круги.
Входные данные:
– Четыре вещественных числа: ( 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"
```
Псевдокод – это упрощенный язык описания алгоритмов, который используется для представления логики решения задачи без привязки к конкретному языку программирования. Он обычно используется для описания шагов алгоритма на естественном языке, что облегчает понимание и написание кода.
В псевдокоде часто используются ключевые слова, похожие на те, что применяются в реальных языках программирования, такие как "если", "то", "цикл", "вывод" и т. д. Однако синтаксис псевдокода более гибкий и менее строгий, чем у конкретного языка программирования.
Псевдокод позволяет описать алгоритм более наглядно и понятно, не углубляясь в детали реализации на определенном языке. Он используется в образовании, при разработке алгоритмов и при описании решения задач до того, как приступить к программированию на конкретном языке.