十进制二进制Lisp的 - 使非嵌套列表 [英] Decimal to Binary in Lisp - make a non-nested list

问题描述

当我到达的情况下递归，我使用列表未来结果追加与当前的一个，但我最终因为递归的嵌套列表。这将导致一个错误，当我有一个数字，导致递归五倍以上。

任何想法我怎么能在一个普通的非嵌套列表，例如得到的结果：

  

CL-用户100：8>（BINARY_LIST 4）

  
  

（1 0 0）

code＆放;输出示例：

  CL-USER 99：8' （defun函数binary_list（I）
（条件
    （（= I 0）0）
    （（= I 1）1）
    （（=（MOD I 2）0）（列表（binary_list（截断I 2））0））
    （T（名单（binary_list（截断I 2））1））
    ）
）
BINARY_LISTCL-USER 100：8是氢。 （BINARY_LIST 4）
（（1 0）0）CL-USER 101：8是氢。 （BINARY_LIST 104）
（（（（＃1）0）0）0）
 

解决方案

您几乎没有。所有你需要做的是更换 列表 与 nconc ：

 （二进制defun函数列表（N）
  （条件（（= N 0）（列表0））
        （（= N 1）（表1））
        （T（nconc（二进制列表（截断N 2））（列表（MOD N 2））））））
 

您可以避免调用这两个 截 和 MOD 通过在整数除法收集这两个值：

 （二进制defun函数列表（N）
  （断言（大于= N 0））
  （多值绑定（Q R）（楼N 2）
    （如果（zerop q）的
        （表R）
        （nconc（二进制列表Q）（列表R）））））
 

请注意，该算法的二次的 nconc 有遍历每个迭代的结果。这可以通过传递一个累加器来避免：

 （二进制defun函数列表（N＆安培;可选ACC）
  （断言（大于= N 0））
  （多值绑定（Q R）（楼N 2）
    （如果（zerop q）的
        （缺点 -  [R ACC）
        （二进制列表Q（缺点 -  [R ACC）））））
 

现在我们已经能够由现代编译器编译为迭代尾递归功能

还有一招最优化您可以使用（其中，事实上的应的由编译器完成 - 尝试的 拆卸 来检查！）正在使用的 灰分 和的 logand ，而不是更具通用性和昂贵的 地板 ：

 （二进制defun函数列表（N＆安培;可选ACC）
  （条件（（zerop N）（或ACC（列表0）））
        （（plusp N）
         （二进制列表（灰N-1）（缺点（1 logand N）ACC）））
        （T（错误382 4：要求非负的说法，得到了〜的二进制名单N））））
 

顺便说一句，lispers平时使用，而不是符号下划线破折号，所以你的 binary_list 应二进制列表如果你不想得罪我们的招标美学。

When reaching my recursion cases, I use list to append the future result with the current one, but I end up with a nested list because of recursion. This causes an error when I have a number that causes recursion for more than five times.

Any ideas how I can get results in a single plain non-nested list, e.g.:

CL-USER 100 : 8 > (BINARY_LIST 4)

(1 0 0)

Code & Example output:

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)

解决方案

You are almost there. All you need to do is to replace list with 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))))))

You can avoid calling both truncate and mod by collecting both values in integer division:

(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)))))

Note that this algorithm is quadratic because nconc has to traverse the result on each iteration. This can be avoided by passing an accumulator:

(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)))))

Now we have a tail-recursive function which can be compiled to iteration by a modern compiler.

One more optimization trick you could use (which, in fact, should be done by the compiler - try disassemble to check!) is using ash and logand instead of the much more general and expensive 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))))

Incidentally, lispers usually use dash instead of underscores in symbols, so your binary_list should be binary-list if you do not want to offend our tender aesthetics.

这篇关于十进制二进制Lisp的 - 使非嵌套列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！