算法--灯全亮

1. 问题描述

给你100盏灯围成一个圆环，灯有两种状态，要么是亮的要么是灭的，灯的初始状态是随机的。每个灯有一个开关，灯的开关具有这样的作用，按一下某个灯的开关，则该灯以及它相邻的两个灯的状态都会发生一次变化，即亮的变成暗的，暗的变成亮的。例如亮–亮--亮，按下中间的开关，则三盏灯全灭，亮–暗--暗，按下中间的开关，变成暗–亮--亮…
问你有没有办法使得100盏灯全亮，如果有，请说明你的算法思路。

2. 解决方法

全灭的灯怎么处理？
我们先来考虑一个特殊情况：所有的灯都是灭的。然后我们这么做：

1. 将灯编号为0，1，2，3，…，98，99；
2. 对每个灯都按一次开关。

分析一下：因为每个灯都是灭的，所以一个朴素的想法就是按一次开关将其变亮。按一下0号开关，0号亮起，99号和1号也亮了；然后假如灯的总数是3的倍数，那么我们完全可以3个一组，将所有的灯都弄亮，但是现在不是3的倍数，不能这么做；继续往下按1号的开关，此时1号灯灭，0号灯灭，2号灯亮；然后因为1号灭了，那么我们按一下1号后面的2号，使1号重新亮起来，但是导致了2号灭了，3号亮了；然后按3号，此时2号亮，3号灭，4号亮；然后按4号，此时3号亮，4号灭，5号亮；可以看到已经形成了一个规律，…；按98号，此时97亮，98灭，99灭（注意此时99号是灭的，之所以和前面的规律不一样，是因为99号此前是亮的而不是灭的，这是因为第一次我们按0号的开关导致的），此时我们凑齐了3相邻的相同状态的灯泡；按99号，98亮，99亮，0号亮，终于全部都亮了。
同理，当灯的数量是3n+2时，也可以这么做，同样能够使得所有的灯都亮。如下图所示，黑色表示灯灭，黄色表示灯亮。

根据上面所述方法，无论有多少灯，都可以在倒数第二次得到3个相邻的灯灭，因此最后一次就可以按亮所有的灯。

如何得到全灭的灯？
假如此时仅有一盏灯是灭的，剩余99盏都是亮的，怎么做可以使得灯全灭？
我们找到灭的那盏灯，然后将其后面的99盏3个一组分成33组，每一组都只按中间灯泡的开关一次，这时所有的灯就都熄灭了。
这时这个方法显然对于101盏 灯是不适用的，也就是说只适用于3n+1的情况。

如何得到仅有一盏灯灭的状态？
对于这100盏灯，顺序从前往后开始检查，当：

1. 该灯亮的时候不用管；
2. 该灯灭的时候，按一下它后面的那盏灯的开关，使得这个灯亮起来。

可以肯定的是，0至97号灯都可以点亮。但是98号灯如果要点亮就很有可能要按99号的开关，但是这会影响0号灯的状态。因此最后就剩98号灯和99号灯，此时有四种状态：

1. 98亮，99亮。遇到这种情况真是幸运，因为所有的灯都已经点亮；
2. 98亮，99灭。这时满足了仅有一盏灯灭的状态；
3. 98灭，99亮。这时也同理满足了仅有一盏灯灭的状态；
4. 98灭，99灭。这时只需要按一下99号的开关，然后98号和99号都亮起来，0号灯灭了，照样满足仅有一盏灯灭的状态。

综上所述，我们可以由随机状态得到仅有一盏灯灭的状态，进而得到全部灯灭的状态，最后得到全部灯亮的状态。

3. java实现

用false表示灭，true表示亮。

package com.ftq.demo.highlevel;

import java.util.Random;

public class LightBulb {

    public static void main(String[] args) {
        int k = 100000;
        int num = 3*k + 1;
        boolean[] bulbs = new boolean[num];
        for (int i = 0; i < num; i++) {
            Random random = new Random();
            bulbs[i] = random.nextBoolean();
            if (bulbs[i]) System.out.print("亮");
            else System.out.print("灭");
        }
        System.out.println();
        System.out.println(LightBulb.lightBulb(bulbs));
    }

    //给你100盏灯围成一个圆环，灯有两种状态，要么是亮的要么是灭的，灯的初始状态是随机的。
    // 每个灯有一个开关，灯的开关具有这样的作用，按一下某个灯的开关，
    // **则该灯以及它相邻的两个灯的状态都会发生一次变化**，即亮的变成暗的，暗的变成亮的。
    //问是否能将所有的灯都点亮？如果是，请点亮。
    //使用false表示灯灭，true表示灯亮.
    public static boolean lightBulb(boolean[] bulbs){
        int num = bulbs.length;
        if ((num % 3) != 1) return false;
//        首先得到仅有一盏灯灭的状态
        int flag = 0;//保存仅有的那盏灭的灯的号码。
        //首先将前num-2盏灯都点亮
        for (int i = 0; i < num-2; i++) {
            if (!bulbs[i]){
//                按下i后面灯(i+1)的开关
                bulbs[i] = !bulbs[i];
                bulbs[i+1] = !bulbs[i+1];
                bulbs[i+2] = !bulbs[i+2];
            }
        }
//        此时还有num-2号灯和num-1号灯状态未知
        if (bulbs[num-2] && bulbs[num-1]) return true;
        if (!bulbs[num-2] && !bulbs[num-1]){
            bulbs[num-2] = true;
            bulbs[num-1] = true;
            bulbs[0] = false;
        }
        if (bulbs[num-2] && !bulbs[num-1]){
            flag = num-1;
        }
        if (!bulbs[num-2] && bulbs[num-1]){
            flag = num-2;
        }

//        得到全灭的状态
        for (int i = 0; i < num-1; i = i + 3) {
            int j = (flag + i + 2) % num;
            bulbs[((j+num)-1) % num] = !bulbs[((j+num)-1) % num];
            bulbs[j] = !bulbs[j];
            bulbs[(j+1) % num] = !bulbs[(j+1) % num];
        }

//        遍历每一盏灯，按他的开关一次
        for (int j = 0; j < num; j++) {
            bulbs[((j+num)-1) % num] = !bulbs[((j+num)-1) % num];
            bulbs[j] = !bulbs[j];
            bulbs[(j+1) % num] = !bulbs[(j+1) % num];
        }

        for (boolean state: bulbs
             ) {
            if (state) System.out.print("亮");
            else{
                System.out.print("灭");
                return false;
            }
        }
        System.out.println();
        return true;
    }
}

4. 后续

因为灯的状态只有两种，并且这两种状态没有任何区别，所以我们也可以