我最近在一次工作面试中担任Java开发人员。我承担了一项任务:考虑一种用Java表示电路的好方法(例如下图中的电路)。

picture for illustration http://oi40.tinypic.com/nnr4wj.jpgg

电路是逻辑门XOR,AND,OR等的组合。每个门都有两个输入端口和一个输出端口。每个输出都连接到另一个门的输入,该门一直到更高的门(如图所示)。使系统简单,不允许循环(尽管现实生活中的电路可以循环使用)。
我被要求考虑使用以下准则来用Java表示此模型的好方法:

  • 给了我一个电路和应该提供给其输入的值列表。
  • 我需要创建一个模型来表示Java中的电路,即,我需要定义可用于表示电路的类和API。
  • 根据输入值以及门的连接方式,我需要计算表示电路将产生的输出。
  • 我需要考虑一种表示板,使用抽象类或接口(interface)以及显示对模型的理解的方法(以及在需要时使用模式设计的方法)。

  • 我选择将系统设计成一棵树,面试官告诉我这是一个不错的选择。然后,我构建这些类:

    节点
    public class gate_node {
        gate_node right_c,left_c;
        Oprtator op;
        int value;
        int right_v,left_v;
        public gate_node(gate_node right,gate_node left,Oprtator op){
            this.left_c=left;
            this.right_c=right;
            this.op=op;
            right_v=left_v=0;
        }
    
    }
    


    public class tree {
        gate_node head;
    
        tree(gate_node head) {
            this.head = head;
        }
    
        void go_right() {
            head = head.right_c;
        }
    
        void go_left() {
            head = head.left_c;
        }
    
        static int arr[] = { 0, 0, 1, 0 };
        static int counter=0;
    
        static int compute(gate_node head) {
    
            if ((head.left_c == null) && (head.right_c == null))
            {
                int ret=(head.op.calc(arr[counter], arr[counter+1]));
                counter++;
                counter++;
                return ret;
            }
            return (head.op.calc(compute(head.left_c), compute(head.right_c)));
    
        }
    
        public static void main(String[] args) {
            tree t = new tree(new gate_node(null, null, new and()));
            t.head.left_c = new gate_node(null, null, new and());
            t.head.right_c = new gate_node(null, null, new or());
            System.out.println(tree.compute(t.head));
        }
    }
    

    审判者类别:
    public abstract class Oprtator {
            abstract int calc(int x, int y);
    }
    

    或门:
    public class or extends Oprtator {
            public int calc(int x, int y){
                return (x|y);
            }
    }
    

    在上面的代码中,我将开发板实现为带有当前头的树(可以向下到左/右子级)。每个节点都有2个子节点(也是节点类型),2个条目(0/1),一个值和一个运算符(抽象类,可以通过OR/AND ..进行扩展)。

    我使用了一个计数器和一个数组将值插入到树的适当叶子中(如代码中所述)。

    它有效,但我仍然觉得我的面试官想要更多。我的代码正确吗?有没有人有更好的方式来表示该电路板以及如何给出良好的输出(就复杂性而言,或者从一种类别到另一种类别使用更好的连接,设计模式等等)?

    最佳答案

    这不是一个“完美”的答案,但是您可以使用一些类来解决此问题,以保留逻辑连接/评估,然后递归评估电路。

    创建基类LogicalNode并为其提供要管理的输入列表。给它一个基类函数来评估所有输入并返回一个输出。这在派生类中被覆盖。每种类型的节点(INPUT,NOT,AND,OR)都将获得具有特殊“ComputOutput”覆盖版本的派生类。如果在输出节点上计算输出,则应该递归树,计算输入等所有输入的输入,直到到达“INPUT”节点,这是系统的固定/逻辑输入。

    您可以相当快地创建新类型(请参见代码)。这里的评论不多,但应该可以自我解释。

    像这样的东西(在C#中):

    public class LogicalNode
        {
            private List<LogicalNode> _inputs = new List<LogicalNode>();
            private String _name = "Not Set";
    
    
            public override string ToString()
            {
                return String.Format("Node {0}", _name);
            }
    
            public void Reset()
            {
                _inputs.Clear();
            }
    
            public void SetName(String name)
            {
                _name = name;
            }
    
            protected List<LogicalNode> GetInputs()
            {
                return _inputs;
            }
    
            public void AddInput(LogicalNode node)
            {
                _inputs.Add(node);
            }
    
            protected virtual bool ComputeOutputInternal()
            {
                return false;
            }
    
            public bool ComputeOutput()
            {
               // Console.WriteLine("Computing output on {0}.", _name);
                return ComputeOutputInternal();
            }
        }
    
        public class LogicalInput : LogicalNode
        {
            private bool _state = true;
    
            public void SetState(bool state)
            {
                _state = state;
            }
    
            public bool GetState() { return _state; }
    
            protected override bool ComputeOutputInternal()
            {
                return _state;
            }
        }
    
        public class LogicalAND : LogicalNode
        {
            protected override bool ComputeOutputInternal()
            {
                List<LogicalNode> inputs = GetInputs();
                bool result = true;
                for (Int32 idx = 0; idx < inputs.Count && result; idx++)
                {
                    result = result && inputs[idx].ComputeOutput();
                }
                return result;
            }
        }
    
        public class LogicalOR : LogicalNode
        {
            protected override bool ComputeOutputInternal()
            {
                List<LogicalNode> inputs = GetInputs();
                bool result = false;
                for (Int32 idx = 0; idx < inputs.Count; idx++)
                {
                    result = inputs[idx].ComputeOutput();
                    if (result)
                        // If we get one true, that is enough.
                        break;
                }
                return result;
            }
        }
    
        public class LogicalNOT : LogicalNode
        {
            protected override bool ComputeOutputInternal()
            {
                List<LogicalNode> inputs = GetInputs();
                if (inputs.Count > 0)
                {   // NOTE:  This is not an optimal design for
                    // handling distinct different kinds of circuits.
                    //
                    // It it demonstrative only!!!!
                    return !inputs[0].ComputeOutput();
                }
                return false;
            }
    

    然后(快速)对其进行测试:
    static void Main(string[] args)
            {
                // The test circuit
                // !((A&&B) || C)
                // A    B   C   Out
                // 1    1   1   0
                // 1    1   0   0
                // 1    0   1   0
                // 1    0   0   1
                // 0    1   1   0
                // 0    1   0   1
                // 0    0   1   0
                // 0    0   0   1
                //
                //
                //
                /*     -------     -------
                 * A - |     |     |     |
                 *     | AND |-----|     |    -------
                 * B - | (D) |     |     |    |     |
                 *     -------     | OR  |----| NOT |----
                 *                 | (E) |    | (F) |
                 * C --------------|     |    |     |
                 *                 -------    -------
                 */
    
                LogicalInput A = new LogicalInput();
                LogicalInput B = new LogicalInput();
                LogicalInput C = new LogicalInput();
                LogicalAND   D = new LogicalAND();
                LogicalOR    E = new LogicalOR();
                LogicalNOT   F = new LogicalNOT();
    
                A.SetName("A");
                B.SetName("B");
                C.SetName("C");
                D.SetName("D");
                E.SetName("E");
                F.SetName("F");
    
                D.AddInput(A);
                D.AddInput(B);
    
                E.AddInput(D);
                E.AddInput(C);
    
                F.AddInput(E);
    
                // Truth Table
                bool[] states = new bool[]{ true, false };
                for(int idxA = 0; idxA < 2; idxA++)
                {
                    for(int idxB = 0; idxB < 2; idxB++)
                    {
                        for(int idxC = 0; idxC < 2; idxC++)
                        {
                            A.SetState(states[idxA]);
                            B.SetState(states[idxB]);
                            C.SetState(states[idxC]);
    
                            bool result = F.ComputeOutput();
    
                            Console.WriteLine("A = {0}, B = {1}, C = {2}, Output = {3}",
                                A.GetState(), B.GetState(), C.GetState(), result.ToString());
    
                        }
                    }
                }
            }
        }
    

    输出:
    A = True, B = True, C = True, Output = False
    A = True, B = True, C = False, Output = False
    A = True, B = False, C = True, Output = False
    A = True, B = False, C = False, Output = True
    A = False, B = True, C = True, Output = False
    A = False, B = True, C = False, Output = True
    A = False, B = False, C = True, Output = False
    A = False, B = False, C = False, Output = True
    

    这个有帮助吗?

    10-07 15:20