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!
Wednesday, December 25, 2013



Sắp đoạn

               Trong một tệp văn bản chứa những đoạn cắt ra từ một trục số. Mỗi đoạn có dạng <d, c> trong đó "<" có thể là một trong hai kí tự ( hoặc [, > có thể là một trong hai kí tự ) hoặc], d và c là các biểu thức dạng x hoặc x + y hoặc x*y với x và y là những số tự nhiên. Ta luôn có d £ c. Chiều dài của đoạn <d, c> là hiệu c - d. Hãy sắp xếp các đoạn tăng theo chiều dài và ghi chúng vào một tệp văn bản theo đúng dạng thức đọc được của mỗi đoạn. Có thể thêm, bớt một số dấu cách trong và ngoài các đoạn. Trên mỗi dòng của tệp luôn luôn chứa trọn một số đoạn.
Thí dụ cho dữ liệu vào trong file input “Doan.inp” là:
[2+1,7) (4,4*3) (5,6]
Sau khi sắp ta được kết quả sau trong file output “Doan.out”:
(5,6] [2+1,7) (4,4*3)
Thuật toán
Ta mô tả cấu trúc của mỗi đoạn như sau:
mo  so1[toan1  so2] , so3[toan2  so4]
trong đó:
s         mo là một trong hai dấu mở ngoặc: ( hoặc [.
s         so1, so2, so3 và so4 là các số tự nhiên xuất hiện trong thành phần của đoạn.
s         toan1 và toan2 là dấu các phép toán (+, *), nếu có trong thành phần của đoạn.
s         dong là một trong hai dấu đóng ngoặc: ) hoặc].
Trong mô tả trên, chúng ta sử dụng kí pháp [*] để chỉ ra thành phần * có thể bỏ qua.
Nếu thành phần thứ i (i = 1..2) của đoạn không có dấu phép toán, thì cũng không có toán hạng thứ hai, tức là thành phần đó có dạng là một số tự nhiên thì ta đặt toan[i] = BL (dấu cách).
       Nếu số thứ i không xuất hiện trong đoạn, ta đặt so[i] = 0.
Thí dụ:
Đoạn
mo
so1
Toan1
so2
so3
Toan2
so4
dong
[2+10,7*6)
[
2
+
10
7
*
6
)
[2+10,7)
[
2
+
10
7
BL
0
)
(2,7+5]
(
2
BL
0
7
+
5
]
Ngoài ra ta thêm một thành phần len để xác định chiều dài của đoạn. len của mỗi đoạn được tính theo công thức sau
len = TriCuoi-TriDau
TriCuoi = so3 Toan2 so4, nếu Toan2 là dấu '+' hoặc '*' và
TriCuoi = so3, nếu Toan2 = BL.
Tương tự,
TriDau = so1 Toan1 so2, nếu Toan1 là dấu '+' hoặc '*' và
TriDau = so1, nếu Toan1 = BL.
Ta sử dụng cấu trúc bản ghi để biểu diễn dữ liệu cho mỗi đoạn:
type
MangSo = array[1..4] of integer; {4 toan hang}
MangToan = array[1..2] of char; {2 toan tu +,*}
KieuDoan = record
              mo: char;
              dong: char;
              so: MangSo;
              Toan: MangToan;
              len: integer;
            end;
Các đoạn đọc được sẽ được ghi dần vào mảng a với biến đếm số phần tử n:
type MangDoan = array[0..1000] of KieuDoan;
var a: MangDoan; n: integer;
Khi đó thủ tục tính chiều dài len của mỗi đoạn sẽ được cài đặt như sau:
procedure LenSeg(i: integer);
var dau, cuoi: integer;
begin
  with a[i] do
   begin
    dau := so[1];
    if Toan[1]='+' then dau := dau+so[2]
    else if Toan[1]='*' then dau:=dau*so[2];
          cuoi:=so[3];
    if Toan[2]='+' then cuoi:=cuoi+so[2]
    else if Toan[2]='*' then cuoi:=cuoi*so[2];
   end;
   len := cuoi-dau;
