mrP đã viết:Biểu diễn tổ hợp dưới dạng a₁, a₂, a₃,...., a_k với điều kiện 1 ≤ a₁ < a₂ < a₃ < ....< a_k ≤ n
- Đặt c₀ := 0;
- Giá trị a_i nằm trong khoảng từ a_i-1 + 1 đến n - k + i

- Proc. Duyet(i: integer);
For j := a_i-1 + 1 to n - k + i do
          a_i := j;
          if i = k then
                    for m := 1 to k do OutPut (a_m)
          else
                    Duyet(i + 1);

Admin đã viết:Làm câu này:
Có bao nhiêu xâu có độ dài 10 được tạo từ tập {a, b, c} thỏa mãn ít nhất 1 trong 2 điều kiện:
- Chứa đúng 3 chữ a & chúng phải đứng cạnh nhau
- Chứa đúng 4 chữ b & chúng phải đứng cạnh nhau
Giải:
- Gọi số xâu có độ dài 10 chứa đúng 3 chữ a & chúng phải đứng cạnh nhau là N(A)
- Gọi số xâu có độ dài 10 chứa đúng 4 chữ b & chúng phải đứng cạnh nhau là N(B)
Trường hợp này tức là bài muốn ta tìm N(AUB)
Theo nguyên lý bù trừ ta có N(AUB) = N(A) + N(B) - N(A∩B)
Mà N(A) được tính như sau:
+ Xâu có 3 chữ a đứng cạnh nhau, thì số ký tự còn lại là 7 ký tự. 7 ký tự này chỉ có 2 giá trị là b, c, vậy số trường hợp đối với 7 ký tự này giống như xâu nhị phân có độ dài 7, hay bằng 2⁷ trường hợp. Xâu có 3 ký tự a trên, có thể được xếp vào 8 vị trí nên số lượng của N(A) = 8.2⁷
+ Tương tự, số lượng xâu có 4 chữ b đứng cạnh nhau, N(B) = 7.2⁶
+ N(A∩B) được tính bằng cách gộp aaa = X, bbbb = Y, còn lại là 3 chữ c. Xét bài toán (tính số SUCSSESS ở sách giáo khoa, khi cho 1 chữ X, 1 chữ Y và 3 chữ b) thì số trường hợp là:
C³₅ * C²₄ * C₃³ = 10 trường hợp
Vậy kết quả số xâu cần tính là:
8.2⁷ + 7.2⁶ - 10 = 2486

Tham khảo bài toán SUCCSESS:

Lời giải:

Admin đã viết:Đề tuyển sinh cao học Toán Rời rạc năm 2010

II. Giải hệ phương trình đồng dư
x ≡ 5 (mod 7)
x ≡ 7 (mod 9)
x ≡ 9 (mod 11)
Lời giải:Ta có các số (7, 9), (7, 11), (9, 11) là nguyên tố cùng nhau từng đôi một, nên có thể áp dụng luôn định lý đồng dư Trung Quốc.
Ta có:
a₁ = 5, a₂ = 7, a₃ = 9
m₁ = 7, m₂ = 9, m₃ = 11
1) Tính giá trị của M = 7 x 9 x 11 = 7623
2) Tính giá trị của
M₁ = 9 x 11 = 99
M₂ = 7 x 11 = 77
M₃ = 7 x 9 = 63
3) Tính các giá trị nghịch đảo y của từng M. Ta có (Tính trong bảng, để được kết quả):
y₁ = 99^-1 mod 7 = 1 mod 7 → (y₁ * 1) ≡ 1 mod 7 -→ y₁ = 1.
y₂ = 77^-1 mod 9 = 5 mod 9 → (y₂ * 5) ≡ 1 mod 9 -→ y₂ = 2
y₃ = 63^-1 mod 11 = 8 mod 9 → (y₃ * 8) ≡ 1 mod 11 -→ y₃ = 7
Hệ phương trình có nghiệm duy nhất:

