49 Просмотров

Задание:

Робот передвигается на экране на клеточном поле и управляется программой. Программа — это строка из букв L, R, D и U. Они соответствуют направлениям движения:
L (left) — влево
R (right) — вправо
D (down) — вниз
U (up) — вверх
Определите по строке с программой для робота, сколько раз он возвращался в клетку, с которой начал движение?

Ввод            Вывод
LR                       1
LRUD                  2
LLUURRD            0

Ответ на задание:

Алгоритм для определения количества возвращений робота в начальную клетку:

1. Преобразуйте строку программы в список команд.

2. Создайте координаты начальной клетки (x, y) = (0, 0).

3. Итерируйте по списку команд: – Для команды L: x -= 1 – Для команды R: x += 1 – Для команды D: y += 1 – Для команды U: y -= 1

4. Счетчик count инициализируйте как 0.

5. После каждой команды проверяйте: – Если (x, y) == (0, 0): – Увеличьте count на 1.

6. Возвратите значение count.

def count_returns(program):
"""
Counts the number of times the robot returns to the initial cell.

Args:
program: A string of commands (L, R, D, U).

Returns:
The number of returns to the initial cell.
"""
commands = list(program)
x, y = 0, 0
count = 0
for command in commands:
if command == "L":
x -= 1
elif command == "R":
x += 1
elif command == "D":
y += 1
elif command == "U":
y -= 1
if (x, y) == (0, 0):
count += 1
return count

# Примеры использования
print(count_returns("LR")) # 1
print(count_returns("LRUD")) # 2
print(count_returns("LLUURRD")) # 0

Данный алгоритм работает следующим образом:

1. Преобразует строку программы в список команд.
2. Создает координаты начальной клетки.
3. Итерирует по списку команд, обновляя координаты робота.
4. После каждой команды проверяет, вернулся ли робот в начальную клетку.
5. Счетчик count увеличивается на 1, если робот вернулся в начальную клетку.
6. Возвращает значение count, которое является количеством возвращений в начальную клетку.

Сложность алгоритма:

• Время: O(n), где n – длина строки программы.
• Память: O(1), так как используется только несколько переменных.