因为过年（懒惰）的原因，有一段时间没有更新了。今天就来解道题吧， 题目是在公交车上刷手机的时候看到的，比较有意思。描述如下：
一个圆环上有100个灯泡和100个对应的开关，灯泡的状态随机， 按一个灯泡开关的时候，该灯泡相邻的灯泡状态也会发生变化。 比如暗-亮-暗，按下中间灯泡的开关，变为亮-暗-亮。 设计一种算法，使得所有灯泡最后都亮。
思路1
最开始看到这道题的时候，其实是有些发懵的，应该从哪里开始入手呢？ 先从简单的开始吧，如果只有3个灯泡，初始状态不合适的话，无论如何是不可能成功的。 4个的话呢，根据初始状态一个个按过去，貌似也有些复杂。 如何从4个推广到5个呢？貌似也有些困难。换条路吧。
思路2
100个灯泡，如果99个都是亮的，应该怎么处理呢？ 如果找到了办法，就把所有的情况都化为99个亮的就可以了。
假设0号灯是暗的，1-99号都是亮着的。 对于这种情况而言，只要1个灯的状态发生变化即可，而其他灯的状态应该保持不变。 也就是说，0号灯的状态需要变化奇数次，其他的需要变化偶数次。 而每次按下开关，都会有3盏灯的状态发生变化。
也就是说，需要满足以下条件：(99 * 2 * a + (2 * b + 1)) % 3 = 0
很容易发现，a = 1, b = 1为最小解。
换句话说，0号灯需要变化3次，其他的需要变化2次。共需要67次操作。
理论上可行，怎么验证呢？手写太复杂了，编程验证一下吧。或者以4盏灯为例试一下：
1 0 3
0 1 2
2 3 0
确实是可行的。
于是，我们知道了如何处理只有1盏灯为暗的情况。
可是怎么将各种情况都变成这种情况呢？ 注意到上述变化的本质，实际上是，如何只改变1盏灯的状态，而让其他灯的状态保持不变的解法。
那么很简单很直接的一个思路，有多少灯是暗的，就执行多少轮上述算法， 每次把1盏暗的灯变亮，最后肯定可以使所有灯都是亮的。
改进
上面，我们已经得到了解法一，可是，这样做的复杂度貌似有些高，如果有n盏暗的灯，需要
操作67*n次，如果有60盏灯是暗的，3000多次会很累。
怎样才能使按开关的次数更少呢？
– 减少暗的灯的数量：
还是从0号灯开始，沿着1号灯的方向：
如果0是暗的，则按下1号开关
如果1是暗的，按下2号开关（防止改变0的状态）
……
如果97是暗的，按下98号开关
这时候，0到97号灯都是亮的，98、99未知
如果98、99都是暗的，则按下99号开关，0号为暗，其他为亮
否则，保持即可
最坏情况为99 + 67 = 166 次操作。
情况好了一些，会不会有更好的解决方案呢？换个思路， 从开关的角度去想，对于同一个开关，按3次和按1次是一样的，按2次和按0次的结果是一样的。 而上面的结果，232次，100个开关，根据鸽巢原理，肯定有开关的次数超过了2次。
那么，新的优化方案来了： 我们建立一个数组，来维护每个开关被按下的次数， 对2取模，结果为1的开关，就是我们最终要按下的开关。
这种优化适用于上述两种方法。最终得到的操作次数，少于100。终于可以用手完成了！
扩展
- 如果有101盏灯呢？102盏灯？（
3n, 3n + 1, 3n + 2) - 如果左右各两盏灯的状态都会发生变化呢？（”暗-亮-暗-暗-亮” 变为 “亮-暗-亮-亮-暗”）