2

上回話說同事誤發一題歐巴桑心理測驗得罪了方丈，衍生出名為研究實為找碴的程式練習題。以下便是黑暗版的C#解法。首先，設定一個物件對應出連線關係是一定要的，我用Dictionary<string, Node>建立一個以題號為Key的Node保存容器，用static GetNode() Method自容器中取出Node，不存在時則會即時新增放入容器中。至於連接的部分，是用Dictionary<string, Node>的方式記下選Y或選N會連至哪一個Node。

   1:  class Node
   2:  {
   3:      static Dictionary<string, Node> nodeList = 
   4:             new Dictionary<string, Node>();
   5:      public static Node GetNode(string name)
   6:      {
   7:          if (nodeList.ContainsKey(name))
   8:              return nodeList[name];
   9:          else
  10:          {
  11:              Node node = new Node(name);
  12:              nodeList.Add(name, node);
  13:              return node;
  14:          }
  15:      }
  16:      public Dictionary<string, Node> ToNodes = 
  17:             new Dictionary<string, Node>();
  18:      public string Name = "";
  19:      public Node(string name)
  20:      {
  21:          Name = name;
  22:      }
  23:      public void LinkTo(string choice, Node node) 
  24:      {
  25:          ToNodes.Add(choice, node);
  26:      }
  27:  }

元件搞定了，接下來用類似搜索子資料夾結構的遞迴(Recursive)寫法逐一走過所有可能的路徑(expore() Method)，已走過的路徑會串出一個字串向下傳，直到Node不再有連出線就算到終點，算是完成一種走法。

   1:  static void Main(string[] args)
   2:  {
   3:      System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
   4:      sw.Start();
   5:      doIt();
   6:      sw.Stop();
   7:      Console.WriteLine(string.Format("Time: {0:#,##0}ms", 
                                           sw.ElapsedMilliseconds));
   8:      foreach (string result in results)
   9:          Console.WriteLine(result);
  10:      Console.Read();
  11:  }
  12:  static void doIt()
  13:  {
  14:      string data =
  15:      "1:Y4,N2;2:Y3,N5;3:Y9,N6;4:Y7,N3;5:Y8,N9;6:Y12,N14;7:Y10,N6;8:Y11,N12;"
         + "9:Y13,N11;10:Y14,N13;11:YB,NA;12:YC,NA;13:YB,ND;14:YC,ND;A:;B:;C:;D:";
  16:      string[] nodeSets = data.Split(';');
  17:      foreach (string nodeSet in nodeSets)
  18:      {
  19:          string nodeName = nodeSet.Split(':')[0];
  20:          string nodePathes = nodeSet.Split(':')[1];
  21:          string[] pathes = (nodePathes.Length > 0) ? 
                                  nodePathes.Split(',') : new string[0];
  22:          Node node = Node.GetNode(nodeName);
  23:          foreach (string path in pathes)
  24:              node.LinkTo(path.Substring(0, 1), 
                               Node.GetNode(path.Substring(1)));
  25:      }
  26:      explore(Node.GetNode("1"), "");
  27:  }
  28:  static void explore(Node node, string route)
  29:  {
  30:      if (route.Length > 0) route += "->";
  31:      route += node.Name;
  32:      if (node.ToNodes.Count == 0)
  33:          results.Add(route);
  34:      else
  35:          foreach (Node toNode in node.ToNodes.Values)
  36:              explore(toNode, route);
  37:  }
  38:  static List<string> results = new List<string>();

不算上班途中邊騎邊想的時間，Coding大約花了半小時不到，程式執行耗時約9ms。以上的邏輯可以改寫成走迷宮，不過需要再加上防止形成Loop的邏輯。

以上程式雖不足70列，執行速度也夠快，但怎麼都只能算是中規中矩。週四題目貼出不過幾小時，網友Ammon就抛出一則以Javascript撰寫的解法，讓我嚇到尿褲子。沒想到短短幾行Javascript也可以搞出這麼靈活的運用，常自詡對Javascript有一定認識，但見了這番媲美吞劍噴火的花式應用，才驚覺自己恐怕還在幼幼班的水準。網路之大，本當卧虎藏龍；學海無涯，切忌意得志滿。領教了!!


Comments

# by Morris

我在執行 Ammon 的 JavaScript 時 會出現如下錯誤 'document.getElementById(...)'是 null 或不是一個物件 請問是什麼問題呢??

# by Morris

自問自答....設定一下該頁的 ID 就 OK 了!!

Post a comment