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

18 February, 2008 (20:42) | Решения упражнений

На самом деле построить процедуру successive-merge совсем не сложно. Алгоритм наших действий прост. Мы будем хранить все деревья и листья в упорядоченном по возрастанию веса списке. Раз так, два самых легких элемента всегда будут находиться на двух первых позициях в списке. Стало быть, нам достаточно на каждом этапе алгоритма последовательного слияния брать два первых элемента из списка, соединять их в один и возвращать полученное дерево обратно в список (при этом оно в нем займет место в соответствии со своим весом, то есть список сохранит свойство упорядоченности). На каждом шаге количество элементов в списке уменьшается на один. Заканчиваем слияния мы тогда, когда в списке остался ровно один элемент, который и является искомым деревом Хаффмана.

Процедура successive-merge, реализующая эту идею, представлена ниже:

(define (successive-merge trees) 
  (if (null? (cdr trees)) 
      (car trees) 
      (successive-merge (adjoin-set (make-code-tree (car trees) 
                                                    (cadr trees)) 
                                    (cddr trees)))))

Определение не лишено некоторой элегантности.

Comments

Pingback from SICP по-русски » Решение упражнения 2.70 из SICP
Date: February 18, 2008, 9:33 pm

[…] процедуру generate-huffman-tree, построим следующее дерево для заданного […]

Comment from skolkerom
Date: July 27, 2013, 2:24 pm

Или так:

(define (successive-merge tree)
  (define (successive-merge-inner tree result)
    (cond ((null? result)  (successive-merge-inner (cdr tree) (car tree))) 
          ((null? (cdr tree))  (make-code-tree (car tree) result))
          (else (successive-merge-inner (cdr tree) (make-code-tree (car tree) result)))))
  (successive-merge-inner tree '()))

Comment from Sergk
Date: April 4, 2015, 1:15 pm

Упорядоченное множество не обязательно должно быть хронологическим. Поэтому если считать, что процедура make-leaf-set написана нами так , что пары идут начиная с той у которой самая большая частота, то процедуру можно записать таким образом:

(define (successive-merge set)
  (if (null? (cdr set))
      (car set)
      (make-code-tree (make-leaf (caar set) (cadr set))
                                (successive-merge (cdr set)))))

Comment from Sergk
Date: April 5, 2015, 9:28 am

ошибочка вместо (cadr set) — (cadar set)

Comment from Sergk
Date: April 5, 2015, 10:35 am

Всё напутал вот 100% правильный вариант)))

(define (successive-merge set)
  (if (null? (cdr set))
      (make-leaf (caadar set) (cadadar set))
      (make-code-tree (make-leaf (caadar set) (cadadar set))
                      (successive-merge (cdr set)))))

если у кого не определяет (cadadar set) то :

(define (cadadar x)
  (car (cdadar x)))

Write a comment