递归欧氏距离

Question

我的任务是编写递归欧氏距离。我一直在谷歌搜索但找不到任何样本。我了解欧几里德距离的功能，并且以如下所示的迭代方式编写它没有问题。有没有人可以建议我应该如何开始递归函数？要求与迭代版本相同。谢谢。

 (defun euclidean-distance-it (p q)  
  (cond
   ((or (null p) (null q)) nil) ;return nil if either list is null
   ((or (atom p) (atom q)) nil) ;return nil if either list is an atom
   ((or (null (cdr p)) (null (cdr q))) nil);return nil if either list contains less than two inputs

   ((or (not (null (car(cdr(cdr p))))) (not (null (car(cdr(cdr q)))))) nil) ;return nil if either list contains more than two inputs
   ((or (or (not (numberp (car p))) (not (numberp (cadr p)))) (or (not (numberp (car q))) (not (numberp (cadr q))))) nil);return nil if any of the four entires aren't numbers
   (T (sqrt (+ (expt (- (car p) (car q)) 2)
              (expt (- (cadr p) (cadr q)) 2)))))) ;Calculate the euclidean distance

Answer 1

查看this Haskell thread，我认为你的任务更有可能计算n维向量的距离，即sqrt((x1-y1)^2 + ... + (xn-yn)^2)。

在您的示例中没有迭代，您只需访问两个列表中的元素。换句话说：您假设 P 和 Q 包含 2 个元素，我认为问题是将其推广到 N 个元素。

此外，您正在做许多无用的检查，以便 return nil 而不是让错误发出信号。例如，如果列表不包含数字，您可能应该 not return nil。

我会这样重写你的版本：

(defun euclidean-distance-it (p q)
  (destructuring-bind (x1 x2) p
    (destructuring-bind (y1 y2) q
      (sqrt (+ (expt (- x1 y1) 2)
               (expt (- x2 y2) 2))))))

对于递归版本，我认为p和q是两个数学向量，因此p包含不同的坐标(p1, ..., pn)，这与您的实现不同其中 p 包含所有 x，q 包含所有 y。

因此，您必须为从 p 和 q 中并行获取的元素对 (pi, qi) 的每个元素计算 (pi - qi)^2，对中间值求和并取平方根。有了高阶函数，你甚至不需要使用递归。

我不会破坏你的递归答案，但这里有一个高阶函数版本：

(defun distance (p q) 
  (sqrt
    (reduce #'+ 
      (map 'list
        (lambda (px qx) (expt (- px qx) 2)) 
        p q))))

另一个 loop:

(defun distance (p q)
  (sqrt (loop for px in p
              for qx in q
              sum (expt (- px qx) 2))))

Answer 2

如果输入是任意维度的两个向量（由列表表示），而不仅仅是 2 或 3，则唯一的时间递归算法将是明智的。在这种情况下，这将计算平方的距离：

(defun sq-euclid-distance (p q)
  (cond ((or (null p) (null q)) 0)
        (t (+ (expt (- (car p) (car q)) 2)
              (sq-euclid-distance (cdr p) (cdr q))))))

要从中获得 SQRT，您需要将其变成辅助助手并制作计算平方根的驱动程序。

(defun euclid-distance (p q) (sqrt sq-euclid-distance p q))

PS。我不检查 p 和 q 是否是原子，但它们可以被视为一维向量。从预期提供数值的函数返回 NIL 不是一个好主意。

递归欧氏距离

Recursive euclidean distance

lisp

recursion