0

我目前正在尝试从点列表中编写一个函数，该函数返回从点 p 到我的点列表中离 p 最远的点的距离。我的要点如下：

((2 . 4) (3 . 6) (5 . 12) (-4 . 3) (8.4 . 9) (0 . -1))

我还做了一些抽象来检索一般的 car 和 cdr（为了在代码中更容易看到），以及列表本身的 car 和 cdr。

(define (get-x p) (car p)
(define (get-y p) (car p)


(define (get-first-point pt-list)
        (get-x pt-list))

(define (get-rest-points pt-list)
        (get-y pt-list))

我还写了一个通用距离公式，我可以将它用于我选择的任何两个点（请记住，我将 car 和 cdr 分别抽象为 get-x 和 get-y）。

(define (distance a b)
    (if (or (null? a) (null? b))
        0
        (sqrt (+ (expt (- (get-x a)
                          (get-x b))  2) 
                 (expt (- (get-y a) 
                          (get-y b))  2)))))

现在我有了这个，我知道我需要比较整个点集的各种距离并选择最大的返回值。我有一个部分解决方案，但不是一个对每一点都正确的解决方案。

(define (max-distance p pt-list)
    (if (null? pt-list)
        0
        (max (distance p (get-first-point pt-list)) ; 1
             (distance p (get-first-point (get-rest-points pt-list))) ; 2
             (distance p (get-first-point (get-rest-points (get-rest-points pt-list)))) ; 3
             (distance p (get-first-point (get-rest-points (get-rest-points (get-rest-points pt-list))))) ; 4
             (distance p (get-first-point (get-rest-points (get-rest-points (get-rest-points (get-rest-points pt-list)))))) ; 5
             (distance p (get-first-point (get-rest-points (get-rest-points (get-rest-points (get-rest-points (get-rest-points pt-list))))))) ; 6
    )
)

)

您可能可以了解我正在（可怕地）尝试做的事情的要点，但这就是我需要帮助的原因。

4

3 回答 3

3

在这种情况下，您希望将函数f折叠到点列表上。函数f应该采用距离d和点x并返回最大值d以及x和您的特殊指定点p之间的距离。我在其他一些答案中更详细地描述了折叠：

要点是在折叠中，您需要一个函数、一个初始值和一个列表。您将函数应用于列表的第一个元素和初始值以产生一些新值。现在您使用相同的函数、新值和列表的其余部分递归折叠。这本质上是一个这样的循环：

当前值=初始值
，而 列表不为空
     当前值=使用列表的第一个元素和当前值调用的函数的结果
     列表=列表的其余部分
返回 当前值

在保证尾调用优化的 Scheme 中，就是那个循环。在您的情况下，您只需要确定初始值应该是什么以及函数应该是什么。由于距离总是非负的，因此合理的初始值为零。功能有点复杂。当前值将是一个距离，但列表的第一个元素将是一个点。函数的结果需要是一个新的距离，新的距离应该是距离当前值与列表中某个点与特殊点之间的距离的最大值。在 Racket 中，这种弃牌被称为foldl，所以我们最终会得到这样的结果：

(define special-points '((2 . 4) (3 . 6) (5 . 12) (-4 . 3) (8.4 . 9) (0 . -1)))

(define (distance a b)
  (let ((square (lambda (x)
                  (* x x))))
    (sqrt (+ (square (- (car a) (car b)))
             (square (- (cdr a) (cdr b)))))))

(define (max-distance point points)
  (foldl (lambda (current-point current-distance)
           (max current-distance
                (distance point current-point)))
         0
         points))

> (max-distance '(4 . 12) special-points)
13.601470508735444
> (max-distance '(8 . 8) special-points)
13.0
> (max-distance '(2 . 5) special-points)
7.615773105863909

如果您不使用 Racket，则必须编写自己的foldl，但这真的不是很难。（这实际上并不像 Racket's 那样复杂foldl，它可以接受任何正数的列表，但它适用于这种情况。）

(define (foldl function initial-value list)
  (if (null? list)
      initial-value
      (foldl function
             (function (car list) initial-value)
             (cdr list))))
于 2013-10-23T16:54:56.340 回答
1

get-y应该使用cdr，不是car。

get-x并get-y错过了一个右括号。

因为max-distance，我会去

(define (max-distance p pt-list)
  (apply max (map (lambda (x) (distance p x)) pt-list)))

这意味着您不需要get-first-pointand get-rest-points。

插图（使用 (1 . 1) 作为 p）：

> (map (lambda (x) (distance '(1 . 1) x)) '((2 . 4) (3 . 6) (5 . 12) (-4 . 3) (8.4 . 9) (0 . -1)))
'(3.1622776601683795 5.385164807134504 11.704699910719626 5.385164807134504 10.897706180660222 2.23606797749979)

> (apply max (map (lambda (x) (distance '(1 . 1) x)) '((2 . 4) (3 . 6) (5 . 12) (-4 . 3) (8.4 . 9) (0 . -1))))
11.704699910719626

根据您对“最远”的定义，您可能希望将其包含abs在表达式中。

于 2013-10-23T09:14:25.600 回答
1

car计算到的距离points。该距离是最大值，或者是距离的cdr最大值points。结果是一个简单的遍历点列表的递归算法。

(define (max-distance-p p points)
  (if (null? points)
      0
      (max (distance p (car points))
           (max-distance-p p (cdr points)))))

0如果您points作为空列表传入，则返回 ；这可能有点可疑。如果是这样：

(define (max-distance-p p points)
  (assert (not (null? points)))
  (if (null? (cdr points))
      (distance p (car points))
      (max (distance p (car points))
           (max-distance-p p (cdr points)))))
于 2013-10-23T14:47:50.073 回答