Возможные "нагрузки на лодку"
Вы знаете проблемы пересечения реки. Вот описание сортировки:
Когда-то три людоеда вели трех миссионеров через джунгли. Они были на пути к ближайшей миссии. Через некоторое время они прибыли к широкой реке, наполненной смертельными змеями и рыбой. Не было возможности пересечь реку без лодки. К счастью, после непродолжительного поиска они нашли гребную лодку с двумя веслами. К сожалению, лодка была слишком маленькой, чтобы перевозить их всех. Он едва мог нести двух человек одновременно. Хуже того, из-за ширины реки не было никакого способа вернуть лодку, кроме как грести обратно. Поскольку миссионеры не могли доверять людоедам, они должны были составить план, как безопасно переправить всех шестерых из них через реку. Проблема заключалась в том, что эти людоеды убивали и ели миссионеров, как только в каком-то месте было больше людоедов, чем миссионеров. Таким образом, наш миссионер-программист должен был разработать план, который гарантировал бы, что в меньшинстве по обе стороны реки никогда не будет миссионеров. Людям, однако, можно доверять, чтобы сотрудничать иначе. В частности, они не откажутся от любой потенциальной пищи, так же как миссионеры не откажутся от любых потенциальных новообращенных.
Мой вопрос является частью этой проблемы. Я пытаюсь создать функцию, которая возвращает список возможных загрузок лодки (например, если boat_capacity равен 3, то [(3mis, 0can), (2mis, 1can), (1mis, 1can),...]). У меня есть num(количество миссионеров или людоедов) и вместимость лодки в качестве входных данных моей функции.
Как вы разрабатываете свою функцию и алгоритм?
4 ответа
Я решил проблему в среде Scheme. Возможно, это не очень быстро, но это работает.
;;; boat-loads : mc_num boat_capacity --> list of boat_loads
;;; returns a list of possible (cannibals cannot be more than missionaries)
;;; boat-loads
(define (boat-loads mc bc storage)
(local
((define isBoatBig (> bc mc))
(define (both mc bc storage)
(cond
[(< mc 1) storage]
[else
(both (- mc 1) bc (append storage (list (list mc (- bc mc)))))]))
(define (single mc bc storage)
(cond
[(= mc 0) storage]
[else
(single (- mc 1) bc (append storage (list (list mc 0) (list 0 mc))))]))
(define (filt l)
(local
((define (filter-equal l acc)
(local
((define (filter-equal-inner f l)
(cond
[(empty? l) (list f)]
[(equal? f (first l)) (filter-equal-inner (first l) (rest l))]
[else (append (list (first l))
(filter-equal-inner f (rest l)))]))
(define done (filter-equal-inner (first l) (rest l))))
(cond
[(= 0 acc) done]
[else (filter-equal done (- acc 1))]))))
(filter-equal l (length l)))))
(cond
[(= bc 0) storage]
[else
(filt (boat-loads mc
(- bc 1)
(append storage
(if isBoatBig
(filter (lambda (x)
(if (>= (first x) (second x))
true false))
(append (both mc bc empty)
(single mc bc empty)))
(filter (lambda (x)
(if (>= (first x) (second x))
true false))
(append (both bc bc empty)
(single bc bc empty)))))))])))
Или вы можете думать об этом, как о генерации всех строк длиной 1,2 и 3, состоящих из двух символов. Как, например, Mи C"S. Или, хм, нули и единицы! 0 для миссионеров и 1 для людоедов.
0 в 1, 00 в 11, а также 000 в 111, "Как" генерировать их просто бросается на вас сейчас, верно?
Думайте об этом рекурсивно, то есть вы хотите думать об этом с точки зрения возможных подзадач. Итак, если у вас есть лодка с тремя пассажирами, это, очевидно, похоже на лодку с одним пассажиром, плюс любую комбинацию из двух пассажиров.
Лодка с двумя пассажирами имеет пассажира плюс "лодка, полная одного жителя".
Таким образом, ваш алгоритм будет в основном выглядеть
to find all combinations of n occupants,
pick an occupant
if n = 1 return
if n > 1 find all combinations of (n-1) occupants.
Обратите внимание, что это не точное решение, так как это выглядит как домашнее задание.