Quay quay...

Quay quay...
Miền nhớ và tốc độ
Một số bài toán tin mới xem tưởng như khó có thể giảm được chi phí miền nhớ đồng thời tăng tốc độ tính toán. Hình như trong lập trình cũng cũng thống trị nguyên lý lợi bao nhiêu lần về không gian nhớ thì thiệt bấy nhiêu lần về tốc độ tính toán. Thật ra thì không phải như vậy. Về nguyên tắc mà nói, quản lý ít bộ nhớ thì chương trình có thể thực hiện nhanh hơn. Dĩ nhiên bạn có thể phản đối nhận định này bằng một phản ví dụ. Chẳng hạn, bạn có thể viết một chương trình chỉ sử dụng có một biến nhưng có thể thực hiện vô hạn lần hoặc thực  hiện lâu bao nhiêu tuỳ ý. Chúng ta đang bàn về một việc khác cụ thể là, cùng xử lý một khối lượng công việc, nếu ta xin cấp phát ít miền nhớ trong một lần thực hiện thì thời gian thực hiện có thể giảm đi. Trong đời thường xu thế trên được chúng ta quan tâm và áp dụng khá thường xuyên. Này nhé, nếu bạn phải bọc bìa cho một chồng vở, chẳng hạn 100 quyển. Bạn chọn phương án nào trong hai phương án sau đây:
- Phương án thứ nhất: Trải 100 quyển vở trên 50 cái bàn đặt trong một hội trường rộng mênh mông rồi lấy từng quyển vở để bọc bìa.
Dĩ nhiên là bạn chọn phương án thứ hai. Xem như vậy thì việc tiết kiệm không gian trong quá trình xử lý có thể tăng tốc độ tính toán. Chúng ta sẽ minh họa nhận định này thông qua một số ví dụ.
Bạn có biết tiết kiệm không
Bài toán 1 (Quay xâu) Cho một xâu s gồm n ký tự. Giá trị n có thể đạt tới 1000. Mỗi lần ta dịch chuyển vòng quanh xâu s sang phải 1 vị trí, ký tự cuối cùng được mang về đầu trái. Sau n lần dịch chuyển ta sẽ thu được n xâu, xâu thứ n chính là xâu đầu tiên. Hãy sắp tăng theo trật tự từ điển n xâu thu được.
Dữ liệu vào được ghi trong tệp văn bản XAU. INP, dòng đầu tiên là giá trị n. Dòng thứ hai là bản thân xâu s được viết dưới dạng dãy chữ cái in hoa A..Z.
Dữ liệu ra ghi trong tệp văn bản XAUQUAY.OUT.
Thí dụ, với n=8 và s="TIETKIEM" ta có



Sau khi quay ta sẽ thu được các xâu như trong bảng 1.
Sau khi sắp tăng ta sẽ thu được tệp XAUQUAY.OUT như trong bảng 2.


Bài giải
Gọi chiều dài xâu mẫu s là n. Ta hãy mường tượng các phần tử của s ghi trên mặt một chiếc đồng hồ. Dễ thấy, với mỗi giá trị i=1..n, bằng cách duyệt vòng tròn trên xâu mẫu bằng n phần tử, bắt đầu từ ký tự thứ i, ta có thể nhận được một xâu gồm n phần tử bắt đầu từ phần tử thứ i của xâu mẫu. Thí dụ, với sâu mẫu s=’TIETKIEM’, (n=8), chọn i=3 ta bắt đầu từ phần tử thứ 3 duyệt về bên phải n vị trí theo vòng tròn sẽ thu được xâu ‘ETKIEMTI’. Ta gọi các xâu này là xâu thứ cấp. Từ nhận xét trên ta thấy có thể quản lý các xâu thứ cấp theo vị trí của phần tử đầu tiên trong xâu mẫu. Ta ký hiệu [i] là xâu có vị trí của phần tử đầu tiên trong xâu mẫu là i. Lưu ý rằng chiều dài của mọi xâu đều là n, tức là dài đúng bằng xâu mẫu. Theo thí dụ trên ta có [3]=’ETKIEMTI’. Như vậy, xâu [i] chính là xâu thứ cấp thu được từ xâu mẫu sau lần dịch chuyển thứ i. Vấn đề còn lại là sắp tăng các xâu thứ cấp [1], [2],...,[n] theo trật tự từ điển.
Ta dùng thủ tục sắp nhanh theo chỉ dẫn QSort để sắp các xâu. Thế nào là sắp theo chỉ dẫn? Thay vì truy nhập trực tiếp đến đối tượng cần sắp ta truy nhập đến chỉ dẫn dành cho đối tượng đó. Trước khi sắp ta thực hiện phép đặt chỉ dẫn để gán cho mỗi đối tượng một chỉ dẫn lấy trong khoảng 1..n. Ta có:
procedure SapChiDan;
var i: integer;
begin
for i:= 1 to n do
cd[i]:=i;
Qsort (1,n);
end;
Mảng cd trong thủ tục trên chứa chỉ dẫn của các xâu thứ cấp.
Để so sánh hai xâu [i] và [j] ta dùng hàm Sanh(i,j). Hàm này cho ra một trong ba giá trị sau:
0: nếu [i]=[j];
1: nếu [i]>[j];
-1: nếu [i]<[j];
Theo quy tắc từ điển, ta tìm cặp phần tử khác nhau đầu tiên của hai xâu. Nếu không