scheme - 麻省理工学院计划中位数程序

Question

您将如何在不使用 list-ref 的情况下定义一个查找列表中位数的过程？例如，(median '(1 2 2))将返回 2 并(median '(1 2 3 4 5 6))返回 3.5。您可以假设它是一个排序整数列表。

这是一个家庭作业问题，所以请不要发布实际代码。我正在寻找的只是一些提示或一些伪代码来帮助我朝着正确的方向前进。如标题中所述，我正在使用 MIT 方案。提前致谢。

Answer 1

你知道如何使用龟兔赛跑算法吗？如果是这样，在您的算法完成后，您的乌龟将位于列表的中间。

如果你真的被卡住了，我有一个有效的实现。或者，这里有一些类似伪代码的东西：

(define (median lst)
  (if (null? lst) #f                         ;; oops, empty list
      (let loop ((tortoise <???>)
                 (hare <???>))
        (cond ((eq? tortoise hare) #f)       ;; oops, circular list
              ((null? hare) <???>)           ;; median value here
              ((null? (cdr hare)) <???>)     ;; average of middle two elements
              (else (loop <???> <???>))))))  ;; keep going

Answer 2

在中位数是列表中两个中间元素的平均值的情况下，使用 list-ref 将是低效的。原因是您将跳过列表的前半部分两次以找到两个中间元素。

一种解决方案是编写一个辅助函数(drop-list a-list n)来删除n列表的第一个元素。例如(drop-list '(a b c d e) 2)是'(c d e)。使用drop-list您现在可以执行以下操作：

1. 查找列表的长度
2. 如果长度是奇数，则使用 list-ref 选择中间元素
3. 如果长度是偶数，则使用 drop-list 删除中间两个元素之前的元素，然后计算结果的前两个元素的平均值。