Jac*_*ale 1 algorithm backtracking data-structures
这是消费税:
你从一个空房间开始,一群n个人在外面等着.在每一步,您可以允许一个人进入房间,或者让一个人进入房间.你能安排一个2 n步骤的序列,这样每个可能的人组合都可以完成一次吗？
我的解决方案是:
我可以有一个有n个元素的位数组.每个元素的状态代表这个人是否在房间里.总而言之,我们将在房间里有2 个不同的人组合.
该算法可以是标准回溯以列出所有组合.
我只是想知道我的想法是太天真还是简单？
这个消费税中的任何陷阱？
编辑:
对于对实施感兴趣的人gray code,请参阅
aio*_*obe 12
该算法可以是标准回溯以列出所有组合.
你的解决方案"有效",但如果天真实施,它将需要超过2 n步.
请参阅问题陈述中的以下句子:
在每一步,您可以允许一个人进入房间,或者让一个人进入房间.
在你的解决方案中,当你列出所有的位向量时,你可能会0111跟着1000这意味着三个人将不得不离开房间,一个人将不得不进入.
这需要4个步骤,而不是一个步骤,因此您将获得超过2 个步骤来运行所有组合.
但是,您可以排列您描述的位向量,使得两个连续向量之间只有一位不同.这就是格雷码.
以下是维基百科文章中的一个例子:
Dec Gray Binary
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110
7 100 111
注意如何
这意味着您将能够以精确的2 n步骤迭代所有组合.
如何实现这样的序列生成器也在维基百科页面中解释,但如果这是一个练习,我建议你在偷看前自己尝试;)