Скорость объекта растёт в геометрической прогрессии с шагом 2. Есть команда реверса. Как попасть в нужную точку?
Суть проблемы: есть задача, есть моя реализация, которая выдает не совсем оптимальные результаты.
Задача:
Объект перемещается вдоль одной линии по поверхности. Линия поделена на блоки, и каждый блок пронумерован, включая блоки с отрицательными номерами. Отправная точка находится в блоке (позиции) 0. Начальная скорость объекта в этом блоке - "+1".
Объект понимает 2 команды:
* "A" - ускорение, при котором позиция изменяется на величину скорости (позиция += скорость), а скорость увеличивается вдвое (скорость *= 2);
* "R" - обратный ход, при котором объект разворачивается на месте и сбрасывает скорость до "+1" или "-1", т.е. знак изменяется на противоположный.
Например, если мы передаём инструкцию "AAR", то объект перемещается по блокам 0->1->3->3, а его скорость изменяется как 1->2->4->(-1).
Наняли человека, который будет составлять подобные инструкции, но при этом необходимо проконтролировать, являются ли его инструкции оптимальными по размеру. В данной задаче необходимо определить длину кратчайшей последовательности инструкций, которая приведёт нас в заранее определённый блок.
На вход подаётся: целое число, обозначающее номер блока, в который должен попасть объект.
На выходе: натуральное число, обозначающее минимальное количество команд в инструкции, позволяющей достичь заданного блока.
Пример 1.
На входе: 3
Ответ: 2
Пояснение: наиболее оптимальная инструкция - "AA", которая позволяет переместить объект по блокам 0->1->3.
Пример 2.
На входе: 6
Ответ: 5
Пояснение: наиболее оптимальная инструкция - "AAARA", которая позволяет переместить объект по блокам 0->1->3->7->7->6.
Очень важно: объект не начинает движение сам по себе, а лишь реагирует на команды.
--------------------------------------
Удалось реализовать нахождение инструкций, которые приведут объект к цели на основе входящего значения с самой целевой точкой. Но инструкции получаются не оптимальными.
Есть ли способы решения данной задачи используя некие известные алгоритмы и/или математические подходы.
Может ли данная задача использоваться в качестве тестового задания на junior программиста?
И Stanislav Ushakov подправьте вопрос чтобы в заголовке было больше существа. Вопрос вобщем интересный, я подписался. Но с формулировкой "для решения данной задачи" его и открывать то никто не будет.
кратчайшая по длине последовательность состоит из нуля команд, если цель лежит по ходу начального движения, или одной, если надо развернуться.
Вердикт: задача пересказана неряхой.
longclaps Бинго. Салютую. Даже ведь в голову не пришло, сам себя переумнил. Конечно, задача в такой постановке решается одной, максимум двумя командами.
Как я понимаю, в задачке, что-то очень быстро поглощает силу инерции с такими скоростями при торможении. Это либо что-то тяжёлое и с высоким трением, либо что-то с реверс-тягой.
Интересно стало: что это за объект такой?
longclaps, Дополнил описание задачи фразой "Очень важно: объект не начинает движение сам по себе, а лишь реагирует на команды."
Т.е. подождать пока он сам достигнет цели, или пнуть его реверсом и снова подождать, не выйдет).
Все просто, двигаешь объект вправо до тех пор, пока целевая точка не совпадет, либо текущая позиция объекта не станет больше целевой, как только это случилось разворачиваешь его, и двигаешь до достижения цели. Все это дело придется выполнить в рекурсии, двигая объект туда-сюда.
P.S. Так как при команде R, объект сбрасывает скорость и разворачивается, то твой пример #2 не верный, раз он сбросил скорость и развернулся, то объект перемещался бы в сторону к нуля, и в позиции 6 не оказался бы. Это значит, что пересказ задачи очень, очень мягко говоря, не очень.
Значит на пол пути сбрасывать скорость, иначе проскок, так и добираться. Даже точнее, перед тем как перескочит. Если на следующем шаге будет перебор, то сбросить скорость.
profesor08, В очередной раз спасибо за ответ. Но и это пробовал.
Пример с целевой точкой 5:
Оптимально: 7 шагов.
Делаем два шага вперед, попадаем в точку 3, даём реверс, оставаясь в точке 3, делаем шаг назад, оказываясь в точке 2, даём реверс, оставаясь в точке 2, делаем два шага вперед, попадаем к цели.
Не оптимально: 9 шагов.
Делаем два шага вперед, попадаем в точку 3, даём реверс два раза (разворот 360 на месте), оставаясь в точке 3, делаем шаг вперед, оказываясь в точке 4, даём реверс два раза (разворот 360 на месте), делаем шаг вперед, попадаем к цели.
В общем, мораль сей басни такова, что двигаться только вперед, попутно притормаживая, не самый оптимальный вариант.)
Stanislav Ushakov, точное описание задачи есть? Иначе тут одни противоречия. То у тебя реверс разворачивает, то не разворачивает, то сбрасывает скорость до -1, то уменьшает ее на 1.
* "R" - обратный ход, при котором объект разворачивается на месте и сбрасывает скорость до "+1" или "-1", т.е. знак изменяется на противоположный.
Если двигаемся вперед и нажали реверс - развернулись и смотрим в противоположную сторону. Т.е. если после этого подать команду А (ускорение) - будем двигаться в противоположную сторону пока не дадим еще раз реверс.
Всё, что в описании задачи, это и есть сама задача. Точнее нету.)
Так и надо было сразу описывать. Вариант со сбросом скорости тут не подойдет. Маятник тут самое оптимальное, это первый вариант решения, который я описал. Но можно и скомбинировать, если цель довольно далеко, то перескакивать, а если близко то доползти..
Простой
Средний
