# 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, ' : ');
125. write('Nhap so con cua ', T^.info, ' : ');
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);