UVa 10120禮物？在Common Lisp中？

Question

我正在學習常用lisp我已經從uVA數據庫（http://acm.uva.es/p/v101/10120.html）和一個廣度搜索函數（它將啓動點，目標點和一個合法的動作生成器），我已經理解了我如何才能得到答案，但Lisp只是不同意我。關於如何從這一點開始，我可以提供一些建議嗎？下面是給出的問題和我的兩個嘗試解決方案與lisp源代碼的鏈接。任何幫助將不勝感激！謝謝！

1.

(defun gift (N G) 
(setq CR 9) 
(setq i 3) 
(cond ((= N G) "N and G equal") 
    ((< N G) "Gift it on a rock outside limits") 
    ((> N 49) "number of rocks is bigger than 49 - it will work") 
    ((< N 9) "number of rocks is less than 9, it wont work") 
    ((= N 0) "number of rocks is 0, it wont work") 
    ((= G 0) "gift isn't on a rock, it wont work")) 
(loop 
    (setq I (+ I 1)) 
    (setq I (-(* I 2) 1)) 
    (setq CR 9) 
(breadth-search CR G #'lmg-moves) 
(when (= CR G) (return "Let me Try!")) 
(when (> CR N) (return "Don't laugh at me!")) 
)) 

(defun lmg-moves (I) 
(list (+ 9 I) 
    (- 9 I) 
    )) 

2.

(defvar *currentRock* 9) 
(defvar *iterator* 3) 

(defun gift (N G) 
(setq *iterator* (+ *iterator* 1)) 
;; (breadth-search *currentRock* G #'LMG) 
) 

(defun LMG (a) 
(+ a (-(* *iterator* 2) 1)) 
    ) 

正如上面可以看到，一般的想法是簡單地適用廣度搜索功能與給定的合法的移動發電機，希望通過分析它的輸出，我們可以確定我們是否可以達到目標狀態。如果上面的代碼太混亂，我會很樂意回答任何問題，再次感謝！

Answer 1

在其他潛在問題中：

您正在使用LOOP錯誤。有關循環的信息，請參閱PCL。我已經重新打了一下，但我不知道你在嘗試什麼。

SETF推薦使用SETQ，因爲SETF更通用。

INCF增加1的地方。

您的縮進不好;如果你確定你會注意到你正在從COND的末尾掉入LOOP。我建議在這裏使用Lisp的自動縮進編輯器。 （Emacs是待機）。

(defun gift (N G) 
    (setq CR 9) 
    (setq i 3) 
    (cond ((= N G) "N and G equal") 
      ((< N G) "Gift it on a rock outside limits") 
      ((> N 49) "number of rocks is bigger than 49 - it will work") 
      ((< N 9) "number of rocks is less than 9, it wont work") 
      ((= N 0) "number of rocks is 0, it wont work") 
      ((= G 0) "gift isn't on a rock, it wont work"))) 
    (loop 
     while t 
     do 
     (setq I (+ I 1)) 
     (setq I (-(* I 2) 1)) 
     (setq CR 9) 
     (breadth-search CR G #'lmg-moves) 
     (when (= CR G) 
     (return "Let me Try!")) 
     (when (> CR N) 
     (return "Don't laugh at me!")))) 

Answer 2

有一些事情是顯而易見：「別取笑我」

• 你恰好有兩個法律的返回值「！讓我試試」，和。第一個拼寫錯誤，第二個拼寫錯誤，並添加了很多沒有用於解決問題的字符串（它們是否意味着評論？）。
• 描述調用變量N和M，但您的嘗試參數爲N和G。爲什麼迷惑自己？要麼稱它們爲N和M，要麼（更好）使用有意義的名稱，如rock-number和gift-place。

現在，讓我們來看看你的程序結構。

(defun gift (N G) 
    (setq CR 9) 
    (setq i 3)) 

這些setq指令已經在這一點上不確定的行爲，因爲CR和I尚未確定。許多Lisp實現會隱式地創建這些名稱的全局特殊變量，但依賴它的風格很糟糕。我要在這裏使用let，像這樣的印象：

(defun gift (rock-number gift-place) 
    (let ((current-rock 0) 
     (jump-number 0)) 
    ;; ... 
    )) 

請注意，你應該從頭開始，因爲當禮物岩石上1或4，你會錯過解決方案。

接下來，cond形式：它是死代碼，因爲它沒有副作用，並且立即丟棄它的返回值。這是最好的評論，你應該使用評論。

最後，我們有這個有趣的循環：

(loop 
    (setq I (+ I 1)) 
    (setq I (-(* I 2) 1)) 
    (setq CR 9) 
    (breadth-search CR G #'lmg-moves) 
    (when (= CR G) (return "Let me Try!")) 
    (when (> CR N) (return "Don't laugh at me!")))) 

我不知道是什麼breadth-search做，但似乎你真的取決於全球特殊變量的操作。我不能說這裏會發生什麼。但是，我可以看到幾個問題：

• 從給定的岩石上跳過一定距離時，最多可以有兩個位置。在每次跳轉後只檢查一個變量是不對的。
• 你似乎混淆了跳數和跳躍距離。 I進入序列1,3,7,15 ......，但是跳轉序列號將是1,2,3,4 ......。而跳距序列則爲1,3,5,7 ......。即使總是向右跳的時候訪問的岩石也是不同的順序（1,4,9,16）。
• 您通過循環每次將CR重置爲9。我不明白這可能是對的。

風格上，你應該讓你的變量本地越好，例如使用let，do，或擴展loop關鍵字:for和:with，然後將它們傳遞到需要它們作爲參數的功能。這使得更容易推斷髮生的事情。

我認爲你的求解算法的心智模型有點困惑。我會以這樣一種方式來構造這個結構，你可以循環跳躍，並在這個跳躍次數後保留一組你可能會遇到的岩石。對於小型N的特殊處理似乎並沒有真正提高效率。如果你有證據表明總是有解決方案，另一方面，你應該有一個保護條款和一個評論，概述證明。