0

プログラミング クラスでの私の課題の 1 つは「ハノイの塔」です。使用していた言語は Common Lisp で、ソース コードは次のとおりです。

コード ：

変数:

(defparameter *Source*      "Peg 1")
(defparameter *Spare*       "Peg 2")
(defparameter *Destination* "Peg 3")

上記の変数宣言を関数内に入れたい

(defun towers-of-hanoi (disks)

;disks accept list as parameter , for e.g `(s m l)

  (let ((tempPeg))
    (if (= (list-length disks) 1)
      (format t "Move ~{~A~} from ~A to ~A~%"
              (last disks) *Source* *Destination*) 
      (progn
        (setq tempPeg *Spare*)
        (setq *Spare* *Destination*)
        (setq *Destination* tempPeg) 

        (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1)))

        (setq tempPeg *Spare*)
        (setq *Spare* *Destination*)
        (setq *Destination* tempPeg)

        (format t "Move ~{~A~} from ~A to ~A~%"
                (last disks) *Source* *Destination*) 

        (setq tempPeg *Spare*)
        (setq *Spare* *Source*)
        (setq *Source* tempPeg)
        (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1)))
        (setq tempPeg *Spare*)
        (setq *Spare* *Source*)
        (setq *Source* tempPeg)
        (format t "")))))

質問 ：

1.) この問題を解決するために再帰アルゴリズムを使用しています。このアルゴリズムでわかっているように、3 つの変数 (ソース、スペア、宛先) は (いくつかの規則によって) 相互に交換する必要があります。defvar関数内に を配置する(setq tempPeg *Spare*) (setq *Spare* *Destination*) (setq *Destination* tempPeg)と、towers-of-hanoi 関数を再度呼び出す前にこの 3 つの操作を実行しますが、関数は再び 3 つの変数を元の値に再定義します。

2.) 私が知りたかったのは、関数内に 3 つの変数の宣言を配置し、関数が呼び出される再帰ごとに同じ変数を再定義するのを防ぐことができるかということです。

P/S 割り当てでは、ディスクを唯一の引数として受け入れる関数ヘッダーのみを定義できますが、 Source 、 Spare 、および Destination ロッドは受け入れません。

4

2 に答える 2

2

ここには、おそらく 2 つの適切なオプションがあります。1 つ目は、関数はいくつかの値に依存するため、関数はそれらを引数として受け取ることができるということです。それはおそらくあなたがやろうとしていることを行うための最も明確な方法であり、呼び出しを行う前に変数の束を再バインドしたり割り当てたりする必要がないため、再帰呼び出しがよりクリーンになります。たとえば、単純な再帰関数は次のとおりです。

(defun swap-until-x-is-zero (x y)
  (print `(swap-until-zero ,x ,y))
  (unless (zerop x)
    (swap-until-x-is-zero (1- y) (1- x))))

CL-USER> (swap-until-x-is-zero 3 5)

(SWAP-UNTIL-ZERO 3 5) 
(SWAP-UNTIL-ZERO 4 2) 
(SWAP-UNTIL-ZERO 1 3) 
(SWAP-UNTIL-ZERO 2 0) 
(SWAP-UNTIL-ZERO -1 1) 
(SWAP-UNTIL-ZERO 0 -2) 
NIL

さて、それがいくつかの妥当なデフォルト値で始まることになっている場合、それらの関数の引数はオプションにすることができます:

(defun swap-until-x-is-zero (&optional (x 3) (y 5))
  (print `(swap-until-zero ,x ,y))
  (unless (zerop x)
    (swap-until-x-is-zero (1- y) (1- x))))

そして、あなたは単に呼び出すことができます(swap-until-x-is-zero):

CL-USER> (swap-until-x-is-zero)

(SWAP-UNTIL-ZERO 3 5) 
(SWAP-UNTIL-ZERO 4 2) 
(SWAP-UNTIL-ZERO 1 3) 
(SWAP-UNTIL-ZERO 2 0) 
(SWAP-UNTIL-ZERO -1 1) 
(SWAP-UNTIL-ZERO 0 -2)

このアプローチがハノイ問題にどのように適用できるかは明らかです。3 つのオプションの引数を に追加hanoiし、変更された値で再帰的に呼び出すだけです。

(defun towers-of-hanoi (disks &optional (source "Peg 1") (spare "Peg 2") (destination "Peg 3"))
  ...
  ;; instead of:
  ;;   (progn
  ;;     (setq tempPeg *Spare*)
  ;;     (setq *Spare* *Destination*)
  ;;     (setq *Destination* tempPeg) 
  ;;     (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1))))
  ;; we do:
  (let ((tempPeg spare))
    (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1))
                     source      ; stays the same
                     destination ; swap destination and spare
                     spare))     ; swap destination and spare
  ...)

そうは言っても、特別な変数（つまり、動的にスコープされた変数）を使用する方が簡単な十分なパラメーターがある場合があります（ただし、これはそのような場合ではないと思います）。それらを取得するには、special宣言を使用できます:

(defun towers-of-hanoi (disks)
  (declare (special *source* *spare* *destination*))
  (let ((tempPeg))
    (if (= (list-length disks) 1)
        (format t "Move ~{~A~} from ~A to ~A~%" (last disks) *Source* *Destination*) 
        (progn
          (setq tempPeg *Spare*)
          (setq *Spare* *Destination*)
          (setq *Destination* tempPeg) 
          (towers-of-hanoi (subseq disks 0 (- (list-length disks) 1)))
          ...))))

ただし、変数の初期バインディングを確立する必要があるため、最も外側の呼び出しについては、次のようにする必要があります。

(defun hanoi-driver (disks)
  (let ((*source* "Peg 1")
        (*spare* "Peg 2")
        (*destination* "Peg 3"))
    (declare (special *source* *spare* *destination*))
    (hanoi disks)))

&optional個人的には、単に 3 つの変数を追加するだけhanoiで、最終的にはよりクリーンなソリューションになると思います。

于 2013-07-14T13:16:55.507 に答える
1

リストの使用は慣用的ではありません。Lisp のリストは単結合のコンス セルであることを思い出してください。リストをトラバースしたり、リストの最後から作業したりするすべての操作は非効率的です。

あなたの質問に答えるには：

(defun do-something (a)
   (let ((foo 42))                            ; binding
      (labels ((do-something-recursively (b)  ; local recursive function
                 (...)))
        (do-something-recursively a))))
于 2013-07-14T19:22:02.877 に答える