方案 - 如何使用用户定义的排序和平均函数找到中位数？

Question

我是 Scheme 新手，遇到了瓶颈。我有我的排序和平均函数，我正在尝试更改我在该站点上找到的中值函数。但是，无论我尝试什么，当我在中值函数中有多个表达式时，或者当我尝试在中值函数中使用 sort 时，我总是会收到错误 "undefined".

(define (sort1 L)
  (if (or (null? L) (<= (length L) 1)) L
    (let loop ((l null) (r null)
      (pivot (car L)) (rest (cdr L)))
        (if (null? rest)
          (append (append (sort1 l) (list pivot)) (sort1 r))
        (if (<= (car rest) pivot)
          (loop (append l (list (car rest))) r pivot (cdr rest))
          (loop l (append r (list (car rest))) pivot (cdr rest)))))))

(define (avg lst)
  (let loop ((count 0) (sum 0) (args lst))
    (if (not (null? args))
        (loop (add1 count) (+ sum (car args)) (cdr args))
        (/ sum count))))

(define (median L)
 (if (null? L) (error "The list is empty")
     (let loop ((L1 L) (L2 L))
       (cond ((null? (cdr L2)) (car L1))
             ((null? (cddr L2)) (list (car L1) (cadr L1)))
             (else (loop (cdr L1) (cddr L2)))))))

我正在尝试编辑中值函数以首先对列表进行排序，如果有偶数个元素，我需要取列表的平均值，并使用最接近平均值的元素。

如有任何帮助，我们将不胜感激，提前致谢。

Answer 1

我认为您误解了 median 的定义。一个非常简单（如果不是特别有效）的实现如下：

(define (my-sort L)
  (sort L <))

(define (average x y)
  (exact->inexact (/ (+ x y) 2)))

(define (median L)
  (if (null? L)
      (error "The list is empty")
      (let* ((n (length L))
             (sorted (my-sort L))
             (half (quotient n 2)))
        (if (odd? n)
            (list-ref sorted half)
            (average (list-ref sorted half)
                     (list-ref sorted (sub1 half)))))))

它按定义工作：

(median '())
=> The list is empty
(median '(3 2 1 5 4))
=> 3
(median '(6 4 3 1 2 5))
=> 3.5

Answer 2

正如我在评论中所说，您想要的不是 let，而是函数组合。

你当前的中值函数是这样的：

(define (median L)
  (if (null? L)
      (error "The list is empty")
      (let loop ((L1 L) (L2 L))
        (cond ((null? (cdr L2)) (car L1))
              ((null? (cddr L2)) (list (car L1) (cadr L1)))
              (else (loop (cdr L1) (cddr L2)))))))

但正如 Oscar Lopez 指出的那样，这并不能正确计算中位数。然而，它做了一些工作，所以保留它。将其重命名为 median-helper 或其他名称。

(define (median-helper L)
  (if (null? L)
      (error "The list is empty")
      (let loop ((L1 L) (L2 L))
        (cond ((null? (cdr L2)) (car L1))
              ((null? (cddr L2)) (list (car L1) (cadr L1)))
              (else (loop (cdr L1) (cddr L2)))))))

然后可以使用函数组合来定义"real"中值函数：

(define (median lst)
   (median-helper (sort1 lst)))

这个 returns 奇数长度列表的中间元素，偶数长度列表的中间两个元素。如果这是你想要的，太好了。如果不是，那么您可以通过返回 cond 的第二种情况的平均值来修复 median-helper。因此，您将 (avg (list (car L1) (cadr L1))).

而不是 (list (car L1) (cadr L1))

;; median-helper : (Listof Number) -> Number
(define (median-helper L)
  (if (null? L)
      (error "The list is empty")
      (let loop ((L1 L) (L2 L))
        (cond ((null? (cdr L2)) (car L1))
              ((null? (cddr L2)) (avg (list (car L1) (cadr L1))))
              (else (loop (cdr L1) (cddr L2)))))))

;; median : (Listof Number) -> Number
(define (median lst)
   (median-helper (sort1 lst)))

方案 - 如何使用用户定义的排序和平均函数找到中位数？

Scheme - How to find the median using user defined sort and average functions?

scheme

racket