Пример изменения счетчика в разделе «Структура и интерпретация компьютерных программ» на Tree Recursion - PullRequest
Новая
       66

Пример изменения счетчика в разделе «Структура и интерпретация компьютерных программ» на Tree Recursion

0 голосов
/ 15 апреля 2020

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

Требуется лишь немного сообразительности, чтобы придумать итерационный алгоритм Фибоначчи. Напротив, рассмотрим следующую проблему: Сколько разных способов мы можем внести изменения в 1 доллар, учитывая полдоллара, кварталы, десять центов, никели и пенни? В более общем смысле, можем ли мы написать процедуру для вычисления количества способов изменить любую сумму денег?

Эта проблема имеет простое решение как рекурсивная процедура. Предположим, мы думаем о доступных типах монет, расположенных в некотором порядке. Тогда имеет место следующее соотношение:

Количество способов изменить сумму a с использованием n видов монет равно ...

... количество способов изменить сумму a с использованием всех монет, кроме первого, плюс количество способов изменить сумму a - d с использованием всех n видов монет, где d - номинал монет первого типа.

Чтобы понять, почему это так, обратите внимание, что способы внесения изменений можно разделить на две группы: те, которые не используют монеты первого типа, и те, которые используют. Таким образом, общее количество способов внесения изменений на определенную сумму равно количеству способов внесения изменений на сумму без использования монет первого типа, плюс количество способов внесения изменений при условии, что мы используем Первый вид монет. Но последнее число равно количеству способов внесения изменений в сумму, оставшуюся после использования монеты первого рода.

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

1 Ответ

0 голосов
/ 15 апреля 2020

Допустим, у нас есть все способы изменить доллар, и мы выбираем любую деноминацию, скажем, кватер (25 c). Мы можем go через решения, разделяющие их между теми, кто использует кватер, и теми, которые этого не делают:

"Все решения для $ 1" = "решения для $ 1, которые используют решения" + "четверти" для $ 1, которые не используйте кватер "

Авторы утверждают, что" Все решения за 1 доллар США, использующие кватер ", имеют тот же размер, что и" все решения за 75 c ". Вы можете интуитивно увидеть, что это правда. Формально вы можете сказать:

a) "решения за 1 доллар, которые используют кватер" <= "все решения за 75 c", потому что для каждого "Решения за 1 доллар, который использует кватер" вы можете удалить кватер и получите решение на 75 c. </p>

b) «все решения на 75 c» <= «Решения на 1 доллар, использующие кватер», поскольку для каждого решения на 75 c можно добавить кватер и получите решение, которое находится в разделе «Решения за 1 доллар США, использующие кватер». </p>

Таким образом, они должны быть одинакового размера, то есть: 

Size of "solutions for $1 that use a quater" 
    = Size of "all solutions for 75c"

, поэтому: 

Size of "All solutions for $1" = 
    Size of "solutions for $1 that use a quater"
    + Size of "solutions for $1 that don't use a quater"

Можно переписать как: 

Size of "All solutions" = 
    Size of "all solutions for 75c"
    + Size of "solutions for $1 that don't use a quater"
...