//
you're reading...
Bài tập huấn luyện

Sắp đoạn


Đề bài



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 trong đó ” 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 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 đó:
mo là một trong hai dấu mở ngoặc: ( hoặc [.
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.
toan1 và toan2 là dấu các phép toán (+, *), nếu có trong thành phần của đoạn.
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 KhoiTriSo KhoiTriToan đượ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ến a[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
gn theo 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}

Sáng tạo trong Thuật toán và Lập trình Tập I 60
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;

Sáng tạo trong Thuật toán và Lập trình Tập I 61
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 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])

Sáng tạo trong Thuật toán và Lập trình Tập I 62
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.
// C#
using System;
using System.IO;
using System.Collections;
namespace SangTao1
{
class SapDoan
{
static public string fn = “Doan.inp”;
static public string gn = “Doan.out”;
static public string s; // du lieu vao
static public Doan[] d = new Doan[5000]; // cac doan
static public int n = 0; // so luong doan
static public char Ket = ‘#’;
static void Main(string[] args)
{
s = File.ReadAllText(fn) + Ket.ToString();
Console.WriteLine(“\n Du lieu ” +
“truoc khi xu li:\n ” + s);
n = DocDoan();
Console.WriteLine(“\n Tong cong ” + n + ” Doan”);
Console.WriteLine(n); Printd();
QSort(d, 0, n-1);
Console.WriteLine(“\n Da sap: “); Printd();
Ghi(); XemLai();
Console.WriteLine(“\n Fini “);
Console.ReadLine();
}
static public void XemLai()
{
Console.WriteLine(“\n Kiem tra lai:\n”);
Console.WriteLine(“\n Input:\n” +
File.ReadAllText(fn));
Console.WriteLine(“\n Output:\n” +
File.ReadAllText(gn));
}
static public int DocDoan()
{

Sáng tạo trong Thuật toán và Lập trình Tập I 63
int n = -1;
int q = 0; // trang thai
int i = 0; // bien tro trong s
int dau, cuoi;
for (; s[i] != Ket; ++i)
{
switch(q)
{
case 0: // Tim dau doan
if (GapMo(s[i]))
{
++n; d[n] = new Doan();
d[n].Mo = s[i]; q = 1;
}
break;
case 1: // Doc so1
if (GapSo(s[i]))
d[n].So1 = DocSo(ref i);
else if (GapToan(s[i]))
{d[n].Toan1 = s[i]; q = 2;}
else if (s[i]==’,’) q = 3;
break;
case 2: // Doc so2
if (GapSo(s[i]))
d[n].So2 = DocSo(ref i);
else if (s[i]==’,’) q = 3;
break;
case 3: // Doc so3
if (GapSo(s[i]))
d[n].So3 = DocSo(ref i);
else if (GapToan(s[i]))
{
d[n].Toan2 = s[i]; q = 4;
}
else if (GapDong(s[i]))
q = 5;
break;
case 4: // Doc so4
if (GapSo(s[i]))
d[n].So4 = DocSo(ref i);
else if (GapDong(s[i]))
q = 5;
break;
case 5: // Xong 1 doan
d[n].Dong = s[–i];
dau = d[n].So1;
if (d[n].Toan1 == ‘+’)
dau += d[n].So2;
else if (d[n].Toan1 == ‘*’)
dau *= d[n].So2;
cuoi = d[n].So3;
if (d[n].Toan2 == ‘+’)
cuoi += d[n].So4;

Sáng tạo trong Thuật toán và Lập trình Tập I 64
else if (d[n].Toan2 == ‘*’)
cuoi *= d[n].So4;
d[n].Len = cuoi-dau;
Console.Write(“\n Doan “+
n + “. “);
d[n].Print(); q = 0; break;
}
} // endfor
return (++n);
}
static public bool GapSo(char c)
{ return (c >= ‘0’ && c <= '9'); }
static public bool GapMo(char c)
{ return (c == '(' || c== '['); }
static public bool GapDong(char c)
{ return (c == ')' || c== ']'); }
static public bool GapToan(char c)
{ return (c == '+' || c== '*'); }
static public int DocSo(ref int i)
{
int m = 0;
do
{ m = m * 10 + s[i++] – '0';
} while (GapSo(s[i]));
–i;
return m;
}
static public void Printd()
{ for (int i = 0;i < n; ++i) d[i].Print(); }
static public void Ghi()
{
StreamWriter g = File.CreateText(gn);
for (int i = 0; i < n; ++i) d[i].FWrite(g);
g.Close();
}
static public void QSort(Doan[] d,int s, int e)
{
int i = s, j = e, m = d[(i+j)/2].Len;
Doan t;
while (i <= j)
{
while (d[i].Len m) –j;
if (i <= j)
{
t = d[i]; d[i] = d[j]; d[j] = t;
++i; –j;
}
}
if (s < j) QSort(d,s,i);
if (i < e) QSort(d,i,e);
}
} // SapDoan

Sáng tạo trong Thuật toán và Lập trình Tập I 65
public class Doan
{
public char Mo;
public char Dong;
public int So1;
public int So2;
public int So3;
public int So4;
public char Toan1;
public char Toan2;
public int Len;
public Doan()
{
Mo = ”;
So1 = So2 = So3 = So4 = 0;
Toan1 = Toan2 = ‘#’;
Len = 0;
}
public void FWrite(StreamWriter g)
{
g.Write(Mo.ToString());
if (Toan1 != ‘#’)
g.Write(So1 + Toan1.ToString() + So2);
else g.Write(So1);
g.Write(“,”);
if (Toan2 != ‘#’)
g.Write(So3 + Toan2.ToString() + So4);
else g.Write(So3);
g.WriteLine(Dong.ToString());
}
public void Print()
{
Console.Write(Mo.ToString());
if(Toan1!=’#’)
Console.Write(So1+Toan1.ToString()+So2);
else Console.Write(So1);
Console.Write(“,”);
if(Toan2!=’#’)
Console.Write(So3+Toan2.ToString()+So4);
else Console.Write(So3);
Console.WriteLine(Dong.ToString()+
” Len = “+Len);
} // Print
} // Doan
} // SangTao1

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: