Есть круг разделен на 16 секторов.Каждый сектор разделен на 10 сегментов.
В секторе 11 сегменте 7 сидит лягушка, которая прыгает: 1) прямо на 3, или на 2 прямо и 1 в влево, или 2 прямо и 1 вправо, или на 1 прямо и 2 в влево, или на 1 прямо и 2 вправо. Она должна допригнуты до 9 сектора 10 сегмента.
Есть две елки на круге на которые она не может прыгнуть.1 елка - сектор 14 сегмент 9, 2 - сектор 5 сегмент 8.
Надо найти минимальное количество прыжков, за которые лягушка достанется в сектор 9 сегмента 10
Лягушка может прыгать только по часовой стрелке. Через центр не может.
За круг также не может выпрыгнуть. Длина прыжка измеряется в секторах и сегментах.
Если прижок 3.0, это значит, что она прыгает на 3 сектора в перед (прямо), если 2.1 - это значит, что на 2 сектора вперед и сместилась на 1 позицию влево к краю круга (была - 11.7 стала 13.9) .если 2. -1 то 13.6(сместилась к центру)
У меня есть пять пар чисел {3,0},{2,1},{2,-1},{1,2},{1,-2}.
Эти пары чисел можно добавлять, например,
так: 3, 0 + 2,1 = 5,1
или так: 3.0 + 3.0 + 2.1 + 1,2 = 9.3
или так: 3.0 + 2.1 + 1.2 + 2.(- 1) = 8.2
Надо составить алгоритм, чтобы найти минимальное количество этих пар чисел (и сами пары), сумма которых будет 14.3.
Ответ
Упаковка рюкзака, правда в странной форме.
Заводите двоичное число, в котором количество битов соответствует количеству ваших пар.
Затем, пишите функцию, которая будет смотреть на биты этого числа и набирать из пар результат. Если дошли до нужного результата - ура, если превысили или так и не достигли - увеличиваем наше двоичное число и повторяем еще раз.
Сложность брутфорса 2^N, так что если у вас не много пар - дерзайте.
Комментариев нет:
Отправить комментарий