x ≡ (a₁.M₁.y₁ + a₂.M₂.y₂ + a₃.M₃.y₃) (mod M) (*)

Bước 4. Thay vào (*) ta có nghiệm của hệ phương trình đã cho là:

x = (5.99.1 + 7.77.2 + 9.63.7) mod 7623 hay x = (495 + 1078 + 3969) mod 7623
5542 mod 7623 → x = 5542

Admin đã viết:V. Cho ma trận vuông cấp n (n ≥ 2). Xây dựng thuật toán để đưa ra các phần tử nhỏ nhất, trên các đường chéo song song như hình vẽ:
[You must be registered and logged in to see this image.]

Lời giải:

trangmeomeo đã viết:

Admin đã viết:Đề tuyển sinh cao học Toán Rời rạc năm 2010

II. Giải hệ phương trình đồng dư
x ≡ 5 (mod 7)
x ≡ 7 (mod 9)
x ≡ 9 (mod 11)
Lời giải:Ta có các số (7, 9), (7, 11), (9, 11) là nguyên tố cùng nhau từng đôi một, nên có thể áp dụng luôn định lý đồng dư Trung Quốc.
Ta có:
a₁ = 5, a₂ = 7, a₃ = 9
m₁ = 7, m₂ = 9, m₃ = 11
1) Tính giá trị của M = 7 x 9 x 11 = 7623
2) Tính giá trị của
M₁ = 9 x 11 = 99
M₂ = 7 x 11 = 77
M₃ = 7 x 9 = 63
3) Tính các giá trị nghịch đảo y của từng M. Ta có (Tính trong bảng, để được kết quả):
y₁ = 99^-1 mod 7 = 1 mod 7 → (y₁ * 1) ≡ 1 mod 7 -→ y₁ = 1.
y₂ = 77^-1 mod 9 = 5 mod 9 → (y₂ * 5) ≡ 1 mod 9 -→ y₂ = 2
y₃ = 63^-1 mod 11 = 8 mod 9 → (y₃ * 8) ≡ 1 mod 11 -→ y₃ = 7
Hệ phương trình có nghiệm duy nhất:

x ≡ (a₁.M₁.y₁ + a₂.M₂.y₂ + a₃.M₃.y₃) (mod M) (*)

Bước 4. Thay vào (*) ta có nghiệm của hệ phương trình đã cho là:

x = (5.99.1 + 7.77.2 + 9.63.7) mod 7623 hay x = (495 + 1078 + 3969) mod 7623
5542 mod 7623 → x = 5542

Mọi người cho em hỏi: Trong quá trình tính y^-1 mình lập bảng, vậy bảng đó có phải viết vào bài hay không ạ? hay chỉ ghi giá trị của y_i vào bài ?

mrP đã viết:+ N(A∩B) được tính bằng cách gộp aaa = X, bbbb = Y, còn lại là 3 chữ c. Xét bài toán (tính số SUCSSESS ở sách giáo khoa, khi cho 1 chữ X, 1 chữ Y và 3 chữ b) thì số trường hợp là:
C(3,5) * C(2,4) * C(3,3) = 10 trường hợp


- Cái này tính sai rồi nhé

Liệt kê thử xem nhé

Trường hợp 1: X luôn đứng trước Y. Được 10 thằng.

XYCCC
XCYCC
XCCYC
XCCCY
CXYCC
CXCYC
CXCCY
CCXYC
CCXCY
CCCXY


Trường hợp 2: Y luôn đứng trước X. Thêm 10 thằng nữa. Mệt quá chẳng liệt kê nữa đâu. Đảo vị trí X cho Y ở trường hợp 1 là được.


Thực ra công thức của nó là
C(1,5) * C(1,4) * C(3,3) = 20 trường hợp nhé.

Hoặc áp dụng công thức

[You must be registered and logged in to see this link.]