end;
Cấu trúc  with x do T cho phép ta thực hiện thao tác T trên các thành phần của bản ghi x  mà không phải viết lại phần tiếp đầu x.
Để đọc các đoạn từ tệp ta sử dụng một máy trạng thái như sau. Hãy tưởng tượng mắt bạn bị bịt kín, do đó bạn phải dùng tay để nhận biết từng kí tự trong tệp văn bản. Mỗi lần bạn sờ một kí tự c nào đó rồi dựa vào kí tự đó bạn xác định các thủ tục cần thực hiện để nhận biết từng đối tượng. Muốn vậy ta sử dụng một biến gọi là biến trạng thái q với mục đích ghi nhận các tình huống đã gặp và trên cơ sở đó xác định các thao tác cần thiết. Gọi q là biến trạng thái. Trong quá trình đọc và xử lí tệp input ta có thể gặp năm trạng thái như sau:
q = 0: Trạng thái dò tìm đầu đoạn: Nếu gặp kí tự mở đầu một đoạn, cụ thể là nếu gặp kí tự c = '(' hoặc c = '[' thì cần tạo một đoạn mới như sau:
-                   Tăng chỉ dẫn ghi nhận đoạn mới: n := n + 1;
-                   Ghi nhận kí tự mở đầu đoạn: a[n].mo:= c;
-                   Khởi trị mảng số: a[n].so := (0, 0, 0, 0);
-                   Khởi trị mảng dấu các phép toán: a[n].Toan:= (BL, BL);
-                   Chuyển qua trạng thái q := 1 là trạng thái tìm đọc so[1].
0: if c in['(','['] then
         begin
n:=n+1; a[n].mo:=c;
a[n].so:=KhoiTriSo;
a[n].Toan:=KhoiTriToan;
q:= 1;
         end;
Các biến KhoiTriSoKhoiTriToan được khai báo và gán trị khởi đầu như sau:
const
         KhoiTriSo: MangSo = (0,0,0,0);
         KhoiTriToan: MangToan = (BL,BL);
q = 1: Trạng thái tìm đọc số thứ nhất, so[1]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[1], nếu gặp dấu phép toán thì ta hiểu là thành phần thứ nhất của đoạn là một biểu thức dạng:
so[1] Toan[1] so[2]
Ta ghi nhận dấu phép toán vào trường Toan[1] và chuyển qua trạng thái q = 2 để đọc số thứ hai. Nếu gặp dấu phẩy (,) là dấu ngăn giữa hai thành phần của đoạn ta chuyển qua trạng thái q = 3 để đọc số đầu tiên của thành phần thứ hai, tức là đọc so[3].
1: if c in ChuSo then DocSo(n,1)
else if c in PhepToan then
begin a[n].Toan[1]:=c; q:=2; end
else if c=',' then q:=3;
Thủ tục DocSo(i,j) nhận thêm 1 chữ số để ghép vào biếna[i].so[j].
q = 2: Đọc số thứ hai, so[2]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[2],nếu gặp dấu phẩy là dấu ngăn giữa hai thành phần của đoạn ta chuyển qua trạng thái q = 3 để đọc số đầu tiên của thành phần thứ hai, tức là đọc so[3].
       2: if c in ChuSo then DocSo(n,2)
else if c =',' then q:=3;
q = 3: Đọc số thứ ba, so[3]: Ở trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[3], nếu gặp dấu phép toán thì ta hiểu là thành phần thứ hai của đoạn là một biểu thức dạng:
so[3] Toan[2] so[4]
Ta ghi nhận dấu phép toán vào trường Toan[2] và chuyển qua trạng thái q = 4 để đọc số thứ tư, so[4], nếu gặp kí tự c = ')' hoặc c = ']' thì ta hiểu là đã kết thúc một đoạn, ta gọi thủ tục KetDoan để thực hiện các thao tác sau:
-     Ghi nhận kí tự đóng đoạn: a[n].dong:= c.
-     Tính chiều dài của đoạn: LenSeg(n);
-     Chuyển qua trạng thái q = 0 để tiếp tục với đoạn tiếp theo, nếu còn.
procedure KetDoan;
begin
a[n].dong:=c; LenSeg(n); q:=0;
end;
Đoạn chương trình thể hiện trạng thái q = 3 khi đó sẽ như sau:
3: if c in ChuSo then DocSo(n,3)
   else if c in PhepToan then
    begin a[n].Toan[2]:=c; q:=4 end
   else if c in[')',']'] then KetDoan;
