樹中的最小元素

我想在Lisp中找到非線性列表中的最小元素（在任何級別）（編輯：樹）。我寫了類似於：樹中的最小元素

(defun minimum (l) 
    (cond 
    ((null l) 99999) 
    ((atom (car l)) (min (minimum (cdr l)) 99999)) 
    ((numberp (car l)) (min (car l) (minimum (cdr l)))) 
    (T (min (minimum (cdr l)) (minimum (Car l))))))

但是，它不工作（因爲非數值原子的條件，我猜...）。有沒有人有任何想法如何修復此密碼？提前致謝。

來源

2016-02-12 Nelly

你numberp情況下永遠不會執行，因爲情況下先測試，數字是原子。所以每個數字都被99999代替。首先將numberp個案。

您的代碼的另一個問題是，如果樹中的最小數字大於99999，它將找不到最小數字。要修復它而不更改代碼太多，您需要自己的版本min支持無窮大的表示：

(defun inf-min (a b) 
    (cond ((eq a :infinity) b) 
      ((eq b :infinity) a) 
      ((< a b) a) 
      (t b)))

然後，inf-min和99999與:infinity替換min。

來源

2016-02-13 06:28:56

非常感謝！有效。 – Nelly

在'（空l）'情況之後添加一個'（atom l）'情況可以讓你支持不正確的列表。 –

(defun minimum (tree) 
    (loop for item in tree 
     if (consp item) minimize (minimum item) 
     else if (numberp item) minimize item))

來源

2016-02-12 22:18:34

神祕性循環法寶：http://www.gigamonkeys.com/book/loop-for-black-belts.html – murphy

這主要是風格問題，但你可以執行一個最小化的關鍵字裏面的測試。 – coredump

99999的使用真的是黑客（不是那種好的黑客），請不要這樣做。使用:infinity稍微好一點，但是，如果給出一個空列表，結果是否爲:infinity？ loop方法更好，但是當列表爲空時，最小返回0，這通常不是我們想要的。

對於零值，最小函數未定義，所以我將定義一個tree-min函數，其中結果爲nil當樹不包含數字時。類似這樣的：

(defun tree-min (tree) 
    (typecase tree 
    ;; base case with numbers 
    (number tree) 

    ;; string are sequences too, but don't iterate over them. 
    (string nil) 

    ;; vectors and lists 
    (sequence (reduce (lambda (m e) 
         (let ((em (tree-min e))) 
          (or (and m em (min em m)) ; Eminem? 
           em))) 
         tree 
         :initial-value nil))))

該函數靜默地跳過任何非數字元素。下面是一些例子：

(tree-min #(3 2 nil (2 1 -20) 100 20)) 
=> -20 

(tree-min nil) 
=> nil 

(tree-min '(a 20)) 
=> 20

在實踐中，你可以概括此功能需要一個比較函數一樣extremum一樣。

來源

2016-02-13 07:24:46 coredump

樹中的最小元素

回答

相關問題