Xin ý kiến về thuật toán

[quangtq]

Em gặp 1 bài như sau nhưng không nghĩ ra được thuật toán như nào. Mọi người giúp em, xin đa tạ. Có code càng tốt
Dãy ngoặc hợp lệ:
Một dãy dấu ngoặc hợp lệ là một dãy các ký tự '(' và ')' được định nghĩa như sau:
- Dãy rỗng (không có ký tự nào) là một dãy dấu ngoặc hợp lệ.
- Nếu A là một dãy dấu ngoặc hợp lệ thì (A) là dãy dấu ngoặc hợp lệ. Dấu ngoặc mở và dấu ngoặc đóng hai bên dãy A được gọi là tương ứng với nhau.
- Nếu A và B là hai dãy dấu ngoặc hợp lệ thì AB là dãy dấu ngoặc hợp lệ.
Ví dụ: ((()))()(()) là dãy dấu ngoặc hợp lệ, người ta viết vào sau mỗi dấu ngoặc mở một số là số dấu ngoặc (cả đóng và mở) nằm giữa trong cặp dấu ngoặc mở đó với dấu ngoặc đóng tương ứng:
Với dãy trên ta có: (4(2(0)))(0)(2(0))
Sau đó người ta lại xoá đi các dấu ngoặc (cả ngoặc đóng và mở)
Với ví dụ trên ta được: 4 2 0 0 2 0
Yêu cầu: Cho biết dãy số còn lại, hãy khôi phục lại dãy ngoặc ban đầu.
Dữ liệu vào: Được lấy từ file văn bản NGOAC.INP có cấu trúc như sau:
- Dòng thứ nhất: Ghi số nguyên dương n là số phần tử của dãy số còn lại (n<=255).
- Dòng thứ hai: Ghi lần lượt các số trong dãy.
Dữ liệu ra: Kết quả ghi vào file văn bản NGOAC.OUT gồm một dòng duy nhất là dãy dấu ngoặc khôi phục được.
Ví dụ :
NGOAC.INP
6
4 2 0 0 2 0
NGOAC.OUT
((()))()(())

NGOAC.INP
8
6 4 2 0 0 0 2 0
NGOAC.OUT (((())))()()(())

[quangtq]