q = 4: Đọc số thứ tư, so[4]: trạng thái này, nếu gặp chữ số thì ta ghép thêm chữ số đó vào so[4], nếu gặp kí tự c = ')' hoặc c = ']' thì ta hiểu là đã kết thúc một đoạn, ta gọi thủ tục KetDoan.
4: if c in ChuSo then DocSo(n,4)
   else if c in[')',']'] then KetDoan;
Đọc tệp xong ta dùng thủ tục qsort sắp các đoạn tăng dần theo chiều dài. Sau khi sắp ta ghi các đoạn vào tệp gntheo các trường.
(*  Pascal  *)
{$B-}
program Segments;
uses crt;
const
      fn = 'DOAN.INP'; {Tep input}
      gn = 'DOAN.OUT';{Tep output}
      MN = 1000; {So luong toi da cac doan}
      BL = #32;{Dau cach}
      ChuSo = ['0'..'9'];
      PhepToan = ['+','*'];
type
      MangSo = array[1..4] of integer;
      MangToan = array[1..2] of char;
      KieuDoan = record
                        mo: char; {dau mo ngoac}
                        dong: char; {dau dong ngoac}
                        so: MangSo; {4 so trong doan}
                        Toan: MangToan; {2 phep toan}
                        len: integer; {chieu dai doan}
                  end;
      MangDoan = array[0..MN] of KieuDoan;
const
      KhoiTriSo: MangSo = (0,0,0,0);
      KhoiTriToan: MangToan = (BL,BL);
var
      f,g:text;
      a: MangDoan;
      c: char;{ky tu dang xet}
      n: integer;{chi so doan dang xet}
      q: integer;{bien trang thai}
(*---------------------------------
Cac trang thai q = 0: do tim dau doan
1: doc so[1]
2: doc so[2]
3: doc so[3]
4: doc so[4]
-----------------------------------*)
procedure LenSeg(i: integer); tự viết
procedure KetDoan; tự viết
(*-----------------------------------------
   Them 1 chu so vao so thu j cua doan i
------------------------------------------*)
procedure DocSo(i,j: integer);
begin
       a[i].so[j]:=a[i].so[j]*10+(ord(c)-ord('0'))
end;
(*--------------------------------------
            Doc cac doan
---------------------------------------*)
procedure doc;
begin
      assign(f,fn); reset(f);
      q:=0; n:=0;
      while not eof(f) do
      begin
         read(f,c);
         case q of
         0: if c in['(','['] then                                 begin
              n:=n+1; a[n].mo:=c;
              a[n].so:=KhoiTriSo;
              a[n].Toan:=KhoiTriToan;
              q:=1;
            end;
         1: if c in ChuSo then DocSo(n,1)
            else if c in PhepToan then
            begin a[n].Toan[1]:=c; q:=2 end
            else if c=',' then q:=3;
         2: if c in ChuSo then DocSo(n,2)
            else if c =',' then q:=3;
         3: if c in ChuSo then DocSo(n,3)
            else if c in PhepToan then
                 begin
                   a[n].Toan[2]:=c; q:=4;
                 end
            else if c in[')',']'] then KetDoan;
         4: if c in ChuSo then DocSo(n,4)
             else if c in [')',']'] then KetDoan;
         end; { case }
      end; { while }
      close(f);
    end;
procedure qsort(d,c:integer);
var   i,j,m: integer;
      x: KieuDoan;
begin
i:=d; j:=c; m:=a[(i+j) div 2].len;
while i<=j do
begin
while a[i].len < m do i:=i+1;
while a[j].len > m do j:=j-1;
if i<=j then
begin
x:=a[i]; a[i]:=a[j]; a[j]:= x;
i:=i+1; j:=j-1;
end;
end;
if d < j then qsort(d,j);
if i < c then qsort(i,c);
end;
procedure Ghi;
var i: integer;
begin
assign(g,gn); rewrite(g);
for i:=1 to n do
with a[i] do
begin
           if Toan[1]<>BL then
              write(g,mo, so[1],Toan[1],so[2])
           else write(g,mo, so[1]);
           if Toan[2]<>BL then
       write(g,',',so[3],Toan[2],so[4],dong,BL)
     else write(g,',',so[3],dong,BL);
   { moi dong viet 10 doan }
if i mod 10 = 0 then writeln(g);
end;
close(g);
end;
BEGIN
Doc; qsort(1,n); Ghi;
END.

0 comments:

Post a Comment

Popular Posts