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

Question

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

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

Answer 1

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

如果您真的陷入困境，I have a working implementation 。或者，这是一些类似伪代码的东西:

(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