灯泡点亮方案

题目描述

有 \(n\) 盏灯泡。熄灭的灯泡用 \(0\) 表示，点亮的灯泡用 \(1\) 表示。这 \(n\) 盏灯泡的点亮/熄灭状态可以用 \(n\) 位的“01串”来表示。 例如 \(01011\) 表示 \(n=5\) 盏灯泡的一种状态，其中第 \(2,4,5\) 盏灯泡被点亮，第 \(1,3\) 盏灯泡熄灭。 可以得出，这些状态总共有 \(2^n\) 种状态。 现在需要求一种方案，从所有灯泡全部熄灭开始，每一步点亮/熄灭一盏灯泡，用恰好 \(2^n\) 步，经过每一种状态恰好一次，并且回到全部熄灭的状态。 例如，3 盏灯泡的一个方案为：\(000 \rightarrow 100 \rightarrow 110 \rightarrow 010 \rightarrow 011 \rightarrow 111 \rightarrow 101 \rightarrow 001 \rightarrow 000\)。 现在需要输出每一步需要操作哪盏灯泡，是打开还是熄灭。

输入格式

从标准输入读入数据。 输入仅一行一个正整数 \(n\)，表示灯泡的数量。保证 \(n \le 20\)。

输出格式

输出到标准输出。 输出 \(2^n\) 行，每行一个正整数和一个字符串，分别表示点亮/熄灭的灯泡编号和该灯泡应该点亮还是熄灭，其中点亮为 `on`，熄灭为 `off`。 这道题答案不唯一，只要你的答案是正确的就能通过评测。

样例 #1

样例输入 #1

``` 3 ```

样例输出 #1

``` 1 on 2 on 1 off 3 on 1 on 2 off 1 off 3 off ```

样例 #2

样例输入 #2

``` 5 ```

样例输出 #2

``` 1 on 2 on 1 off 3 on 1 on 2 off 1 off 4 on 1 on 2 on 1 off 3 off 1 on 2 off 1 off 5 on 1 on 2 on 1 off 3 on 1 on 2 off 1 off 4 off 1 on 2 on 1 off 3 off 1 on 2 off 1 off 5 off ``` 写出一个正确的C++代码内容：```cpp #include #include #include

using namespace std;

void dfs(int n, int step, vector& state, vector<pair<int, string>>& ans) { if (step == (1 << n)) { return; } for (int i = 0; i < n; i++) { if (state[i] == 0) { state[i] = 1; dfs(n, step + 1, state, ans); ans.push_back({i + 1, "on"}); state[i] = 0; dfs(n, step + 1, state, ans); ans.push_back({i + 1, "off"}); return; } } }

int main() { int n; cin >> n;

vector<int> state(n, 0);
vector<pair<int, string>> ans;
dfs(n, 0, state, ans);

for (auto p : ans) {
    cout << p.first << " " << p.second << endl;
}

return 0;

}