Chủ đề này có 5 trả lời

[Mrnhan]

Hỏi có bao nhiêu xâu nhị phân có độ dài là 10 chứa xâu con 000 hoặc 1111?

 

P.s: Xâu nhị phân là xâu mà mỗi vị trí chỉ có 2 phần từ là 0 hoặc 1.

[Ispectorgadget]

Hỏi có bao nhiêu xâu nhị phân có độ dài là 10 chứa xâu con 000 hoặc 1111?

 

P.s: Xâu nhị phân là xâu mà mỗi vị trí chỉ có 2 phần từ là 0 hoặc 1.

Đặt $S_n$ 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 thỏa mãn đề bài thuộc một trong các dạng sau

$A1$ (A là chuỗi có độ dài $n-1$, 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 bit 0 liên tục), số cách là $S_{n-2}$.

$C100$ (D là chuỗi tùy ý dài $n-3$), số cách tính được là $2^{n-3}$

 

Công thức truy hồi: 

$$S_n=S_{n-1}+S_{n-2}+S{n-3}+2^{n-3}$$

Giá trị khởi tạo $S_1=S_2=0;S_3=1$

 

Đặt $K_n$ là số chuỗi nhị phân độ dài n có 4 bit 1 liên tiếp.

Một chuỗi dài n thỏa mãn đề bài thuộc một trong các dạng sau

$A0$ (A là chuỗi có độ dài $n-1$, chứa 4 bit 1 liên tục), gọi số cách là $K_{n-1}$

$B01$ (B là chuỗi có độ dài $n-2$, B chứa 4 bit 0 liên tục), số cách là $S_{n-2}$.

$C001$ (C là chuỗi tùy ý dài $n-3$), số cách tính được là $S_{n-3}$

$D1111$ (D là chuỗi tùy ý dài $n-4)$ số cách tính được là $2^{n-4}$

Công thức truy hồi: 

$$K_n=K_{n-1}+K_{n-2}+K{n-3}+K_{n-3}+2^{n-4}$$

Giá trị khởi tạo $K_1=K_2=0=K_3=0;K_4=1$

 

Vậy số xâu thỏa mãn là $S_n+K_n=S_{n-1}+S_{n-2}+S{n-3}+2^{n-3}+S_{n-1}+S_{n-2}+S{n-3}+S_{n-3}+2^{n-4}$

 

Đề chắc là và chứ nhỉ :'( để hoặc nhìn biểu thức xấu kinh.

[Kofee]

Theo em thì:

Gọi $S, K$ lần lượt là tập hợp các  xâu nhị phân có độ dài là 10 chứa xâu con 000  và 1111. Thì ta có:

$n(S\cup K) =n(S)+n(K)-n(S\cap K)$

Do đó KQ trên phải trừ đi số các xâu  chứa cả 2 xâu con 000  và 1111.

 

(Em tính $n(S\cap K)=160$ xâu không biết đúng không?)

Bài viết đã được chỉnh sửa nội dung bởi Kofee: 11-02-2015 - 10:55

[chanhquocnghiem]

Hỏi có bao nhiêu xâu nhị phân có độ dài là 10 chứa xâu con 000 hoặc 1111?

 

P.s: Xâu nhị phân là xâu mà mỗi vị trí chỉ có 2 phần từ là 0 hoặc 1.

Gọi $M_{i}$ là tập hợp các xâu nhị phân 10 cs gồm $i$ cs 1 và $10-i$ cs 0 ($i$ từ 0 đến 10) $\Rightarrow \left | M_{i} \right |=C_{10}^{i}$

$N_{i}$ là tập hợp các xâu thuộc $M_{i}$ nhưng không chứa xâu con 000

$P_{i}$ là tập hợp các xâu thuộc $N_{i}$ và chứa xâu con 1111

$R_{i}$ là tập hợp các xâu thuộc $M_{i}$ nhưng không chứa xâu con 1111

$S_{i}$ là tập hợp các xâu thuộc $R_{i}$ và chứa xâu con 000

$Q_{i}$ là tập hợp các xâu thuộc $M_{i}$ và thỏa mãn ĐK đề bài.

Ta có : $\left | Q_{i} \right |=\left | M_{i} \right |-\left | N_{i} \right |+\left | P_{i} \right |$ (1)

hoặc : $\left | Q_{i} \right |=\left | M_{i} \right |-\left | R_{i} \right |+\left | S_{i} \right |$ (2)

Để việc tính toán thuận tiện, với $i$ từ 0 đến 5, ta dùng công thức (1); với $i$ từ 6 đến 10, ta dùng công thức (2).

$A/$ $i$ từ 0 đến 5 :

+ $i=0$ : $\left | Q_{0} \right |=C_{10}^{0}-0+0=1$

+ $i=1$ : $\left | Q_{1} \right |=C_{10}^{1}-0+0=10$

+ $i=2$ : $\left | Q_{2} \right |=C_{10}^{2}-0+0=45$

+ $i=3$ : $\left | N_{3} \right |$ chính là số nghiệm nguyên từ 0 đến 2 của pt $x_{1}+x_{2}+x_{3}+x_{4}=7$ và bằng $C_{4}^{1}.C_{3}^{3}=4$ ; $\left | P_{3} \right |=0\Rightarrow \left | Q_{3} \right |=C_{10}^{3}-4+0=116$

+ $i=4$ : $\left | N_{4} \right |$ là số nghiệm nguyên từ 0 đến 2 của pt $x_{1}+x_{2}+...+x_{5}=6$ và bằng $C_{5}^{0}.C_{5}^{3}+C_{5}^{2}.C_{3}^{2}+C_{5}^{4}.C_{1}^{1}=45$ ; $\left | P_{4} \right |=0\Rightarrow \left | Q_{4} \right |=C_{10}^{4}-45+0=165$

