2

我在使用 common lisp 计算两个位向量之间的距离时遇到问题。

我对 lisp 很陌生，这是我的人工智能作业的最后一道作业问题，我相信我遇到的问题是语法问题。

这是问题：

在由 1 和 0 的列表表示的相同长度的两个位向量之间编写递归函数 DISTANCE。例如，

（距离'（1 0 1 1）'（0 1 0 1））

答案：3

讨论如果向量的长度不同，必须做什么。

据我了解，两个位向量之间的距离只是对两者进行异或运算，然后计算 1。

使用该示例，我们将有 1011 ^ 0101 = 1110 等于 3。

假设这是计算距离的正确方法，那么我的问题是找到一种在 lisp 中进行 XOR 的方法，以及使其递归。

如何获取两个列表并将它们放入我可以使用的格式logxor （如图所示），然后计算结果列表中的 1？

在尝试这样做(logxor '(1 0 1 1) '(0 1 0 1))时，它告诉我 '(1 0 1 1) 不是整数，因此它似乎logxor不适用于列表，这让我不知所措。

您可以提供的任何帮助将不胜感激

谢谢！

4

5 回答 5

7
于 2014-02-10T01:06:41.797 回答
4

LOGXOR 适用于数字：

CL-USER 43 > (logxor 2 1)
3

还有一种符号可以将数字写为 0 和 1。

CL-USER 44 > (logxor #b1010 #b0101)
15

也可以看看：

CL-USER 45 > (logcount (logxor #b1011 #b0101))
3
于 2014-02-09T20:17:51.817 回答
1

简单递归版本不是尾递归：

(defun distance (v u)
  (cond ((null v) (length u)) ; assume that missing is different from both 0 & 1
        ((null u) (length v)) ; ditto
        (t (+ (if (= (first u) (first v)) 0 1) 
              (distance (rest v) (rest u))))))

这对应于距离的公理化定义（差异的数量）为

  1. 如果一个向量为空，则距离是另一个向量的长度
  2. 距离是加法的：dist(v1,u1)+dist(v2,u2)=dist(v1+v2,u1+u2)如果length(v1)=length(u1)；+表示串联
  3. 如果length(v1)=length(v2)=1, 那么dist(v1,v2):=(v1==v2? 0 : 1)

如果您需要尾递归版本（编译器可以更轻松地将其转换为迭代），则需要将部分结果与函数一起携带。

于 2014-02-09T20:43:35.640 回答
1

只需映射logxor到您的列表：

? (mapcar #'logxor '(1 0 1 1) '(0 1 0 1))
(1 1 1 0)

数一下：

? (count 1 (mapcar #'logxor '(1 0 1 1) '(0 1 0 1)))
3

或者只是将所有内容加在一起：

? (apply #'+ (mapcar #'logxor '(1 0 1 1) '(0 1 0 1)))
3

现在您只需要将其转换为递归

(defun distance (lst1 lst2)
  (if (or (null lst1) (null lst2))
    0
    (+ (logxor (car lst1) (car lst2))
       (distance (cdr lst1) (cdr lst2)))))

或尾递归版本：

(defun distance (lst1 lst2 &optional (res 0))
  (if (or (null lst1) (null lst2))
    res
    (distance (cdr lst1) 
              (cdr lst2) 
              (+ res (logxor (car lst1) (car lst2)))))))

然后

? (distance '(1 0 1 1) '(0 1 0 1))
3
于 2014-02-09T19:59:33.810 回答
0

如果你想使用一个简单的 defun 语句，你总是可以做类似的事情。

(defun distance (a b)
     (cond
          ((equal nil a) 0)
          (t (+ (rem (+ (first a) (first b)) 2) (distance (rest a) (rest b))))
     )
)
于 2014-02-09T20:18:26.040 回答