3

你知道过河的问题。以下是排序说明：

曾几何时，三个食人族正带领三个传教士穿过丛林。他们正在前往最近的宣教站的路上。过了一会儿，他们来到了一条宽阔的河流，那里满是致命的蛇和鱼。没有船就没有办法过河。幸运的是，经过短暂的搜索，他们找到了一艘带有两支桨的划艇。不幸的是，这艘船太小了，无法承载所有人。它一次几乎不能承载两个人。更糟糕的是，由于河流的宽度，没有办法把船拉回来，只能把它划回去。由于传教士无法信任食人族，他们不得不想出一个计划，让他们六个人安全过河。问题是，一旦某个地方的食人族比传教士多，这些食人族就会杀死并吃掉传教士。因此，我们的传教士程序员必须制定一个计划，确保在河的两岸永远不会有少数传教士。然而，可以信任食人族会以其他方式进行合作。具体来说，他们不会放弃任何潜在的食物，就像传教士不会放弃任何潜在的皈依者一样。

我的问题是这个问题的一部分。我正在尝试设计一个返回可能船载列表的函数（例如，如果boat_capacity 为 3，则[(3mis, 0can), (2mis, 1can), (1mis, 1can), ...]）。我有num（传教士或食人者的人数）和船容量作为我的职能的输入。

你是如何设计你的函数和算法的？

4

3 回答 3

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

或者您可以将其视为生成由两个符号组成的所有长度为 1,2 和 3 的字符串。比如，M's 和C's。或者，嗯，零和一！0传教士和1食人者。

0到1,00到11,000到111. 生成它们的“如何”现在就跳出来了，对吧？

于 2010-08-10T15:43:33.030 回答
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 回答