Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 1 - Chương 2: Sinh dữ liệu vào và ra

Các biến KhoiTriSo và KhoiTriToan được khai báo và gán trị khởi đầu như 
sau: 
const 
 KhoiTriSo: MangSo = (0,0,0,0); 
 KhoiTriToan: MangToan = (BL,BL); 
q = 1: Trạng thái tìm đọc số thứ nhất, so[1]: Ở trạng thái này, nếu gặp chữ số thì ta 
ghép thêm chữ số đó vào so[1], nếu gặp dấu phép toán thì ta hiểu là thành phần thứ 
nhất của đoạn là một biểu thức dạng: 
so[1] Toan[1] so[2] 
Ta ghi nhận dấu phép toán vào trường Toan[1] và chuyển qua trạng thái q = 2 
để đọc số thứ hai. Nếu gặp dấu phẩy (,) là dấu ngăn giữa hai thành phần của đoạn ta 
chuyển qua trạng thái q = 3 để đọc số đầu tiên của thành phần thứ hai, tức là đọc 
so[3]. 
1: if c in ChuSo then DocSo(n,1) 
 else if c in PhepToan then 
begin a[n].Toan[1]:=c; q:=2; end 
 else if c=',' then q:=3; 
Thủ tục DocSo(i,j) nhận thêm 1 chữ số để ghép vào biến a[i].so[j]. 
q = 2: Đọc số thứ hai, so[2]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số 
đó vào so[2], nếu gặp dấu phẩy là dấu ngăn giữa hai thành phần của đoạn ta chuyển 
qua trạng thái q = 3 để đọc số đầu tiên của thành phần thứ hai, tức là đọc so[3]. 
 2: if c in ChuSo then DocSo(n,2) 
 else if c =',' then q:=3; 
q = 3: Đọc số thứ ba, so[3]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số 
đó vào so[3], nếu gặp dấu phép toán thì ta hiểu là thành phần thứ hai của đoạn là một 
biểu thức dạng: 
Sáng tạo trong Thuật toán và Lập trình Tập I 
59 
so[3] Toan[2] so[4] 
Ta ghi nhận dấu phép toán vào trường Toan[2] và chuyển qua trạng thái q = 4 để đọc 
số thứ tư, so[4], nếu gặp kí tự c = ')' hoặc c = ']' thì ta hiểu là đã kết thúc một 
đoạn, ta gọi thủ tục KetDoan để thực hiện các thao tác sau: 
- Ghi nhận kí tự đóng đoạn: a[n].dong:= c. 
- Tính chiều dài của đoạn: LenSeg(n); 
- Chuyển qua trạng thái q = 0 để tiếp tục với đoạn tiếp theo, nếu còn. 
procedure KetDoan; 
begin 
a[n].dong:=c; LenSeg(n); q:=0; 
end; 
Đoạn chương trình thể hiện trạng thái q = 3 khi đó sẽ như sau: 
3: if c in ChuSo then DocSo(n,3) 
 else if c in PhepToan then 
 begin a[n].Toan[2]:=c; q:=4 end 
 else if c in[')',']'] then KetDoan; 
q = 4: Đọc số thứ tƣ, so[4]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số 
đó vào so[4], nếu gặp kí tự c = ')' hoặc c = ']' thì ta hiểu là đã kết thúc một 
đoạn, ta gọi thủ tục KetDoan. 
4: if c in ChuSo then DocSo(n,4) 
 else if c in[')',']'] then KetDoan; 
Đọc tệp xong ta dùng thủ tục qsort sắp các đoạn tăng dần theo chiều dài. Sau khi 
sắp ta ghi các đoạn vào tệp gn theo các trường. 
(* Pascal *) 
{$B-} 
program Segments; 
uses crt; 
const 
 fn = 'DOAN.INP'; {Tep input} 
 gn = 'DOAN.OUT';{Tep output} 
 MN = 1000; {So luong toi da cac doan} 
 BL = #32;{Dau cach} 
 ChuSo = ['0'..'9']; 
 PhepToan = ['+','*']; 
 type 
 MangSo = array[1..4] of integer; 
 MangToan = array[1..2] of char; 
 KieuDoan = record 
 mo: char; {dau mo ngoac} 
 dong: char; {dau dong ngoac} 
 so: MangSo; {4 so trong doan} 
 Toan: MangToan; {2 phep toan} 
 len: integer; {chieu dai doan} 
Sáng tạo trong Thuật toán và Lập trình Tập I 
60 
 end; 
 MangDoan = array[0..MN] of KieuDoan; 
const 
 KhoiTriSo: MangSo = (0,0,0,0); 
 KhoiTriToan: MangToan = (BL,BL); 
var 
 f,g:text; 
 a: MangDoan; 
 c: char;{ky tu dang xet} 
 n: integer;{chi so doan dang xet} 
 q: integer;{bien trang thai} 
