Решение упражнения 2.62 из SICP

12 February, 2008 (21:41) | Решения упражнений

Идея реализации union-set за линейный проход абсолютно аналогична идее, положенной в основу intersection-set из книги. Мы движемся параллельно по двум спискам и сравниваем их текущие первые элементы. Если они равны, мы решаем задачу для хвостов списков и приписываем любой из двух равных головных элементов в начало. Если же один из элементов меньше другого, то его гарантированно нет во втором списке, а значит мы решаем задачу для хвоста его списка и всего второго списка, а затем приписываем этот минимальный элемент в начало результата. Идею иллюстрирует следующее определение процедуры:

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
         (let ((x1 (car set1)) (rest1 (cdr set1))
               (x2 (car set2)) (rest2 (cdr set2)))
           (cond ((= x1 x2) (cons x1 (union-set rest1 rest2)))
                 ((< x1 x2) (cons x1 (union-set rest1 set2)))
                 (else (cons x2 (union-set set1 rest2))))))))

Под головным элементом списка s я подразумеваю (car s), а хвостом обзываю (cdr s).

Comments

Comment from White
Date: March 30, 2010, 6:34 pm

Концептуально ничего нового

(define (union set1 set2)
  (cond
    [(null? set1) set2]
    [(null? set2) set1]
    [(= (car set1) (car set2)) (cons (car set2) (union (cdr set1) (cdr set2)))]
    [(< (car set1) (car set2)) (cons (car set1) (union (cdr set1) set2))]
    [#t (cons (car set2) (union set1 (cdr set2)))]))

Write a comment