SICP считает проблему изменения - почему N = X + Y?

Question

Я скрытный дилетант, пытающийся научить себя CS , и в настоящее время я прохожу путь через первую главу SICP .

Я сталкивался с примером процедуры «подсчета изменений» и, подобно некоторым другим , хотя я понимаю саму процедуру, я борюсь с предпосылкой на котором она основана:

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

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

• количество способов изменить сумму a с использованием всех монет, кроме первого, плюс

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

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

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

Что я не понимаю, так это почему они всегда равны:

1. Общее количество «путей», меньше «способов» получения полной суммы без использования монеты первого типа .
2. Количество «способов» использования всех типов монет для получения оставшейся суммы, после вычитания номинала первой монеты .

Я пробежал бесчисленные тестовые примеры вручную, и да, отношения верны, но я не понимаю, почему.

Первое предложение их объяснения имеет смысл:

Обратите внимание, что способы внесения изменений могут быть разделены разделить на две группы: те, которые не используют монеты первого типа, и те, которые используют.

Если у нас есть общее количество «путей», мы можем разделить эту сумму на две группы в соответствии с этим правилом. Нет проблем.

Второе предложение также ясно:

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

Это просто означает, что общее количество способов является сумма способов, которые были разделены на две категории. ОК.

Вот где меня теряют:

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

Я предполагаю, что это означает, что "последнее число" относится ко всем способам внесения изменений, которые должны использовать хотя бы одну монету первого номинала.

Почему и как это число соответствует количеству способов внесения изменений со всеми монетами на общую сумму, меньшую номинала первой монеты?

Чтобы попытаться визуализировать проблему, Я повторил это как попытку достичь определенного веса 80 кг на штангу с набором из 3 весовых номиналов:

1. Красный: 5 кг
2. Зеленый: 10 кг
3. Синий: 20 кг

Я выложил каждый сценарий визуально, и отношения действительно сохранились, но я до сих пор не понимаю, почему:

Рекурсия для бодибилдеров

Такое ощущение, что Ответ на этот вопрос прямо у меня под носом, но, возможно, размер этого конкретного придатка навсегда затеняет ответ.

Answer 1

Давайте представим упрощенную валюту, с номиналом в 1 и 5 фунтов стерлингов. Я прошу вас произвести ¤15, с условием, что по крайней мере одна из монет, которую вы мне даете, должна быть ¤5. Сколько способов вы могли бы сделать это? К этому моменту вы могли бы попытаться сгенерировать все способы произвести изменения для ¤15, а затем выбросить все те, которые не соответствуют моему требованию. Но просто заметить, что вы также можете начать с выделения одного setting5 для удовлетворения моих потребностей, а затем выяснить, как внести изменения в оставшиеся ¤10 любым способом, который вы выберете.

Answer 2

Хитрость в том, что, учитывая кучу номиналов монет, одну из которых мы назовем d, есть два способа внесения изменений на определенную сумму A:

• не использовать любые монеты достоинством d вообще;
• используйте хотя бы один d (где я имею в виду «монета достоинством d» под «d»).

И общее количество способов внесение изменений - это сумма этих двух способов (в частности, мы не пропустили других способов).

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

Во втором случае мы будем использовать хотя бы один d. Итак, мы знаем, что, поскольку мы используем хотя бы один d, количество A можно разделить на A = d + (A - d): вот что означает «использовать хотя бы один d». Так сколько же сейчас способов составить подобную комбинацию монет? Ну, ответ таков: это количество способов внести изменения для суммы (A - d), за исключением того, что на этот раз нам все еще разрешено использовать ds для внесения изменений.

Answer 3

Подумав об этом в течение нескольких дней с помощью других респондентов, я думаю, что эту проблему можно прояснить (по крайней мере, для меня), добавив уточнение к первоначальному объяснению книги после строки, которая гласит:

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

Я бы сформулировал новый абзац следующим образом:

Это потому, что мы можем предположить, что для каждой комбинации должно содержать хотя бы одну монету первого типа, которую мы уже использовали («врученная») экземпляр этой суммы. Нам просто нужно рассчитать способы внесения изменений для оставшейся суммы n .

Следовательно, нет разницы в количестве способов внесения изменений для:

1. полная сумма с использованием хотя бы одного достоинства, а
2. сумма n за вычетом стоимости первого достоинства с использованием любого количества монет.

Впоследствии мне удалось успешно написать свою версию проблемы «комнаты веса», и ее вывод соответствует моему визуальному решению:

(define (loadways weight plates)
(cond
   [(= weight 0) 1]
   [(or (= (length plates) 0) 
        (< weight 0)
        ) 0]
   [else (+ (loadways weight (cdr plates))
            (loadways (- weight (car plates)) plates))]
   ))  

(define weight-rack (list 20 10 5))

(loadways 40 weight-rack)