作者Schelfaniel (Schelfaniel)
看板Programming
標題Re: [問題] 遞迴改非遞迴
時間Sun Apr 18 21:44:07 2010
用 Clojure 改寫 :QQ
; 邊是否在點上?
(defn other-point [point edge]
(cond
(= point (first edge)) (second edge)
(= point (second edge)) (first edge)
:else nil))
; 列印一筆劃，假設是全雙向邊
; point : 初期點
; edges : 邊，格式 [['1 '2] ['1 '3] ['1 '5]]
; history : 歷史，初期為 nil
(defn stretch-single-line0 [point edges history]
(if (empty? edges)
(println (apply str (reverse (cons point history))))
(doseq [edge (filter #(other-point point %) edges)]
(stretch-single-line (other-point point edge)
(remove #(= edge %) edges) (cons point history)))))
; 非遞迴格式
(defn stretch-single-line1 [point edges]
(loop [stack (list (list point edges nil))]
(when-not (empty? stack)
(let [[point edges history] (first stack)
stack (rest stack)]
(if (nil? (first edges))
(do
(println (apply str (reverse (cons point history))))
(recur stack))
(let [items (map #(list (other-point point %)
(remove (partial = %) edges) (cons point history))
(filter #(other-point point %) edges))]
(recur (into stack (reverse items)))))))))
; 測試用函式
(defn test0 []
(stretch-single-line0 '1 [['1 '2] ['1 '3] ['1 '5] ['2 '3]
['2 '5] ['3 '4] ['3 '5] ['4 '5]] nil))
(defn test1 []
(stretch-single-line1 '1 [['1 '2] ['1 '3] ['1 '5] ['2 '3]
['2 '5] ['3 '4] ['3 '5] ['4 '5]]))
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.74.159