Liệt kê quay lui dãy nhị phân độ dài n

đăng lúc

Bài toán liệt kê các dãy nhị phân độ dài n là bài toán cổ điển dùng để minh họa cho phương pháp sinh và thuật toán quay lui. Trong loạt bài trước mình đã viết về cách giải bài toán này bằng phương pháp sinh. Vì thế trong bài này, mình sẽ viết về cách giải bài toán này sử dụng thuật toán quay lui.

Bài toán liệt kê các dãy nhị phân độ dài n là bài toán cổ điển dùng để minh họa cho phương pháp sinh và thuật toán quay lui. Trong loạt bài trước mình đã viết về cách giải bài toán này bằng phương pháp sinh. Vì thế trong bài này, mình sẽ viết về cách giải bài toán này sử dụng thuật toán quay lui.

Nếu các bạn muốn tham khảo cách giải bài toán này bằng phương pháp sinh thì có thể đọc bài này : Thuật toán sinh các dãy nhị phân có độ dài n



Yêu cầu : Liệt kê tất cả các dãy nhị phân có độ dài n. (dãy nhị phân là dãy chỉ gồm hai số 0 và 1)

Input : nhập vào n - độ dài của chuỗi nhị phân cần in ra.

Output : In ra màn hình tất cả các chuỗi nhị phân có độ dài n nhập từ đầu vào.

ví dụ :

Input : 3

Output : 000   001   010   011   100   101   110   111

Bổ trợ : Để có thể dễ hiểu nhất bài viết này bạn cần hiểu rõ 2 khái niệm quay lui và đệ qui. Bạn có xem video sau đây nếu thấy cần thiết. Video bên dưới mình tìm thấy trên Google và thấy tác giả giải thích khá dễ hiểu và đẩy đủ về hai thuật toán kia.

https://www.youtube.com/watch?v=nootqR6fz6k



Nếu các bạn thấy vẫn chưa thỏa mãn thì có thể tìm kiếm thêm trên Google về : "Đệ quy là gì?", "Quay lui là gì?",... Sẽ có rất nhiều kết quả, trang đã viết về hai thuật này rồi.

Tiếp theo chúng ta sẽ đi tới ý tưởng để giải bài toán này bằng thuật toán quay lui.

Ý tưởng : Trong một dãy nhị phân, tại một vị trí mỗi phần tử có thể nhận một trong hai giá trị 0 và 1. Vì một vị trí có hai khả năng xảy ra và có tất cả n vị trí (n là độ dài một dãy nhị phân) nên sẽ có tất cả 2^n (2 mũ n) dãy nhị phân.

Tưởng tượng như sau : - Vị trí đầu tiên có 2 cách chọn (0 và 1).
                                       - Ứng với mỗi cách chọn vị trí đầu tiên, ta lại có 2 cách chọn cho vị trí thứ hai. (cũng là 0 và 1)
                                       ...

nên ta sẽ có :   2 * 2 * 2 * ..... * 2 = 2^n dãy nhị phân.
                              {có n số 2}

Và cách sử dụng thuật toán quay lui để giải quyết bài toán này cũng y như đoạn "tưởng tượng" trên.

Ta gọi dãy nhị phân là X, và X1, X2, X3,.... Xn là các phần tử từ trái qua phải trong dãy.

Tại vị trí Xi (1 <= i <= n), ta gán cho nó các giá trị mà nó có thể nhận được (ở bài toán này là 0 và 1). Tại mỗi lần gán giá trị cho Xi ta lại gán các giá trị có thể nhận được (là 0 và 1) cho X(i+1),... cứ thế cho hết độ dài của dãy.

Hơi khó hiểu một chút nhỉ. Các bạn hãy xem hình minh họa bên dưới và đọc đoạn giải thích bên dưới hình để dễ hình dung hơn.


Cây nhị phân quay lui.

"Tại mỗi bước gán các giá trị mà nó có thể nhận được. Tại mỗi lần gán giá trị cho Xi thì ta lại gán các giá trị có thể cho X(i+1)"

Các bạn hãy nhìn vào nhánh ngoài cùng bên trái của hình trên (nhánh 000) :



Bước 1 : gán cho X1 = 0;
Bước 2 : gán cho X2 = 0;
Bước 3 : gán cho X3 = 0;

Vì X3 bây giờ là vị trí cuối của dãy nên ta sẽ in ra dãy tìm được là : 000.

Sau đó ta lại gán các giá trị có thể khác cho X3 : X3 = 1;



 Mũi tên màu xanh sáng hơn là hướng đang đi. Các mũi tên màu tối hơn là hướng đã đi qua.

Vì giá trị X3 đã thay đổi nên ta sẽ được 1 chuỗi mới, ta lại in ra màn hình dãy mới tìm được : 001;

Lúc này, X3 đã hết giá trị có thể nhận được, nên ta sẽ quay lui lại bước 2, gán các giá trị có thể khác cho X2 : X2 = 1;



 Mũi tên màu xanh sáng hơn là hướng đang đi. Các mũi tên màu tối hơn là hướng đã đi qua.

Vì X2 (X2 = 1) lúc này chưa phải phần tử cuối dãy, nên ta lại sang bước 3 và gán các giá trị có thể cho X3,..... Cứ thế, làm tương tự như bước 3 phía trên (khi X2 có giá trị bằng 0). Ta lại được 2 chuỗi mới là 010 và 011.

Rồi lại quay lại bước 2 thì đã thấy hết giá trị có thể gán được, ta lại quay về bước 1. Và gán X1 = 1,.....

Đó là thuật toán quay lui để tìm kiếm các dãy nhị phân độ dài n.

Code C minh họa :

#include<stdio.h>
#include<conio.h>

void quayLui(int i, int n, int *X)
{
    int val;    // val la cac gia tri co the gan cho cac vi tri trong X
    for (val = 0; val < 2; val++)      // val co the nhan hai gia tri la : 0 va 1
    {
        X[i] = val;

        if (i == (n-1))         // neu i la phan tu cuoi cua day
        {
            int j;
            for(j = 0; j < n; j ++)         // in ra day so nhi phan moi tim duoc
            {
                printf("%d  ", X[j]);
            }
            printf("\n");
        }

        else              // neu i chua phai phan tu cuoi thi ta se gan gia tri cho phan tu sau i.
        {
            quayLui(i+1, n, X);
        }
    }
}


int main()
{
    int n;
    printf("nhap n : ");     // nhap n
    scanf("%d", &n);

    int X[n];     // khai bao mang X co do dai n - chuoi nhi phan do dai n

    quayLui(0, n, X);  // goi ham xu ly quay lui

    getch();
    return 0;
}



Nếu cần trợ giúp thay thắc mắc về điều gì các bạn có thể comment bên dưới bài viết này nhé. Nếu bài viết hữu ích thì cũng comment nha. 😛😛😛

Chúc các bạn thành công.

Tham khảo tại : Giải thuật và lập trình - Lê Minh Hoàng.

Nội dung chính
    Bài đăng mới hơn Bài đăng cũ hơn