BÀI TẬP TOÁN RỜI RẠC BÀI TOÁN ĐẾM: ( Ra 1 bài bình thường , 1 bài đếm nâng cao ) Một nhóm sinh viên gồm n nam và n nữ. Có bao nhiêu cách xếp thành một hàng ngang sao cho nam nữ đứng xen kẽ nhau? 2.1. 2.2. Một tập hợp có 10 phần tử có bao nhiêu tập con với số phần tử lẻ? a. Có bao nhiêu số có n chữ số mà có m chữ số đầu và m chữ số cuối tương ứng giống nhau. (n>2m>2, n,m thuộc N). b. Ứng dụng tính số chữ số có 10 chữ số mà 3 chữ số đầu và 3 chữ số cuối tương ứng giống nhau 2.3. Xét 3 chuỗi ký tự trên tập mẫu tự {a, b, c} ( với a < b < c) : s1 = ac, s2 = aacb, s3 =aba a. Hãy sắp xếp chúng theo thứ tự tăng đối với thứ tự từ điển. b. Cho biết giữa s1 và s3 có bao nhiêu chuỗi ký tự có chiều dài 6 2.4. Một tổ có 13 người: a) Có bao nhiêu cách chọn 10 người đi làm một công việc định sẵn? Biết rằng mọi người đều làm được công việc đó. b) Có bao nhiêu cách chọn 10 người để làm 10 việc khác nhau? Biết rằng mọi người đều làm được mọi việc như nhau. c) Có bao nhiêu cách chọn 10 người sao cho có ít nhất 1 nữ? Biết trong tổ có 3 nữ. 2.5. Có bao nhiêu xâu nhị phân có độ dài 10 nếu trong xâu có: a) b) c) d) Đúng 3 số 0. Ít nhất 3 số 1. Số các số 0 bằng số các số 1. Có ít nhất 3 số 0 và ít nhất 3 số 1. 2.6. Có bao nhiêu biển đăng ký xe. Biết mỗi biển gồm 3 chữ cái tiếng Anh khác nhau và tiếp đến là 3 chữ số khác nhau? 2.7. Có bao nhiêu cách phân công 3 công việc cho 5 người làm, nếu 1 người có thể làm được cả 3 việc. Một “con lợn tiết kiệm” có 50 đồng xu. Có thể có bao nhiêu tổ hợp khác nhau các đồng xu: 200đ, 500đ, 1000đ, 2000đ, 5000đ trong đó? 2.8. Tìm số cách xếp 30 viên bi giống nhau vào 5 hộp khác nhau sao cho hộp 1 có nhất 5 bi, biết rằng hộp 2 và hộp 3 không chứa quá 6 bi. 2.9. 2.10. Có 100 viên bi hoàn toàn giống nhau. Có bao nhiêu cách để xếp các viên bi vào 3 cái hộp? biết mọi cái hộp đều có thể chứa đến 100 viên bi. 2.11. Phương trình: x1 + x2 + x3 + x4 = 17 có bao nhiêu nghiệm nguyên không âm? Tìm số nghiệm nguyên không âm của phương trình x1 + x2 + x3 + x4 =20 thỏa mãn x1 ≤ 3; x2 ≥ 2; x3 > 4 2.12. Phương trình: x1 + x2 + x3 + x4 + x5 = 21 có bao nhiêu nghiệm nguyên không âm sao cho: a) x1 1 ; c) 0 x1 10 ; b) xi 2 với i = 1, 2, 3, 4, 5 d) 0 x1 3 và 1 x2 4 và x3 15 ~ by Nô Riven 2.13. Tìm số nghiệm nguyên không âm của phương trình x1 + x2 +x3 +x4 = 40 trong các trường hợp sau: a) x1 ≥ 3, x2 ≤ 4 b) x1 > 3, x2 < 4 c) 2 ≤ x1 ≤ 8, x2 ≤ 4, x3 > 3, x4 < 6 . 2.14. Có bao nhiêu xâu có đủ các chữ cái trong từ MISSISSIPPI ? 2.15. Có bao nhiêu cách phát 100 phần thưởng giống nhau cho 60 học sinh. Mỗi học sinh có ít nhất 1 phần thưởng. 2.16. Mỗi khóa gồm 5 vòng số ghi 0, 1, 2, …..,9. Mỗi dãy 5 chữ số cho một cách để mở khóa. Có bao nhiêu khóa có cách mở khác nhau. 2.17. Có bao nhiêu cách xếp kn vật khác nhau thành k nhóm, mỗi nhóm có n vật? 2.18. Có bao nhiêu bộ ba số nguyên không âm ( x1, x2 , x3 ) thỏa điều kiện: x1 + x2 +x3 ≤15 , x1>2, x2 < 4 2.19. Hỏi có bao nhiêu số có 10 chữ số mà 3 chữ số đầu và 3 chữ số cuối tương ứng giống nhau? 2.20. Có bao nhiêu xâu khác nhau có 7 hoặc nhiều hơn các ký tự có thể lập được từ các chữ cái của từ NONGNGHIEP ? 2.21. Có bao nhiêu xâu nhị phân khác nhau gồm 6 chữ số 0 và 8 chữ số 1? 2.22. Một đề thi có 10 câu hỏi. Có bao nhiêu cách gán điểm cho các câu hỏi nếu tổng số điểm là 100 và mỗi câu được ít nhất 5 điểm? 2.23. Bất phương trình: x1 + x2 + x3 ≤ 11 có bao nhiêu nghiệm nguyên không âm? Gợi ý: Bổ sung thêm biến phụ x4 sao cho: x1 + x2 + x3 + x4 = 11. 2.24. Trong không gian Oxyz một con bọ di chuyển bằng cách nhảy từng bước, mỗi bước 1 đơn vị theo hướng hoặc truc Ox, hoặc trục Oy, hoặc trục Oz và không được nhảy giật lùi. Tính số cách để con bọ đó có thể di chuyển từ gốc tọa độ (0, 0, 0) đến điểm (4, 3, 5). NGUYÊN LÝ BÙ TRỪ: ( Bổ trợ làm bài toán đếm nâng cao ) 2.25. Hãy tìm số phần tử của ABC nếu mỗi tập A, B, C đều có 100 phần tử và nếu các tập hợp A, B, C thỏa mãn: a) Đôi một rời nhau. b) Có 50 phần tử chung của mỗi cặp tập và không có phần tử nào chung của cả 3 tập hợp. c) Có 50 phần tử chung của mỗi cặp tập và 25 có phần tử chung của cả ba tập hợp. 2.26. Kiểm tra 270 sinh viên mới tốt nghiệp của một trường đại học. Kết quả cho thấy có 64 sinh viên thành thạo tiếng Anh, 94 sinh viên thành thạo tiếng Pháp, 108 sinh viên thành thạo vi tính văn phòng, 26 sinh viên vừa thành thạo tiếng Pháp vừa thành thạo vi tính, 28 sinh viên vừa thành thạo tiếng Anh vừa thành thạo vi tính, 22 sinh viên vừa thành thạo tiếng Pháp vừa thành thạo tiếng Anh và 11 sinh viên thành thạo cả 3 thứ (tiếng Anh, tiếng Pháp và vi tính). Hỏi trong số 270 sinh viên đó có bao nhiêu người không biết cả 3 thứ kể trên? 2.27. Có bao nhiêu xâu nhị phân có độ dài 8 và không chứa 6 số 0 liên tiếp? 2.28. Có bao nhiêu số nguyên dương không vượt quá 100 và hoặc là số lẻ hoặc là số chính phương. 2.29. Có bao nhiêu hoán vị của 10 chữ số nguyên dương đầu tiên hoặc là bắt đầu bằng ba số 987, hoặc là chứa các số 45 ở vị trí thứ 5 và thứ 6, hoặc là kết thúc bằng 3 số 123. GIẢI CÁC HỆ THỨC TRUY HỒI: ( Chắc chắn 1 câu cho điểm ) 2.30. Số lượng một loài sinh vật sẽ tăng gấp ba sau mỗi giờ. ~ by Nô Riven a) Lập công thức truy hồi tính số lượng vi sinh vật đó sau n giờ. b) Nếu lúc đầu có 100 con thì sau 10 giờ sẽ có bao nhiêu con? a) Tìm hệ thức truy hồi tính số cách đi lên n bậc cầu thang của một người. Biết người đó có thể bước mỗi lần một hoặc hai bậc. b) Có bao nhiêu cách để người đó đi lên một cầu thang có 8 bậc? 2.31. ( Khả năng không ra dạng này ) 2.32. Chứng minh rằng các số Fibonacci thoả mãn hệ thức truy hồi: fn = 5fn – 4 + 3fn – 5 , n 5; f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3. Dùng hệ thức này chứng minh rằng f5n chia hết cho 5 với n = 1, 2, 3, ... ( Khả năng không ra dạng này ) 2.33. Tìm hệ thức truy hồi tính số xâu nhị phân có độ dài n và: a) Không có 2 số 0 liên tiếp. b) Có 2 số 0 liên tiếp. Tính cụ thể số xâu nhị phân thoả mãn điều kiện a hoặc b nếu n = 5 ( Khả năng không ra dạng này ) 2.34. Một người đầu tư 100 triệu đồng vào một cơ sở sản xuất. Sau 1 năm người đó được hai khoản lãi: Khoản thứ nhất là 20% tổng số tiền trong năm cuối; Khoản thứ hai là 13% của tổng số tiền có trong năm trước đó. a) Tìm công thức truy hồi tính {Pn}, trong đó Pn là tổng số tiền có vào cuối năm thứ n. b) Tìm công thức trực tiếp tính Pn. Giả thiết rằng người đó không rút bất cứ khoản tiền nào trong cả n năm dó. 2.35. 2.36. Với các tấm lát kích thước 12 và 22 có thể lát một bảng 2n bằng bao nhiêu cách? 2.37. Giải các hệ thức truy hồi sau: a) an = 5an – 1 – 6an – 2 , n 2; a0 = 1, a1 = 0. b) an = 4an – 1 – 4an – 2 , n 2; a0 = 6, a1 = 8 c) an = ( an -2) /4 , , n 2; a0 = 1, a1 = 0 d) an = 7an – 2 + 6an – 3 , a0 = 9, a1 = 10, a2 = 32. e) an = 2an – 1 + 5a n – 2 – 6an – 3 , a0 = 7, a1 = - 4, a2 = 8. BÀI TOÁN TỒN TẠI: Chắc chắn ra 1 câu ( 1 – 2 đ ) 3.1. Cho n là một số nguyên dương. Chứng minh rằng trong mọi tập hợp có n số nguyên dương liên tiếp có đúng một số chia hết cho n. Cho (xi, yi, zi), i = 1, 2, ..., 9 là một tập hợp gồm 9 điểm khác nhau có toạ độ nguyên trong không gian Oxyz. Chứng minh rằng các điểm giữa của đường nối của 2 trong 9 điểm đó có ít nhất một điểm có toạ độ nguyên. 3.2. Trong mặt phẳng xOy lấy ngẫu nhiên 5 điểm tọa độ nguyên. Chứng tỏ rằng có ít nhất một trung điểm của các đoạn nối chúng có tọa độ nguyên 3.3. Trong một mặt phẳng có 17 điểm phân biệt được nối với nhau từng đôi một bởi các đoạn thẳng màu xanh, hoặc màu đỏ, hoặc màu vàng. CMR luôn tồn tại ba điểm nối với nhau bởi các đoạn thẳng cùng màu 3.4. Một mạng máy tính có n (n>1) máy tính. Mỗi máy tính được nối trực tiếp hoặc không nối với các máy khác. CMR có ít nhất hai máy tính mà số các máy tính khác nối với chúng là bằng nhau 3.5. Một võ sĩ quyền anh thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ đấu ít nhất một trận, nhưng toàn bộ không quá 125 trận. Chứng tỏ rằng có những giờ liên tiếp đã đấu 24 trận 3.6. ~ by Nô Riven Trong một hộp kín có 10 viên bi màu đỏ và 10 bi màu xanh. Một người lấy ngẫu nhiên các viên bi trong bóng tối. Hỏi người đó cần lấy ít nhất bao nhiêu viên bi để chắc chắn lấy được ít nhất 2 viên bi cùng màu. 3.7. 3.8. Chứng tỏ rằng trong 5 số chọn từ 8 số nguyên dương đầu tiên chắc chắn có một cặp có tổng bằng 9 Có 12 cầu thủ bóng đá mặc áo mang số từ 1 đến 12 dứng thành một vòng tròn giữa sân. Chứng minh rằng luôn luôn tìm được 3 người đứng liên tiếp nhau có tổng các số trên áo ít nhất bằng 20. 3.9. 3.10. a) Trong phòng có 6 máy tính. Mỗi máy được nối trực tiếp hoặc không nối với các máy khác. Hãy chứng tỏ rằng có ít nhất hai máy có cùng số kết nối với các máy khác hoặc có ít nhất hai máy không được nối với máy khác. b) Một mạng máy tính có 6 máy. Mỗi máy được nối trực tiếp với ít nhất một máy khác. Hãy chứng tỏ rằng có ít nhất hai máy có cùng số kết nối với các máy khác. PHƯƠNG PHÁP SINH, TRUY HỒI: ( 1 câu dưới dạng thuật toán hoặc viết code ) - Phần này các bạn ôn ở trong slide thầy, một số chưa có thì trên slide mình gửi. Có thể chia đề chẵn lẽ hoặc chỉ ra pp Sinh ~ by Nô Riven Show ~ by Nô Riven Trong phần đầu Lập trình và tư duy thuật toán sáng tạo (Kì 1) Mình đã giới thiệu về khái niệm, lý do bạn cần sử dụng thuật toán và những điều cơ bản đề giải quyết một bài toán. Và giờ thì chúng ta bắt đầu tìm hiểu xem thế giới "diệu kỳ" này có gì nhé. Nội dung "Kì 2"
Chuyện là Tí rất thích chơi trò xì tố 5 cây với bạn bè nhưng do tình hình giãn cách xã hội nên Tí đã quyết định viết một cong bot để có thể chơi cùng mình trong khoảng thời gian rảnh rỗi không biết làm gì. Luật chơi như sau: Mỗi người có 5 quân bài, hãy:
 Trước khi đi chi tiết hơn về giải thuật, mình sẽ "Tóm tắt một số kiến thức về đại số tổ hợp ứng dụng trong tin học" để các bạn tiện theo dõi các nội dung tiếp theo Hoán vị
