Tổ chức tính toán

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.