Chuỗi hạt - gia sư tin học
Trong
một tệp văn bản tên CHUOI.DAT có biểu diễn
một chuỗi hạt, mỗi hạt có thể nhận một trong số các màu mã số từ 1 đến 30.
Lập trình thực hiện các việc sau:
a) Đọc chuỗi hạt từ tệp vào mảng
nguyên dương a.
b) Hiển thị số màu có trong
chuỗi.
c) Tìm một điểm để cắt chuỗi rồi
căng thẳng ra sao cho tổng số các hạt cùng màu ở hai đầu là lớn nhất.
Chuỗi được thể hiện trong tệp dưới dạng hình
thoi, dòng đầu tiên và dòng cuối cùng mỗi dòng có một hạt.
Mỗi dòng còn lại có hai hạt (xem
hình).
Các hạt của chuỗi được đánh số
bắt đầu từ hạt trên cùng và theo chiều kim đồng hồ.
|
CHUOI.DAT
|
Trong thí dụ này, các thông báo trên màn hình sẽ là:
Số màu trong chuỗi: 5
Cắt giữa hạt thứ 7 và thứ 8, tổng số lớn nhất là 7.
|
|
4
4 7
1 4
5 8
5 8
5 8
8
|
|
|
Chuỗi hạt
|
Thuật toán
Khung chương trình được phác thảo như sau:
procedure run;
var i:
integer;
begin
Đọc dữ liệu;
Tính và thông
bỏo số màu
Xử lý để tìm điểm cắt;
Thông báo điểm cắt
end;
Để đọc chuỗi từ tệp vào mảng a ta dùng thêm một mảng phụ b có cùng cấu trúc như mảng a. Mảng b sẽ chứa các hạt ở nửa trái chuỗi, trong khi mảng a chứa các hạt ở nửa phải. Lúc đầu, do
chỉ có 1 hạt tại dòng đầu tiên nên ta đọc hạt đó vào a[1]. Tại các dòng tiếp theo, mỗi dòng n = 2,… ta đọc số hiệu màu của 2 hạt, hạt trái vào b[n]
và hạt phải vào a[n]. Dấu hiệu kết thúc chuỗi là 1 hạt.
Hạt này được đọc vào b[n]. Ta để ý rằng, theo cấu trúc của
chuỗi hạt thì số hạt trong chuỗi luôn luôn là một số chẵn.
Thí dụ dưới đây minh hoạ giai
đoạn đầu của thủ tục đọc dữ liệu. Khi kết thúc giai đoạn này ta thu được n = 7 và nửa phải của chuỗi hạt (số có
gạch dưới) được ghi trong a[1..(n – 1)], nửa trái được ghi trong b[2..n]. Tổng số hạt trong chuỗi khi đó sẽ là
2*(n – 1).
2*(n – 1).
|
CHUOI.DAT
|
|
|
4
4
7
1
4
5
8
5
8
5
8
8
|
4 a[1]
b[2] 4 7
a[2]
b[3] 1 4
a[3]
b[4] 5 8
a[4]
b[5] 5 8
a[5]
b[6] 5 8
a[6]
b[7] 8
|
|
|
Đọc dữ liệu của chuỗi hạt vào hai mảng a và b
a[1..6]=(4,7,4,8,8,8)
b[2..7]=(4,1,5,5,5,8)
|
Sau khi đọc xong ta duyệt ngược
mảng b để nối nửa trái của chuỗi hạt
vào sau nửa phải a.
(*-----------------------------------
Doc du lieu tu file CHUOI.DAT
ghi vao mang a
------------------------------------*)
procedure Doc;
var
f: text;
i: integer;
begin
assign(f,fn); reset(f);
n := 1; read(f,a[n]);
while NOT
SeekEof(f) do
begin
inc(n); read(f,b[n]);
if NOT
SeekEof(f) then read(f,a[n]);
end;
{noi nua trai
b (duyet nguoc) vao nua phai a}
for i:= 0 to
n-2 do a[n+i]:= b[n-i];
n := 2*(n-1); close(f);
end;
Theo thí dụ trên, sau khi nối b[2..n] vào sau a[1..(n – 1)] ta thu được
a[1..12] = (4,7,4,8,8,8,8,5,5,5,1,4)
Để đếm số màu trong chuỗi ta
dùng phương pháp đánh dấu. Ta sử dụng mảng b với ý nghĩa như sau:
-
b[i] = 0: màu i chưa
xuất hiện trong chuỗi hạt;
-
b[i] = 1: màu i đã
xuất hiện trong chuỗi hạt.
Lần lượt duyệt các phần tử a[i], i = 1..n trong chuỗi. Nếu màu a[i] chưa xuất hiện ta tăng trị của con đếm màu d thêm 1, inc(d) và đánh dấu màu
a[i] đó
trong b bằng
phép gán b[a[i]] := 1.
(*-----------------------------------
Dem so mau trong chuoi
------------------------------------*)
function Dem: integer;
var i,d: integer;
begin
d := 0;
fillchar(b,sizeof(b),0);
for i := 1 to
n do
if b[a[i]] = 0
then
begin
inc(d);
b[a[i]] := 1;
end;
Dem := d;
end;
Để tìm điểm cắt với tổng chiều dài hai đầu lớn nhất ta thực hiện như
sau. Trước hết ta định nghĩa điểm đổi màu trên chuỗi hạt là hạt (chỉ số) mà màu
của nó khác với màu của hạt đứng sát nó (sát phải hay sát trái, tùy theo chiều
duyệt xuôi từ trái qua phải hay duyệt ngược từ phải qua trái). Ta cũng định
nghĩa một đoạn trong chuỗi hạt là một dãy liên tiếp các hạt cùng màu với chiều
dài tối đa. Mỗi đoạn đều có điểm đầu và điểm cuối. Vì điểm cuối của mỗi đoạn
chỉ lệch 1 đơn vị so với điểm đầu của đoạn tiếp theo, cho nên với mỗi đoạn ta
chỉ cần quản lí một trong hai điểm: điểm đầu hoặc điểm cuối của đoạn đó. Ta
chọn điểm đầu. Kĩ thuật này được gọi là quản lí theo đoạn.
Thí dụ,
chuỗi hạt a với n = 12 hạt màu như
trong thí dụ đã cho:
a[1..12] = (4,7,4,8,8,8,8,5,5,5,1,4)
mới xem tưởng như được tạo từ bảy đoạn là:
a[1..1] = (4)
a[2..2] = (7)
a[3..3] = (4)
a[4..7] = (8,8,8,8)
a[8..10] = (5,5,5)
a[11..11] = (1)
a[12..12] = (4)
Tuy nhiên, do chuỗi là một dãy
hạt khép kín và các hạt được bố trí theo chiều quay của kim đồng hồ nên thực
chất a chỉ gồm sáu đoạn:
a[2..2] = (7)
a[3..3] = (4)
a[4..7] = (8,8,8,8)
a[8..10] = (5,5,5)
a[11..11] = (1)
a[12..1] = (4,4)
trong đó a[x..y] cho biết chỉ số đầu đoạn là x, cuối đoạn là y.
Nếu
x £ y thì các hạt trong đoạn được duyệt theo chiều kim đồng hồ
từ chỉ số nhỏ đến chỉ số lớn, ngược lại, nếu x > y thì các hạt trong đoạn cũng được duyệt theo chiều kim
đồng hồ từ chỉ số lớn đến chỉ số nhỏ. Các phần tử đầu mỗi đoạn được gạch chân.
Có thể có những đoạn chứa cả hạt cuối cùng a[n] và hạt đầu tiên a[1] nên ta cần xét riêng trường hợp này.
Đoạn trình dưới đây xác định các
điểm đầu của mỗi đoạn và ghi vào mảng b[1..sdc]. Giá trị sdc cho biết số lượng các đoạn.
sdc
:= 0;
if a[1]<>a[n] then
begin
sdc := 1;
b[sdc] := 1;
end;
for i := 1 to n-1 do
if a[i] <> a[i+1] then
begin
inc(sdc);
b[sdc] := i+1;
end;
Gọi điểm đầu của ba đoạn liên tiếp là d1, d2 và d3. Ta thấy,
nếu chọn điểm cắt sát trái hạt d2 thì
hiệu d3 - d1 chính là tổng số hạt
đồng màu tại hai đầu của chuỗi hạt được căng ra. Từ đó ta phác thảo được sơ đồ
cho thủ tục xuly để tìm điểm cắt DiemCat với chiều dài lớn nhất Lmax như sau:
Khởi trị;
Duyệt từ bộ ba điểm đầu của
ba đoạn liên tiếp d1, d2, d3
Nếu d3-d1 > Lmax thì
Đặt lại Lmax := d3-d1
Đặt lại DiemCat := d2
xong nếu
Giả sử chuỗi hạt có m đoạn. Theo
phương thức duyệt chuỗi hạt vòng tròn theo chiều kim đồng hồ, ta cần xét riêng
hai đoạn đầu và cuối, cụ thể là:
s
Với đoạn 1 ta phải xét hai đoạn đứng trước và sau
đoạn đó là đoạn m và đoạn 2.
s
Với đoạn m ta
phải xét hai đoạn đứng trước và sau đoạn đó là đoạn
m – 1 và đoạn 1.
m – 1 và đoạn 1.
Ta xử lí riêng hai đoạn này ở bước khởi trị như sau:
{xu li diem cat dau}
Lmax := (b[1]+(n-b[sdc]))+(b[2]-b[1]);
DiemCat := b[1];
{xu li diem cat cuoi}
if (b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]) >
Lmax then
begin
Lmax := (b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]);
DiemCat := b[sdc];
end;
Phương án
cuối cùng của thủ tục xuly sẽ như sau:
procedure xuly;
var i,sdc: integer;
{sdc: so diem cat}
begin
sdc:=0;
if a[1]<>a[n] then
begin
sdc := 1;
b[sdc]:= 1;
end;
for i:=1 to n-1 do
if a[i] <> a[i+1] then
begin
inc(sdc);
b[sdc] := i+1;
end;
if sdc=0 then
begin
DiemCat:=0;
Lmax:=n;
exit;
end;
{xu li diem cat dau}
Lmax := (b[1]+(n-b[sdc]))+(b[2]-b[1]);
DiemCat := b[1];
{xu li diem cat cuoi}
if (b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]) > Lmax then
begin
Lmax := (b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]);
DiemCat := b[sdc];
end;
{xu li cac diem cat giua}
for i:= 2 to sdc-1 do
if b[i+1]-b[i-1] >
Lmax then
begin
Lmax := b[i+1]-b[i-1];
DiemCat := b[i];
end;
end;
(* Pascal
*)
(*--------------------
CHUOI HAT
---------------------*)
program Chuoi;
{$B-}
uses crt;
const
MN = 500; {So luong hat
toi da trong chuoi}
MC = 30; {So luong mau}
fn = 'CHUOI.DAT';
BL = #32;
var
a,b,len: array[0..MN] of
byte;
n: integer; {So luong phan
tu thuc co trong chuoi hat}
DiemCat: integer; {diem
cat}
Lmax: integer; {Chieu dai
toi da}
(*-----------------------------------
Doc du lieu tu tep CHUOI.DAT ghi
vao mang a
------------------------------------*)
procedure Doc;
var
f: text;
i: integer;
begin
assign(f,fn);
reset(f);
n:= 1;
read(f,a[1]);
while not SeekEof(f)
do
begin
inc(n);
read(f,b[n]);
if not SeekEof(f) then read(f,a[n]);
end;
for i:=0 to n-2 do
a[n+i]:= b[n-i];
n:= 2*(n-1);
close(f);
end;
(*-------------------------------------
Hien thi chuoi tren man hinh
de kiem tra ket qua doc
--------------------------------------*)
procedure Xem;
var i: integer;
begin
writeln;
writeln('Tong so hat:
',n);
for i:= 1 to n do
write(a[i],bl);
end;
(*-----------------------------------
Dem so mau trong chuoi
------------------------------------*)
function Dem: integer;
var i,d: integer;
begin
d:=0;
fillchar(b,sizeof(b),0);
for i:= 1 to n do
if b[a[i]] = 0 then
begin
inc(d);
b[a[i]]:=1;
end;
Dem:= d;
end;
procedure xuly;
var i,sdc: integer; {sdc:
so diem cat}
begin
sdc:=0;
if a[1]<>a[n] then
begin
sdc:=1;
b[sdc]:=1;
end;
for i:=1 to n-1 do
if a[i] <> a[i+1] then
begin
inc(sdc);
b[sdc]:=i+1;
end;
if sdc=0 then
begin
DiemCat:=0;
Lmax:=n;
exit;
end;
{xu li diem cat dau}
Lmax:=
(b[1]+(n-b[sdc]))+(b[2]-b[1]);
DiemCat:=b[1];
{xu li diem cat cuoi}
if
(b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]) > Lmax
then
begin
Lmax:= (b[1]+(n-b[sdc]))+(b[sdc]-b[sdc-1]);
DiemCat:=b[sdc];
end;
{xu li cac diem cat
giua}
for i:=2 to sdc-1 do
if b[i+1]-b[i-1] >
Lmax then
begin
Lmax:= b[i+1]-b[i-1];
DiemCat:=b[i];
end;
end;
procedure run;
var i: integer;
begin
Doc; Xem; writeln;
writeln('So mau trong chuoi: ',Dem);
xuly;
writeln;
if DiemCat=0 then
writeln(' Chuoi dong
mau, cat tai diem tuy y')
else
begin
if DiemCat = 1 then i :=n
else
i:=DiemCat-1;
writeln('Cat giua hat ',i,
' va hat ',DiemCat);
end;
writeln(' Chieu dai
max: ',Lmax);
readln;
end;
BEGIN
run;
END.
|
Dữ
liệu kiểm thử CHUOI.DAT
|
Kết quả dự kiến
|
|
4
4 7
1 4
5 8
5 8
5 8
8
|
Cắt giữa hạt: 7 và 8
Chiều dài max: 7
|
Không có nhận xét nào:
Đăng nhận xét