computer 版 (精华区)

发信人: wizard (Python), 信区: computer       
标  题: 这个是利用上面的包解决分水问题的
发信站: BBS 听涛站 (Thu Mar 25 15:29:03 2004), 站内

用的是深度优先

(load "search")

(defvar rules '(
              (0 1)
              (0 2)
              (1 0)
              (1 2)
              (2 0)
              (2 1)
              ))

(defvar limits '(8 5 3))
(defvar start '(8 0 0))
(defvar finish '(
               (4 4 0)
               ))

(defun index(lst idx)
  (cond ((equal idx 0) (car lst))
        (t (index (cdr lst) (1- idx)))))

(defun setidx-base(lst idx val ret)
  (let ((first-lst (car lst))
        (rest-lst (cdr lst))
        )
    (cond ((eql 0 idx) (append ret (cons val rest-lst)))
          (t (setidx-base
              rest-lst
              (1- idx)
              val
              (append ret (list first-lst)))))))

(defun setidx(lst idx val)
  (setidx-base lst idx val nil))

(defun pour-water (q src dst)
  (let* ((src-wt (index q src))
         (dst-wt (index q dst))
         (empty (- (index limits dst) dst-wt))
         )
    (cond ((equal 0 src-wt) q)
          ((> src-wt empty)
           (let* ((new (setidx q src (- src-wt empty)))
                  (new (setidx new dst (index limits dst)))
                  )
             new))
          (t (let* ((new (setidx q src 0))
                    (new (setidx new dst (+ src-wt dst-wt)))
                    )
               new)))))

(defun pour (q r)
  (pour-water q (first r) (second r)))

(print (search-base:DFS start finish rules 'pour))

(quit)

--
(defun power-set (set)
  (if (null set) '(())
    (let ((pset-of-rest (power-set (cdr set))))
      (append
      (mapcar #'(lambda (subset) (cons (car set) subset))
              pset-of-rest) pset-of-rest))))


※ 修改:·wizard 于 Mar 25 15:29:37 修改本文·[FROM: 219.224.175.139]
※ 来源:·BBS 听涛站 tingtao.net·[FROM: 219.224.175.139]