開關組位于水平行中。最右邊的開關可以隨時打開或關閉。任何其他開關只有在其右側的開關打開并且右側的所有其他開關都關閉時才能切換。所有開關最初都是關閉的。創建一個函式，該函式接受 n 個開關并回傳打開所有開關所需的最小開關次數。需要輸出切換開關的每一步。
Example:
n = 3;
[0; 0; 0] --> [0; 0; 1] --> [0; 1; 1] --> [0; 1; 0] --> [1; 1; 0] --> [1; 1; 1];
count = 5.
我的想法是測驗我們要啟用的下一個開關。然后檢查其右側的每個開關并檢查所需的狀態。你能建議什么解決方案？
uj5u.com熱心網友回復：
這實際上產生了一個格雷碼序列。
雖然您當然可以以一種非常幼稚的方式實作這一點，但我們也可以使用以下觀察：當我們從右到左對陣列中的索引進行編號時，最右邊的條目從 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 31 個輸出時，幾乎沒有任何實際用途......
選擇
We could also use the following observation from Wikipedia:
the ??th Gray code is obtained by computing ?? ⊕ ???/2?
While this calculation is simple with 32-bit operators, one needs to build the array from a number in each iteration:
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));轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/325466.html
標籤：javascript 算法 位操作
上一篇：加法后獲取最大可能值
下一篇：這個演算法的復雜度是多少？