Hix. Ko ai giúp em à? (

[hoangQuangThanh]

đọc còn không hiểu nữa chứ giúp, cái ngoặc đóng với mở đó !

[xistem]

Góp ý chút^^ : trước hết đọc cho dãy số trong file IN vào 1 mảng (vd: 420020-->mảng-đọc chỉ số 6 để tạo mảng có kích cỡ phù hợp)
Ý tưởng bài toán:
1.đọc dãy số,nếu gặp số 0 là biết kết thúc 1 chu kỳ đóng mở ngoặc,lúc đó cần xử lý tạo ngoặc từ số 0 đó trở về trước
2.các dãy số con bị giới hạn 2 đầu bởi số 0 được duyệt đến và số 0 trước đó (có ngoại lệ với chuỗi số đầu tiên )
Vd: với dãy 4 2 0 0 2 0 ta được 3 chuỗi con: 4 2 0 -- 0-- 2 0
3.sau đó ứng với mỗi dãy bạn thực hiện sinh ngoặc theo cách sau: đếm số lượng số trong mỗi dãy con--giả sử là NumCount-->tạo ra mảng có kích cỡ numCount*2 để chứa số ký tự ngoặc đóng và mở (vd: 4 2 0 -->numCount = 3----->số lượng ngoặc đóng mở là 3*2 = 6)
4.xử lý ngược lại từ số 0 trong chuỗi con (4-2-0),gặp số 0 thì sinh ra 1 cặp đóng-mở,sau đó cứ gặp 1 số nào trước số 0 thì sinh ra 1 cặp ngoặc bao cặp ngoặc trước lại
vd: 4-2-0: 0--sinh 1 cặp ()
duyệt ngược gặp 2-->sinh ra 1 cặp bao (())
tương tự cho 4---> ((()))
Có 1 vấn đề là vị trí ngoặc được sinh ra sao cho hợp lý: 4-2-0 thì ngoặc của 4 ở vị trí 0-5 trong mảng (mảng 6 phần tử),ngoặc ứng với 2 ở vị trí 1-4,ứng với 0 ở vị trí 2-3. 1 cách tham khảo là dùng 2 biến để mark vị trí (start và end)
Ứng với số 0 trong dãy : end = sizeofArray/numCount
start = end-1
sau đó cập nhật lại ứng với số tiếp theo (vd là 2 trong dãy 4-2-0) thì
end = end+1
start = start -1
5.Ứng với mỗi dãy con là 1 mảng chứa các ký tự đóng mở ngoặc tương ứng,cuối cùng là nối các mảng đó lại^^
Trên đây chỉ là ý tưởng của mình,dĩ nhiên ko thích dùng mảng bạn có thể dùng List cho uyển chuyển.
Have fun!

[bld]

Em gặp 1 bài như sau nhưng không nghĩ ra được thuật toán như nào. Mọi người giúp em, xin đa tạ. Có code càng tốt
Dãy ngoặc hợp lệ:
Một dãy dấu ngoặc hợp lệ là một dãy các ký tự '(' và ')' được định nghĩa như sau:
- Dãy rỗng (không có ký tự nào) là một dãy dấu ngoặc hợp lệ.
- Nếu A là một dãy dấu ngoặc hợp lệ thì (A) là dãy dấu ngoặc hợp lệ. Dấu ngoặc mở và dấu ngoặc đóng hai bên dãy A được gọi là tương ứng với nhau.
- Nếu A và B là hai dãy dấu ngoặc hợp lệ thì AB là dãy dấu ngoặc hợp lệ.
Ví dụ: ((()))()(()) là dãy dấu ngoặc hợp lệ, người ta viết vào sau mỗi dấu ngoặc mở một số là số dấu ngoặc (cả đóng và mở) nằm giữa trong cặp dấu ngoặc mở đó với dấu ngoặc đóng tương ứng:
Với dãy trên ta có: (4(2(0)))(0)(2(0))
Sau đó người ta lại xoá đi các dấu ngoặc (cả ngoặc đóng và mở)
Với ví dụ trên ta được: 4 2 0 0 2 0
Yêu cầu: Cho biết dãy số còn lại, hãy khôi phục lại dãy ngoặc ban đầu.
Dữ liệu vào: Được lấy từ file văn bản NGOAC.INP có cấu trúc như sau:
- Dòng thứ nhất: Ghi số nguyên dương n là số phần tử của dãy số còn lại (n<=255).
- Dòng thứ hai: Ghi lần lượt các số trong dãy.
Dữ liệu ra: Kết quả ghi vào file văn bản NGOAC.OUT gồm một dòng duy nhất là dãy dấu ngoặc khôi phục được.
Ví dụ :
NGOAC.INP
6
4 2 0 0 2 0
NGOAC.OUT
((()))()(())

NGOAC.INP
8
6 4 2 0 0 0 2 0
NGOAC.OUT (((())))()()(())

ta xem dãy ngoặc chính là dãy lớn nhất , được chia làm các dãy ngoặc con, rồi các dãy ngoặc con chia thành các dãy ngoặc nhỏ hơn nữa , ta tiếp tục chia đề được dãy ngoặc nhỏ nhất (không bao gồm 2 dãy con nhỏ hơn ghép lại) vì sau mỗi dấu ngoặc mở đều thêm số nên dãy số đại diện cho các dãy ngoặc con nhỏ nhất là giảm dần 2 đơn vị , dễ dàng xác định được các dãy con nhỏ nhất này và sinh dãy ngoặc tương ứng nhờ tính chất của nó , sau khi xác định chúng (và thay thế các con số = dãy ngoặc tương ứng), việc còn lại là duyệt các số còn lại,số x có dãy x phần tử ở sau đều là ngoặc thì bỏ x đi là đặt ngoặc (có thể đảm bảo điều này vì sau mỗi bược ta có dãy ngoặc được tạo ra đều là dãy ngợac đúng), công việc kết thúc khi không còn số nào trong dãy

[quangtq]

Thanks mọi người. Em làm được rồi. Hóa ra đơn giản hơn mình nghĩ nhiều. Chỉ cần dùng 1 xâu để chứa kết quả và 2 thủ tục Push để thêm 1 cặp ngoặc.
Code của em (chưa cho vào file thôi)

Uses Crt;
Var
    A:Array***91;1..100***93; of Integer;
    i,j,bg,bgstr,n:integer;
    s:String;
    FO:Text;
Procedure Push1(Var s:String; Pos:Integer);
Begin
    Insert('()',S,Pos+1);
End;

Procedure Push2(Var s:String; Start,Finish:Integer);
Begin
    Insert('(',S,Start);
    Insert(')',S,Finish+1);
End;

BEGIN
    Assign(FO,'ngoac.txt');
    Rewrite(FO);
    ClrScr;
    Write(' N = '); Readln(n);
    For i:=1 to n do Begin Write('A***91;',i,'***93; = '); Readln(A***91;i***93;); End;
    bg:=1; s:=''; bgstr:=1;
    Repeat
        For i:=bg to n do If a***91;i***93;=0 then Begin j:=i; Push1(s,Length(s)); Break; End;
        bgstr:=2*bg;
        For i:=j-1 downto bg do Push2(s,bgstr,Length(s));
        bg:=j+1;
    Until bg>n;
    Writeln(s); Writeln(FO,s);
    Close(FO);
    Readln;
END.