1![[Lời giải]Tổng hợp các bài toán đếm xâu Empty](https://2img.net/i/empty.gif)
[Lời giải]Tổng hợp các bài toán đếm xâu Mon Jun 27, 2011 7:10 am
Admin
Quản trị viên
Tổng hợp các bài toán đếm số chuỗi với các điều kiện
Lời giải của LVĐ, NKP, HTH, AM, đọc lời giải bằng cách nháy vào phần nền tương ứng.
1. Lời giải của LVĐ, NKP, HTH, AM, đọc lời giải bằng cách nháy vào phần nền tương ứng.
- Tính số chuỗi n bit không chứa mẫu 00:
- Chuỗi dài n thỏa mãn không chứa 00 thì có một trong 2 dạng
* A1 (A không chứa mu 00)
* B10 (B không chứa mẫu 00)
Vậy có hệ thức truy hồi:
Sn = Sn-1 + Sn-2
S1 = 2 (0;1),
S2 = 3 (01;10;11)
- Tính số dãy bit độ dài n có 2 bit 0 kề nhau:
- Một số có 2 bít 0 kề nhau thuộc 1 trong 3 dạng
* A00 (A bất kì dài n - 2, số trường hợp là 2n-2)
* B10 (B chứa 2 bít 0 liền nhau dài n - 2, số trường hợp là an-2)
* C1 (C chứa 2 bít 0 liền nhau dài n - 1, số trường hợp là an-1)
Vậy
an = an-1 + an-2 + 2n-2
ao = 0
a1 = 0
- Tính số dãy bit độ dài n không có 2 bit 0 kề nhau:
- Một dãy độ dài n không có 2 bit 0 kề nhau thì có 1 trong 2 dạng
* A10 (A có n - 2 bit và không có 2 bit 0 kề nhau)
* B1 (B có n - 1 bít và không có 2 bit 0 kề nhau)
Vậy suy ra
an = a(n - 1) + a(n - 2)
a1 = 2;
a2 = 3
Dãy này bắt đầu từ a1 = 2 là dãy dạng Fibonaci
Giải truy hồi bằng cách xét nghiệm của phương trình đặc trưng
x2 = x + 1
x1 = (1 + √5)/2;
x2 = (1 - √5)/2
an = c1. x1n + c2. x2n
Thay n = 1, 2 vào tìm c1, c2 (Khách viếng thăm tự thực hiện)
- Tính số chuỗi nhị phân độ dài n có chứa chuỗi con 01:
- Đặt Sn là số chuỗi nhị phân có chứa chuỗi con 01 (*) ta suy ra ngay số chuỗi nhị phân không chứa chuỗi con 01 là 2n-Sn (**)
Chuỗi nhị phân có chứa chuỗi con 01, thuộc 1 trong 2 dạng:
Ax (A là chuỗi có độ dài n - 1, A chứa chuỗi con 01, x = 0 hoặc 1) gọi số cách là S(n-1), nhưng do x có 2 trạng thái 0 và 1, nên nhớ phải nhân 2.
B01 (B là chuỗi có độ dài n - 2, B không chứa chuỗi 01) lập luận như (**) thì B là 2(n-2)-Sn-2
Ta có hệ thức truy hồi:
Sn=2 Sn-1 + (2(n-2)-Sn-2)
hay Sn = 2 Sn-1 - Sn-2 + 2(n-2)
Giá trị khởi tạo: S1 = 0;S2 = 1
Thực ra Sn có thể tính dễ dàng không truy hồi như sau:
Chuỗi không thỏa mãn (*) chỉ có thể có dạng: 111...111000...000 số chuỗi thế này = n + 1
Suy ra:
Sn=2n - (n + 1)
- Tính số chuỗi nhị phân độ dài n có một số chẵn bit 0:
- Gọi Sn là số chuỗi có số chẵn bit 0
Gọi Kn là số chuỗi có số lẻ bít 0
Ta có Sn + Kn = 2n
Một chuỗi dài n có số chẵn bit 0, được thành lập bằng 2 cách
* Chuỗi số chẵn bít 0 có độ dài n-1, thêm 1
* Chuỗi số lẻ bít 0 có độ dài n-1, thêm 0
Ta có hệ thức sau:
Sn=S(n-1)+K(n-1)
Tương tự ta có:
Kn = S(n-1) + K(n-1)
Suy ra: Sn = Kn
Hay hệ thức truy hồi là:
Sn = 2S(n-1)
Với giá trị khởi tạo :
S1 = 1
- Tính số chuỗi nhị phân độ dài n có 3 bit 0 liên tiếp:
- Đặt Sn là số chuỗi nhị phân độ dài n, có 3 bit 0 liên tiếp:
Một chuỗi dài n (n>3) thoả mãn điều kiện đầu bài sẽ thuộc một trong các dạng sau:
A1 ( A là chuỗi có độ dài n -1, A chứa 3 bit 0 liên tục) , gọi số cách là S(n-1)
B10 (B là chuỗi có độ dài n - 2, B chứa 3 bít 0 liên tục), gọi số cách là S(n-2)
C100 (C là chuỗi có độ dài n - 3, C chứa 3 bít 0 liên tục, gọi số cách là S(n-3)
D000 (D là chuỗi tùy ý dài n - 3), số cách tính được luôn là 2(n-3)
Ta có công thức truy hồi:
Sn=S(n-1) + S(n-2) + S(n-3) + 2(n-3)
Khởi tạo:
S1 = S2 = 0; S3 = 1.
- Tính số chuỗi nhị phân độ dài n không có 3 bit 0 liên tiếp:
- Đặt Sn là số chuỗi nhị phân độ dài n, không có 3 bit 0 liên tiếp:
Một chuỗi dài n (n>3) thoả mãn điều kiện đầu bài sẽ thuộc một trong các dạng sau:
A1 (A là chuỗi có độ dài n - 1, không có 3 bit 0 liên tiếp), gọi số cách là S(n-1)
B10 (B là chuỗi có độ dài n - 2, không có 3 bit 0 liên tiếp), gọi số cách là S(n-2)
C100 (C là chuỗi có độ dài n - 3, không có 3 bit 0 liên tiếp), gọi số cách là S(n-3)
Nên ta có hệ thức truy hồi:
Sn=Sn-1 + Sn-2 + Sn-3
Khởi tạo: S1 = 2, S2 = 4, S3 = 7
- Tính số xâu nhị phân có độ dài 8 và có đúng 2 cặp 01:
- Đây không phải là lời giải, mà đây chỉ là bình giảng lời giải.
Cách giải của thầy đưa ra rất hay, khi viết chuỗi cần tìm có dạng:[You must be registered and logged in to see this image.]Trong đó:
x1 là số lượng các con số 1.
x2 là số lượng các con số 0.
x3 là số lượng các con số 1.
x4 là số lượng các con số 0.
x5 là số lượng các con số 1.
x6 là số lượng các con số 0.
Giáp ranh của x2x3 với x4x5 đã tạo ra 2 cặp số 01 rồi. Nên x1có thể thêm tuỳ ý số lượng số 1 miễn là thoả mãn điều kiện đầu bài về chiều dài xâu, mà không thể tạo ra được cặp 01 mới.Tương tự lập luận cho các biến khác.
Theo điều kiện đầu bài, số lượng các con số của xâu 8 ký tự, nên ta có:
x1 + x2 + x3 + x4 + x5 + x6 = 8
Trong đó các con số tao lập nên 2 cặp 01 bắt buộc phải có, nghĩa là x2, x3, x4, x5 tối thiểu phải 1 lần nên các điều kiện đầu tiên là:
x2 ≥ 1
x3 ≥ 1
x4 ≥ 1
x5 ≥ 1
Còn số lượng các con số x1 và x6 có thể không có cũng chẳng sao, nên điều kiện 2 là:
x1 ≥ 0
x6 ≥ 0
Từ đây ta sẽ đưa về [You must be registered and logged in to see this link.] để giải.
Vấn đề giải bài toán cơ bản này các đồng chí có thể xem lại bằng cách nháy vào link trên.
Nghĩa là số cách có thể thành lập được xâu nhị phân có độ dài 8 và có đúng 2 cặp 01 là nghiệm của phương trình:
x1 + x2+ x3 + x4 + x5 + x6 = 8
với điều kiện:
x2 ≥ 1
x3 ≥ 1
x4 ≥ 1
x5 ≥ 1
x1 ≥ 0
x6 ≥ 0
- Tính số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp và hai số 1 liên tiếp:
- Trước hết ta tìm số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp:
Gọi Kn là số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp. Ta có các trường hợp xảy ra:
− Số thứ n bằng 1. Số xâu thỏa mãn là Kn-1
− Số thứ n bằng 0. Ta xét tiếp:
Số thứ n-1 bằng 1 thì số xâu thỏa mãn là Kn-2
Số thứ n-1 bằng 0 thì số xâu thỏa mãn là 2n-2
Vậy Kn = Kn-1 + Kn-2 + 2n-2
Với điều kiện ban đầu K1 = 0; K2 = 1.
Bằng cách chứng minh tương tự, ta có số xâu nhị phân có độ dài n chứa hai số 1 liên tiếp cũng là:
Kn = Kn-1 + Kn-2 + 2n-2
Với điều kiện ban đầu K1 = 0; K2 = 1.
Bây giờ, ta gọi số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp và hai số 1 liên tiếp là Sn, ta có các khả năng xảy ra:
− Hai số cuối là 00. Số xâu nhị phân thỏa mãn chính bằng số xâu nhị phân có độ dài n-2 chứa hai số 1 liên tiếp và bằng Kn-2.
− Hai số cuối là 11. Số xâu nhị phân thỏa mãn chính bằng số xâu nhị phân có độ dài n-2 chứa hai số 0 liên tiếp và bằng Kn-2.
− Trường hợp còn lại. Số xâu nhị phân thỏa mãn bằng Sn-1.
Vậy số xâu nhị phân có độ dài n chứa hai số 0 liên tiếp và hai số 1 liên tiếp cho bởi công thức:
Sn = Sn-1 + 2Kn-2 với điều kiện ban đầu là K1 = K2 = K3 = 0.
- Tính số xâu nhị phân có độ dài 8 và có đúng 1 cặp 00:
- Xét xâu nhị phân có độ dài 7, sao cho có ít nhất 1 số 0 và không có 2 số 0 nào cạnh nhau, do đó số số không trong xâu lớn nhất sẽ là 4 (nó không được lớn hơn số số 1 cộng 1).
- Với xâu có 1 số 0; 6 số 1: có [You must be registered and logged in to see this image.]
- Với xâu có 2 số 0; 5 số 1: có [You must be registered and logged in to see this image.]
- Với xâu có 3 số 0; 4 số 1: có [You must be registered and logged in to see this image.]
- Với xâu có 4 số 0; 3 số 1: có [You must be registered and logged in to see this image.]
Để thỏa mãn yêu cầu của bài toán, tức là chỉ có đúng một cặp 00 trong xâu nhị phân có độ dài là 8, ta chỉ cần thêm 1 số 0 vào xâu nhị phân có độ dài là 7 như trên ta đã xét, sao cho số 0 mới thêm nằm cạnh với số 0 đã có trong xâu (đặt trước hay sau thì cũng chỉ là một cách). Với xâu có bao nhiêu số 0 thì có bấy nhiêu cách để thêm sô 0.
Vậy đáp án là:
[You must be registered and logged in to see this image.]
Còn công thức tổng quát với xâu có độ dài là n thì có lẽ là
[You must be registered and logged in to see this image.]
Nếu nó đã thành cặp 00 rồi thì sao? Ta thêm số 0 nữa cho đủ độ dài 8, thì không thoả mãn đầu bài có đúng 1 cặp 00
- Khách viếng thăm tưởng tượng như thế này nhé. Giả sử Khách viếng thăm có một xâu thỏa mãn yêu cầu, tức là xâu có độ dài 8 chỉ có đúng 1 cặp 00. Khách viếng thăm xóa béng một số 0 trong cặp đó, lúc này xâu nhị phân sẽ có độ dài là 7, và không có bất cứ cặp 00 nào. Nhớ là xâu có độ dài 7 không có bất cứ cặp 00 nào nhé. Công việc của Khách viếng thăm là làm ngược lại. Tìm tất cả các trường hợp có độ dài là 7, không có 2 số 0 đứng cạnh nhau. Sau đó thêm 1 số 0 vào cạnh số 0 trong xâu có độ dài 7.
Ví dụ: xâu có độ dài 7: 0110101
Như vậy ta sẽ có 3 cách thêm (tương ứng với số số 0 trong xâu, thêm trước hay sau số 0 đó đều như nhau) như sau:
00110101 (hoặc 00110101)
01100101 (hoặc 01100101)
01101001 (hoặc 01101001)
- Còn trường hợp tính : Với xâu có 2 số 0; 5 số 1; Với xâu có 3 số 0; 4 số 1; Với xâu có 4 số 0; 3 số 1. Khách viếng thăm hãy xem lại [You must be registered and logged in to see this link.], nó không được bò dọc liên tiếp, cũng như việc 2 số 0 không đứng cạnh nhau.
[You must be registered and logged in to see this image.]
= 7 + 30 + 15 + 4 = 56
- Tính xâu có độ dài n mà các số 0 và 1 đứng xen nhau (cả 0 đứng trước và cả 1 đứng trước):
TH1: 0 đứng trước. mỗi cách xếp sẽ có dạng: 0101....01. Mỗi cách sắp xếp 0 vào n vị trí này là một hoán vị không lặp của n, tương tự mỗi cách sắp xếp 1 vào n vị trí trong dãy là một hoán vị không lặp của n → số cách sắp xếp là: n! n!
TH2: 1 đứng trước. Lập luận tương tự ta cũng có số cách sắp như trên.
Vậy đáp số của bài toán là: 2 n!n!
- Có bao nhiêu xâu nhị phân chứa đúng 5 số 0 và mười bốn số 1 và ngay sau mỗi số 0 nhất thiết là hai số 1?:
- Mỗi xâu nhị phân theo đầu bài chứa 5 cặp 011 và 4 số 1 đứng xen kẽ bất kì.
Nếu coi:
- Mỗi cặp 011 là một phần tử: Phần tử A → Vì đề bài yêu cầu 5 cặp số 011 → Có 5 phần tử A
- Mỗi số 1 cũng là một phần tử: Phần tử B → Vì đề bài đã cho có 14 chữ số 1 (Trừ đi 10 chữ số 1 nằm trong 5 phần tử A rồi) nên phần tử B còn 4 chữ số 1.
Thì trong một cách xếp xâu nhị phân có tất cả 9 phần tử. Như vậy mỗi cách xếp xâu nhị phân thỏa măn điều kiện bài toán là một hoán vị có lặp của 9 phần tử trong đó có 5 phần tử A và 4 phần tử B. Hay nói cách khác là tổ hợp chập 5 của 9 phần tử, Vậy số xâu nhị phân thỏa mãn điều kiện bài toán là
[You must be registered and logged in to see this image.]
- Tính số chuỗi ký tự gồm A, B, C có độ dài n chứa hai kí tự liên tiếp giống nhau:
- Gọi Sn là số chuỗi thỏa mãn: Có chưa 2 kí tự liên tiếp giống nhau (*) thì số chuỗi không thỏa mãn (*) là 3n - Sn
Chuỗi thỏa mãn có 1 trong 2 dạng:
* Mx (M thỏa (*), x có 3 cách)
* Nxx (Nx không thỏa (*))
→ Sn = 3 Sn - 1 + (3n-1 - Sn - 1) = 2 Sn - 1 + 3n-1
Khởi tạo: S1 = 0,
S2 = 3
Có thể giải không truy hồi như sau:
Đầu tiên tìm số chuỗi không có 2 kí tự liên tiếp bằng nhau:
Chọn kí tự đầu tiên có 3 cách, kí tự tiếp theo có 2 cách (Trừ kí tự trước nó)
Vậy tất cả có: 3. 2n-1 cách
→ Sn = 3n - 3. 2n-1
- Có bao nhiêu xâu 20 chữ số của hệ thập phân chứa đúng 2 số 0, bốn chữ số 1, ba chữ số 2, một chữ số 3, hai chữ số 4, ba chữ số 5, hai chữ số 7 và 3 chữ số 9?:
- Xét tất cả các trường hợp (kể cả số 0 đứng đầu xâu) 20 chữ số thì mỗi cách sắp xếp xâu 20 chữ số thì:
- Tổng số: 20 vị trí. → n = 20
Trong đó:
- 2 vị trí chứa số 0 → k1 = 2
- 4 vị trí chứa số 1 → k2 = 4
- 3 vị trí chứa số 2 → k3 = 3
- 1 vị trí chứa số 3 → k4 = 1
- 2 vị trí chứa số 4 → k5 = 2
- 3 vị trí chứa số 5 → k6 = 3
- 2 vị trí chứa số 7 → k7 = 2
- 3 vị trí chứa số 9 → k8 = 3
Là một hoán vị có lặp của 20 phần tử gồm các phần tử nêu trên. Vậy số cách sắp xếp xâu 20 chữ số, theo công thức tính ta có:
[You must be registered and logged in to see this image.]
Nhưng vì xâu 20 chữ số ở dạng thập phân, nên những xâu có số 0 ở đầu xâu vô nghĩa (do bỏ đi thì xâu không đủ 20 chữ số) phải trừ ra. Để đếm số trường hợp phải trừ ra này thì xét trường hợp xâu có số 0 đứng đầu.
Giống như xét trong 19 vị trí còn lại, ta có:
- Tổng số có 19 vị trí → n = 19
- 1 vị trí chứa số 0 → k1 =1
- 4 vị trí chứa số 1 → k2 = 4
- 3 vị trí chứa số 2 → k3 = 3
- 1 vị trí chứa số 3 → k4 = 1
- 2 vị trí chứa số 4 → k5 = 2
- 3 vị trí chứa số 5 → k6 = 3
- 2 vị trí chứa số 7 → k7 = 2
- 3 vị trí chứa số 9 → k8 = 3
Vậy số trường hợp phải loại với 1 số 0 đứng đầu là:
[You must be registered and logged in to see this image.]
nhưng trong 19 chữ số của X1 trên vẫn còn trường hợp số 0 đứng đầu. (Xét về tổng quát thì phải trừ đi tiếp, nghĩa là phải trừ tiếp trường hợp X có 2 số 0 đứng đầu.
Ta lại xét tương tự trong 198 vị trí còn lại, ta có:
- Tổng số có 18 vị trí → n = 18
- 4 vị trí chứa số 1 → k1 = 4
- 3 vị trí chứa số 2 → k2 = 3
- 1 vị trí chứa số 3 → k3 = 1
- 2 vị trí chứa số 4 → k4 = 2
- 3 vị trí chứa số 5 → k5 = 3
- 2 vị trí chứa số 7 → k6 = 2
- 3 vị trí chứa số 9 → k7 = 3
Ta có công thức:
[You must be registered and logged in to see this image.]
Số xâu 20 chữ số hệ thập phân thỏa mãn đk đầu bài là:
[You must be registered and logged in to see this image.]
Ta có:
[You must be registered and logged in to see this image.]
Do 20! = 18! * 19 * 20 nên → X = 19 * 20 * X2 / 2!
Do 19! = 18! * 19 nên → X1 = 2 * 19 * 20 * X2
Vậy kết quả:
KQ = 19 * 10 * X2 - 19 * X2 - X2
KQ = X2( 19 * 10 - 19 - 1) = 170 * X2
Thay số:
[You must be registered and logged in to see this image.]
