Bài tập đệ quy quay lui trong c năm 2024

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

Tư tưởng

Dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.

Các bước trong việc liệt kê cấu hình dạng X[1...n]:

• Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
• Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]...tiếp tục như vậy cho tới bước:
• ...
• ....
• Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
• Thông báo cấu hình tìm được.

Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu(Depth-First Search).

Mô hình thuật toán

• Mã giả cho thuật toán quay lui.

Backtracking(k) {
  for([Mỗi phương án chọn i(thuộc tập D)]) {
    if ([Chấp nhận i]) {
      [Chọn i cho X[k]];
      if ([Thành công]) {
        [Đưa ra kết quả];
      } else {
        Backtracking(k+1);
        [Bỏ chọn i cho X[k]];
      }
    }
  }
}

Ví dụ: Trò chơi Sudoku

Sudoku là một trò chơi khá phổ biến và chắc ai cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9x9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và còn lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3x3 chính là các số khác nhau từ 1 đến 9. Sau đây là 1 ví dụ về đề bài và lời giải:

Áp dụng quay lui để giải bài toán sudoku. Ý tưởng: Mỗi bước tìm tập các giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán (ở đây chú ý mảng chỉ có kích thước 9×9×9)

void solveSudoku(int S[][9], int x, int y){
    if(y == 9){
        if(x == 8){
            printSolution(S);
            exit(0);
        } else {
            solveSudoku(S, x+1,0);
        }
    } else if(S[x][y] == 0){
        for (int k = 1; k <=9; k++){
            if(checkValid(S,x,y,k)){
                S[x][y] = k;
                solveSudoku(S, x, y+1);
                S[x][y] = 0;
            }
        }
    } else {
        solveSudoku(S,x,y+1);
    }
}
boolean checkValid(int S[][9], int x, int y, int k){
    for(int i = 0; i <9 ; i++){
        if(S[x][i] == k) return false;
    }
    for(int i = 0; i <9 ; i++){
        if(S[i][y] == k) return false;
    }
    int a = x/3, b = y/3;
    for(int i = 3*a; i < 3*a+3; i++){
        for(int j = 3*b; j < 3*b+3; j++){
            if(S[i][j] == k) return false;
        }
    }
    return true;
}

Nhận xét

• -Ưu điểm: Việc quay lui là thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian chạy.

Nhược điểm: Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó mắc phải các nhược điểm sau:

Trong cuộc sống, chúng ta thường thấy hình ảnh về những vật mà bên trong lại chứa một vật khác giống hệt nó, như hình ảnh trong sách giáo khoa Toán lớp 3 cũ, màn hình của streamer khi họ mở cửa sổ ứng dụng live stream, link này, ... Trong khoa học máy tính, ta gọi đó là đệ quy. Trong bài viết này, chúng mình sẽ giúp các bạn hiểu rõ hơn về đệ quy và cách ứng dụng nó trong tin học.

1.1 Khái niệm

Ta gọi một đối tượng là đệ quy (recursion) nếu nó được định nghĩa qua chính nó hoặc một đối tượng cùng dạng với chính nó bằng quy nạp.

Ví dụ:

• Tìm số fibonacci thứ $n$, ta có $fib(n) = fib(n - 1) + fib(n - 2)$

Nếu một bài toán $P$ có lời giải được thực hiện bằng bài toán con $P'$ có dạng giống $P$ thì đó là một giải thuật đệ quy. $P'$ ở đây là một bài toán đơn giản hơn $P$ và không cần đến $P$ để giải nó.

Khi bài toán $P'$ đã tối giản, không thể thực hiện bài toán con đơn giản hơn nữa mà phải có lời giải riêng cho trường hợp này thì ta gọi đó là trường hợp cơ sở.

Ta cũng có thể gọi một hàm là đệ quy nếu hàm đó tự gọi chính nó.

1.2 Cài đặt

Đề bài: cho số tự nhiên $n$ $(n \le 50)$. Hãy tìm số fibonacci thứ $n$.

Cài đặt cơ bản

Nhận xét

Dựa vào tính chất đã nêu trên để xét, ta cần có trường hợp cơ sở là $fib(1)$ và $fib(2)$ (tùy tài liệu). Ở bài viết này chúng mình sẽ chọn $fib(1) = 0$ và $fib(2) = 1$

Code mẫu

