2

So I have a list of integers and I'm trying to find the index where 

list(i) > list(i+1)

I have the base cases where if the list is empty or length 1, it returns the list length, but I'm having trouble with actually traversing the list and keeping track of the index.

The code I have right now:

(defunc out-of-order (l)
(cond ((or (equal (length l) 0) (equal (length l) 1)) (length l))
    ; this is where the index search goes

)
4

3 回答 3

2

这是一种模板，概述了解决问题的方法。

(defun out-of-order (list)
  (labels ((recur (list index)
             (cond ((or #<list is empty> #<list only has one item>)
                    nil)
                   ((> #<the first item> #<the second item>)
                    index)
                   (t
                    (recur #<advance the recursion> #<increment the index>)))))
    (recur list 0)))

想想过程的各个部分（#<these things>），以及它们各自对解决方案的贡献。填写它们将引导您找到解决方案，我认为还可以帮助您更好地理解递归过程。

当然，如果有不清楚的部分，请评论。

如果您不熟悉标签，这里的逻辑相同，但使用了外部帮助程序：

(defun out-of-order-aux (list index)
  (cond ((or #<list is empty> #<list only has one item>)
         nil)
        ((> #<the first item> #<the second item>)
         index)
        (t
         (out-of-order-aux #<advance the recursion> #<increment the index>))))

(defun out-of-order (list)
  (out-of-order-aux list 0))
于 2013-11-09T21:12:41.840 回答
2

编写一个递归函数，它接受“已遍历的节点数”的参数。在 内，使用已遍历的数字out-of-order调用该函数。0

......这对你来说足够了吗？再试一次，看看你能不能得到它。

另一个提示

 (defun out-of-order (lst)
   (out-of-order-rec lst 0))
 (defun out-of-order-rec (lst i)
   (if (or (endp lst) (endp (cdr lst)))
      ; something...
      (if (> (car lst) (car (cdr lst)))
         ; something...
         ; something...
         )))
于 2013-11-09T16:07:52.563 回答
0

无需递归执行此操作。在 Common Lisp 中，将其表示为显式循环更为惯用。这导致代码的可移植性更高，因为 Common Lisp 实现不需要消除尾调用。

你可以用一个简单的loop. 您有三个循环变量：当前元素、下一个元素和当前索引。一旦找到满足条件的当前元素和下一个元素，就返回当前索引。

(defun find-downstep-index (list)
  (if (endp (rest list))
      (length list)
      (loop :for current-element :in list
            :for next-element :in (rest list)
            :for current-index :upfrom 0
            :when (> current-element next-element)
            :do (return-from find-downstep-index current-index)
            :finally (return (+ current-index 2)))))

（如果没有找到这样的索引，返回列表长度的特殊行为会导致相当特别的初始保护并在末尾添加 2。在这种情况下返回会更常见nil，但也许有一些优化在周围使用中。）

于 2013-11-10T16:58:07.607 回答