2

次のように、リストを右または左に回転させるために、LISP に再帰関数があります。

(数値が正の場合は左に押し、負の場合は右に押します)

> (rotate-n ‘(5 6 7 8 9) -3)
    (7 8 9 5 6)

> (rotate-n ‘(5 6 7 8 9) 3)
    (8 9 5 6 7)

関数：

(defun rotate-n (L n)
  (cond ((= n 0) L)
        ((> n 0) (rotate-n (rotate-left L) (- n 1)))
        ((< n 0) (rotate-n (rotate-right L) (+ n 1)))))

末尾再帰を使用して同じ結果を得る方法はありますか? 関数rotate-rightとrotate-leftは正常に機能します。

編集：混乱しました。上で書いた関数は末尾再帰です。私が間違っていなければ、この関数は同じ目的のための通常の再帰です:

(defun rotate-n-r (L n)
  (cond ((= n 0) L)
        ((> n 0) (rotate-left (rotate-n-r L (- n 1))))
        ((< n 0) (rotate-right (rotate-n-r L (+ n 1))))))
4

1 に答える 1

1

これは、必要なことを行う末尾再帰関数です。

(defun rotate-list (list n)
  (cond ((plusp n)
         (rotate-list
          (append (rest list) (list (first list)))
          (1- n)))
        ((minusp n)
         (rotate-list
          (append (last list) (butlast list))
          (1+ n)))
        (t list)))

大量に消費する (つまり、メモリを割り当てる) ことに注意してください。

(ext:time (rotate-list '(5 6 7 8 9) 30))
                                           Permanent            Temporary
Class                                 instances   bytes    instances   bytes
-----                                 --------- ---------  --------- ---------
CONS                                          5        80        145      2320
-----                                 --------- ---------  --------- ---------
Total                                         5        80        145      2320
Real time: 3.2E-5 sec.
Run time: 0.0 sec.
Space: 2400 Bytes
(5 6 7 8 9)

非consingバージョン:

(defun nrotate-list (list n )
  (cond ((plusp n)
         (nrotate-list
          (nconc (rest list) (progn (setf (cdr list) nil) list))
          (1- n)))
        ((minusp n)
         (nrotate-list
          (nconc (last list) (nbutlast list))
          (1+ n)))
        (t list)))

末尾再帰である間は何も割り当てません:

(time (nrotate-list '(5 6 7 8 9) 30))
Real time: 2.3E-5 sec.
Run time: 0.0 sec.
Space: 0 Bytes
(5 6 7 8 9)

どちらのバージョンも、パフォーマンスに関してかなりばかげていることに注意してください (反復ごとにリストを 2 回スキャンします。つまり、時間計算量は ですO(n*length(list)))。

効率的なバージョンでは、リストを1 回だけスキャンし(つまり、時間の複雑さO(length(list)))、再帰的ではありません。

于 2013-01-01T18:14:44.177 に答える