戴帽子的猫挑战。python

Question

我得到了这个问题的解决方案，但是：我很难看到解决方案背后的逻辑！有人能解释一下它是如何工作的吗

你有100只猫。 有一天你决定把你所有的猫排成一个大圆圈。最初，你的猫都没有戴帽子。你绕着圆圈走100圈，总是从同一个点开始，第一只猫（猫1）。每次你在一只猫面前停下来，如果它没有戴帽子，你就给它戴上帽子；如果它戴帽子，你就把它的帽子摘下来

1. 第一轮，你在每只猫面前停下来，给每只猫戴上帽子
2. 在第二轮比赛中，你只会在每一只猫（2、4、6、8等）停下来
3. 第三轮，你只在每三只猫（3、6、9、12等）停一次
4. 你继续这个过程，直到你绕着猫转了100圈（例如，你只拜访了第100只猫）

编写一个程序，只输出哪只猫的帽子在最后

以下是解决方案 解决方案#1：

def get_cats_with_hats(array_of_cats):
    cats_with_hats_on = []

    for num in range(1, 100 + 1):
        for cat in range(1, 100 + 1):
            if cat % num == 0:
                if array_of_cats[cat] is True:
                    array_of_cats[cat] = False
                else:
                    array_of_cats[cat] = True
    for cat in range(1, 100 + 1):
        if cats[cat] is True:
            cats_with_hats_on.append(cat)
    return cats_with_hats_on


cats = [False] * (100 + 1)
print(get_cats_with_hats(cats))

---

解决方案#2：

number_of_cats = 100
cats_with_hats = []
number_of_laps = 100

# We want the laps to be from 1 to 100 instead of 0 to 99
for lap in range(1, number_of_laps + 1):
    for cat in range(1, number_of_cats + 1):

        # Only look at cats that are divisible by the lap
        if cat % lap == 0:
            if cat in cats_with_hats:
                cats_with_hats.remove(cat)
            else:
                cats_with_hats.append(cat)

print(cats_with_hats)

Answer 1

我认为你在努力编码。这些解决方案可能会很耗时，我的意思是对于编程竞赛来说效率不高
第一只猫=真正的cuz圆从这只猫开始，永远不会是同一个点
第二个cat=假，因为圆将在该点第二次开始 在此之后，您可以知道您是否知道这只猫的分频器
例如：第八类
8的除数=1,2,4,8
第8类将为假
如果除法器计数%2==0，则为false 否则就是真的

你能分享问题的联系吗

Answer 2

这是一个著名的数学难题。catc状态翻转的次数等于该数c具有多少不同的因子。猫c要在最后戴帽子，它必须被翻转奇数次，这意味着c必须有奇数个不同的因素

因子成对出现，例如12=2×6，因此因子2与因子6成对出现。c可以拥有奇数个因子的唯一方法是，如果某个因子f与其自身配对，即c=f×f。也就是说，猫c当且仅当c是一个平方数时才戴上帽子。所以，我们只需要输出一个范围内的平方数列表

def get_cats_with_hats():
    return [i*i for i in range(1, 11)]