创意品牌网站,wordpress php最大输出变量,搜索词分析工具,代理网游要多少钱试题 D: 七段码 本题总分#xff1a;10 分
【问题描述】 小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示#xff0c;数码管中一共有 7 段可以发光的二极管#xff0c;分别标记为 a, b, c, d, e, f, g。 小蓝要选择一部分二极管#xff0…试题 D: 七段码 本题总分10 分
【问题描述】 小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示数码管中一共有 7 段可以发光的二极管分别标记为 a, b, c, d, e, f, g。 小蓝要选择一部分二极管至少要有一个发光来表达字符。在设计字符的表达时要求所有发光的二极管是连成一片的。
例如 b 发光其他二极管不发光可以用来表达一种字符。 例如 c 发光其他二极管不发光可以用来表达一种字符。这种 方案与上 一行的方案可以用来表示不同的字符尽管看上去比较相似。 例如 a, b, c, d, e 发光 f, g 不发光可以用来表达一种字符。 例如 b, f 发光其他二极管不发光则不能用来表达一种字符因为发光 的二极管没有连成一片。 请问小蓝可以用七段码数码管表达多少种不同的字符
【答案提交】 这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。
【思路】 深度优先搜索状态压缩HashSet唯一性
【Java代码】
package lanqiao2020;import java.util.ArrayList;
import java.util.HashSet;public class test {//使用HashSet可以唯一性存储符合条件的数码管亮灭情况状态static HashSetInteger set new HashSet(); //使用邻接链表存储数码管连通情况static ArrayListInteger[] list new ArrayList[7];public static void main(String[] args) {//初始化连通情况for(int i 0; i 7; i) {list[i] new ArrayListInteger();}list[0].add(1);list[0].add(5);list[1].add(0);list[1].add(6);list[1].add(2);list[2].add(1);list[2].add(3);list[2].add(6);list[3].add(2);list[3].add(4);list[4].add(3);list[4].add(5);list[4].add(6);list[5].add(0);list[5].add(4);list[5].add(6);list[6].add(1);list[6].add(2);list[6].add(4);list[6].add(5);//以每个数码管作为起点即在该数码管必须亮情况下for (int i 0; i 7; i) {set.add(1i); //单独亮也符合情况所以存储进去dfs(1, i, 1i); //深度优先搜索}System.out.println(set.size()); //因为唯一性所以set中元素的个数即为符合条件的数码管亮灭状态的数量}//深度优先搜索第一个参数代表当前亮了几个数码管第二个参数代表当前最近亮起的数码管第三个参数即为当前状态如0000001代表0号数码管亮其余不亮static void dfs(int total, int cur, int state) {//最多亮起7个数码管if (total 7) {return;}for (Integer item : list[cur]) {if (!set.contains(state | (1item))) {set.add(state | (1item));}dfs(total1, item, state | (1item));}}
}【结果】 80