(*--------------------------------- 
Cac trang thai q = 0: do tim dau doan 
1: doc so[1] 
2: doc so[2] 
3: doc so[3] 
4: doc so[4] 
-----------------------------------*) 
procedure LenSeg(i: integer); tự viết 
procedure KetDoan; tự viết 
(*----------------------------------------- 
 Them 1 chu so vao so thu j cua doan i 
------------------------------------------*) 
procedure DocSo(i,j: integer); 
begin 
 a[i].so[j]:=a[i].so[j]*10+(ord(c)-ord('0')) 
end; 
(*-------------------------------------- 
 Doc cac doan 
---------------------------------------*) 
procedure doc; 
begin 
 assign(f,fn); reset(f); 
 q:=0; n:=0; 
 while not eof(f) do 
 begin 
 read(f,c); 
 case q of 
 0: if c in['(','['] then 
 begin 
 n:=n+1; a[n].mo:=c; 
 a[n].so:=KhoiTriSo; 
 a[n].Toan:=KhoiTriToan; 
 q:=1; 
 end; 
Sáng tạo trong Thuật toán và Lập trình Tập I 
61 
 1: if c in ChuSo then DocSo(n,1) 
 else if c in PhepToan then 
 begin a[n].Toan[1]:=c; q:=2 end 
 else if c=',' then q:=3; 
 2: if c in ChuSo then DocSo(n,2) 
 else if c =',' then q:=3; 
 3: if c in ChuSo then DocSo(n,3) 
 else if c in PhepToan then 
 begin 
 a[n].Toan[2]:=c; q:=4; 
 end 
 else if c in[')',']'] then KetDoan; 
 4: if c in ChuSo then DocSo(n,4) 
 else if c in [')',']'] then KetDoan; 
 end; { case } 
 end; { while } 
 close(f); 
 end; 
procedure qsort(d,c:integer); 
var i,j,m: integer; 
 x: KieuDoan; 
begin 
i:=d; j:=c; m:=a[(i+j) div 2].len; 
while i<=j do 
begin 
while a[i].len < m do i:=i+1; 
while a[j].len > m do j:=j-1; 
if i<=j then 
begin 
x:=a[i]; a[i]:=a[j]; a[j]:= x; 
i:=i+1; j:=j-1; 
end; 
end; 
if d < j then qsort(d,j); 
if i < c then qsort(i,c); 
end; 
procedure Ghi; 
var i: integer; 
begin 
assign(g,gn); rewrite(g); 
for i:=1 to n do 
with a[i] do 
begin 
 if Toan[1]BL then 
 write(g,mo, so[1],Toan[1],so[2]) 
Sáng tạo trong Thuật toán và Lập trình Tập I 
62 
 else write(g,mo, so[1]); 
 if Toan[2]BL then 
 write(g,',',so[3],Toan[2],so[4],dong,BL) 
 else write(g,',',so[3],dong,BL); 
 { moi dong viet 10 doan } 
