Tổ chức tính toán
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (102.29 KB, 9 trang )
Tổ chức tính toán
Nguyễn Xuân Huy
Bài tập 1: Chiều dàiđủ của một xâu gọn s là số kí tự trong dạng khai triển của xâu đó. Thí
dụ chiềudài đủ của xâu gọn s=A2(C2A)3(AB4)0D3 là 14. Viết thủ tục tính chiều dài đủ
củamột xâu gọn cho trước.
Bài giải:
Trướchết ta gọi thủ tục XauGon để tạo ra bảng phục vụ cho việc tổ chức tính toán.Với thí
dụ đã cho ta thu được bảng như trong Hình 1.
Bây giờ ta chỉ việc
thực hiệnpha 2
bằng cách sửa lại
thủ tục ThucHien
như sau. Thay vì in
các ký tự của
dạngkhai triển ta
đếm số kí tự được
in và tích luỹ trong
biến d. Giá trị cuối
cùngcủa d sẽ chính
là chiều dài đủ của
xâu gọn. Như vậy ta sẽ thay các lệnh ghi tệpwrite(g,Kt[i]) trong thủ tục ThucHien bằng
lệnh inc(d). Vì các lệnh ghi tệpđược đặt trong vòng for cho nên ta chỉ thay dòng lệnh
for j := 1 to Lap[i] do
write(g,Kt[i]);
bằng dòng lệnh
d := d + Lap[i];
Thủ tục mới có tên là Len.
Procedure Len;
Số hiệu
dòng (n)
Kí tự (kt) Số lần lặp
(lap)
Lặp từ
dòng (tu)
1 A 2
2 C 2
3 A 1
4 * 3 2
5 D 3
Hình 1. Bảng hoàn chỉnh ứng với xâu gọn
s = A2(C2A)3(AB4)0D3.
Var i,j: byte;
Begin
d := 0;
for i := 1 to n do Dem[i] := 0;
i := 1;
while i <= n do
begin
if Kt[i] = '*' then
begin
inc(Dem[i]);
if Dem[i] < Lap[i] then i := Tu[i]
else
begin
Dem[i] := 0;
inc(i);
end;
end
else
begin
d := d + Lap[i];
inc(i);
end;
end;
End;
Để bạn đọc tiện theo dõichúng tôi viết lại các thủ tục của pha 1.
Const
DauTu = ['(','A'..'Z','á..'z'];
ChuSo = ['0'..'9'];
MN = 250;
Var
Kt: array[0..MN] of char;
Tu: array[0..MN] of byte;
Lap: array[0..MN] of word;
s: string;
ii,n: byte;
d: longint;
Procedure Loi;
Begin
writeln('Loi cu phap');
readln;
halt;
End;
Function DocSo: word;
Var m: word;
Begin
DocSo := 1;
if not (s[ii] in ChuSo) then exit;
m := 0;
while s[ii] in ChuSo do
begin
m := m*10 + ord(s[ii]) - ord('0');
inc(ii);
end;
DocSo := m;
End;
Procedure XauDon;
Begin
inc(n);
Kt[n] := s[ii];
inc(ii);
Lap[n] := DocSo;
if Lap[n] = 0 then dec(n);
End;
Procedure XauGon;
Var g: byte;
Begin
while s[ii] in DauTu do
if s[ii] = '(' then
begin
g := n;
inc(ii);
XauGon;
if s[ii] <> ')' then Loi;
inc(ii);
inc(n);
Kt[n] := '*';
Tu[n] := g+1;
Lap[n] := DocSo;
if Lap[n] = 0 then n := g
else if Lap[n] = 1 then dec(n);
end
else XauDon;
End;
Procedure TinhLen;
Begin
s := s + #;
ii := 0;
n := 0;
