Các bài toán đơn giản về quay lui năm 2024
Bây giờ, tôi sẽ giới thiệu tới các bạn một số bài toán ví dụ kinh điển về giải thuật quay lui. Hãy cùng nhau phân tích chúng và đối chiếu lại với phương pháp chung ở bài viết trước để hiểu rõ hơn về lý thuyết phương pháp nhé! Show 1. Bài toán xếp hậuĐề bàiMột bàn cờ vua n×nn \times n đang để trống. Cần đặt nn quân hậu khác nhau vào bàn cờ vua sao cho không có hai quân hậu nào tấn công được nhau, biết rằng hai quân hậu sẽ tấn công nhau nếu như chúng đứng cùng hàng, cùng cột hoặc cùng đường chéo. Input:
Ràng buộc:
Output:
Ý tưởngTrong bài toán xếp hậu, nghiệm có thể được biểu diễn dưới dạng một vector {x1,x2,...,xn}\{x_1, x_2,..., x_n\} thỏa mãn ba điều kiện sau:
Vậy tựu chung lại, khi đã xây dựng được vector nghiệm {x1,x2,...,xi−1},\{x_1, x_2,..., x_{i - 1}\}, thì xix_i tiếp theo được chọn phải thỏa mãn các điều kiện dưới đây: {xi≠xjj−xj≠i−xjj+xj≠i+xi;∀j:1≤j≤i−1\begin{cases}x_i \ne x_j \\ j - x_j \ne i - x_j \\ j + x_j \ne i + x_i \end{cases}; \forall j: 1 \le j \le i - 1 Để xác định được tập SiS_i là các ứng cử viên cho thành phần xi,x_i, ta có thể thực hiện bằng cách sử dụng các mảng đánh dấu để chương trình trở nênn đơn giản hơn. Cụ thể, khi đặt một quân hậu jj vào ô (j,xj),(j, x_j), ta sẽ đánh dấu luôn cột xj,x_j, đường chéo chính có số hiệu j−xjj - x_j và đường chéo phụ có số hiệu j+xj,j + x_j, thể hiện rằng trên cột này và các đường chéo này đã có một quân hậu. Độ phức tạp của giải thuật sẽ là O(nn),O(n^n), do ta có nn thành phần cần sinh và mỗi thành phần lại có nn khả năng. Cài đặtDưới đây là chương trình cài đặt bằng mô hình đệ quy.
2. Tổ hợp chập kk của nnĐề bàiCho một tập gồm nn số nguyên dương {1,2,3,...,n}\{1, 2, 3,..., n\}. Một tổ hợp chập kk của nn là một cách chọn ra kk phần tử bất kỳ trong tập hợp, các phần tử không được lặp lại và không quan trọng về thứ tự. Hãy tìm tất cả các tổ hợp chập kk của n?n? Input:
Ràng buộc:
Output:
Sample Input:
Sample Output:
Ý tưởngNghiệm của bài toán có thể được mô tả dưới dạng một tập các thành phần {x1,x2,...,xk}\{x_1, x_2,..., x_k\} thỏa mãn các điều kiện sau:
Ta cần tạo ra kk thành phần của nghiệm, mỗi thành phần có thể có tối đa nn giá trị. Độ phức tạp của giải thuật sẽ rơi vào khoảng O(kn)O(k^n). Cài đặt:
3. Chỉnh hợp không lặp chập kk của nnĐề bàiCho hai số nguyên nn và kk. Một chỉnh hợp không lặp chập kk của nn là một cách chọn ra kk phần tử trong nn và có xét tới tính thứ tự. Yêu cầu: Hãy liệt kê ra các chỉnh hợp không lặp chập kk của nn phần tử 1,2,…,n1, 2, \dots, n theo thứ tự từ điển? Input:
Ràng buộc:
Output:
Sample Input 1:
Sample Output 1:
Sample Input 2:
Sample Output 2:
Ý tưởngDễ thấy, nghiệm của bài toán vẫn có thể đưa về biểu diễn dưới dạng một tập các thành phần {x1,x2,...,xk}\{x_1, x_2,..., x_k\} thỏa mãn các điều kiện sau:
Do chỉnh hợp khác với tổ hợp ở chỗ mỗi chỉnh hợp đều xét tới tính thứ tự, nên ta sẽ không cần ràng buộc xi Độ phức tạp giải thuật là O(nk),O(n^k), do mỗi thành phần ta vẫn phải thử chọn trong nn giá trị. 4. Cây ATMĐề bàiMột khách hàng muốn rút số tiền TT từ một cây ATM bên đường. Bên trong cây ATM hiện đang có nn tờ tiền có mệnh giá a1,a2,…,ana_1, a_2,…, a_n. Hãy tìm một cách trả tiền của máy ATM cho khách hàng? Input:
Ràng buộc:
Output:
Sample Input:
Sample Output:
0 Ý tưởngTa biểu diễn nghiệm của bài toán dưới dạng một dãy nhị phân 0−1,0 - 1, trong đó bit thứ ii bằng 11 nếu tờ tiền thứ ii được sử dụng để trả tiền, bằng 00 trong trường hợp ngược lại. Tập {x1,x2,...,xn}\{x_1, x_2,..., x_n\} là nghiệm nếu: {0≤xi≤1;∀i:1≤i≤n.x1×a1+x2×a2+⋯+xn×an=T.\begin{cases}0 \le x_i \le 1; \forall i: 1 \le i \le n. \\ x_1 \times a_1 + x_2 \times a_2 + \cdots + x_n \times a_n = T.\end{cases} Độ phức tạp của giải thuật là O(2n),O(2^n), do mỗi thành phần xix_i có thể ở một trong hai trường hợp 00 hoặc 11. Cài đặt
1 5. Hành trình của quân mãĐề bàiTrên bàn cờ vua 8×8,8 \times 8, mỗi bên sở hữu hai quân mã (knights). Cách di chuyển của quân mã trên bàn cờ giống hình chữ
5, được mô tả theo như hình vẽ dưới đây: Mở rộng bài toán một chút, xét bàn cờ vua kích thước n×nn \times n với các hàng được đánh số từ 11 tới nn từ trên xuống dưới, các cột được đánh số từ 11 tới nn từ trái qua phải. Hãy tìm một hành trình cho quân mã di chuyển từ ô (1,1),(1, 1), đi qua tất cả các ô trên bàn cờ, mỗi ô đúng một lần? Input:
Ràng buộc:
Output:
Sample Input:
2 Sample Output:
3 Ý tưởngTổng số bước đi cần sử dụng là n×n,n \times n, nhưng các bước đi này lại ở trên một ma trận có hàng cột. Vì vậy, vector nghiệm của bài toán sẽ ở dạng một tập các tọa độ hàng cột: {(x1,y1),(x2,y2),...,(xn×n,yn×n)}\big\{(x_1, y_1), (x_2, y_2),..., (x_{n \times n}, y_{n \times n})\big\} thỏa mãn các điều kiện sau:
Để cho đơn giản, chúng ta có thể biểu diễn nghiệm của bài toán bằng một ma trận visited[x][y],\text{visited}[x][y], mỗi ô sẽ lưu một số nguyên dương là số thứ tự bước đi của quân mã khi tới ô đó. Khởi đầu từ ô (1,1),(1, 1), thử tất cả các trường hợp có thể di chuyển đến trên bàn cờ từ một ô (x,y)(x, y) bất kỳ và đánh dấu lại số thứ tự của bước đi trên vị trí visited[x][y]\text{visited}[x][y]. Các bạn cần sử dụng thêm một biến step_used\text{step\_used} để kiểm soát số bước đi đã thực hiện được, nếu như nó bằng n×nn \times n nghĩa là bài toán đã có nghiệm, lúc đó chỉ cần in ra ma trận visited\text{visited} là biết cách đi của quân mã. Ta có tổng cộng n×nn \times n thành phần cần sinh, mà mỗi thành phần lại có thể có 88 khả năng di chuyển, vậy độ phức tạp của giải thuật trong trường hợp tệ nhất là O(8n2)O(8^{n^2}). Trong code dưới đây, tôi sử dụng thêm một mảng step[8][2]step[8][2] để mô tả các phương án di chuyển tới 88 hướng của một quân mã. Dùng mảng này sẽ thuận tiện hơn để xét các hướng đi. Kết thúc quá trình quay lui, nếu không có phương án nào được in ra thì kết quả sẽ là −1-1. Cài đặt
4 IV. Nhận xét về phương phápNhìn chung, quay lui là một phương pháp chạy khá chậm, do nó phải xét hết mọi trường hợp có thể của kết quả và tìm ra đáp án đúng. Tuy nhiên, lợi thế của phương pháp này là kết quả luôn luôn chính xác 100%100\%. Ngoài ra, từ phương pháp quay lui, người ta có thể cài đặt được những cải tiến như Nhánh và cận để loại bỏ bớt các trường hợp không cần thiết, giảm độ phức tạp tính toán. Tuy nhiên, phần lớn các bài toán sử dụng giải thuật quay lui đều sẽ cho ra độ phức tạp cấp số mũ. Do đó, nó vẫn có những nhược điểm như sau:
Vì những điều trên, giải thuật quay lui thường chỉ phù hợp với những bài toán có kích thước nhỏ, đặc biệt là trong lập trình thi đấu. |