javascript - 熄灯算法 - 找到打开所有开关的最小开关数量

Question

该组开关位于水平行中。最右边的开关可以随时打开或关闭。只有当右侧的开关打开且右侧的所有其他开关都关闭时，才能切换任何其他开关。所有开关最初都是关闭的。创建一个函数，该函数接受 n 个开关并返回打开所有开关所需的最小开关次数。需要输出切换开关的每一步。

Example: 
n = 3;
[0; 0; 0] --> [0; 0; 1] --> [0; 1; 1] --> [0; 1; 0] --> [1; 1; 0] --> [1; 1; 1];
count = 5. 

我的想法是测试我们想要启用的下一个开关。然后检查它右侧的每个开关并检查所需的状态。你能建议什么解决方案？

标签： javascriptalgorithmbit-manipulation

Answer 1

这实际上产生了一个格雷码序列。

虽然您当然可以以一种非常幼稚的方式实现这一点，但我们也可以使用以下观察：当我们从右到左对数组中的索引进行编号时，从最右边的条目的 0 开始，然后是数字应该切换的索引遵循以下顺序：

0 1 0 2 0 1 0 3 0 1 0 2 0...

当我们从 1 开始对输出进行编号时，上述索引对应于该编号中最右边 1 位的索引。该表应说明这一点：

输出编号	二进制	最右边 1 的索引	格雷码
1	00001	0	00001
2	00010	1	00011
3	00011	0	00010
4	00100	2	00110
5	00101	0	00111
6	00110	1	00101
7	00111	0	00100
8	01000	3	01100
9	01001	0	01101
10	01010	1	01111
...

如果输入不超过 31 个（灯泡），我们可以使用 32 位操作来导出最右边 1 位的索引。例如i & ~(i - 1)，返回设置的最低有效位i- 作为 2 的幂。要将 2 的幂转换为位索引，我们可以使用鲜为人知的Math.clz32函数。

我们可以跟踪有多少灯泡打开并在所有灯泡都打开时停止循环（实际上在每次迭代中从零开始计数灯泡）：

function steps(bulbCount) {
    let i, onCount;
    const bulbs = Array(bulbCount).fill(0);
    console.log(...bulbs);
    
    for (i = 1, onCount = 0; onCount < bulbCount; i++) {
        let index = bulbCount + Math.clz32(i & ~(i - 1)) - 32;
        bulbs[index] ^= 1; // Toggle
        onCount += bulbs[index] || -1; // Either increment or decrement
        console.log(...bulbs);
    }

    return i - 1; // Number of switch actions
}

console.log("Number of switch operations: ", steps(4));

对于更多数量的灯泡，您需要用更“手动”的相同原理实现来替换位运算符，但是当您必须等待生成超过 2 ³¹个输出时，几乎没有任何实际用途......

选择

我们还可以使用来自Wikipedia的以下观察：

第^th个格雷码是通过计算⊕⌊/2⌋</p>得到的

虽然使用 32 位运算符进行此计算很简单，但需要在每次迭代中从一个数字构建数组：

function steps(bulbCount) {
    let i, onCount,
        bits = 0,
        end = (1 << bulbCount) - 1;
    const bulbs = Array(bulbCount).fill(0);
    console.log(...bulbs);
    for (i = 1; bits < end; i++) {
        bits = i ^ (i >> 1);
        console.log(...Array.from(bits.toString(2).padStart(bulbCount, "0"), Number));
    }

    return i - 1; // Number of switch actions
}

console.log("Number of switch operations: ", steps(4));