Xâu thuận nghịch

[humalo]

Các anh có thể xem giúp em một bài toán rời rạc được không ạ

Xâu thuận nghịch là một xâu khi viết theo thứ tự ngược lại cũng bằng chính nó. Hãy đếm số xâu nhị phân có độ dài n là thuận nghịch

[jiSh@n]

=> Đếm số xâu nhị phân có độ dài là n/2

[humalo]

Cam on anh jiSh@n. Anh co the cho em hoi nhu vay co nghia la tong so xau nhi phan thuan nghich se la A(n/2)(2) = 2^(n/2) ??? dung ko aj

[kimduquan]

bài này chắc chỉ cần dùng phương pháp sinh hoán vị kế tiếp kết hợp với kiểm tra thuận nghịch thui,cứ viết giống y như bài toán liệt kê các xâu nhị phân có độ dài n nhưng trong hàm xuất hoán vị hiện tại có thêm phần kiểm tra thuận nghịch,nếu xâu thuận nghịch thì mới xuất ra.

[humalo]

Hi anh kimduquan. Em dang muon tim cong thuc de tinh dc tong so xau nhi phan thuan nghich do dai n co the co. Mot bai toan trong toan roi rac, khong phai la mot phep duyet trong lap trinh aj

[kimduquan]

1 xâu thuận nghịch khi nó đối xứng qua phần tử ở giữa,ta có 2 cách chọn phần tử ở giữa và có 2 mũ n/2 cách chọn phần tử 2 bên nên ->có 2*2^(n/2)=2^(n/2+1) cách nếu n lẻ,còn n chẵn thì có 2^(n/2) cách.

[humalo]

Cảm ơn anh kimduquan

[jiSh@n]

Cam on anh jiSh@n. Anh co the cho em hoi nhu vay co nghia la tong so xau nhi phan thuan nghich se la A(n/2)(2) = 2^(n/2) ??? dung ko aj

Chia 2 trường hợp n chẵn và lẻ nữa.

[bld]

đếm số xâu nhị phân n div 2 , n chẵn thì là kết quả , lẻ thì nhân 2 lên , không biết có đúng không

[quangtq]

Không phải. N lẻ thì + 2 chứ.
Vd: 101->101101.
101->(1010101,1011101)

[bld]

ồ không chính xác là nhân 2 , nhưng tóm lại cũng sai
tính số xâu nhị phân n div 2 =x
n chẵn thì số lượng = sum(1..x-1);
lẻ thì = 2*sum(1..x-1);

[quangtq]

Hình như vẫn chưa phải.
x = n div 2.
n lẻ thì là x*2+2
n chẵn là x*2.
Đã đếm = tay. Chuẩn rồi đấy.

[bld]

khoan đã nào :
giả sử có x xâu nhị phân n div 2 đó mới chỉ là 1 nửa, thì cũng có tương ứng x xâu n div 2 ở nửa bên kia đề tạo đối xứng , như vậy có x trường hợp nếu chẵn , trường hợp lẻ ta lại chèn 1 trong 2 giá trị 0 or 1 vào giữa , vậy là 2x
thử xem nào :n=5
n div 2 = 2
số xâu n div 2 là 4
00 01 10 11
vậy số xâu n là 2*4=8 :
00000
01010
10001
11011
-------------
00100
01110
10101
11111

8 , không lặp , chuẩn

[quangtq]

n=4: 0000, 0110, 1001, 1111.
n div 2 = 2. Số xâu là: 2*(n div 2)
=> N chẵn: n
N lẻ: 4(n div 2)

[khonggiannet]

Kết quả là 2^[n/2]
trong đó [n/2] là phần nguyên của n/2

[bld]

thế n=5 thì 2^2=4 àh anh ?
a giải thích thêm về công thức của a đi ^^

[cal]

Công thức:
http://img99.imageshack.us/img99/7428/equation.jpg
Ký hiệu ceiling là 1 ký hiệu chuẩn trong toán rời rạc.

[bld]

>.< em chưa học toán rời rạc và kí hiệu ceiling. chỉ giúp em với

[jiSh@n]

>.< em chưa học toán rời rạc và kí hiệu ceiling. chỉ giúp em với

Ceiling và floor trong toán phổ thông đã có rồi, cần gì đến toán rời rạc. ceiling là số nguyên gần nhất ở cân trên, floor là số nguyên gần nhất ở cận dưới.

ceiling(3.1) = 4
floor(3.1) = 3

[quangtq]

Thế mà anh ko nói = Tiếng Việt ra. Em làm sao biết được.
C/m tính đúng đắn của ct trên ko khó. Chuẩn rồi