Possible boat loads

Question

You know the problems of crossing rivers . Here is a description of the genus:

Once, three cannibals sent three missionaries through the jungle. They were heading to the nearest mission station. After some time, they arrived on a wide river filled with deadly snakes and fish. It is impossible to cross the river without a boat. Fortunately, after a short search, they found a boat with two oars. Unfortunately, the boat was too small to carry anything. He could barely carry two people at a time. Worse, because of the width of the river, it was not possible to return the boat, in addition to turning it back. Since the missionaries could not trust the cannibals, they needed to make a plan so that all six of them cross the river safely. The problem was that these cannibals would kill and eat missionaries as soon as there were more cannibals in some places than missionaries. In this way,our missionary programmer had to develop a plan to ensure that there were never missionaries in the minority on either side of the river. However, cannibals can be trusted otherwise. In particular, they will not give up any potential food, just as missionaries will not give up any potential converts.

My question is part of this problem. I am trying to create a function that returns a list of possible boat loads (for example, if the hull boat is 3, then [(3mis, 0can), (2mis, 1can), (1mis, 1can), ...] ). I have num (number of missionaries or cannibals) and boat capacity as inputs of my function.

How do you develop your function and algorithm?

Answer 1

Think of it in a recursive way, that is, you want to think about it in terms of possible subtasks. So, if you have a boat with three tenants, which obviously looks like a boat with one tenant plus any combination of two passengers.

", ".

,

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 2

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 3

, 1,2 3, . , M C. , , ! 0 1 .

0 1, 00 11 000 111. "" ?

Answer 4

Escape from Zurg.