用除数查找开关

Question

有N个开关（从1到N）和N个灯泡（从1到N）。在

此开关只能按下一次，并且可以打开/关闭灯泡。 一个开关可以打开/关闭1个以上的灯泡。在

例如： 12号开关可以打开/关闭灯泡{1, 2, 3, 4, 6, 12} （因为{1, 2, 3, 4, 6, 12}是12的除数）

所以我们有一个函数main（N，setON）

• N是灯光的数量
• SetOn是一组从一开始就亮着的灯泡

此函数必须返回用于打开所有灯泡的开关列表

例如给定N=6和setON = {2,4}，返回列表[2,5,6]

• 按下按钮2将点亮{1,4}灯泡
• 按下按钮5将点亮{4,5}灯泡
• 按下按钮后，6将点亮{1,2,3,4,5,6}灯泡

---

我开始问这个问题，但我不知道该怎么解决。 我是这样做的，我调用一个函数除数，它为每个数找到除数，然后返回一个N的除数列表，然后我对每个列表运行一个循环，看看它在哪里打开或关闭，并将开关的编号放到一个新的列表中。 但事实上我没有得到我想要的结果，我也没有办法。在

我想在这里你的建议，我不是要求你解决我的问题，只是给我一个提示：）或如果你想纠正我。在

import math
def main(N, setON):
    newList= []
    acces = set(range(1,N+1))
    turnOFF = set()
    for number in range(N,1,-1):
        divs = divisors(number)                    
        for i in divs:
            if i in setON:
                turnOFF.add(i)
                setON.remove(i)
            else:
                setON.add(i)
                if i in turnOFF:
                    turnOFF.remove(i)
        newList.append(divs[-1])
        if len(setON) == N-1:
            print(newList)


def divisors(n):
    divs = [x for x in range(1, int(math.sqrt(n))+1) if n % x == 0]
    opps = [int(n/x) for x in divs]
    return list(set(divs + opps))


N=6
setON={2,4}
main(N, setON)

它给了我[6，5，4]

Answer 1

你的代码基本上是正确的，但是当灯泡已经打开时，你正在切换灯泡，这是一个错误的答案。另外，你没有检查灯泡1，所有的检查都是错误的。这里是你的固定版本：

for number in range(N,0,-1):
    if number in setON:
        continue
    #your previous code
    if len(setON) == N:
        print(newList)

这里有一个更快（避免使用集合）和更简洁的实现：

^{pr2}$

Answer 2

从编号最高的开关开始，一路向下。在

如果开关X是你能切换的最高开关，那么它是唯一可以改变灯泡X的开关，所以看看灯泡X，看看这个开关是开还是关。在

然后确定开关X是否必须打开，然后切换除数的灯泡，然后转到下一个最小的开关，因为这个开关现在是可以改变的最高开关。在

继续，直到开关用完为止。不是所有的灯泡都亮着，就是没有答案。在