本文主要是介绍n段码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
n段码 【问题描述】 小K要用n段数码管来表示一种特殊的符号（n取1,2,3,4,5,6,7），n段数码管就对应着有n个发光二极管。
上图给出了n段码数码管的一个图示，数码管中一共有n 段可以发光的二极管
以7段码为例，上图二极管分别标记为0,1,2,3,4,5,6。小K要选择一部分二极管（至少要有一个）发光来表达符号。在设计字符的表达时，要求所有发光的二极管是连成一片的，发光记为1，不发光记为0. 例如：1 发光，其他二极管不发光可以用来表达一种符号（0 1 0 0 0 0 0）。 例如：2 发光，其他二极管不发光可以用来表达一种符号（0 0 1 0 0 0 0）。 例如：0, 1, 2, 3, 4发光，5, 6 不发光可以用来表达一种符号（1 1 1 1 1 0 0）。
例如：1,5发光，其他二极管不发光则不能用来表达一种符号，因为发光的二极管没有连成一片。 请问，小K可以用n段码数码管表达哪些不同的符号？
(1<=n<=7)
输入格式:
第一行输入一个正整数n表示n段码数码管。
输出格式：
输出n段码数码管所能表达出哪些不同的符号。
输出为从小到大输出，每行的输出不能有多余空格.
观察题目，类似2020年的蓝桥的七段码，相较之下，这题更难一些。
思路：
对于每一个输入n，我们应该要构建相应的每一段灯管之间的关系图，而这题的数据并不大，所以用简单易懂的邻接矩阵
int m[7][7] = {{1,1,0,0,0,1,0},{1,1,1,0,0,0,1},{0,1,1,1,0,0,1},{0,0,1,1,1,0,0},{0,0,0,1,1,1,1},{1,0,0,0,1,1,1},{0,1,1,0,1,1,1}
};
上表我相信大家是可以看得懂的，1表示i-j之间有边连接，0表示i-j之间没有连接，至于自身到自身，1也可以，0也可以，因为代码的逻辑不会让我们同时遍历一个点两次。
建完了图，有了一个n那么继续看题目的要求，从小到大输出，也就是我们可以从1开始（0不亮没必要判断）一直到（1 << n ）-1,就可以把全部的情况遍历过去，并且是按顺序的输出。这个数字的二进制表示就代表，该位上亮灯或者不亮灯。
比如数字6
| 二进制 | 1 | 1 | 0 |
|---|---|---|---|
| 下标 | 2 | 1 | 0 |
当然，这样的顺序有点奇怪，我们可以在代码中作以修改。
接下来，开始重点，如何判断这次枚举的状态可行还是不可行。首先我们不断对这次枚举的i右移，不断提取出当前这个位置上的数字，而后用n减去cnt（提取的次数- 1），就得到了实际上的下标。（这里的减一或者不减，只需要自己拿一个例子算一下就可以得除了）
然后我们把所有亮灯的灯管，insert进一个set，然后以每一个点为起点做bfs，如果有一个点可以遍历完所有亮灯的灯管的话，也就是说明，亮着的灯是连成一块的。那么就可行，如果没有一个点作为起点可以遍历完全部亮灯的灯管的话，就说明不行。
然后调整一下输出格式就可以拉。
代码如下：
#include<iostream>
#include<stack>
#include<set>
#include<queue>
#include<cstring>
using namespace std;
int n;
int m[7][7] = {{1,1,0,0,0,1,0},{1,1,1,0,0,0,1},{0,1,1,1,0,0,1},{0,0,1,1,1,0,0},{0,0,0,1,1,1,1},{1,0,0,0,1,1,1},{0,1,1,0,1,1,1}
};
int ans = 0;
set<int>s;
int vis[7];
bool bfs(int t)
{queue<int>q;memset(vis, 0, sizeof vis);q.push(t);vis[t] = 1;while (q.size()){int x = q.front();q.pop();for (int i = 0; i < n; ++i){if (i == x)continue;if (s.find(i)!=s.end()&&m[x][i] && !vis[i]){q.push(i); vis[i] = 1;}}}for (auto& x : s){if (!vis[x])return false;}return true;
}
bool check(int t)
{s.clear();int cnt = 0,f = 0;for (int i = t; i; i >>= 1,cnt++){if (i & 1)s.insert(n-cnt-1);}for (auto& x : s){if (bfs(x)) {f = 1; break;}}return f;
}
void print(int t)
{int cnt = 0;stack<int>st;for (; cnt < n; t >>= 1,cnt++){st.push(t & 1);}while (st.size()){printf("%d", st.top()); st.pop();if(st.size())putchar(' ');}puts("");
}
int main() {cin >> n;for (int i = 1; i < (1 << n); ++i){if (check(i)){print(i);ans++;}}//cout << ans;return 0;
}
这篇关于n段码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
