3.数学问题
2020-07-24 本文已影响0人
做一只有趣的芦苇
1025. 除数博弈
证明
N = 1N=1 和 N = 2N=2 时结论成立。
N > 2时,假设 N≤k 时该结论成立,则 N = k + 1 时:
如果 k 为偶数,则 k + 1 为奇数,x 是 k + 1 的因数,只可能是奇数,而奇数减去奇数等于偶数,且 k + 1 - x ≤k,故轮到 Bob 的时候都是偶数。而根据我们的猜想假设 N≤k 的时候偶数的时候先手必胜,故此时无论 Alice 拿走什么,Bob 都会处于必胜态,所以 Alice 处于必败态。
如果 k 为奇数,则 k + 1 为偶数,x 可以是奇数也可以是偶数,若 Alice 减去一个奇数,那么 k + 1 - x 是一个小于等于 k 的奇数,此时 Bob 占有它,处于必败态,则 Alice 处于必胜态。
综上所述,这个猜想是正确的。
个人其实在代码实现环节被搞晕的是这一块
如果 k 为奇数,则 k + 1 为偶数,x 可以是奇数也可以是偶数,若 Alice 减去一个奇数,那么 k + 1 - x 是一个小于等于 k 的奇数,此时 Bob 占有它,处于必败态,则 Alice 处于必胜态。
就是当alice拿到偶数的时候,总能找到一个奇数的因子并减去它,这样bob永远只能拿到奇数
剑指 Offer 62. 圆圈中最后剩下的数字
约瑟夫环问题 看这里
这是一个推出结论之后再套用公式的过程,是逆推
当只剩下最后一个人时,下标为0,所以初始化res=0,然后我们一直要求到N个人,所以range到n+1
def lastRemaining(self, n: int, m: int) -> int:
res=0 #当
for i in range(2,n+1):
res=(res+m)%i
return res