+ $i=5$ : $\left | N_{5} \right |$ là số nghiệm nguyên từ 0 đến 2 của pt $x_{1}+x_{2}+...+x_{6}=5$ và bằng $C_{6}^{1}.C_{5}^{2}+C_{6}^{3}.C_{3}^{1}+C_{6}^{5}.C_{1}^{0}=126$

   $\left | P_{5} \right |=6$ ($x_{2}=x_{3}=x_{4}=0$ có 3 cách ; $x_{3}=x_{4}=x_{5}=0$ có 3 cách) $\Rightarrow \left | Q_{5} \right |=C_{10}^{5}-126+6=132$

$B/$ $i$ từ 6 đến 10 :

+ $i=6$ : $\left | R_{6} \right |$ là số nghiệm nguyên từ 0 đến 3 của pt $y_{1}+y_{2}+...+y_{5}=6$ và bằng $135$

   (Nếu nghiệm là hoán vị của (3,3,0,0,0) ---> $C_{5}^{2}=10$ nghiệm

   Nếu nghiệm là hoán vị của (3,2,1,0,0) ---> $5.4.3=60$ nghiệm

   Nếu nghiệm là hoán vị của (3,1,1,1,0) ---> $5.4=20$ nghiệm

   Nếu nghiệm là hoán vị của (2,2,2,0,0) ---> $C_{5}^{3}=10$ nghiệm

   Nếu nghiệm là hoán vị của (2,2,1,1,0) ---> $C_{5}^{2}.C_{3}^{2}=30$ nghiệm

   Nếu nghiệm là hoán vị của (2,1,1,1,1) ---> $C_{5}^{1}=5$ nghiệm)

   $\left | S_{6} \right |=19$

   (Nếu nghiệm là hoán vị của (3,3,0,0,0) và $y_{2}=y_{3}=0$ ; $y_{1}$ hoặc $y_{5}$ bằng 0 ---> 2 cách

   Nếu nghiệm là hoán vị của (3,3,0,0,0) và $y_{3}=y_{4}=0$ ; $y_{1}$ hoặc $y_{5}$ bằng 0 ---> 2 cách

   Nếu nghiệm là hoán vị của (3,3,0,0,0) và $y_{2}=y_{3}=y_{4}=0$ ---> 1 cách

   Nếu nghiệm là hoán vị của (3,2,1,0,0) và $y_{2}=y_{3}=0$ ---> 6 cách

   Nếu nghiệm là hoán vị của (3,2,1,0,0) và $y_{3}=y_{4}=0$ ---> 6 cách

   Nếu nghiệm là hoán vị của (2,2,2,0,0) ---> 2 cách)

   $\Rightarrow \left | Q_{6} \right |=C_{10}^{6}-135+19=94$

+ $i=7$ : $\left | R_{7} \right |$ là số nghiệm nguyên từ 0 đến 3 của pt $y_{1}+y_{2}+...+y_{4}=7$ và bằng $40$

   (Nếu nghiệm là hoán vị của (3,3,1,0) ---> $4.3=12$ nghiệm

   Nếu nghiệm là hoán vị của (3,2,2,0) ---> $4.3=12$ nghiệm

   Nếu nghiệm là hoán vị của (3,2,1,1) ---> $4.3=12$ nghiệm

   Nếu nghiệm là hoán vị của (2,2,2,1) ---> $4.3=4$ nghiệm)

   $\left | S_{7} \right |=0$ $\Rightarrow \left | Q_{7} \right |=C_{10}^{7}-40+0=80$

+ $i=8$ : $\left | R_{8} \right |$ là số nghiệm nguyên từ 0 đến 3 của pt $y_{1}+y_{2}+y_{3}=8$ và bằng $3$

   $\left | S_{8} \right |=0$ $\Rightarrow \left | Q_{8} \right |=C_{10}^{8}-3+0=42$

+ $i=9$ : $\left | R_{9} \right |=0$ ; $\left | S_{9} \right |=0$ $\Rightarrow \left | Q_{9} \right |=C_{10}^{9}=10$

+ $i=10$ : $\left | R_{10} \right |=0$ ; $\left | S_{10} \right |=0$ $\Rightarrow \left | Q_{10} \right |=C_{10}^{10}=1$

 

Vậy đáp án là $1+10+45+116+165+132+94+80+42+10+1=696$ xâu.

Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 21-03-2015 - 21:49

[Mrnhan]

Có thể code trong C/C++ như sau để tính số xâu nhị phân có 000 hoặc 1111:

#include <bits/stdc++.h>

using namespace std;

int main()
{
	const int maxx = 50;
	int n;
	int B[3][maxx];
	cout << "Do dai xau nhi phan n = "; cin >> n;
	
	// Do dai la 1.
	B[0][1] = 1;
	B[1][1] = 1;
	
	//Do dai la 2.
	B[0][2] = 2;
	B[1][2] = 2;
	
	//Do dai la 3.
	B[0][3] = 3;
	B[1][3] = 4;
	
	for (int i = 4; i <= n; i++)
	{
		B[0][i] = B[1][i - 1] + B[1][i - 2];
		B[1][i] = B[0][i - 1] + B[0][i - 2] + B[0][i - 3];
	}
	
	cout << "So xau do dai " << n <<" la " << pow(2, n) - B[0][n] - B[1][n];
	return 0;
}

[eyelevel]

Nhiều đáp án hay quá, mình sẽ test code chạy thử