Advertisement
nguyenvanquan7826

cắt tủa anpha beta

Oct 24th, 2013
2,500
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. PROGRAM CAT_TIA;
  2. uses crt;
  3. const
  4. n = 3;
  5. m = n*n;
  6. type
  7. item = integer; {Kieu du lieu}
  8. pointer = ^node;
  9. node = record
  10. info : item; {Gia tri cac Nut, 1 X thang, 0 hoa nhau, -1 X thua}
  11. numChild : integer; {So con cua Nut}
  12. lab : char; {Nhan cua Nut}
  13. child : array[1..m] of pointer; {Mang cac con cua Nut}
  14. end;
  15. M2C = array[1..n,1..n] of char;
  16. IJ = record {Toa do trong bang}
  17. i, j: integer;
  18. end;
  19. var
  20. T : pointer; {Cay}
  21. MT : M2C; {Mang cac o caro}
  22. lb : integer; {Nhan cac o}
  23.  
  24.  
  25. function setValLa(MT: M2C): integer; {Kiem tra xem co thang?}
  26. var
  27. i, j, c, x, y: integer;
  28. check : boolean;
  29. begin
  30. c := 0;
  31. for i:=1 to n do
  32. begin
  33. for j:=1 to n do
  34. begin
  35. if ((j<=n-2) and (MT[i][j] = MT[i][j+1]) and (MT[i][j+1] = MT[i][j+2]) and (MT[i][j] <> '_'))
  36. or ((i<=n-2) and (MT[i][j] = MT[i+1][j]) and (MT[i+1][j] = MT[i+2][j]) and (MT[i][j] <> '_'))
  37. or ((i<=n-2) and (j <= n-2) and (MT[i][j] = MT[i+1][j+1]) and (MT[i+1][j+1] = MT[i+2][j+2]) and (MT[i][j] <> '_'))
  38. or ((i<=n-2) and (j >2) and (MT[i][j] = MT[i+1][j-1]) and (MT[i+1][j-1] = MT[i+2][j-2]) and (MT[i][j] <> '_'))
  39. then
  40. begin
  41. c := 1;
  42. end;
  43. if c=1 then break;
  44. end;
  45. if c=1 then break;
  46. end;
  47. setValLa := c;
  48. end;
  49.  
  50.  
  51. procedure newMT(var MT: M2c); {Khoi tao cau hinh rong}
  52. var
  53. i, j: integer;
  54. begin
  55. for i:=1 to n do
  56. for j:=1 to n do
  57. MT[i][j] := '_';
  58. end;
  59.  
  60. procedure creatMT(MT: M2c; c : char; var T: pointer); {Sinh cac TH va tao du lieu cho cay}
  61. var
  62. i, j, count, check: integer; {i, j la chi so Ma tran, count - dem cac o con trong, check - kiem tra thang thua}
  63. A : array[1..n] of IJ;
  64. p: pointer;
  65. begin
  66. count := 0;
  67. check := 0;
  68. for i:= 1 to n do {Dem va luu lai cac o rong, in ra cau hinh thu duoc}
  69. begin
  70. for j:=1 to n do
  71. begin
  72. if (MT[i][j] <> 'X') and (MT[i][j] <> 'O') then
  73. begin
  74. inc(count);
  75. A[count].i := i;
  76. A[count].j := j;
  77. end;
  78. write(MT[i][j]);
  79. end;
  80. writeln();
  81. end;
  82. check := setValLa(MT); {Kiem tra thang thua}
  83.  
  84.  
  85. if (T = nil) then new (T); {Khoi tao cay}
  86. T^.numChild := count; {Tao so Nut con cua Nut = so o rong}
  87.  
  88. if (count = 0) then T^.info := 0; {Neu khong o nao rong thi info = 0 - 2 ben hoa nhau}
  89. if (c = 'X') and (check = 1) then T^.info := -1 {X thua}
  90. else
  91. if (c = 'X') and (check <> 1) and (count <> 0) then T^.info := -2 {chua xac dinh, gia tri tam la -2}
  92. else
  93. if (c = 'O') and (check = 1) then T^.info := 1 {X thang}
  94. else if (c = 'O') and (check <> 1) and (count <>0) then T^.info := 2; {chua xac dinh, tam la 2}
  95.  
  96. inc(lb);
  97. T^.lab := chr(lb); {gan nhan cho Nut}
  98. writeln('Gai tri Nut cua cau hinh ', T^.lab, ' la: ', T^.info);
  99.  
  100. writeln('-----------------So o rong: ', count, ' , luot di cua ', c);
  101. writeln;
  102.  
  103. if (check = 1) or (count = 0) then T^.numChild := 0
  104. else
  105. begin {De quy tao cay va cau hinh tuong ung}
  106. for i:= 1 to count do
  107. begin
  108. new (T^.child[i]);
  109. MT[A[i].i][A[i].j] := c;
  110. if c = 'X' then creatMT(MT, 'O', T^.child[i])
  111. else if c = 'O' then creatMT(MT, 'X', T^.child[i]);
  112. MT[A[i].i][A[i].j] := '_';
  113. end;
  114. end;
  115. end;
  116. {
  117. procedure inputTree1(var T: pointer);
  118. var
  119. i: integer;
  120. p: pointer;
  121. begin
  122. if (T = nil) then new (T);
  123. write('Nhap nut con cua ', T^.info, ' : ');
  124. readln(T^.info);
  125. write('Nhap so con cua ', T^.info, ' : ');
  126. readln(T^.numChild);
  127. for i:=1 to T^.numChild do
  128. begin
  129. new (T^.child[i]);
  130. inputTree1(T^.child[i]);
  131. end;
  132. end;
  133. }
  134.  
  135. function nutLa(p: pointer): boolean; {Kiem tra p co la nut la ko}
  136. begin
  137. if p^.numChild = 0 then nutLa := true
  138. else nutLa := false;
  139. end;
  140.  
  141. procedure duyetTruoc(T: pointer); {Duyet theo thu tu truoc}
  142. var
  143. p: pointer;
  144. i: integer;
  145. begin
  146. if T <> nil then
  147. begin
  148. writeln(T^.lab, ' = ', T^.info);
  149. {if (nutLa(T)) then writeln(T^.lab , ' la la');}
  150. for i:=1 to T^.numChild do
  151. duyetTruoc(T^.child[i]);
  152. end;
  153. end;
  154.  
  155.  
  156. function max(a:item; b: item): item;
  157. begin
  158. if a>b then max:=a
  159. else max:=b;
  160. end;
  161.  
  162. function min(a:item; b:item): item;
  163. begin
  164. if a<b then min:=a
  165. else min := b;
  166. end;
  167.  
  168. {Ham tra ve gia tri trang thai khi dung minmax - thuat toan minmax}
  169. function val(var q: pointer; c: char; Vp: item): item;
  170. var
  171. i: integer;
  172. begin
  173. if (nutLa(q)) then {Neu la nut la thi lay ngay KQ gia tri cua nut do}
  174. begin
  175. {writeln(q^.lab,'->>> ', q^.info);}
  176. val:= q^.info;
  177. end
  178. else
  179. begin
  180. {if c = 'X' then Vq := -2 else Vq := 2;}
  181. for i:= 1 to q^.numChild do {Duyet cac nut con cua q}
  182. begin
  183. if c = 'X' then {Neu dang la luot X}
  184. begin
  185. q^.info:= max(q^.info, val(q^.child[i], 'O', q^.info));
  186. {writeln(q^.lab,'->>> ', q^.info);}
  187. val := q^.info;
  188. end
  189. else {Nguoc lai la luot O}
  190. begin
  191. q^.info:= min(q^.info, val(q^.child[i], 'X', q^.info));
  192. {writeln(q^.lab,'->>> ', q^.info);}
  193. val := q^.info;
  194. break;
  195. end;
  196. end;
  197. end;
  198. end;
  199.  
  200.  
  201.  
  202. procedure catTia(var T: pointer); {Dua thuat toan vao cay}
  203. begin
  204. if T <> nil then
  205. begin
  206. T^.info := val (T, 'X', T^.info);
  207. end;
  208. end;
  209.  
  210.  
  211. BEGIN
  212. clrscr;
  213. lb := 64;
  214. newMT(MT);
  215. {Khoi tao cau hinh ban dau}
  216. MT[1][1] := 'X'; MT[1][3]:= 'X'; MT[2][2] := 'X';
  217. MT[2][3] := 'O'; MT[3][1]:= 'O'; MT[3][3] := 'O';
  218. creatMT(MT, 'X', T);
  219. {inputTree1(T);}
  220. if T = nil then writeln('NIL');
  221. writeln('Truoc khi cat tia:');
  222. duyetTruoc(T);
  223. writeln;
  224. writeln('Qua trinh cat tia');
  225. catTia(T);
  226. writeln;
  227. writeln('Ket qua cat tia');
  228. duyetTruoc(T);
  229. readln;
  230. END.
Advertisement
RAW Paste Data Copied
Advertisement