1

我正在阅读以下文章,无法理解第 4 段背后的逻辑

给你 N 个灯和四个开关。第一个开关切换所有灯,第二个切换偶数灯,第三个切换奇数灯,最后一个开关切换灯 1、4、7、10,...。

给定灯的数量 N、按下按钮的次数(最多 10,000 次)以及一些灯的状态(例如灯 7 关闭),输出灯可能处于的所有可能状态。

天真地,对于每个按钮按下,您必须尝试 4 种可能性,总共 4^10000 (大约 10^6020 ),这意味着您无法进行完整搜索(这种特定算法将利用递归)。

注意到按钮按下的顺序无关紧要,这个数字下降到大约 10000^4 (大约 10^16 ),仍然太大而无法完全搜索(但肯定更接近 10^6000 倍)。

但是,按两次按钮与没有按一次按钮相同,因此您真正需要检查的是按每个按钮 0 次或 1 次。这只是 2^4 = 16 种可能性,肯定是在时间限制内可以解决的迭代次数。

当订单无关紧要时,总配置的数量是多少 10000^4 ?

4

1 回答 1

2

作者规定按钮按下次数限制为 10,000 次:

按下按钮的次数(最多 10,000 次)

and if you know the order of button presses doesn't matter, but nothing else, then all that matters is how many times each button has been pressed. There are 10,000 possibilities for each of 4 buttons, so about 10000^4 overall. (Of course the real number is a bit smaller because you can't, e.g., have pressed all four buttons 10,000 times each.)

于 2012-04-28T07:54:05.077 回答