Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Monday, January 13, 2014



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).
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ếux £ 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, d2d3. 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.
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


0 comments:

Post a Comment

Popular Posts