Hộ mình cái

[hachtn]

Cho trước 1 số nguyên dương N (N<=100). Hãy tìm xâu gồm các kí tự a,b,c thỏa mãn 3 điều kiện sau:

- Có độ dài N.

-2 đoạn con bất kỳ liền nhau đều khác nhau.(Đoạn con là dãy kí tự liên tiêp của xâu phải khác nhau. VD: Trong xâu không được có những đoạn như aa,abab,abcabc v. v...)

- Có ít kí tự c nhất

[quangtq]

Quay lui + nhánh cận. Bài này trong quyển DSAP mà.
Như sau:
Do 2 xâu con bất kì liền nhau đều khác nhau, nên cứ 4 kí tự phải có 1 kí tự 'C'.
=> Với 1 dãy con độ dài L, số kí tự 'C' >= L div 4.
Tại bước thử chọn X[i], nếu đã có T[i] kí tự 'C' từ X[1] đến X[i] thì số kí tự 'C' phải chọn thêm luôn lớn >= (n-i) div 4 => Số kí tự 'C' trong kết quả từ X[1] -> X[n] luôn >= T[i] + (n-i) div 4. Dùng số này để đánh giá nhánh cận.
Không được thì mình code

[hachtn]

Mình không biết!Bạn làm hộ cái

[quangtq]

Viết cái thủ tục Try chính ra thôi nhá


Procedure Try(i:Integer);
Var j:'a'..'c';
Begin
For j:='a' to 'c' do
Begin
X[i]:=j;
If Check(i) then // Kiem tra xem co lam hong tinh lap khong
Begin
If j='C' then T[i]:=T[i-1]+1
Else T[i]:=T[i-1];
If T[i]+(N-i) div 4<MinC then If i=N then SaveResult // luu giu nhanh can
Else Try(i+1);
End;
End;
End;

[hachtn]

Trời đất! Mình chả hiểu gì cả!

[quangtq]

1. Bài này thuộc pp quay lui + nhánh cận. Nếu bạn chưa biết thì nên tìm sách đọc đi. Đây mình có quyển này:
http://www.mediafire.com/?txzsugy3bww
2. Nếu biết rồi thì bạn tự code đi. Mình nói hết rồi. Sai đâu up lên mọi người sẽ sửa

[hachtn]

Bạn có thể cho mình code hoặc tư tưong lời giải dược không

[quangtq]

Tư tưởng:
Thủ tục Try(i) để thử giá trị i của kết quả.
Var j:char;
Cho j chạy từ 'a' đên 'c'
Thử gán j cho x[i]. (x là mảng kết quả).
Nếu chọn như vậy ko làm hỏng tính ko lặp của xâu thì xét 2 th: Nếu nó là kí tự 'c' thì T[i]:=T[i-1]+1 (T[i] là số kí tự c tính đến vị trí thứ i).
Nếu ko phải kí tự 'c' thì T[i]:=T[i-1];
Nếu t[i]+(n-i) div 4 < MinC (MinC đây khởi tạo = dương vô cực) thì lưu giữ kết quả, ngược lại gọi đệ quy thử tiếp i+1 (Try(i+1))

[hachtn]

Bạn có thể viết cho mình hàm kiểm tra 2 đoạn con khác nhau được không? Mãi mà mình vẫm không viết được.

[quangtq]

Down quyển sách của mình về đi. Nó đầy đủ hơn nhiều. Trên đấy mình chỉ nói cơ bản thôi

[hachtn]

Không down dược bạn ơi! Nick mình là langtu93_tn01@yahoo.com. Bạn send cho mình đi

[quangtq]

Chính tay mình up lên, không có chuyện đó. Mình vừa test thử. Link vẫn tốt. Bạn xem lại

[hachtn]

Mình làm được rùi cảm ơn bạn nha

[quangtq]

Ko có gì. Ở 4rum nhiều người giỏi lắm. Bạn mắc j cứ lên hỏi.

[hachtn]

Bạn ơi! Mình lại không down dc rui`

[quangtq]

Chả hiểu sao tự dưng link die.
Mình up lại rồi. Đây: http://www.mediafire.com/?gvtywcxgdyn

[mini_bestboy]

Hỏi bạn quang cái này cái
1. mình không hiểu lắm về cái cứ 4 ký tự phải có 1 chử 'C', bạn chứng minh dùm được không ?
2. Check(i) kiểm tra lặp làm sao vậy, bạn post luôn đi, hix, mình làm không được
3. Bạn chỉ mình nhánh cận chỗ nào đi, mình chưa học nhánh cận, chỉ học quay lui thôi, nên mình thấy cái bài đó y hệt quay lui, không hiểu là nhánh cận chỗ nào cả.

[quangtq]

1. Mình đã nói rồi: Tại 2 xâu liền nhau phải khác nhau
=> 2 kí tự liên tiếp phải khác nhau => 4 kí tự phải có 1 kí tự C
2. Trong sách của mình
3. Đọc sách đi