Возможные "нагрузки на лодку"

Question

Вы знаете проблемы пересечения реки . Вот описание сортировки:

Когда-то три людоеда вели трех миссионеров через джунгли. Они были на пути к ближайшей миссии. Через некоторое время они прибыли к широкой реке, заполненной смертельными змеями и рыбой. Не было возможности пересечь реку без лодки. К счастью, после короткого обыска они обнаружили гребную лодку с двумя веслами. К сожалению, лодка была слишком маленькой, чтобы перевозить их всех. Он едва мог нести двух человек одновременно. Хуже того, из-за ширины реки не было никакого способа вернуть лодку, кроме как грести обратно. Поскольку миссионеры не могли доверять каннибалам, им пришлось составить план, как безопасно переправить всех шестерых из них через реку. Проблема заключалась в том, что эти людоеды убивали и ели миссионеров, как только в каком-то месте было больше людоедов, чем миссионеров. Таким образом, наш миссионер-программист должен был разработать план, который гарантировал бы, что в меньшинстве по обе стороны реки никогда не будет миссионеров. Людям, однако, можно доверять, чтобы сотрудничать иначе. В частности, они не откажутся от любой потенциальной пищи, точно так же, как миссионеры не откажутся от любых потенциальных новообращенных.

Мой вопрос является частью этой проблемы. Я пытаюсь создать функцию, которая возвращает список возможных загрузок лодки (например, если boat_capacity равен 3, то [(3mis, 0can), (2mis, 1can), (1mis, 1can), ...] ). У меня num (количество миссионеров или людоедов) и вместимость лодки в качестве входных данных моей функции.

Как вы разрабатываете свою функцию и алгоритм?

Answer 1

Я решил проблему в среде 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)))))))])))

Answer 2

Или вместо этого вы можете думать об этом как о генерации всех строк длиной 1,2 и 3, состоящих из двух символов. Как, например, M и C. Или, хм, нули и единицы! 0 для миссионеров и 1 для каннибалов.

0 до 1, 00 до 11 и 000 до 111. «Как» генерировать их просто бросается на вас сейчас, верно?

Answer 3

Думайте об этом рекурсивно, то есть вы хотите думать об этом с точки зрения возможных подзадач. Итак, если у вас есть лодка с тремя пассажирами, это, очевидно, похоже на лодку с одним пассажиром, плюс любую комбинацию из двух пассажиров.

Лодка с двумя пассажирами имеет пассажира плюс «лодка, заполненная одним жителем».

Итак, ваш алгоритм будет выглядеть в основном как

to find all combinations of n occupants,
    pick an occupant
    if n = 1 return
    if n > 1 find all combinations of (n-1) occupants.

Обратите внимание, что это не точное решение, так как это очень похоже на домашнюю работу.

Answer 4

Ваша проблема похожа на Побег из Цурга .