long long fib(int n) {

if (n == 1) return 0;
if (n == 2) return 1;
long long fib1 = 0, fib2 = 1, ans;
for (int i = 3; i <= n; i++) {
    ans = fib1 + fib2;
    fib1 = fib2;
    fib2 = ans;
}
return ans;

Đây là một cách khá tốt để giải bài toán này, tuy nhiên ở bài viết này ta đang tìm hiểu về đệ quy, nên ta cũng có thể dùng đệ quy để giải quyết bài toán một cách ngắn gọn hơn.

Cài đặt bằng đệ quy

Để hiểu cách mà đệ quy hoạt động, trước hết hãy xem xét trường hợp $n = 4$, để tính $fib(4)$, ta phải tính qua $fib(2)$ và $fib(3)$, để tính $fib(3)$, ta phải tính qua $fib(2)$ và $fib(1)$, để tính $fib(2)$, ta có $2$ lựa chọn sau:

• Tính qua $fib(0)$ và $fib(1)$
• Thay $fib(2) = 1$, $fib(1) = 0$ vào và tính tiếp.

Lựa chọn thứ nhất có vẻ không khả thi, phần vì ta chưa quy ước $fib(0)$ là bao nhiêu, phần vì cứ tiếp tục thì ta sẽ chẳng biết phải dừng ở đâu cả. Vậy khi thay $fib(1) = 0, fib(2) = 1$ ta đã có thể tính tiếp được $fib(3)$, có $fib(2)$ và $fib(3)$, ta có thể tính tiếp được $fib(4)$.

Phân tích dài dòng nhưng code lại khá đơn giản.

Code mẫu

long long fib(int n) {

if (n == 1) return 0;           // nếu đang xét đến số fibonacci thứ 1
if (n == 2) return 1;           // hoặc 2 thì trả về 0 hoặc 1
return fib(n - 2) + fib(n - 1); // nếu không thì trả về tổng số thứ n - 2 và n - 1

1.3 Ứng dụng

Ưu điểm mà chúng ta thấy ngay được của việc sử dụng đệ quy là viết code ngắn gọn hơn. Ở một số bài toán lớn, việc không sử dụng đệ quy sẽ làm bài giải của chúng ta cồng kềnh hơn rất nhiều, ví dụ khi duyệt cây và đồ thị.

Nhược điểm dễ thấy là khi không tính toán độ phức tạp hoặc không sử dụng các kỹ thuật lưu trữ dữ liệu, giải bằng đệ quy đôi khi sẽ tốn thời gian chạy và bộ nhớ vô cùng lớn!

Ngoài ra ta còn dùng đệ quy cho hầu hết các bài toán sử dụng giải thuật quay lui dưới đây.

2. Quay lui

2.1 Khái niệm

Thuật toán quay lui (backtracking) dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.

Việc thử hết toàn bộ khả năng khiến cho giải thuật này còn có tên gọi khác là vét cạn.

2.2 Cài đặt

Một hàm quay lui thông thường có cấu trúc như sau:

void backtrack(int pos) {

// Trường hợp cơ sở
if () {
    
    return;
}
//Phần đệ quy
for (){
    
    backtrack(pos + 1);
    
}

Việc thêm giá trị mới vào tập đang xét rồi cuối cùng xoá bỏ nó ra khỏi tập giải thích cho tên gọi "quay lui" của thuật toán. Đó là việc khôi phục lại trạng thái cũ của tập hợp sau khi kết thúc việc gọi đệ quy.

Cụ thể hơn, ta hãy làm một bài tập kinh điển về quay lui.

Đề bài: cho số tự nhiên $n$ $(n \le 20)$. Hãy sinh tất cả xâu nhị phân có độ dài $n$. Ví dụ: với $n = 3$, ta có danh sách các xâu nhị phân $000,001,010,011,100,101,110,111$.

Cách giải bài này theo tư tưởng quay lui như sau: ta xây dựng từng ký tự cho từng xâu trong danh sách. Ở ký tự tiếp theo, ta sử dụng xâu đã xây dựng trước đó và tiếp tục chọn. Bạn đọc có thể xem ảnh dưới để hiểu một cách trực quan cho trường hợp $n = 3$

Nguồn ảnh: VNOI Code tham khảo

int n; string cur; void gen(int i) {

if (i > n) {                        // xâu đã xây dựng xong
    cout << cur << '\n';
    return;
}
for (char c = '0'; c <= '1'; c++) { // chọn từng trường hợp khi xây dựng
    cur.push_back(c);
    gen(i + 1);                     // với trường hợp đã chọn, xây dựng ký tự tiếp theo
    cur.pop_back();                 // bỏ ký tự này đi
}

cin >> n;
cur = "";
gen(1);
return 0;

Ta cũng có thể giải bài này mà không cần dùng đệ quy bằng cách sử dụng các thao tác trên bit. Phần này chúng mình nhường bạn đọc tìm hiểu.

Đề bài: cho $n$ quả táo $(n \le 20)$, quả thứ $i$ có khối lượng là $a_i$. Hãy tìm cách chia số quả táo này vào $2$ tập sao cho chênh lệch khối lượng là nhỏ nhất.

Ý tưởng: Với quả táo thứ $i$, ta thử thêm nó vào tập $1$ hoặc tập $2$ và xét đến quả táo tiếp theo. Khi đã đủ $n$ quả táo, ta tính độ chênh lệch và lấy $min$.

Code tham khảo

int n; vector weights; int recurse_apples(int index, int sum1, int sum2) { // Khi đã đủ n quả táo

if (index == n) { 
    return abs(sum1 - sum2);
}
return min(recurse_apples(index + 1, sum1 + weights[index], sum2),   // thêm vào tập 1
       recurse_apples(index + 1, sum1, sum2 + weights[index]));  // thêm vào tập 2

cin >> n;
weights.resize(n);
for (int i = 0; i < n; i++) cin >> weights[i];
// Bắt đầu với 0 quả táo ở cả 2 tập
cout << recurse_apples(0, 0, 0);
return 0;

2.3 Ứng dụng

Ta dùng quay lui ở những bài toán cần thử toàn bộ khả năng để tìm kết quả tốt nhất. Đây là một cách hiệu quả khi gặp những bài toán có bộ dữ liệu lớn nhưng số trường hợp có thể xảy ra lại nhỏ.

Trong lập trình thi đấu, khi gặp những bài toán phức tạp không thể đưa ngay lời giải tối ưu, ta có thể dùng quay lui để hiểu được bản chất của những trường hợp nhỏ, từ đó xây dựng lời giải cho bài toán tổng quát.

Đây cũng là cách thường dùng để ăn điểm khi không thể tìm được lời giải tổng quát trong những kỳ thi.