3

あなたは川を渡る問題を知っています。並べ替えの説明は次のとおりです。

むかしむかし、3 人の人食い人種が 3 人の宣教師をジャングルに案内していました。彼らは最寄りの伝道所に向かう途中でした。しばらくすると、彼らは恐ろしいヘビや魚でいっぱいの広い川に到着しました。船がなければ川を渡ることができませんでした。幸いなことに、彼らは短い捜索の後、2 つのオールを備えた手漕ぎボートを見つけました。残念ながら、ボートは小さすぎて全員を運ぶことができませんでした。一度に 2 人を運ぶことはほとんどできませんでした。さらに悪いことに、川幅が広いため、漕ぐ以外にボートを戻す方法がありませんでした。宣教師たちは人食い人種を信頼できなかったので、6人全員を安全に川を渡らせる計画を立てなければなりませんでした。問題は、ある場所で宣教師よりも人食い人種の方が多いとすぐに、これらの人食い人種が宣教師を殺して食べてしまうことでした。したがって、私たちの宣教師兼プログラマーは、川の両側に少数派の宣教師が決していないことを保証する計画を考案する必要がありました。ただし、人食い人種は、それ以外の場合は協力すると信頼できます。具体的には、宣教師が潜在的な改宗者を捨てないのと同じように、彼らは潜在的な食べ物を捨てません。

私の質問はこの問題の一部です。可能なボート負荷のリストを返す関数を設計しようとしています (たとえば、boat_capacity が 3 の場合[(3mis, 0can), (2mis, 1can), (1mis, 1can), ...] )。関数の入力として num (宣教師または人食い人種の数) とボートの収容人数があります。

関数とアルゴリズムをどのように設計しますか?

4

3 に答える 3

1

または、代わりに、2 つのシンボルで構成される長さ 1、2、および 3 のすべての文字列を生成すると考えることができます。たとえば、 と のようMにC。または、うーん、0 と 1 です。0宣教師と1人食い人種のために。

0へ1、00へ11、000へ111。それらを生成する「方法」がすぐに飛び出しますよね？

于 2010-08-10T15:43:33.030 に答える
1

これを再帰的に考えてください。つまり、考えられる部分問題の観点から考えたいということです。したがって、3 人乗りのボートがある場合、それは明らかに 1 人乗りのボートに加えて 2 人乗りの任意の組み合わせのようなものです。

2 人の乗員がいるボートには、乗員と「1 人の乗員でいっぱいのボート」があります。

したがって、アルゴリズムは基本的に次のようになります

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

これは宿題の問題によく似ているため、正確な解決策ではないことに注意してください。

于 2010-08-07T21:41:02.447 に答える
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)))))))])))
于 2010-08-07T22:40:29.073 に答える