Как бы вы определили процедуру поиска медианы списка без использования list-ref? Например, (median '(1 2 2)) вернет 2, а (median '(1 2 3 4 5 6)) вернет 3,5. Можно предположить, что это список отсортированных целых чисел.
Это вопрос домашнего задания, поэтому, пожалуйста, не публикуйте фактический код. Все, что я ищу, это какие-то подсказки или какой-то псевдокод, который поможет мне двигаться в правильном направлении. Как указано в заголовке, я использую схему MIT. Заранее спасибо.
Вы знаете, как использовать алгоритм черепахи и зайца? Если да, то после завершения алгоритма ваша черепаха окажется в середине списка.
Если вы действительно застряли, у меня есть работающая реализация. Или вот что-то похожее на псевдокод:
(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
В случае, когда медиана является средним значением двух средних элементов в списке, использование list-ref будет неэффективным. Причина в том, что вам придется дважды пропустить первую половину списка, чтобы найти два средних элемента.
Одним из решений является написание вспомогательной функции (drop-list a-list n), которая удаляет первые n элементов списка. Например. (drop-list '(a b c d e) 2) это '(c d e). Теперь с помощью drop-list вы можете сделать следующее:
list-ref не столько для эффективности, сколько для демонстрации понимания алгоритма черепахи и зайца. :-)
- person Chris Jester-Young; 17.03.2013
