关闭postgresql 关闭所有灯

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 = 10086;
        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)的开关
                pressOn(bulbs, i+1);
            }
        }
//        此时还有num-2号灯和num-1号灯状态未知
        if (bulbs[num-2] && bulbs[num-1]) return true;
        if (!bulbs[num-2] && !bulbs[num-1]){
            pressOn(bulbs, num-1);
        }
        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;
            pressOn(bulbs, j);
        }

//        遍历每一盏灯，按他的开关一次
        for (int j = 0; j < num; j++) {
            pressOn(bulbs, j);
        }

        for (boolean state: bulbs
             ) {
            if (state) System.out.print("亮");
            else{
                System.out.print("灭");
                return false;
            }
        }
        System.out.println();
        return true;
    }
//    按下i的开关
    public static void pressOn(boolean[] bulbs, int i){
        int num = bulbs.length;
        int pre = (i+num -1) % num;
        bulbs[pre] = !bulbs[pre];

        bulbs[i % num] = !bulbs[i % num];

        int next = (i + 1) % num;
        bulbs[next] = !bulbs[next];
    }
}

4. 后续

因为灯的状态只有两种，并且这两种状态没有什么分别，因此你可能会想，既然第二步能够得到全灭的状态，那么自然也能得到全亮的状态，何不在第一步得到仅有一盏灯亮的状态呢，这样就可以直接在第二步得到全亮的状态了。直接省去了第三步将全灭变全亮。
但是实际上你可能遗忘了一件事，那就是第一步是可能得到全灭状态的，就是说你想要只得到一盏灯亮，但是有可能你运气不好灯是全灭的，这时你仍然需要再进行一次转换，代码是不可能少些的。但是由原来的三步变成了两步：

1. 想办法得到仅有一盏灯亮的状态。
2. 如果得到（3/4的可能性），则3个一组全都可以点亮；
   如果全灭（1/4的可能性），则遍历一遍，仍然可以全部点亮。

原来的方法有1/4的可能性一步得到全亮状态，3/4的可能性三步得到全亮状态。第一步的操作次数为n/2（因为初状态随机，所以默认为有一半的灯灭），第二步为n/3（3个一组进行操作），第三步为n（遍历一次）。期望为：n/2 * 1/4 + n/2 * 3/4 + n/3 * 3/4 + n * 3/4 = 3n/2.
两步法的期望：n/2 + n/3 * 3/4 + n * 1/4 = n。
少了一半的操作次数，但基本上都还是O(n)的复杂度。