Tìm giải thuật cho bài toán

[tianang]

_ Cho một dãy ký tự được tạo thành bởi từng cặp ký tự "AB". Các cặp ký tự "AB" chỉ có thể đứng lồng vào nhau hoặc rời nhau chứ không được giao nhau (ví dụ : ABAB: rời nhau, hoặc AABB : lồng nhau)
_ Một chuỗi thông tin được tạo thành từ dãy ký tự đã cho bằng cách ghi số lượng các ký tự chứa trong mỗi cặp ký tự theo thứ tự từ trái qua phải của dãy.
ví dụ :
Cho dãy AAABABBBAB , sẽ có dãy thông tin tương ứng là : 6 4 0 0 0
(tức là cặp ký tự "AB" đầu tiên chứa trong nó 6 ký tự, cặp thứ hai chứa trong nó 4 ký tự, hai cặp tiếp theo không chứa ký tự nào bên trong và cặp cuối cùng cũng không chứa ký tự)
_ Yêu cầu : từ dãy thông tin cho trước hãy phục hồi lại dãy ký tự

[VHHX]

cái vd của bác khó hiểu quá ! nói rõ lắm rồi hả bác, vây mà tui chưa hiểu lắm . hồi bên pascal có làm mấy bài decrypt-encrypt kiểu naỳ, nhưng đề này phức tạp quá :P

[Rikku]

AAABABBBAB
Sao cứ phải AB làm gì. Viết thành ( và ) có phải dễ nhìn không?
Ban đầu dãy là trống
Tìm kí tự đầu tiên chưa điền gì.
Đọc dãy số ->6
Vậy điền vào đó A và cách đó 6+1 ô, tức là ô 8 là B-> 1 và 8 đã được điền.
Tiếp đến ô 2 là trống. Đọc dãy số ->4
Điền vào A vào 2-> cách đó 4+1 ô, ô 7 là B.->2 và 7
Đến ô 3.Đọc dãy là 0-> cách đó 0+1 ô, là ô 4 là B->3 và 4
Đến ô 4.Điền rồi.
Ô 5 chưa điền, đọc dãy số là 0-> 5 và 6
Tiếp đó 7 và 8 đều đã điền-> Tới ô 9.Đọc được 0 ->9 và 10 là A,B.

Tóm lại là, đi đến ô đầu tiên chưa điền. Đọc tiếp từ dãy số cho trước số x.Điền tại ô hiện thời A và ô cách đó x+1 là B.

Chắc không sai đâu lol

[tianang]

Tớ thử biểu diễn thuật toán của cậu như sau, không biết có đúng không :
var so : string;
kytu : string;
BEGIN
j=1
for i=1 to length(so)
begin
if so[i] <> " " then
begin
while kytu[j] <> " " do
j = j +1;
kytu[j]="A"
kytu[j+so[i]] = "B"
end
end
END;

[Rikku]

Thuật toán mình viết đã quá chi tiết, nếu đúng test đề bài -> cài đúng or else là bạn cài sai lol

[tianang]

Mình chưa test thử, nhưng mình nghĩ thuật toán của cậu rất tốt. Ta có thể khép lại bài này được rối.
Bây giờ qua bài này xem sao :
" Cho 2 số nguyên dương A có N chữ số và B có M chữ số(2 <= N,M <= 100). Xét số C được tạo thành từ hai số A và B thỏa tính chất sau :
_C có N+M chữ số
_Có thể đánh dấu N chữ số trong C (theo trình tự từ trái qua phải) để tạo thành số A, và M chữ số không được đánh dấu (cũng theo trình tự như vậy) sẽ tạo thành số B
Hãy tìm số lớn nhất Cmax và số nhỏ nhất Cmin ?

[Rikku]

Chưa nghĩ kĩ lắm lol.
Theo mình thì ta chạy từ 1->M+N:
Mỗi lần , chọn ra số nhỏ hơn ở hai đầu (bên trái) của A và B. Chọn bên nào thì xóa chữ số bên đó đi.
VD:A= 1249; B= 5634;
Đầu tiên là 1.-> 249 5634
Đến 2: 49 5634
Đến 4: -> 9 5634.
Đến 5-> 9 634
Tiếp tục với 634 rồi đến 9:
Cmin=12456349.
Tương tự với Cmax chọn số lớn hơn trong mỗi bứoc duyệt
-> Cmax=56341249

Làm tham lam, nhưng chắc là đúng đắn.

[tianang]

Thuật toán như cậu là đúng rồi,
i:=1;
j:=1;
for k:=1 to N+M do
begin
if (N[i]<M[j]) and (i<=N) then
c[k]:=N[i];
i:=i+1;
else
c[k]:=M[j];
j:=j+1;
endif
endl;