Сообщение Re: Задача с собеседования от 02.07.2018 3:45
Изменено 02.07.2018 3:46 nekocoder
Re: Задача с собеседования
Здравствуйте, mbait, Вы писали:
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Совсем брутфорс решение:
— Предполагаем, что размер доски 3х3 и робот в ее центре
— Перебираем все ячейки в пределах предпологаемого размера, и пытаемся посетить каждую ячейку (с помощью того же А*). Считаем, сколько удалось посетить.
— После того, как все ячейки посещены, увеличиваем предполагаемый размер доски (3х3 — 5х5 — 7х7 — ...) и повторяем
— Если по сранению с предыдущей итерацией количество посещенных ячеек не увеличилось, значит мы достигли пределов доски
За час можно даже успеть код написать.
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Совсем брутфорс решение:
— Предполагаем, что размер доски 3х3 и робот в ее центре
— Перебираем все ячейки в пределах предпологаемого размера, и пытаемся посетить каждую ячейку (с помощью того же А*). Считаем, сколько удалось посетить.
— После того, как все ячейки посещены, увеличиваем предполагаемый размер доски (3х3 — 5х5 — 7х7 — ...) и повторяем
— Если по сранению с предыдущей итерацией количество посещенных ячеек не увеличилось, значит мы достигли пределов доски
За час можно даже успеть код написать.
Re: Задача с собеседования
Здравствуйте, mbait, Вы писали:
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Совсем брутфорс решение:
— Предполагаем, что размер доски 3х3 и робот в ее центре
— Перебираем все ячейки в пределах предполагаемого размера, и пытаемся посетить каждую ячейку (с помощью того же А*). Считаем, сколько удалось посетить.
— После того, как все ячейки посещены, увеличиваем предполагаемый размер доски (3х3 — 5х5 — 7х7 — ...) и повторяем
— Если по сравнению с предыдущей итерацией количество посещенных ячеек не увеличилось, значит мы достигли пределов доски
За час можно даже успеть код написать.
M>Вы управляете роботом, который двигается по клетчатому полю. Ваша задача написать алгоритм, с помощью которого робот гарантированно посетить все клетки поля, до которых возможно добраться. Каждая клетка может быть либо свободной, либо занятой стеной. Робот может передвигаться только из свободной клетки в свободную. Размер и форма поля заранее неизвестны. Роботу можно отдать одну из четырёх команд передвижения: вперёд, назад, влево, вправо. По результату выполнения компанды можно понять, сделал ли робот движение, или на пути оказалась стена.
Совсем брутфорс решение:
— Предполагаем, что размер доски 3х3 и робот в ее центре
— Перебираем все ячейки в пределах предполагаемого размера, и пытаемся посетить каждую ячейку (с помощью того же А*). Считаем, сколько удалось посетить.
— После того, как все ячейки посещены, увеличиваем предполагаемый размер доски (3х3 — 5х5 — 7х7 — ...) и повторяем
— Если по сравнению с предыдущей итерацией количество посещенных ячеек не увеличилось, значит мы достигли пределов доски
За час можно даже успеть код написать.