Ví dụ: với tập A = {1, 2, 3} có tất cả 6 hoán vị của tập gồm 3 phần tử là: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1Gọi Pₙ là số lượng hoán vị của n phần tử, thì ta có công thức tính số hoán vị
Giải thích:
Các bạn có thể theo dõi hình ảnh minh họa để hiểu hơn về tư tưởng. Hoán vị vòng quanh
Ví dụ: Với tập A = {1, 2, 3}, chỉ có 2 hoán vị vòng quanh là {1, 2, 3} và {1, 3, 2} Các hoán vị như {2, 3, 1} và {3, 1, 2} cũng chính là hoán vị {1, 2, 3} với điểm bắt đầu khác! Gọi Qₙ là số hoán vị vòng quanh của n phần tử, ta có công thức
Do có n hoán vị bình thường sẽ cho ra cùng 1 hoán vị vòng quanh (với điểm bắt đầu khác nhau nhưng thứ tự sắp xếp giống nhau)
Hoán vị lặp
Ví dụ: Có bao nhiêu hoán vị của các chữ cái trong chuỗi S = "AABC" Nhận xét: Chuỗi S có 4 phần tử, nếu 4 phần tử này khác nhau thì ta sẽ có P(4) = 4! = 24 hoán vị Tuy nhiên do chữ A xuất hiện 2 lần, nên các hoán vị của 2 chữ A này (2!=2 hoán vị) sẽ không được tính! Vì vậy số lượng hoán vị trong trường hợp này sẽ là 4! / 2! = 12 hoán vị. Ta có thể dễ dàng liệt kê 12 hoán vị này: AABC, AACB, ABAC, ABCA, ACAB, ACBA, BAAC, BACA, BCAA, CAAB, CABA, CBAA.Ta có công thức tính hoán vị lặp:
Trong đó:
Chỉnh hợp (Permutation)
Ví dụ: với tập A = {1, 2, 3, 4}, các chỉnh hợp chập 2 của A sẽ là: 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3Giải thích: Với k phần tử trong một chỉnh hợp,
Do vậy, số lượng các chỉnh hợp chập k của n phần tử là:
Lưu ý: với k = n, các chỉnh hợp trở thành các hoán vị!
Chỉnh hợp lặp (Permutation with repetition)
Ví dụ: với tập A = {1, 2, 3}, các chỉnh hợp lặp chập 2 của A sẽ là: 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3Mỗi phần tử trong số k phần tử của chỉnh hợp lặp đểu có thể nhận n giá trị khác nhau (do các giá trị có thể lặp lại). Vì vậy, số lượng các chỉnh hợp lặp chập k của n phần tử sẽ là:
Tổ hợp (Combination)
Ví dụ: với tập A = {tennis, đạp xe, bóng chày}, các tổ hợp chập 2 của A sẽ là:
Nhận xét: Mỗi tổ hợp chập k phần tử có thể tạo ra k! chỉnh hợp chập k phần tử (bằng cách hoán vị k phần tử của tổ hợp này). Do vậy, số lượng tổ hợp chập k có thể dễ tính tính được thông qua số lượng chỉnh hợp như sau:
Tổ hợp lặp (Combination with repetition)
Ví dụ: với tập A = {1, 2, 3}, các tổ hợp lặp chập 2 của A sẽ là: 1 1 1 2 1 3 2 2 2 3 3 3Mỗi tổ hợp lặp chập k của n phần tử có thể biểu diễn bằng một dãy gồm k dấu ? (ứng với k phần tử) và n-1 thanh | (để chia k dấu ? thành n ngăn, ứng với n giá trị). Ở ví dụ trên, n = 3 và k = 2, các tổ hợp lặp chập 2 của tập A sẽ tương ứng với các dãy ? và | như sau: 1 1 -> ??|| 1 2 -> ?|?| 1 3 -> ?||? 2 2 -> |??| 2 3 -> |?|? 3 3 -> ||??Như vậy, số lượng các tổ hợp lặp chập k của n phần tử chính là số cách chọn ra k dấu ? từ dãy n+k-1 ký tự ? và |
Và để minh họa rõ hơn về khái niệm chỉnh hợp (Permutation), chỉnh hợp lặp (Permutation with repetition), tổ hợp (Combination), tổ hợp lặp (Combination with repetition). Mình sẽ sử dụng một hình ảnh minh họa
Một số bài toán ví dụBài toán 1: Có bao nhiêu cách xếp 5 người thành một hàng? *Lời giải: P(5) = 5! = 120 cách Bài toán 2: Từ các chữ số 0, 1, 2, 3, 4 có thể lập được bao nhiêu số tự nhiên có 5 chữ số khác nhau Lời giải: Xét chữ số có 5 chữ số là abcde Có 4 cách để chọn ra chữ số thỏa mãn đặt vào e (do e ở hàng chục ngàn nên vị trí này phải khác 0). Với 4 vị trí còn lại, ta còn 4 chữ số và có 4!=24 hoán vị của chúng. Vậy có 4 × 4! = 96 số Bài toán 3: Có bao nhiêu cách sắp xếp 5 người vào một bàn tròn có 5 chỗ, biết hai cách sắp xếp là khác nhau nếu từ cách sắp xếp thứ nhất ta không thể thu được cách xếp thứ hai khi xoay cùng chiều tất cả mọi người theo cùng một khoảng cách? Lời giải: Đây chính là số hoán vị vòng quanh của 5 phần tử, tức là 4! = 24 cách. Bài toán 4: Có bao nhiêu hoán vị của chuỗi MISSISSIPPI? Lời giải: Chuỗi trên có 11 ký tự, trong đó có 4 chữ I, 4 chữ S, 2 chữ P và 1 chữ M. Đây chính là ví dụ điển hình của hoán vị lặp, và tổng số hoán vị sẽ là:
Bài toán 5: Có bao nhiêu cách xếp 5 người vào một băng ghế có 7 chỗ? Lời giải: Đây là mô hình của bài toán chỉnh hợp, đáp số chính là số lượng chỉnh hợp chập 5 của 7, tức là: 7! / (7-5)! = 2520 cách Bài toán 6 Có bao nhiêu số tự nhiên có 4 chữ số khác nhau, được tạo thành bởi các chữ số {0, 1, 2, 3, 4, 5}? Lời giải: Có 5 cách chọn chữ số đầu tiên (chữ số này phải khác 0). Còn lại 3 vị trí và 5 chữ số, số cách chọn cho 3 vị trí này chính là số chỉnh hợp chập 3 của 5 chữ số còn lại. Kết quả: 5 × A(3, 5) = 5 × 5! ÷ (5-3)! = 300 số Bài toán 7: Biển đăng kí ô tô có 6 chữ số và 2 chữ cái tiếng Anh, không dùng chữ O và I . Hỏi số lượng ô tô có thể được đăng kí nhiều nhất là bao nhiêu? (Biết bảng chữ cái tiếng Anh gồm 26 chữ cái) Lời giải: Có F(6,10) cách chọn ra 6 chữ số Có F(2, 24) cách chọn ra 2 chữ cái (bảng chữ cái tiếng Anh có 26 chữ cái, trừ đi 2 chữ O và I do dễ nhầm với số 0 và 1). Vậy kết quả là: 10⁶ × 24² = 576.000.000 ôtô Bài toán 8: Một nhóm có 5 nam và 3 nữ. Có bao nhiêu cách chọn ra 3 người sao cho trong đó có ít nhất 1 nữ? Lời giải: Ta có các trường hợp sau: 1 nữ, 2 nam: 3 × C(2, 5) = 30 2 nữ, 1 nam: C(2,3) × 5 = 15 3 nữ: C(3,3) = 1 Tổng cộng: 30 + 15 + 1 = 46 cách Bài toán 9: Có bao nhiêu số có 4 chữ số khác nhau mà các chữ số giảm dần theo chiều từ trái qua phải. Lời giải: Với mỗi cách chọn 4 chữ số khác nhau (từ 10 chữ số 0, 1, ..., 9), ta tạo được thành đúng 1 số có 4 chữ số thỏa mãn yêu cầu. Vậy số lượng các số như vậy sẽ là C(4, 10) = 10! ÷ 4! ÷ (10-4)! = 210 số Bài toán 10: Giả sử có n viên bi giống nhau và m cái hộp (n>m), ta xếp bi vào các hộp. Gọi xᵢ (với i = 1, 2, 3 ...) và m là số bi ở hộp i. Chứng minh rằng: a) Số cách xếp khác nhau n viên bi vào m cái hộp là C(n, m+n-1) b) Trong C(n, m+n-1) cách xếp đó có C(m-1, n-1) cách xếp cho tất cả các hộp đều có bi. Lời giải: a) Ta biểu diễn n cái kẹo bởi n dấu ?, và dùng m-1 vách ngăn | để chia n cái kẹo này vào m hộp. Ví dụ: 3 vạch để chia 9 cái kẹo vào 4 hộp: ??|???||???? (hộp 1 có 2 kẹo, hộp 2 có 3 kẹo, hộp 3 có 0 kẹo, hộp 4 có 4 kẹo) Như vậy, có ***n+m-1*** ký tự (cả ? và |), ta cần chọn ra ***m-1*** vị trí để đặt các vạch | (hoặc n vị trí để đặt các dấu ?), do vậy, số cách xếp sẽ là: C(n, m+n-1) = C(m-1, n+m-1) b) Trong trường hợp mỗi hộp cần có ít nhất một viên kẹo, các vạch | không được đứng cạnh nhau và phải đứng giữa các dấu ?. Có n-1 vị trí giữa các dấu ?, ta cần chọn ra m-1 vị trí để đặt các vạch | Vậy số cách sẽ là C(m-1, n-1) Hệ quả: Từ bài toán trên ta suy ra hai hệ quả thú vị sau:
Và hệ quả này ta lại sinh ra 1 bài toán: Tìm số nghiệm nguyên không âm của phương trình x₁ + x₂ + x₃ + x₄ = 20 thỏa điều kiện x₁ ≤ 3; x₂ ≥ 2; x₃ > 4. Hướng dẫn: Viết lại 3 điều kiện trên thành: x₁ ≤ 3; x₂ ≥ 2; x₃ ≥ 5. Ta sẽ tính số nghiệm của phương trình với điều kiện x₂ ≥ 2; x₃ ≥ 5 (1) Sau đó, trừ đi số nghiệm của cùng phương trình đó với điều ngược của điều kiện thứ nhất, tức là: x₁ ≥ 4; x₂ ≥ 2; x₃ ≥ 5 (2) (1) Đặt y₁=x₁; y₂=x₂-2; y₃=x₃-5; y₄=x₄, bài toàn trở thành tính số nghiệm nguyên không âm của phương trình: y₁ + y₂ + y₃ + y₄ = 13 Theo hệ quả ở trên, số nghiệm là: C(4-1, 4+13-1) = C(3,16) = 560 (2) Đặt y₁=x₁-4; y₂=x₂-2; y₃=x₃-5; y₄=x₄, bài toàn trở thành tính số nghiệm nguyên không âm của phương trình: y₁ + y₂ + y₃ + y₄ = 9 Theo hệ quả ở trên, số nghiệm là: C(4-1, 9+4+-1) = C(3,12) = 220 Kết quả cuối cùng: (1) - (2) = 560 - 220 = 340 Bàn luậnTrong lập trình, một lớp bài toán phổ biến là bài toán liệt kê tất cả các cấu hình của một loại tổ hợp nào đó. Ví dụ: liệt kê các tập hợp con của một tập hợp, liệt kê tất cả các cách xếp hàng, liệt kê các hoán vị của một xâu để tìm hoán vị phù hợp... Để giải lớp bài toán này, chúng ta có nhiều phương pháp giải thuật nhưng đơn giản và phổ biến thì có thể kể đến: Phương pháp sinh (Generation), Thuật toán quay lui (Backtracking),... Và chúng ta sẽ cùng nhau tìm hiểu chi tiết hơn về các thuật toán này trong các kỳ tới nhé. |
