Объединить две кучи с учетом отношения первого порядка

Что я должен сделать:

Определите процедуру SCHEME с именем (combine f Ha Hb), которая принимает три аргумента, f, отношение первого порядка, которое используется для упорядочения элементов в куче, и две структуры кучи, Ha и Hb, которые были построены с использованием одного и того же отношение первого порядка.

Пример тестового примера:

( define Ha ( heap-insert-list > ( list 9 5 7 3) ( list )))
( define Hb ( heap-insert-list > ( list 2 8 4 6) ( list )))
( combine > Ha Hb )
(9 (7 () (5 () (3 () ()))) (8 (4 () ()) (6 () (2 () ()))))

Мой код:

(define (create-heap v H1 H2)
(list v H1 H2))
(define (h-min H) (car H))
(define (left heap)
  (cadr heap))
(define (right heap)
  (caddr heap))

(define (combine f Ha Hb)
  (cond ((null? Ha) Hb)
    ((null? Hb) Ha)
    ((< (h-min Ha) (h-min Hb))
     (create-heap (h-min Ha)
                  Hb
                  (combine (left Ha) (right Ha))))
    (else
     (create-heap (h-min Hb)
                  Ha
                  (combine (left Hb) (right Hb)) Ha))))

Мой код делает что-то правильно, так как я получаю 50% в своих тестовых примерах, но он не проходит их полностью.


data-structures heap scheme racket r5rs
person carbonblast    schedule 31.03.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Ну, во-первых, вы не используете процедуру f! Этот:

((< (h-min Ha) (h-min Hb))

... Скорее всего должно выглядеть так:

((f (h-min Ha) (h-min Hb))

Также вы забыли передать параметр f при вызове рекурсии:

(combine f (left Ha) (right Ha))
person Óscar López    schedule 31.03.2020
comment
Это имеет смысл. Однако при попытке реализовать это все мои тестовые примеры потерпели неудачу. Я более-менее застрял на том, какие три параметра должна принимать моя функция объединения вместо двух в моем коде (слева Ха, справа Ха). - person carbonblast; 31.03.2020
comment
Вы также забыли передать параметр f при вызове рекурсии, код в вопросе изначально не компилировался. - person Óscar López; 31.03.2020