CTD-K56 Bài 09: Bài tập giữa kỳ

2 bình luận cho CTD-K56 Bài 09: Bài tập giữa kỳ

• 

  27/12/2017 - 22:28

  admin  says:

  Mã nguồn minh họa thuật toán BOTTOM-UP viết bằng ngôn ngữ lập trình C#

  C#

  using System; using System.Collections.Generic; class Rule {     public string left, right;     public Rule(string l, string r) {         left = l;         right = r;     }     public string ToFineString() {         string s = left + " -->";         for (int i = 0; i < right.Length; i++) s += " " + right[i];         return s;     } } class Step {     public int ruleNumber, position;     public Step(int r, int p) {         ruleNumber = r;         position = p;     } } class PTBU {     public List<Rule> rules = new List<Rule>();     public List<Step> steps;     string word = null;     public void AddRule(string left, string right) {         rules.Add(new Rule(left, right));     }     public void PrintAllRules() {         Console.WriteLine("<bo luat van pham>");         foreach (Rule r in rules)             Console.WriteLine("  " + r.ToFineString());     }     public void PrintSteps() {         Console.WriteLine("Doan nhan thanh cong sau {0} buoc", steps.Count);         string w = word;         foreach (Step s in steps) {             string x = DoBackStep(w, s); Console.WriteLine(" {0} <= {1} (o vi tri {2}, thu gon bang luat {3})", w, x, s.position+1, rules[s.ruleNumber].ToFineString()); w = x;         }     }     string DoBackStep(string w, Step s) {         string w1 = w.Substring(0, s.position);         string w2 = w.Substring(s.position + rules[s.ruleNumber].right.Length);         return w1 + rules[s.ruleNumber].left + w2;     } public bool Process(string x) {     steps = new List<Step>();     word = x;     return BottomUp(x); } // áp dụng được luật k ở vị trí i của chuỗi w? bool CanApplyHere(string w, int i, int k) { string s = w.Substring(i); if (s.Length > rules[k].right.Length) s = s.Substring(0, rules[k].right.Length); return (s == rules[k].right); } public bool BottomUp(string w) { if ("S" == w) return true; for (int i = 0; i < w.Length; i++) for (int k = 0; k < rules.Count; k++) if (CanApplyHere(w, i, k)) { Step st = new Step(k, i); steps.Add(st); String b = DoBackStep(w, st); Console.WriteLine("{0} <= {1}", w, b); if (BottomUp(b)) return true; steps.RemoveAt(steps.Count - 1); } Console.WriteLine("<<<"); return false; } } class Program {     public static void Main() {         PTBU parser = new PTBU();         parser.AddRule("S", "AB");         parser.AddRule("S", "B");         parser.AddRule("A", "a");         parser.AddRule("A", "aA");         parser.AddRule("B", "b");         parser.AddRule("B", "bB");         parser.PrintAllRules();         if (parser.Process("aaab")) parser.PrintSteps();     } }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

  using System; using System.Collections.Generic;   class Rule {     public string left, right;     public Rule(string l, string r) {         left = l;         right = r;     }     public string ToFineString() {         string s = left + " -->";         for (int i = 0; i < right.Length; i++) s += " " + right[i];         return s;     } }   class Step {     public int ruleNumber, position;     public Step(int r, int p) {         ruleNumber = r;         position = p;     } }   class PTBU {     public List<Rule> rules = new List<Rule>();     public List<Step> steps;     string word = null;       public void AddRule(string left, string right) {         rules.Add(new Rule(left, right));     }     public void PrintAllRules() {         Console.WriteLine("<bo luat van pham>");         foreach (Rule r in rules)             Console.WriteLine("  " + r.ToFineString());     }     public void PrintSteps() {         Console.WriteLine("Doan nhan thanh cong sau {0} buoc", steps.Count);         string w = word;         foreach (Step s in steps) {             string x = DoBackStep(w, s);             Console.WriteLine("  {0} <= {1} (o vi tri {2}, thu gon bang luat {3})", w, x, s.position+1, rules[s.ruleNumber].ToFineString());             w = x;         }     }     string DoBackStep(string w, Step s) {         string w1 = w.Substring(0, s.position);         string w2 = w.Substring(s.position + rules[s.ruleNumber].right.Length);         return w1 + rules[s.ruleNumber].left + w2;     }     public bool Process(string x) {         steps = new List<Step>();         word = x;         return BottomUp(x);     }     // áp dụng được luật k ở vị trí i của chuỗi w?     bool CanApplyHere(string w, int i, int k) {         string s = w.Substring(i);         if (s.Length > rules[k].right.Length)             s = s.Substring(0, rules[k].right.Length);         return (s == rules[k].right);     }     public bool BottomUp(string w) {         if ("S" == w) return true;         for (int i = 0; i < w.Length; i++)             for (int k = 0; k < rules.Count; k++)                 if (CanApplyHere(w, i, k)) {                     Step st = new Step(k, i);                     steps.Add(st);                     String b = DoBackStep(w, st);                     Console.WriteLine("{0} <= {1}", w, b);                     if (BottomUp(b)) return true;                     steps.RemoveAt(steps.Count - 1);                 }         Console.WriteLine("<<<");         return false;     } } class Program {     public static void Main() {         PTBU parser = new PTBU();         parser.AddRule("S", "AB");         parser.AddRule("S", "B");         parser.AddRule("A", "a");         parser.AddRule("A", "aA");         parser.AddRule("B", "b");         parser.AddRule("B", "bB");         parser.PrintAllRules();         if (parser.Process("aaab"))             parser.PrintSteps();     } }

  Trả lời
• 

  27/12/2017 - 22:27

  admin  says:

  Mã nguồn minh họa thuật toán TOP-DOWN viết bằng ngôn ngữ lập trình C#

  C#

  using System; using System.Collections.Generic; // Lớp chứa luật văn phạm, dạng left -> right class Rule {   public string left, right;   public Rule(string l, string r) {     left = l; right = r;   } // chuyển đổi luật về dạng string (để in cho dễ nhìn)   public string ToFineString() {     string s = left + " -->";     for (int i = 0; i < right.Length; i++)       s += " " + right[i];     return s;   } } // Lớp chứa một bước áp dụng luật suy diễn // + ruleNumber: số thứ tự của luật sẽ được dùng // + position: vị trí sẽ áp dụng luật đó class Step {   public int ruleNumber, position;   public Step(int r, int p) {     ruleNumber = r;     position = p;  } } class PTTD {   public List<Rule> rules = new List<Rule>(); // bộ luật   public List<Step> steps; // các bước suy diễn   string w = null; // chuỗi W đích   // thêm luật left --> right vào tập luật   public void AddRule(string left, string right) {     rules.Add(new Rule(left, right));   }   public void PrintAllRules() {     Console.WriteLine("<bo luat van pham>");     foreach (Rule r in rules)       Console.WriteLine("  " + r.ToFineString());   }   public void PrintSteps() {     string w = "S"; Console.Write(" S");     foreach (Step s in steps) {       string w0 = DoStep(w, s);       Console.Write(" => {0}", w0);       w = w0;     } Console.WriteLine();   }   string DoStep(string w, Step s) {     string w1 = w.Substring(0, s.position);     string w2 = w.Substring(s.position + 1);     return w1 + rules[s.ruleNumber].right + w2;   } public bool Process(string x) {     steps = new List<Step>();     w = x;     return Try("S"); } // tìm vị trí non-terminal trái nhất trong s // trả về -1 nếu không tìm được public int FindNonterminal(string s) {     for (int i = 0; i < s.Length; i++) {       if (i >= w.Length) return i;       if (s[i] != w[i]) return i;      }     return -1; } // hàm thử-sai-quay-lui với chuỗi s public bool Try(string s) { PrintSteps();     if (s == w) return true;     int n = FindNonterminal(s);     if (n != -1)       for (int i = 0; i < rules.Count; i++)         if (rules[i].left[0] == s[n]) {           Step st = new Step(i, n);           steps.Add(st);           if (Try(DoStep(s, st))) return true;           steps.RemoveAt(steps.Count - 1);         }     return false; } } class Program {   public static void Main() {     PTTD parser = new PTTD(); // nạp thử bộ luật     parser.AddRule("S", "AB"); parser.AddRule("A", "aA");     parser.AddRule("A", "");     parser.AddRule("B", "b");     parser.AddRule("B", "bB");     parser.PrintAllRules();     if (parser.Process("aaab")); //parser.PrintSteps();   } }

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

  using System; using System.Collections.Generic;   // Lớp chứa luật văn phạm, dạng left -> right class Rule {   public string left, right;   public Rule(string l, string r) {     left = l; right = r;   }   // chuyển đổi luật về dạng string (để in cho dễ nhìn)   public string ToFineString() {     string s = left + " -->";     for (int i = 0; i < right.Length; i++)       s += " " + right[i];     return s;   } }   // Lớp chứa một bước áp dụng luật suy diễn // + ruleNumber: số thứ tự của luật sẽ được dùng // + position: vị trí sẽ áp dụng luật đó class Step {   public int ruleNumber, position;   public Step(int r, int p) {     ruleNumber = r;     position = p;  } }   class PTTD {   public List<Rule> rules = new List<Rule>();   // bộ luật   public List<Step> steps;                      // các bước suy diễn   string w = null;                              // chuỗi W đích   // thêm luật left --> right vào tập luật   public void AddRule(string left, string right) {     rules.Add(new Rule(left, right));   }   public void PrintAllRules() {     Console.WriteLine("<bo luat van pham>");     foreach (Rule r in rules)       Console.WriteLine("  " + r.ToFineString());   }   public void PrintSteps() {     string w = "S";     Console.Write("  S");     foreach (Step s in steps) {       string w0 = DoStep(w, s);       Console.Write(" => {0}", w0);       w = w0;     }     Console.WriteLine();   }   string DoStep(string w, Step s) {     string w1 = w.Substring(0, s.position);     string w2 = w.Substring(s.position + 1);     return w1 + rules[s.ruleNumber].right + w2;   }   public bool Process(string x) {     steps = new List<Step>();     w = x;     return Try("S");   }   // tìm vị trí non-terminal trái nhất trong s   // trả về -1 nếu không tìm được   public int FindNonterminal(string s) {     for (int i = 0; i < s.Length; i++) {       if (i >= w.Length) return i;       if (s[i] != w[i]) return i;      }     return -1;   }   // hàm thử-sai-quay-lui với chuỗi s   public bool Try(string s) {     PrintSteps();     if (s == w) return true;     int n = FindNonterminal(s);     if (n != -1)       for (int i = 0; i < rules.Count; i++)         if (rules[i].left[0] == s[n]) {           Step st = new Step(i, n);           steps.Add(st);           if (Try(DoStep(s, st))) return true;           steps.RemoveAt(steps.Count - 1);         }     return false;   } } class Program {   public static void Main() {     PTTD parser = new PTTD();     // nạp thử bộ luật     parser.AddRule("S", "AB");     parser.AddRule("A", "aA");     parser.AddRule("A", "");     parser.AddRule("B", "b");     parser.AddRule("B", "bB");     parser.PrintAllRules();     if (parser.Process("aaab"));  //parser.PrintSteps();   } }

  Trả lời