Mögliche "Bootsladungen"

Question

Sie kennen die Probleme beim Überqueren von Flüssen . Hier ist eine Sortenbeschreibung:

Es waren einmal drei Kannibalen, die drei Missionare durch einen Dschungel führten. Sie waren auf dem Weg zur nächstgelegenen Missionsstation. Nach einiger Zeit kamen sie an einen breiten Fluss, in dem es tödliche Schlangen und Fische gab. Es gab keine Möglichkeit, den Fluss ohne ein Boot zu überqueren. Glücklicherweise fanden sie nach einer kurzen Suche ein Ruderboot mit zwei Rudern. Leider war das Boot zu klein, um sie alle zu tragen. Es konnte kaum zwei Personen auf einmal tragen. Schlimmer noch, aufgrund der Breite des Flusses gab es keine andere Möglichkeit, das Boot zurückzubringen, als es zurückzurudern. Da die Missionare den Kannibalen nicht trauen konnten, mussten sie sich einen Plan ausdenken, wie sie alle sechs sicher über den Fluss bringen konnten. Das Problem war, dass diese Kannibalen die Missionare töten und fressen würden, sobald es an einem Ort mehr Kannibalen als Missionare gäbe. Also musste unser Missionsprogrammierer einen Plan ausarbeiten, der sicherstellte, dass auf beiden Seiten des Flusses niemals Missionare in der Minderheit waren. Bei den Kannibalen kann man sich jedoch darauf verlassen, dass sie sonst kooperieren. Insbesondere werden sie keine potenzielle Nahrung aufgeben, so wie die Missionare keine potenziellen Bekehrten aufgeben werden.

Meine Frage ist ein Teil dieses Problems. Ich versuche, eine Funktion zu entwickeln, die eine Liste möglicher Bootsladungen zurückgibt (z.B. wenn boat_capacity 3 ist, dann [(3mis, 0can), (2mis, 1can), (1mis, 1can), ...] ). Ich habe num (Anzahl der Missionare oder Kannibalen) und Bootskapazität als Eingaben für meine Funktion.

Wie gestalten Sie Ihre Funktion und Ihren Algorithmus?

Answer 1

Denken Sie darüber in einer rekursiven Weise nach, d.h. Sie wollen es in Form von möglichen Unterproblemen betrachten. Wenn Sie also ein Boot mit drei Insassen haben, ist das natürlich wie ein Boot mit einem Insassen, plus eine beliebige Kombination von zwei Insassen.

Ein Boot mit zwei Insassen hat einen Insassen plus "ein Boot voll mit einem Insassen".

Ihr Algorithmus wird also im Wesentlichen wie folgt aussehen

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

Beachten Sie, dass dies nicht die genau Lösung, da dies sehr nach einer Hausaufgabe aussieht.

Answer 2

Ich habe das Problem in einer Scheme-Umgebung gelöst. Wahrscheinlich ist es nicht sehr schnell, aber es funktioniert.

;;; 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

Man könnte es sich auch so vorstellen, dass es alle Zeichenketten der Länge 1, 2 und 3 erzeugt, die aus zwei Symbolen bestehen. Wie zum Beispiel, M und C 's. Oder, hmm, Nullen und Einsen! 0 für Missionare und 1 für Kannibalen.

0 まで 1 , 00 まで 11 und 000 まで 111 . Das "Wie" ihrer Erstellung springt Ihnen jetzt geradezu ins Auge, nicht wahr?