Решение упражнения 2.19 из SICP
Определить процедуры no-more?, first-denmomination и except-first-denomination можно таким образом:
(define (no-more? coin-values) (null? coin-values))
(define (first-denomination coin-values) (car coin-values))
(define (except-first-denomination coin-values) (cdr coin-values))
Определения тривиальны, но это достигается продуманностью процедуры cc, которая берет сложность работы на себя.
Порядок списка coin-values на результат не влияет, так как алгоритм, реализуемый процедурой cc, работает независимо от того, как упорядочены номиналы монет. Проверим это:
> (define us-coins (list 50 25 10 5 1)) > (define us-coins-reversed (list 1 5 10 25 50)) > (cc 30 us-coins) 18 > (cc 30 us-coins-reversed) 18 > (cc 100 us-coins) 292 > (cc 100 us-coins-reversed) 292
Результаты действительно идентичны.
Comments
Comment from Sergey Khenkin
Date: January 26, 2008, 7:27 pm
Очень симпатичную попытку обоснования того, почему порядок расположения номиналов монет в списке не влияет на результат вычисления количества способов размена, пытается привести Эли Бендерски у себя на странице http://eli.thegreenplace.net/2007/08/10/sicp-section-221/.
Его идея заключается в том, чтобы рассмотреть дерево рекурсии вызовов процедуры cc до глубины 2 (то есть первые два уровня рекурсии). Пусть нам нужно разменять сумму N монетами номиналов a, b, c, …, z.
Тогда дерево вызовов процедуры cc можно описать схематично так:
(N; a, b, c, ..., z) | +-- (N; b, c, ..., z) | | | +-- (N; c, ..., z) | | | +-- (N-b; b, c, ..., z) | +-- (N-a; a, b, c, ..., z) | +-- (N-a; b, c, ..., z) | +-- (N-a-a; a, b, c, ..., z)
К сожалению, Эли делает небольшую ошибку (скорее всего, играет свою пагубную роль wishful thinking) и записывает последнюю строчку как (N-a-b; a, b, c, …, z), после чего утверждает, что полученные 4 результата симметричны относительно a и b, то есть их можно переставить и ничего не поменяется.
Очень красивое доказательство, но, к сожалению, с ошибкой.
Мне кажется, для доказательства отсутствия влияния порядка следования номиналов на результат достаточно доказательства корректности применяемого алгоритма, так как это автоматически исключает два разных решения одной и той же задачи (ведь число ваирантов размена очевидно не может зависеть от порядка номиналов).
Comment from gorilych
Date: July 19, 2008, 7:32 am
Лемма. Пусть C(S, a_0, a_1, .., a_n) – количество способов размена суммы S монетами номиналов a_0, a_1, .., a_n. Тогда
C(S, a_0, a_1, .., a_n) = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)
Доказательство<<<<<<<< расширенный набор входит в L. При этом он содержит добавленную монету номиналом a_0 => входит в L1. При убирании монеты номиналом a_0, получим исходный набор и при этом по способу построения L1′ он будет туда входить – противоречие.
Таким образом, мощность L1 = мощность L1` = C(S – a_0, a_0, a_1, .., a_n)
C(S, a_0, a_1, .., a_n) = мощность L = Мощность L2 + мощность L1 = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)
чтд
>>>>>>>>>>
Доказанная лемма показывает, что способ разветвления в алгоритме правилен
Докажем теперь следующее утверждение: алгоритм, используемый в задаче, корректен, то есть находит все возможные варианты и при этом не учитывает один и тот же вариант более одного раза.
Доказательство методом индукции по количеству номиналов монет n для набора произвольной суммы S.<<<<<<<<<
При n = 1 утверждение доказывается элементарно. Алгоритм отнимает от S номинал монеты, пока не дойдёт до нуля, либо до отрицательного числа. Первое означает, что S кратно номиналу, имеется один единственный вариант и возвращается 1. Во втором случае алгоритм вернёт 0, поскольку S не делится на номинал нацело. При подсчёте алгоритм не разветвляется, поскольку второй вызов сразу возвращает ноль для пустого списка.
Допустим, что утверждение верно для n номиналов. Докажем его для n + 1.
пусть k = S mod a_0
алгоритм подсчёта C(S, a_0, a_1, .., a_n) рекурсивно вызывает сам себя для подсчёта
C(S, a_1, .., a_n), C(S – a_0, a_0, a_1, .., a_n);
C(S – a_0, a_1, .., a_n), C(S – a_0 – a_0, a_0, a_1, .., a_n);
C(S – a_0 – a_0 – a_0, a_0, a_1, .., a_n), C(S – a_0 – a_0 – a_0, a_1, .., a_n);
…
C(S – (k-2)*a_0, a_1, .., a_n), C(S – (k-1)*a_0, a_0, a_1, .., a_n);
C(S – (k-1)*a_0, a_1, .., a_n), C(S – k*a_0, a_0, a_1, .., a_n);
C(S – k*a_0, a_1, .., a_n), C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n)
Поскольку [S – (k+1)*a_0] = 0, то алгоритм обрубается:
– либо на подсчёте C(S – k*a_0, a_0, a_1, .., a_n), при [S – k*a_0] = 0
– либо на подсчёте C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n), при [S – k*a_0] > 0
Корректность вычисления каждой суммы зависит от корректности вычисления последующих, что следует из леммы.
Корректность вычисления каждой C(S – j*a_0, a_1, .., a_n) вытекает из предположения индукции.
Следовательно, нам нужно доказать только корректность вычисления C(S – (k-1)*a_0, a_0, a_1, .., a_n), поскольку из этого следует по цепочке корректность вычисления всех остальных сумм вида C(S – j*a_0, a_0, a_1, .., a_n) вплоть до C(S, a_0, a_1, .., a_n).
Возможны два случая:
1) [S – k*a_0] = 0
Тогда [S – (k-1)*a_0] = a_0, C(S – (k-1)*a_0, a_0, a_1, .., a_n) = C(a_0, a_0, a_1, .., a_n).
Множество L1, обсуждаемое в лемме, состоит всего из одного набора, в который включается одна монета номиналом a_0. Следовательно
C(a_0, a_0, a_1, .., a_n) = 1 + C(a_0, a_1, .., a_n). Вспомним при этом, что именно 1 возвращает алгоритм, в случае равенства нулю передаваемой ему суммы (а ему и передастся [a_0 – a_0] = 0). Ну а подсчёт C(a_0, a_1, .., a_n) опять же корректен по предположению индукции.
2) [S – k*a_0] > 0.
При этом [S – (k+1)*a_0] [S – k*a_0] … C(S – j*a_0, a_0, a_1, .., a_n) … => подсчёт C(S, a_0, a_1, .., a_n) корректен
чтд
>>>>>>>>>>
Comment from gorilych
Date: July 19, 2008, 7:35 am
Зря я угловых скобок напихал…
Ещё раз. ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ АЛГОРИТМА
Лемма. Пусть C(S, a_0, a_1, .., a_n) – количество способов размена суммы S монетами номиналов a_0, a_1, .., a_n. Тогда
C(S, a_0, a_1, .., a_n) = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)
Доказательство
==============
Очевидно, что множество всевозможных различных наборов монет L, составлющих сумму S, можно разделить на два непересекающихся подмножества – подмножество L1 наборов, содержащих монету номиналом a_0, и подмножество L2, без монет с таким номиналом. Действительно, в наборе либо есть, либо нету такой монеты, поэтому нет такого набора, который входит одновременно в оба подмножества и поэтому они не пересекающиеся. Следовательно мощность множества L равна сумме мощностей подмножеств.
Мощность L2 равна C(S, a_1, .., a_n), поскольку любой набор из монет a_1, .., a_n с суммой S входит в L и при том входит в L2, поскольку не содержит монет с номиналом a_0.
Поскольку каждый набор в L1 содержит хотя бы одну монету номинала a_0 то из L1 можно получить равномощное множество L1′, убрав из каждого набора по одной монете ном. a_0. При этом сумма каждого набора уменьшится на величину номинала и будет равна (S – a_0).
Покажем от противного, что L1′ содержит все возможные наборы монет номиналами a_0, a_1, .., a_n с суммой (S – a_0). Пусть есть такой набор, не входящий в L1′, сумма которого равна (S – a_0). Добавим к этому набору монету номиналом a_0. Сумма набора станет равной S => расширенный набор входит в L. При этом он содержит добавленную монету номиналом a_0 => входит в L1. При убирании монеты номиналом a_0, получим исходный набор и при этом по способу построения L1′ он будет туда входить – противоречие.
Таким образом, мощность L1 = мощность L1` = C(S – a_0, a_0, a_1, .., a_n)
C(S, a_0, a_1, .., a_n) = мощность L = Мощность L2 + мощность L1 = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)
чтд
==============
Доказанная лемма показывает, что способ разветвления в алгоритме правилен
Докажем теперь следующее утверждение: алгоритм, используемый в задаче, корректен, то есть находит все возможные варианты и при этом не учитывает один и тот же вариант более одного раза.
Доказательство методом индукции по количеству номиналов монет n для набора произвольной суммы S.
==============
При n = 1 утверждение доказывается элементарно. Алгоритм отнимает от S номинал монеты, пока не дойдёт до нуля, либо до отрицательного числа. Первое означает, что S кратно номиналу, имеется один единственный вариант и возвращается 1. Во втором случае алгоритм вернёт 0, поскольку S не делится на номинал нацело. При подсчёте алгоритм не разветвляется, поскольку второй вызов сразу возвращает ноль для пустого списка.
Допустим, что утверждение верно для n номиналов. Докажем его для n + 1.
пусть k = S mod a_0
алгоритм подсчёта C(S, a_0, a_1, .., a_n) рекурсивно вызывает сам себя для подсчёта
C(S, a_1, .., a_n), C(S – a_0, a_0, a_1, .., a_n);
C(S – a_0, a_1, .., a_n), C(S – a_0 – a_0, a_0, a_1, .., a_n);
C(S – a_0 – a_0 – a_0, a_0, a_1, .., a_n), C(S – a_0 – a_0 – a_0, a_1, .., a_n);
…
C(S – (k-2)*a_0, a_1, .., a_n), C(S – (k-1)*a_0, a_0, a_1, .., a_n);
C(S – (k-1)*a_0, a_1, .., a_n), C(S – k*a_0, a_0, a_1, .., a_n);
C(S – k*a_0, a_1, .., a_n), C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n)
Поскольку [S – (k+1)*a_0] = 0, то алгоритм обрубается:
– либо на подсчёте C(S – k*a_0, a_0, a_1, .., a_n), при [S – k*a_0] = 0
– либо на подсчёте C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n), при [S – k*a_0] > 0
Корректность вычисления каждой суммы зависит от корректности вычисления последующих, что следует из леммы.
Корректность вычисления каждой C(S – j*a_0, a_1, .., a_n) вытекает из предположения индукции.
Следовательно, нам нужно доказать только корректность вычисления C(S – (k-1)*a_0, a_0, a_1, .., a_n), поскольку из этого следует по цепочке корректность вычисления всех остальных сумм вида C(S – j*a_0, a_0, a_1, .., a_n) вплоть до C(S, a_0, a_1, .., a_n).
Возможны два случая:
1) [S – k*a_0] = 0
Тогда [S – (k-1)*a_0] = a_0, C(S – (k-1)*a_0, a_0, a_1, .., a_n) = C(a_0, a_0, a_1, .., a_n).
Множество L1, обсуждаемое в лемме, состоит всего из одного набора, в который включается одна монета номиналом a_0. Следовательно
C(a_0, a_0, a_1, .., a_n) = 1 + C(a_0, a_1, .., a_n). Вспомним при этом, что именно 1 возвращает алгоритм, в случае равенства нулю передаваемой ему суммы (а ему и передастся [a_0 – a_0] = 0). Ну а подсчёт C(a_0, a_1, .., a_n) опять же корректен по предположению индукции.
2) [S – k*a_0] > 0.
При этом [S – (k+1)*a_0] [S – k*a_0] … C(S – j*a_0, a_0, a_1, .., a_n) … => подсчёт C(S, a_0, a_1, .., a_n) корректен
чтд
==============
Comment from gorilych
Date: July 19, 2008, 7:46 am
Ну всё.. заменил угловые скобки на “меньше”
Последний раз, надеюсь:
ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ АЛГОРИТМА
Лемма. Пусть C(S, a_0, a_1, .., a_n) – количество способов размена суммы S монетами номиналов a_0, a_1, .., a_n. Тогда
C(S, a_0, a_1, .., a_n) = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)
Доказательство
==============
Очевидно, что множество всевозможных различных наборов монет L, составлющих сумму S, можно разделить на два непересекающихся подмножества – подмножество L1 наборов, содержащих монету номиналом a_0, и подмножество L2, без монет с таким номиналом. Действительно, в наборе либо есть, либо нету такой монеты, поэтому нет такого набора, который входит одновременно в оба подмножества и поэтому они не пересекающиеся. Следовательно мощность множества L равна сумме мощностей подмножеств.
Мощность L2 равна C(S, a_1, .., a_n), поскольку любой набор из монет a_1, .., a_n с суммой S входит в L и при том входит в L2, поскольку не содержит монет с номиналом a_0.
Поскольку каждый набор в L1 содержит хотя бы одну монету номинала a_0 то из L1 можно получить равномощное множество L1′, убрав из каждого набора по одной монете ном. a_0. При этом сумма каждого набора уменьшится на величину номинала и будет равна (S – a_0).
Покажем от противного, что L1′ содержит все возможные наборы монет номиналами a_0, a_1, .., a_n с суммой (S – a_0). Пусть есть такой набор, не входящий в L1′, сумма которого равна (S – a_0). Добавим к этому набору монету номиналом a_0. Сумма набора станет равной S => расширенный набор входит в L. При этом он содержит добавленную монету номиналом a_0 => входит в L1. При убирании монеты номиналом a_0, получим исходный набор и при этом по способу построения L1′ он будет туда входить – противоречие.
Таким образом, мощность L1 = мощность L1` = C(S – a_0, a_0, a_1, .., a_n)
C(S, a_0, a_1, .., a_n) = мощность L = Мощность L2 + мощность L1 = C(S, a_1, .., a_n) + C(S – a_0, a_0, a_1, .., a_n)
чтд
==============
Доказанная лемма показывает, что способ разветвления в алгоритме правилен
Докажем теперь следующее утверждение: алгоритм, используемый в задаче, корректен, то есть находит все возможные варианты и при этом не учитывает один и тот же вариант более одного раза.
Доказательство методом индукции по количеству номиналов монет n для набора произвольной суммы S.
==============
При n = 1 утверждение доказывается элементарно. Алгоритм отнимает от S номинал монеты, пока не дойдёт до нуля, либо до отрицательного числа. Первое означает, что S кратно номиналу, имеется один единственный вариант и возвращается 1. Во втором случае алгоритм вернёт 0, поскольку S не делится на номинал нацело. При подсчёте алгоритм не разветвляется, поскольку второй вызов сразу возвращает ноль для пустого списка.
Допустим, что утверждение верно для n номиналов. Докажем его для n + 1.
пусть k = S mod a_0
алгоритм подсчёта C(S, a_0, a_1, .., a_n) рекурсивно вызывает сам себя для подсчёта
C(S, a_1, .., a_n), C(S – a_0, a_0, a_1, .., a_n);
C(S – a_0, a_1, .., a_n), C(S – a_0 – a_0, a_0, a_1, .., a_n);
C(S – a_0 – a_0 – a_0, a_0, a_1, .., a_n), C(S – a_0 – a_0 – a_0, a_1, .., a_n);
…
C(S – (k-2)*a_0, a_1, .., a_n), C(S – (k-1)*a_0, a_0, a_1, .., a_n);
C(S – (k-1)*a_0, a_1, .., a_n), C(S – k*a_0, a_0, a_1, .., a_n);
C(S – k*a_0, a_1, .., a_n), C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n)
Поскольку [S – (k+1)*a_0] меньше 0 а [S – k*a_0] >= 0, то алгоритм обрубается:
– либо на подсчёте C(S – k*a_0, a_0, a_1, .., a_n), при [S – k*a_0] = 0
– либо на подсчёте C(S – (k+1)*a_0 – a_0, a_0, a_1, .., a_n), при [S – k*a_0] > 0
Корректность вычисления каждой суммы зависит от корректности вычисления последующих, что следует из леммы.
Корректность вычисления каждой C(S – j*a_0, a_1, .., a_n) вытекает из предположения индукции.
Следовательно, нам нужно доказать только корректность вычисления C(S – (k-1)*a_0, a_0, a_1, .., a_n), поскольку из этого следует по цепочке корректность вычисления всех остальных сумм вида C(S – j*a_0, a_0, a_1, .., a_n) вплоть до C(S, a_0, a_1, .., a_n).
Возможны два случая:
1) [S – k*a_0] = 0
Тогда [S – (k-1)*a_0] = a_0, C(S – (k-1)*a_0, a_0, a_1, .., a_n) = C(a_0, a_0, a_1, .., a_n).
Множество L1, обсуждаемое в лемме, состоит всего из одного набора, в который включается одна монета номиналом a_0. Следовательно
C(a_0, a_0, a_1, .., a_n) = 1 + C(a_0, a_1, .., a_n). Вспомним при этом, что именно 1 возвращает алгоритм, в случае равенства нулю передаваемой ему суммы (а ему и передастся [a_0 – a_0] = 0). Ну а подсчёт C(a_0, a_1, .., a_n) опять же корректен по предположению индукции.
2) [S – k*a_0] > 0.
При этом [S – (k+1)*a_0] меньше 0 => [S – k*a_0] меньше a_0. Раз сумма для подсчёта [S – k*a_0] меньше номинала a_0, то монеты номинала a_0 не могут входить в возможные наборы. это значит, что
C(S – k*a_0, a_0, a_1, .., a_n) === C(S – k*a_0, a_1, .., a_n) + 0
Вспомним, что именно ноль вернёт алгоритм при отрицательной сумме
Значит, в обоих случаях подсчёт C(S – (k-1)*a_0, a_0, a_1, .., a_n) корректен => … C(S – j*a_0, a_0, a_1, .., a_n) … => подсчёт C(S, a_0, a_1, .., a_n) корректен
чтд
==============
Comment from gorilych
Date: July 19, 2008, 7:52 am
поскольку в доказательстве нигде не учитывался порядок номиналов, следовательно и корректность алгоритма от него не зависит.
Write a comment