функция, медиана в схеме

Question

Я новичок в Схеме, и я использую Dr.Racket, чтобы попытаться найти медиану списка.

Если длина списка L нечетна, функция median возвращает медианный элемент в списке. Если длина L четно, то функция возвращает 0. медиана пример

(median ‘(1)) returns 1 
(median ‘(1 2)) returns 0 
(median ‘(1 2 3)) returns 2 
(median ‘(1 2 3 4) returns 0 

я только разрешено использовать

- null? 
- car 
- cdr 
- else 
- = 
- + 
- median 
- cond 
- if 
- user defined names (for my variables) 
- integer literals 
- parentheses 

Есть идеи?

Answer 1

Эта проблема может быть решена с использованием tortoise and hare algorithm, если допускается внутренняя процедура помощника - нам нужно передать два параметра для этого. Кроме того, исполняются все ограничения:

(define (median lst) 
    (define (median tortoise hare) 
    (cond ((null? hare) 0) 
      ((null? (cdr hare)) (car tortoise)) 
      (else (median (cdr tortoise) (cdr (cdr hare)))))) 
    (median lst lst)) 

Он работает, как ожидалось:

(median '(1))  ; returns 1 
(median '(1 2))  ; returns 0 
(median '(1 2 3)) ; returns 2 
(median '(1 2 3 4)) ; returns 0