集美网站开发,正能量erp软件下载网站,公司官网首页,弓长岭网站建设题目背景 土豪大学的计算机系开了一门数字逻辑电路课#xff0c;第一个实验叫做“点亮数字人生”#xff0c;要用最基础的逻辑元件组装出实际可用的电路。时间已经是深夜了#xff0c;尽管实验箱上密密麻麻的连线已经拆装了好几遍#xff0c;小君同学却依旧没能让她的电路正…题目背景 土豪大学的计算机系开了一门数字逻辑电路课第一个实验叫做“点亮数字人生”要用最基础的逻辑元件组装出实际可用的电路。时间已经是深夜了尽管实验箱上密密麻麻的连线已经拆装了好几遍小君同学却依旧没能让她的电路正常工作。你能帮助她模拟出电路的功能成功点亮她的数字人生吗
问题描述 本题中你需要实现一个简单的数字逻辑电路模拟器。如果你已经有了此方面的基础可以直接跳过本节。在阅读时也可以参照前两个样例的图示和解释这有助于你更好地理解数字逻辑电路的工作原理。
数字逻辑电路是用来传输数字信号也就是二进制信号的电路。一般来说数字逻辑电路可以分为两大类即组合逻辑combinational logic电路和时序逻辑sequential logic电路。在本题中我们仅关注组合逻辑电路。这种电路仅由逻辑门logical gate构成。一个逻辑门可以理解为一个多输入单输出的函数输入端连接至少一个信号而后经过一定的逻辑运算输出一个信号。常见的逻辑门包括与AND、或OR、非NOT、异或XOR等均与编程语言中的按位运算是对应的。
将一系列的逻辑门连接起来就能构成具有特定功能的电路。它的功能可能很简单如一位二进制加法只需要一个异或门也可能极其复杂如除法。无论复杂程度这类电路的特点是它不维持任何的状态任何时刻输出只与输入有关随输入变化。真实世界中的逻辑器件由于物理规律的限制存在信号传播延时。为了简单起见本题中我们模拟的组合逻辑电路不考虑延时一旦输入变化输出立刻跟着变化。
考虑到组合逻辑电路的这一特性设计时不能允许组合环路combinational loop的存在即某逻辑门的输入经过了一系列器件之后又被连接到了自己的输入端。真实世界中这种做法将导致电路变得不稳定甚至损坏元器件。因此你也需要探测可能的环路。需要注意环路的存在性与逻辑门的具体功能没有任何关系只要连接关系上存在环路电路就无法正常工作。
输入格式 输入数据包括若干个独立的问题第一行一个整数 满足 。接下来依次是这 个问题的输入你需要对每个问题进行处理并且按照顺序输出对应的答案。
每一个问题的输入在逻辑上可分为两部分。第一部分定义了整个电路的结构第二部分定义了输入和输出的要求。实际上两部分之间没有分隔顺序读入即可。
第一部分 第一行是两个空格分隔的整数 分别表示了整个电路的输入和器件的数量满足 并且 。其中 和 都是与测试点编号有关的参数。
接下来 行每行描述一个器件编号从 1 开始递增格式如下
FUNC k L_1 L_2 … L_k None 其中 FUNC 代表具体的逻辑功能 表示输入的数量后面跟着该器件的 个输入端描述 格式是以下二者之一
Im表示第 m 个输入信号连接到此输入端保证 On表示第 n 个器件的输出连接到此输入端保证 。 所有可能的 FUNC 和允许的输入端数量如下表所述
FUNC 最少输入数量 最多输入数量 功能描述 NOT 1 1 非 AND 2 与 OR 2 或 XOR 2 异或 NAND 2 与非先全部与后取非 NOR 2 或非先全部或后取非 所有的器件均只有一个输出但这个输出信号可以被用作多个器件的输入。
第二部分 第一行是一个整数 表示此电路需要运行 次。每次运行都会给定一组输入并检查部分器件的输出是否正确。 满足 其中 是一个与测试点编号有关的参数。
接下来的 行为输入描述每一行的格式如下
I_1 I_2 … I_M None 每行有 个可能为 0 或 1 的数字表示各个输入信号按编号排列的状态。
接下来的 行为输出描述每一行的格式如下
s_i O_1 O_2 … O_s None 第一个整数 表示需要输出的信号数量。后面共有 个在 到 之间的数字表示在对应的输入下组合逻辑完成计算后需要输出结果的器件编号。
注意 O 序列不一定是递增的即要求输出的器件可能以任意顺序出现。
输出格式 对于输入中的 个问题你需要按照输入顺序输出每一个问题的答案
如果你检测到电路中存在组合环路则请输出一行内容是 LOOP无需输出其他任何内容。
如果电路可以正常工作则请输出 行每一行包含 个用空格分隔的数字可能为 0 或 1依次表示“输出描述”中要求的各个器件的运算结果。
样例输入1 1 3 5 XOR 2 I1 I2 XOR 2 O1 I3 AND 2 O1 I3 AND 2 I1 I2 OR 2 O3 O4 4 0 1 1 1 0 1 1 1 1 0 0 0 2 5 2 2 5 2 2 5 2 2 5 2 Data 样例输出1 1 0 1 0 1 1 0 0 Data 样例1说明 本样例只有一个问题它定义的组合逻辑电路结构如下图所示。其功能是一位全加器即将三个信号相加得到一个两位二进制数。要求的器件 2 的输出是向更高位的进位信号器件 5 的输出是本位的求和信号。
p3.jpg
对于第一组输入 0 1 1输出是 1 0对于第二组输入 1 0 1输出恰好依旧是 1 0但电路内部状态不同。
样例输入2 1 2 6 NOR 2 O4 I2 AND 2 O4 O6 XOR 2 O5 O1 NOT 1 O6 NAND 2 O2 O2 AND 2 I1 O3 2 0 0 1 0 3 2 3 4 6 1 2 3 4 5 6 Data 样例输出2 LOOP Data 样例2说明 本样例也只有一个问题它定义的组合逻辑电路结构如下图所示。
p4.jpg
这是一个带组合环路的电路因此无法正常工作。特别地其中最短的环路有以下三条
6 - 2 - 5 - 3 - 6 4 - 1 - 3 - 6 - 4 2 - 5 - 3 - 6 - 2 评测用例规模与约定 import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.*;public class DigitalMock {static StreamTokenizer stnew StreamTokenizer(new BufferedInputStream(System.in));static int nextInt() throws IOException{st.nextToken();return (int)st.nval;}static String next() throws IOException{st.nextToken();return st.sval;}static int Q;//问题个数static int m;//信号输入个数static int n;//器件个数static Nop nops[]new Nop[550];static int head[]new int[550];static int ne[]new int[50000];static int to[]new int[50000];static int cnt1;static int du[]new int[550];static void init(){//初始化Arrays.fill(head,0);Arrays.fill(nops,null);Arrays.fill(ne,0);Arrays.fill(to,0);Arrays.fill(du,0);cnt1;}static void add(int u,int v){to[cnt]v;ne[cnt]head[u];head[u]cnt;}public static void main(String[] args) throws IOException{QnextInt();for (int i 0; i Q; i) {init();mnextInt();nnextInt();for (int i1 1; i1 n; i1) {String typenext();int inputsNumnextInt();for (int j 0; j inputsNum; j) {String innext();char tin.charAt(0);int uInteger.valueOf(in.substring(1));du[i1];//起始输入点if(tI){add(un,i1);}//其他器件else{add(u,i1);}}Nop nop new Nop(type);nops[i1]nop;}for (int k 1; k m; k) {nops[kn]new Nop(SUPER);}int snextInt();ListListInteger inputs new ArrayList();ListListInteger ques new ArrayList();for (int i1 0; i1 s; i1) {ListInteger sign new ArrayList();for (int i2 0; i2 m; i2) {sign.add(nextInt());}inputs.add(sign);}for (int p 0; p s; p) {int numnextInt();ListInteger q new ArrayList();for (int i1 0; i1 num; i1) {q.add(nextInt());}ques.add(q);}if(isLoop()false){System.out.println(LOOP);continue;}for (int i1 0; i1 s; i1) {query(inputs.get(i1),ques.get(i1));}}}static void query(ListInteger input,ListInteger ques){for (int i 1; i n; i) {//清空所有信号nops[i].inputnew ArrayList();}for (int i 1; i input.size(); i) {nops[in].outputinput.get(i-1);}topo();ArrayListInteger res new ArrayList();for (Integer que : ques) {res.add(nops[que].getOut());}for (int i 0; i res.size(); i) {System.out.printf(res.get(i) );}System.out.println();}static boolean isLoop(){int visnum0;int rudu[];rududu.clone();QueueInteger qnew LinkedList();for (int i 1; i mn; i) {if(rudu[i]0)q.offer(i);}while (!q.isEmpty()){Integer x q.poll();//出队visnum;//访问点1for(int ihead[x];i!0;ine[i]){int yto[i];rudu[y]--;if(rudu[y]0){q.offer(y);}}}return visnummn;}static void topo(){int rudu[];rududu.clone();QueueInteger qnew LinkedList();for (int i 1; i mn; i) {if(rudu[i]0)q.offer(i);}while (!q.isEmpty()){Integer x q.poll();//出队for(int ihead[x];i!0;ine[i]){int yto[i];rudu[y]--;nops[y].input.add(nops[x].getOut());if(rudu[y]0){q.offer(y);}}}}
}
class Nop{//NOT/AND/OR/XOR/NAND/NOR/SUPER(指输入信号节点超级节点)String type;ListInteger input;//输入端int output-1;//输出端public Nop(String type) {this.type type;this.inputnew ArrayList();}public int getOut(){//计算输出端结果if(output!-1) return output;if(type.equals(NOT)){return input.get(0)0?1:0;}else if(type.equals(SUPER)){return output;}else if(type.equals(AND)){for (Integer integer : input) {if(integer0) return 0;}return 1;}else if(type.equals(OR)){for (Integer integer : input) {if(integer1) return 1;}return 0;}else if(type.equals(XOR)){int res0;for (Integer integer : input) {res^integer;}return res;}else if(type.equals(NAND)){for (Integer integer : input) {if(integer0) return 1;}return 0;}else{for (Integer integer : input) {if(integer1) return 0;}return 1;}}
}
