Lisp中的十进制到二进制 - 创建一个非嵌套列表

Question

到达我的递归情况时,我使用list当前的结果附加未来结果,但由于递归,我最终得到了一个嵌套列表.当我有一个导致递归超过五次的数字时,这会导致错误.

任何想法如何在一个简单的非嵌套列表中得到结果,例如:

CL-USER 100:8>(BINARY_LIST 4)

(1 0 0)

代码和示例输出:

CL-USER 99 : 8 > (defun binary_list (i)
(COND 
    ((= i 0) 0)
    ((= i 1) 1)
    ((= (mod i 2) 0) (list (binary_list (truncate i 2)) 0))
    (t (list (binary_list (truncate i 2)) 1))
    )
)
BINARY_LIST

CL-USER 100 : 8 > (BINARY_LIST 4)
((1 0) 0)

CL-USER 101 : 8 > (BINARY_LIST 104)
((((# 1) 0) 0) 0)

Answer 1

你快到了.您需要做的就是替换list为nconc:

(defun binary-list (n)
  (cond ((= n 0) (list 0))
        ((= n 1) (list 1))
        (t (nconc (binary-list (truncate n 2)) (list (mod n 2))))))

您可以避免调用两者truncate并mod通过收集整数除法中的两个值:

(defun binary-list (n)
  (assert (>= n 0))
  (multiple-value-bind (q r) (floor n 2)
    (if (zerop q)
        (list r)
        (nconc (binary-list q) (list r)))))

请注意,此算法是二次的,因为nconc必须在每次迭代时遍历结果.通过传递累加器可以避免这种情况:

(defun binary-list (n &optional acc)
  (assert (>= n 0))
  (multiple-value-bind (q r) (floor n 2)
    (if (zerop q)
        (cons r acc)
        (binary-list q (cons r acc)))))

现在我们有一个尾递归函数,可以通过现代编译器编译为迭代.

您可以使用的另一个优化技巧(事实上,应该由编译器完成 - 尝试disassemble检查!)正在使用ash而logand不是更通用和昂贵的floor:

(defun binary-list (n &optional acc)
  (cond ((zerop n) (or acc (list 0)))
        ((plusp n)
         (binary-list (ash n -1) (cons (logand 1 n) acc)))
        (t (error "~S: non-negative argument required, got ~s" 'binary-list n))))

顺便提一句,lispers通常在符号中使用破折号而不是下划线,所以如果你不想冒犯我们温柔的美学,你binary_list应该binary-list这样做.