if i mod 10 = 0 then writeln(g); 
end; 
close(g); 
end; 
BEGIN 
Doc; qsort(1,n); Ghi; 
END. 
// C# 
 using System; 
 using System.IO; 
 using System.Collections; 
 namespace SangTao1 
 { 
 class SapDoan 
 { 
 static public string fn = "Doan.inp"; 
 static public string gn = "Doan.out"; 
 static public string s; // du lieu vao 
 static public Doan[] d = new Doan[5000]; // cac doan 
 static public int n = 0; // so luong doan 
 static public char Ket = '#'; 
 static void Main(string[] args) 
 { 
 s = File.ReadAllText(fn) + Ket.ToString(); 
 Console.WriteLine("\n Du lieu " + 
 "truoc khi xu li:\n " + s); 
 n = DocDoan(); 
 Console.WriteLine("\n Tong cong " + n + " Doan"); 
 Console.WriteLine(n); Printd(); 
 QSort(d, 0, n-1); 
 Console.WriteLine("\n Da sap: "); Printd(); 
 Ghi(); XemLai(); 
 Console.WriteLine("\n Fini "); 
 Console.ReadLine(); 
 } 
 static public void XemLai() 
 { 
 Console.WriteLine("\n Kiem tra lai:\n"); 
 Console.WriteLine("\n Input:\n" + 
 File.ReadAllText(fn)); 
 Console.WriteLine("\n Output:\n" + 
 File.ReadAllText(gn)); 
 } 
 static public int DocDoan() 
 { 
Sáng tạo trong Thuật toán và Lập trình Tập I 
63 
 int n = -1; 
 int q = 0; // trang thai 
 int i = 0; // bien tro trong s 
 int dau, cuoi; 
 for (; s[i] != Ket; ++i) 
 { 
 switch(q) 
 { 
 case 0: // Tim dau doan 
 if (GapMo(s[i])) 
 { 
 ++n; d[n] = new Doan(); 
 d[n].Mo = s[i]; q = 1; 
 } 
 break; 
 case 1: // Doc so1 
 if (GapSo(s[i])) 
 d[n].So1 = DocSo(ref i); 
 else if (GapToan(s[i])) 
 {d[n].Toan1 = s[i]; q = 2;} 
 else if (s[i]==',') q = 3; 
 break; 
 case 2: // Doc so2 
 if (GapSo(s[i])) 
 d[n].So2 = DocSo(ref i); 
 else if (s[i]==',') q = 3; 
 break; 
 case 3: // Doc so3 
 if (GapSo(s[i])) 
 d[n].So3 = DocSo(ref i); 
 else if (GapToan(s[i])) 
 { 
 d[n].Toan2 = s[i]; q = 4; 
 } 
 else if (GapDong(s[i])) 
 q = 5; 
 break; 
 case 4: // Doc so4 
 if (GapSo(s[i])) 
 d[n].So4 = DocSo(ref i); 
 else if (GapDong(s[i])) 
 q = 5; 
 break; 
 case 5: // Xong 1 doan 
 d[n].Dong = s[--i]; 
 dau = d[n].So1; 
 if (d[n].Toan1 == '+') 
 dau += d[n].So2; 
 else if (d[n].Toan1 == '*') 
 dau *= d[n].So2; 
 cuoi = d[n].So3; 
 if (d[n].Toan2 == '+') 
 cuoi += d[n].So4; 
Sáng tạo trong Thuật toán và Lập trình Tập I 
64 
 else if (d[n].Toan2 == '*') 
 cuoi *= d[n].So4; 
 d[n].Len = cuoi-dau; 
 Console.Write("\n Doan "+ 
 n + ". "); 
 d[n].Print(); q = 0; break; 
 } 
 } // endfor 
 return (++n); 
 } 
 static public bool GapSo(char c) 
 { return (c >= '0' && c <= '9'); } 
 static public bool GapMo(char c) 
 { return (c == '(' || c== '['); } 
 static public bool GapDong(char c) 
 { return (c == ')' || c== ']'); } 
 static public bool GapToan(char c) 
 { return (c == '+' || c== '*'); } 
 static public int DocSo(ref int i) 
 { 
 int m = 0; 
 do 
 { m = m * 10 + s[i++] - '0'; 
 } while (GapSo(s[i])); 
 --i; 
 return m; 
 } 
 static public void Printd() 
 { for (int i = 0;i < n; ++i) d[i].Print(); } 
 static public void Ghi() 
 { 
 StreamWriter g = File.CreateText(gn); 
 for (int i = 0; i < n; ++i) d[i].FWrite(g); 
 g.Close(); 
 } 
 static public void QSort(Doan[] d,int s, int e) 
 { 
 int i = s, j = e, m = d[(i+j)/2].Len; 
 Doan t; 
 while (i <= j) 
 { 
 while (d[i].Len < m) ++i; 
 while (d[j].Len > m) --j; 
 if (i <= j) 
 { 
 t = d[i]; d[i] = d[j]; d[j] = t; 
 ++i; --j; 
 } 
 } 
 if (s < j) QSort(d,s,i); 
 if (i < e) QSort(d,i,e); 
 } 
 } // SapDoan 
Sáng tạo trong Thuật toán và Lập trình Tập I 
65 
 public class Doan 
 { 
 public char Mo; 
 public char Dong; 
 public int So1; 
 public int So2; 
 public int So3; 
 public int So4; 
 public char Toan1; 
 public char Toan2; 
 public int Len; 
 public Doan() 
 { 
 Mo = ''; 
 So1 = So2 = So3 = So4 = 0; 
 Toan1 = Toan2 = '#'; 
 Len = 0; 
 } 
 public void FWrite(StreamWriter g) 
 { 
 g.Write(Mo.ToString()); 
 if (Toan1 != '#') 
 g.Write(So1 + Toan1.ToString() + So2); 
 else g.Write(So1); 
 g.Write(","); 
 if (Toan2 != '#') 
 g.Write(So3 + Toan2.ToString() + So4); 
 else g.Write(So3); 
 g.WriteLine(Dong.ToString()); 
 } 
 public void Print() 
 { 
 Console.Write(Mo.ToString()); 
 if(Toan1!='#') 
 Console.Write(So1+Toan1.ToString()+So2); 
 else Console.Write(So1); 
 Console.Write(","); 
 if(Toan2!='#') 
 Console.Write(So3+Toan2.ToString()+So4); 
 else Console.Write(So3); 
 Console.WriteLine(Dong.ToString()+ 
 " Len = "+Len); 
 } // Print 
 } // Doan 
 } // SangTao1