non*_*ble 12 algorithm recursion scheme sicp coin-change
我是麻省理工学院开放式课程的SICP课程的初学者,使用视频讲座和在线提供的书籍.昨天我遇到了一个例子,它询问我们是否可以编写一个程序来计算改变任何给定金额的方法的数量.
这个问题有一个简单的解决方案作为递归过程:
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(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)))
如果你想检查更多,我从这里拿走它.
他们通过添加以下内容计算使用K种硬币改变数量(N)的数量(N):
没有第一类硬币的改变A的方式(X)的数量.
改变(A - D)的方式(Y)的数量,其中D是fisrt硬币的面额,使用所有K种类型的硬币.
问题是,我只是不明白这一点.接着,他们试图解释说:
"要明白为什么这是真的,请注意改变的方法可以分为两组:那些不使用任何第一种硬币的那些,以及那些使用任何第三种硬币的方法.因此,改变方法的总数对于某些金额等于不使用任何第一种硬币进行金额变更的方式的数量,加上假设我们使用第一种硬币进行变更的方式的数量.(最后一句话)与加法N = X + Y相同？)但后一个数字等于使用第一种硬币后剩余数量的变化方式的数量.(使用此硬币后,它们指的是方式是否使用第一种硬币进行更改？) "
我理解他们如何实现递归算法,但我无法看到它们是如何实现的.英语不是我的母语,所以我可能会遗漏一些东西.如果您能解释我,使用其他术语,解决方案背后的逻辑我会非常感激.谢谢.
Wil*_*ess 15
"使用N种的方式的数量(N)"这两个N显然是不一样的.让我们说K种硬币.
我们有很多硬币,但每枚硬币分别为1,5,10,25或50美分,总共5种硬币.我们需要买一美元,100美分.假设每种硬币都能无限量供应.我们有多少种方法可以达到100的总和？
我们要么使用50美分的硬币(一个或多个),要么不使用.如果没有,我们仍然需要只用4种硬币到达100.但是如果我们这样做,那么在使用一个50美分的硬币之后,总金额是100 - 50 = 50美分,我们仍然可以使用所有5种硬币来达到新的,更小的总和:
ways{ 100, 5 } = ways{ 100, 5 - 1 } ; never use any 50-cent coins
+ ; OR
ways{ 100 - 50, 5 } ; may use 50-cent coins, so use one
或者一般来说,
ways( sum, k ) = ways( sum, k - 1 )
+
ways( sum - first_denomination(k), k )
这里的所有都是它的.看到？泛化自然来自抽象(用符号替换具体值并在函数定义中使它们成为参数).
然后我们需要关心基本情况.如果sum = 0,结果为1:有一种方法可以达到0的总和(并且它是:不带硬币).
如果k = 0,这意味着我们不允许使用任何种类的硬币; 换句话说,我们没有办法得到一笔金额,任何金额,而不使用至少一些硬币(除非总和为0,但我们已经处理过上述情况).所以结果必须是0.
sum < 0当然,如果相同的话.使用任何正面值的硬币,不可能,即0种方式来总结它.
对(结构)递归的观点是小思考 - 不是试图一次性描绘整个操作序列,而是试图理解你当前的情况.它是解决问题的心理工具,它是以最简单最自然的方式解决问题,尽可能小的一步.
自己打电话(副本)是技术性的.最重要的是信念的飞跃,你可以自称:假设你已经写下了你的定义,只需使用它就是合适的.这就是它被记录下来的方式.你只需要描述你拥有的东西,它是如何制成的(它们中的一些类似于完整的东西),以及如何将这些部分的结果组合起来以获得你所拥有的完整解决方案.
编辑(来自评论):递归地解决问题的关键是要认识到它可以被分解为一个较小的子问题的集合,每个子问题都适用于我们正在寻求的相同的一般求解程序,并且整个解决方案是然后以一些简单的方式从那些子问题的解决方案中找到(通过相同的一般程序找到它们就好像我们已经可以使用它们一样).这样创建的子问题中的每一个都是"较小的",这保证了最终将达到基本情况.
换句话说,尝试在问题中找到结构,使其具有与整体相似的子结构(如分形;例如,列表的后缀也是列表;等等); 然后,递归是:假设我们已经有了解决方案; 将问题实例分开(根据我们构建问题的方式); 通过解决方案改变"较小的"子结构; 以一种简单的方式将它们组合在一起(根据我们构建问题的方式).诀窍是识别问题中现有的固有结构,以便解决方案自然而然.
或者,在Prolog中:
recursion( In, Out) :-
is_base_case( In),
base_relation( In, Out).
recursion( In, Out) :-
not_base_case( In),
constituents( In, SelfSimilarParts, LeftOvers), % forth >>>
maplist( recursion, SelfSimilarParts,
InterimResults),
constituents( Out, InterimResults, LeftOvers). % and back <<<
上面 Will Ness 回答中的第一个代码框让我有足够的洞察力来理解算法。一旦我理解了它，我意识到我可能会通过实际逐步了解算法的作用而很快到达那里。
下面是一个简单案例的算法如何进行的图表。金额是 6 便士，我们有两种硬币：五便士（指数 2）和一便士（指数 1）。
请注意，叶子节点的计算结果都为 0 或 1。当我们查看过程中的条件时，这一点很明显（返回这些值之一，否则函数再次调用自己。）只有两个叶子节点的计算结果为 1，因此有两种方法可以用这两种硬币制作 6 便士，即 6 便士，或 1 便士和 5 便士。
我现在理解了算法，但我仍然不明白如何从最初的问题中计算出算法。也许，随着我阅读更多 SICP 书籍，这种解决方案对我来说似乎更加明显。
(cc 6 2)
|
-----------------------------------
| |
(cc 6 1) (cc 1 2)
| |
------------------ --------------
| | | |
(cc 6 0)=0 (cc 5 1) (cc 1 1) (cc -4 2)=0
| |
------------- -------------
| | | |
(cc 5 0)=0 (cc 4 1) (cc 1 0)=0 (cc 0 1)=1
|
--------------
| |
(cc 4 0)=0 (cc 3 1)
|
--------------
| |
(cc 3 0)=0 (cc 2 1)
|
--------------
| |
(cc 2 0)=0 (cc 1 1)
|
--------------
| |
(cc 1 0)=0 (cc 0 1)=1
如果我们认为递归太过困难,我们就已经失败了.就个人而言,我在思考递归时使用了两个隐喻.一个来自小书"小阴谋家":The Seventh Commandment - Recur on the subparts that are of the same nature.另一个是用于设计算法的分治 - 组合范式.从本质上讲,它们在如何递归思考方面是相同的.
问题有两个变量:货币的数量(N)和硬币的种类(K),因此任何分工都需要满足以下要求: 1. reducing all variables: both N and K, 2. the subparts are the same nature so each subpart can be solved by the recursion process itself or be can solved directly. 3. all subparts together == the original one part, no more and no less.
解决方案中的划分将原始问题分为两个子部分:第一个子部分是使用第一个硬币的所有组合(我们可以重申所有组合使用相同含义的第一个硬币的至少一个硬币).剩下的部分是所有组合都不使用第一枚硬币.N在第一子部分减少,K在第二部分减少.两者都是相同的性质,可以递归地解决,它们在一起是最初的问题.
在这一步中,我考虑了基本情况.当问题减少到可以直接给出答案的最小值时,所有基本情况是什么？在这个解决方案中,有三种基本情况.第一个是N减少到0.第二个是N减少到负数.第三是硬币减少到0但N仍然是正数.
解析子部分时如何组合结果.在这个解决方案中,它们只是+.
更重要的是,如果我们在列表上递归,则除法通常是列表中的汽车和列表的cdr.如果自己不是列表,通常可以直接解决列表中的汽车.cdr部分应该递归解决.如果满足,基本情况是列表的结尾.
顺便说一句,我强烈建议the little schemer学习递归.就我所读到的而言,在这个特定点上它比其他任何人都要好得多.