丹尼尔
我很疯狂,试图找出一种方法来制作一个不会尝试每个单独组合的程序。一个简单的例子:我想知道是否可以通过将序列(2,5,10,20)中的数字相加来生成11,是否有一种简单的方法可以尝试所有可能性?在这种情况下,我们可以用3个2s和1个5s来做。
泽维尔·诺巴尔(Xavier Norbal)
我想我想出了一种解决方案
- 您必须按从高到低的顺序排列列表。它给了我们[20,10,5,2]
- 然后,我们将使用某种堆栈。
我们从n = 0开始
一种。您将列表的第n个元素放在堆栈的顶部。
b。如果堆栈中的数字总和大于目标数字,则删除堆栈中的最后一个元素并返回到点a。其中n = n + 1。如果从堆栈中删除的元素是您的小数,则还删除下面的元素,并返回到点a。n =(您的集合中最后删除的数字的索引)+1
C。如果不是,请尝试再添加一次,然后返回到b点。
d。此算法是递归算法,当您从堆栈中删除最后一个数字,并且此数字是您的较低数字(那么您将无法从集合中生成数字)时,或者当堆栈中的数字总和等于时,它将停止您的目标编号(然后您就可以从您的目标编号中生成它)
运行示例:目标11,设置为[20,10,5,2]
- 堆栈状态:空,n = 0
- 将20放入堆栈:堆栈状态:[20]> 11,从堆栈中删除20 => n = 1
- 将10放入堆栈:堆栈状态:[10] <11,n = 1
- 将10放入堆栈:堆栈状态:[10,10]> 11,从堆栈中删除10 => n = 2
- 将5放入堆栈:堆栈状态:[10,5]> 11,从堆栈中删除5 => n = 3
- 将2放入堆栈:堆栈状态:[10,2]> 11,从堆栈中删除2和10 => n = 2
- 将5放入堆栈:堆栈状态:[5] <11,n = 2
- 将5放入堆栈:堆栈状态:[5,5] <11,n = 2
- 将5放入堆栈:堆栈状态:[5,5,5]> 11,从堆栈中删除5 => n = 3
- 将2放入堆栈:堆栈状态:[5,5,2]> 11,从堆栈中删除2和5 => n = 3
- 将2放入堆栈:堆栈状态:[5,2] <11,n = 3
- 将2放入堆栈:堆栈状态:[5,2,2] <11,n = 3
- 将2放入堆栈:堆栈状态:[5,2,2,2] = 11,您赢得了
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
编辑于
我来说两句