Sắp đoạn
Trong một tệp văn bản chứa những đoạn cắt ra
từ một trục số. Mỗi đoạn có dạng <d, c> trong đó "<" có thể
là một trong hai kí tự ( hoặc [, > có thể là một trong hai kí tự ) hoặc], d
và c là các biểu thức dạng x hoặc x + y hoặc x*y với x và y là những số tự
nhiên. Ta luôn có d £ c. Chiều dài của
đoạn <d, c> là hiệu c - d. Hãy sắp xếp các đoạn tăng theo chiều dài và
ghi chúng vào một tệp văn bản theo đúng dạng thức đọc được của mỗi đoạn. Có thể
thêm, bớt một số dấu cách trong và ngoài các đoạn. Trên mỗi dòng của tệp luôn
luôn chứa trọn một số đoạn.
Thí dụ cho dữ liệu vào trong file input
“Doan.inp” là:
[2+1,7) (4,4*3) (5,6]
Sau khi sắp ta được kết quả sau trong file
output “Doan.out”:
(5,6] [2+1,7) (4,4*3)
Thuật toán
Ta mô tả cấu trúc của mỗi đoạn như sau:
mo so1[toan1
so2] , so3[toan2 so4]
trong đó:
s
mo là một trong
hai dấu mở ngoặc: ( hoặc [.
s
so1, so2, so3 và
so4 là các số tự nhiên xuất hiện trong thành phần của đoạn.
s
toan1 và toan2 là
dấu các phép toán (+, *), nếu có trong thành phần của đoạn.
s
dong là một trong
hai dấu đóng ngoặc: ) hoặc].
Trong mô tả trên, chúng ta sử dụng kí pháp [*] để chỉ ra thành phần *
có thể bỏ qua.
Nếu thành phần thứ i (i = 1..2) của đoạn
không có dấu phép toán, thì cũng không có toán hạng thứ hai, tức là thành phần
đó có dạng là một số tự nhiên thì ta đặt toan[i] = BL (dấu cách).
Nếu số thứ i không xuất hiện trong đoạn, ta đặt so[i] = 0.
Thí dụ:
Đoạn
|
mo
|
so1
|
Toan1
|
so2
|
so3
|
Toan2
|
so4
|
dong
|
[2+10,7*6)
|
[
|
2
|
+
|
10
|
7
|
*
|
6
|
)
|
[2+10,7)
|
[
|
2
|
+
|
10
|
7
|
BL
|
0
|
)
|
(2,7+5]
|
(
|
2
|
BL
|
0
|
7
|
+
|
5
|
]
|
Ngoài ra ta thêm một thành phần len để xác định chiều dài của đoạn. len
của mỗi đoạn được tính theo công thức sau
len =
TriCuoi-TriDau
TriCuoi = so3 Toan2 so4, nếu Toan2 là dấu '+' hoặc '*' và
TriCuoi = so3,
nếu Toan2 = BL.
Tương tự,
TriDau = so1 Toan1 so2, nếu Toan1 là dấu '+' hoặc '*' và
TriDau = so1,
nếu Toan1 = BL.
Ta sử dụng cấu trúc bản ghi để
biểu diễn dữ liệu cho mỗi đoạn:
type
MangSo = array[1..4] of integer; {4 toan hang}
MangToan = array[1..2] of
char; {2 toan tu +,*}
KieuDoan = record
mo: char;
dong: char;
so: MangSo;
Toan: MangToan;
len: integer;
end;
Các đoạn đọc
được sẽ được ghi dần vào mảng a với biến đếm số phần tử n:
type MangDoan =
array[0..1000] of KieuDoan;
var a: MangDoan; n: integer;
Khi đó thủ tục tính chiều dài len của mỗi đoạn sẽ được cài đặt như sau:
procedure LenSeg(i:
integer);
var dau, cuoi: integer;
begin
with a[i] do
begin
dau := so[1];
if Toan[1]='+' then dau :=
dau+so[2]
else if Toan[1]='*' then dau:=dau*so[2];
cuoi:=so[3];
if Toan[2]='+'
then cuoi:=cuoi+so[2]
else if Toan[2]='*' then
cuoi:=cuoi*so[2];
end;
len := cuoi-dau;
end;
Cấu trúc with x do T cho phép ta thực hiện thao tác T trên các thành phần
của bản ghi x mà không phải viết lại phần tiếp đầu x.
Để đọc các đoạn từ tệp ta sử dụng một máy trạng thái như sau. Hãy tưởng tượng mắt bạn bị bịt kín, do
đó bạn phải dùng tay để nhận biết từng kí tự trong tệp văn bản. Mỗi lần bạn sờ
một kí tự c nào đó rồi dựa vào kí tự đó bạn xác định các thủ tục cần thực hiện
để nhận biết từng đối tượng. Muốn vậy ta sử dụng một biến gọi là biến trạng
thái q với mục đích ghi nhận các tình
huống đã gặp và trên cơ sở đó xác định các thao tác cần thiết. Gọi q là biến trạng thái. Trong quá trình
đọc và xử lí tệp input ta có thể gặp năm trạng thái như sau:
q = 0: Trạng
thái dò tìm đầu đoạn: Nếu gặp kí
tự mở đầu một đoạn, cụ thể là nếu gặp kí tự c = '(' hoặc c = '[' thì cần tạo một đoạn mới như sau:
-
Tăng chỉ dẫn ghi
nhận đoạn mới: n := n + 1;
-
Ghi nhận kí tự mở đầu đoạn: a[n].mo:= c;
-
Khởi trị mảng số:
a[n].so := (0, 0, 0, 0);
-
Khởi trị mảng dấu
các phép toán: a[n].Toan:= (BL, BL);
-
Chuyển qua trạng
thái q := 1 là
trạng thái tìm đọc so[1].
0: if c in['(','[']
then
begin
n:=n+1; a[n].mo:=c;
a[n].so:=KhoiTriSo;
a[n].Toan:=KhoiTriToan;
q:= 1;
end;
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:
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}
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;
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])
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.
Không có nhận xét nào:
Đăng nhận xét