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"
```
Псевдокод – это упрощенный язык описания алгоритмов, который используется для представления логики решения задачи без привязки к конкретному языку программирования. Он обычно используется для описания шагов алгоритма на естественном языке, что облегчает понимание и написание кода.
В псевдокоде часто используются ключевые слова, похожие на те, что применяются в реальных языках программирования, такие как "если", "то", "цикл", "вывод" и т. д. Однако синтаксис псевдокода более гибкий и менее строгий, чем у конкретного языка программирования.
Псевдокод позволяет описать алгоритм более наглядно и понятно, не углубляясь в детали реализации на определенном языке. Он используется в образовании, при разработке алгоритмов и при описании решения задач до того, как приступить к программированию на конкретном языке.