一行代码就能解决的算法题 :: labuladong的算法小抄

[labuladong]

文章链接点这里：一行代码就能解决的算法题

评论礼仪 见这里，违者直接拉黑。

[61go]

Nim游戏的本质似乎还能够更进一步解释。
对手可能的选择：1　2　3
我的选择也是 1　2　3
所以我们总能凑出一个 4 来。
1.假如现在是4 的整数倍个石子，那么只要对方先拿，不管他每次能拿多少，我都能故意给他凑成 4.　到最后 4 个时，我肯定赢。即，谁先拿谁输。
2。假如现在不是 4 的整数倍，那么我先拿的时候，只要保证拿完后的石子数量是 4 的整数倍即可。因为这样，就强迫情形来到 1.我必胜

推而广之，如果最少拿 1 个，最多拿 n个，其实就换成了凑n＋1 的整数倍问题。

[61go]

电灯开关问题

就假设现在总共有 16 盏灯，我们求 16 的平方根，等于 4，这就说明最后会有 4 盏灯亮着，它们分别是第 11=1 盏、第 22=4 盏、第 33=9 盏和第 44=16 盏。

能否解释下第 15 个灯的情况，为什么是偶数次呢

[neo-lift]

第15灯被按的点： 1， 3， 5， 15
所以偶数次被按

[61go]

忽略上述问题，明白了，15　＝　1×15 = 15x1

[gaofeiseu]

15 = 3 ✖️ 5 被你吃了吗(⊙o⊙)…

[gaofeiseu]

电灯开关的问题不是很懂。。。废废的了

[bert82503]

打卡，感谢楼主！

[LebronHarden1]

稍微思考一下,没思考出来啊?谁能解释一下小于等于根号n的所有正整数的平方就是最好亮着的灯的索引...

[LebronHarden1]

哦哦哦,明白了,小于等于根号n,所以平方之后小于等于n,这也就是在算1-n有多少个平方数,而每个平方数索引处的灯都会被操作奇数次,所以一定是最后亮着的灯,非平方数的索引位置处的灯由于以根号非平方数为界限总有成对的因子出现,这将导致该灯会被操作偶数次,也就是灯灭,谢谢东哥

[bjtuql]

就是算能完全开方的下标数量，不能完全开方的第i盏灯因子一定是偶数个，能完全开方的第i盏灯因子一定是奇数个

[paroniriaa]

@gaofeiseu16盏灯的情况下, 第15个灯被按了一共4次(1x15, 3x5), 也就是偶数次, 所以最后是灭的:
第一次: n = 1
第二次: n = 3
第三次: n = 5
第四次: n = 15

[zhuxiaoze]

灯泡开关的问题，个人理解：
比如对16开方得4，这个4是有4个数的平方小于等于16，即11=1, 22=4, 33=9, 44=16
1,4,9,16 代表的其实是位置
对任意位置i，都有i = 1 * i 即在第1轮和第i轮都会被按压，可见如果i是素数 那么它到最后一定是熄灭的
前文分析一盏灯开着的话 必须要经过奇数次按压，那么有哪些位置上的灯一定是奇数次呢
答案就是1,4,9,16
因为这些数在第1轮和第i轮会被按，其次在第sqrt(i)轮也会被按
说白了就是给你一个数，并对他分解因子，因子是奇数个就是开着的，偶数个就是关着的

[SE-LinJz]

灯泡开关的问题，为什么说能完全开方的第i盏灯因子一定灯亮，首先得知道得按奇数次灯才会亮，接着就是看每个数是奇数次还是偶数次，找出所有奇数次的就可以了，能被完全开方的数必有n=a*a，而a只计一次，所以一定是奇数次，而不能完全被开方的数就只能是偶数次

[HCWGH]

灯泡最后开着的条件就是被操作奇数次，对于第i个灯泡来说，能被操作机会只能是它的第约数次操作，比如说：第6个灯泡，能被操作的次数是 1, 2 , 3 ,6,发现都输成对出现的，6=23, 6=16，什么情况下能够出现奇数的情况呢？那就是i能够开完全平方 比如：4. 4=14, 4=22 ，那么4的约数就是1， 4 ，2。所以说只需要找n个灯泡，有多少个能够开完全平方的即可。因为他们被操作的次数只会是奇数次，而根据数学推论，小于等于n能够开完全平方的数字的个数为n的平方根。

[AllenPi]

石头问题其实就是树. 算树两边哪边节点加起来大就选哪边.

[AllenPi]

但是因为:"石头的堆的数量为偶数，所以你们两人拿走的堆数一定是相同的。石头的总数为奇数"
然后自己肯定数过了,又是先手,必须赢.

[AllenPi]

当然,如果分堆完,数都数不对,就注定无了.