我正在阅读以下文章,无法理解第 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 ?