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

27 August, 2007 (20:50) | Решения упражнений

В этом упражнении нет никаких хитростей. Нужно просто быть внимательным и уметь рисовать бинарные деревья (это не так просто как кажется). Правильное дерево приведено на рисунке ниже.

Решение

В качестве иллюстрации важности внимательности приведу решение Кена Дика. Найдите в нем ошибку в одном узле.

Теперь перейдем к оценке порядка роста требуемой памяти и числа шагов при увеличении суммы размена.

При вызове процедуры CC в памяти требуется объем, пропорциональный глубине соответствующего параметрам вызова узла дерева. Так как максимальная высота дерева растет линейно с ростом суммы, которую требуется разменять, порядок роста памяти также линеен (Θ(n)).

А вот с числом шагов расчет не так прост. Нас спрашивают, как растет число шагов с ростом суммы. Про номиналы и количество монет ничего не говорится, потому будем предполагать, что они остаются прежними (5 монет достоинством в 1, 5, 10, 25 и 50 центов). Нас интересует асимптотический рост (порядок роста), потому будем считать, что сумма достаточно велика и много больше номиналов монет. Очевидно, что число шагов, необходимых для вычисления (CC n 1) равно Θ(n).

При вычислении (CC n 2) при достаточно большом n нам нужно вычислить (CC n 1) и (CC n-5 2).  Повторив эту редукцию для второго выражения примерно n/5 раз мы получим результат. То есть нам потребуется примерно n/5 итераций, на каждой из которых делается Θ(n) шагов, а значит общее число шагов будет Θ(n²).

Рассуждая аналогичным образом приходим к тому, что число шагов равно Θ(nk), где n – сумма для размена, k – число номиналов монет. В нашем случае с пятью номиналами ответ получается Θ(n5).

Хочу отметить, что и у Эли Бендерски, и у Кена Дика решение этого упражнения в части оценки числа шагов не выдерживает никакой критики. Поэтому упражнение не такое простое, как может показаться.

Comments

Comment from thror
Date: February 14, 2008, 11:51 pm

А вот так можно автоматически построить требуемое в задании дерево. И вы нигде не ошибетесь, и бумаги не потратите (дерево-то большое =) у меня на лист A4 только кусками влезло =))

(define (mknode amount kinds-of-coins left right)
  (list amount kinds-of-coins left right))

(define (mkleaf amount)
  (list amount))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
	((= kinds-of-coins 2) 5)
	((= kinds-of-coins 3) 10)
	((= kinds-of-coins 4) 25)
	((= kinds-of-coins 5) 50)))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) (mkleaf 1))
	((or (< amount 0) (= kinds-of-coins 0)) (mkleaf 0))
	(else (mknode amount
		      kinds-of-coins
		      (cc amount
			  (- kinds-of-coins 1))
		      (cc (- amount (first-denomination kinds-of-coins))
			  kinds-of-coins)))))

(define (count-change amount)
  (cc amount 5))

(count-change 11)

–thror

Comment from Sergey Khenkin
Date: February 15, 2008, 9:45 am

Да, дерево немаленькое и строить его вручную задачка не самая веселая. Я точно знаю 🙂
Но, безусловно, для начинающего смысл поработать руками есть.

Однако понимание того, как можно применить к рутинной задаче автоматизацию, также очень важно.

Comment from Sergey Khenkin
Date: February 15, 2008, 9:46 am

Кстати, в новом варианте интерфейса картинка съехала. Сейчас поправил. Спасибо, благодаря комментарию обратил на это внимание.

Comment from Vlad
Date: June 30, 2008, 2:26 pm

Дело в том, что сложность алгоритма зависит так же от номинала монет, а не только от их количества. Например количество вызовов сс при номинале монет из книги для 130 ровняется 41.175, а при номиналах (1,5,10,15,20) уже 100.069. Это не учтено ни в одном из приведеных решений. Стоит отметить, что Ваш вариант 130^5=37.129.300.000 очень далек от истины.

Comment from gorilych
Date: September 23, 2008, 11:13 am

у меня, достаточно простыми (и схожими по рассуждению) выкладками получилось, что сложность алгоритма (количество узлов в дереве) пропорциональна сумме в степени количества номиналов и обратно пропорциональна перемноженным номиналам.

то есть сложность (cc n 1) – n/1, сложность (cc n 2) – n^2/1/5 … сложность (cc n 5) – n^5/1/5/10/25/50

В выкладках последовательно определяется сложность (cc n 1), потом через неё – сложность (cc n 2), а потом обобщённо можно получить, как из сложности (cc n (m-1)) получить сложность для (cc n m).

При этом сколько занято в памяти процессом – определяется только монетой наименьшего номинала – глубина дерева практически всегда n/1 (сумма, поделённая на наименьший номинал)

То есть наши выводы совпадают

Comment from Ayrat
Date: March 31, 2010, 7:54 pm

Я практически проверил ваше решение о количестве шагов Θ(n5). Оно оказалось верным. Сам я не додумался, вообще сложновато как-то дается эта тема с порядками роста, может посоветуете дополнительную литературу на эту тему?
А вот насчет важности внимательности, найдите ошибку в своем дереве =)

Comment from Александр
Date: July 27, 2012, 11:25 am

Ayrat, гдеее там ошибка? O_o

Comment from В.Колесников
Date: September 3, 2015, 6:28 pm

Тоже делаю SICP. Подглядываю иногда к вам. Ошибка в дереве есть) Самый нижний лист должен быть (сс 0 1), а у вас – (сс 1 1) насколь это можно разглядеть.

Comment from regbot
Date: April 27, 2018, 6:55 pm

Так как максимальная высота дерева растет линейно с ростом суммы, которую требуется разменять, порядок роста памяти также линеен (Θ(n)).

Это не очевидно.

Write a comment