python - 按除数查找开关

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} 灯泡

---

我开始提出这个问题，但我不知道如何解决这个问题。 我这样做的方式是调用一个函数 divisors 为每个数字找到除数，然后返回一个数字 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

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

如果开关 X 是您可以切换的最高开关，那么它是唯一可以改变灯泡 X 的开关，因此请查看灯泡 X 以确定该开关是否必须打开或关闭。

然后确定开关 X - 如果它必须打开，则切换其除数的灯泡并继续到下一个最小的开关，因为现在那个是您可以更改的最高开关。

继续，直到你没有开关。要么所有灯泡都亮着，要么没有应答。