Lượt xem 0 Nhận xét

Liệt kê quay lui các tập con k phần tử

Cập nhật: 05 thg 4, 2018 4:40 CH
Bài toán liệt kê tập con k phần tử là bài toán cổ điển trong loạt bài minh họa về Giải thuật lập trình. Để giải quyết bài toán này, ta có thể dùng phương pháp sinh hoặc thuật toán quay lui. Trong bài này, mình sẽ nói về cách sử dụng thuật toán quay lui để giải quyết bài toán liệt kê các tập con k phần tử.

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 : Liệt kê tập con k phần tử bằng phương pháp Sinh.



Yêu cầu : Cho một tập mẹ gồm n phần tử là các số tự nhiên từ 1 đến n. Hãy liệt kê tất cả các tập con có k phần tử của tập này.

Input : Yêu cầu người dùng nhập vào : n - số phần tử của tập mẹ và k - số phần tử của tập con.

Output : Tất cả tập con k phần tử của tập mẹ.

Ví dụ :

Input : n = 5, k = 3

Output : 123  124  125  134  135  145  234  235  245  345 (Thứ tự này cũng chính là thứ tự các tập con được in ra khi chạy chương trình.)

- Các bạn có thể đọc bài : Liệt kê quay lui dãy nhị phân độ dài n trước khi đọc bài này để có thể hiểu thế là quay lui và dễ dàng hiểu được ý tưởng giải quyết bài toán hiện tại. Vì bài toán hiện tại chỉ là dạng nâng cao hơn một chút so với bài toán Liệt kê quay lui dãy nhị phân độ dài n.

Nhận xét : - Gọi X là một phần tử cần liệt kê ra của tập con k phần tử. (suy ra X có k vị trí.)
                    - Xi là một vị trí của phần tử X. (1<= i <= k)

(Ví dụ : 234 là một phần tử cần liệt kê ra của bộ tập con 3 phần tử trong ví dụ bên trên. ta có : X1 = 2, X2 = 3, X3 = 4)

Khi đó : vị trí Xi chỉ có nhận giá trị trong khoảng sau : X(i-1) + 1 <=   Xi   <= n - k + i.

Các bạn hãy nhìn vào Ví dụ sau để dễ hình dung :

khi n = 5, k = 3 thì ta có Output :

123  124  125  134  135  145  234  235  245  345

Mọi phần tử được liệt kê ra đều thỏa mãn tính chất :

+  Có 3 vị trí.
+  Vị trí thứ nhất của một phần tử có thể đạt giá trị lớn nhất là : n - k + i = 5 - 3 + 1 = 3
+  Vị trí thứ hai của một phần tử có thể đạt giá trị lớn nhất là : n - k + i = 5 - 3 + 2 =4
+  Vị trí thứ ba của một phần tử có thể đạt giá trị lớn nhất là : n - k + i = 5 - 3 + 3 = 5

Ghép lại ta được phần tử 345 cũng chính là phần tử cuối cùng, phần tử lớn nhất có thể liệt kê ra.

Ngoài ra : Tại các vị trí trong mỗi phần tử của bộ số được liệt kê ra, vị trí sau luôn lớn hơn vị trí trước nó ít nhất 1 đơn vị : X1 + 1 <=  X2 và X2 + 1 <=  X3


Tổng quát :

         1                  <=          X1           <=          n - k + 1
X1 + 1                  <=          X2           <=          n - k + 2
X2 + 1                  <=          X3           <=          n - k + 3

                                           .....

X(i-1) + 1             <=          Xi            <=           n - k + i

                                           ......

Riêng X1 sẽ có khoảng giá trị cố định là từ 1 tới n - k + 1. Còn các vị trí khác sẽ có khoảng giá trị tại mỗi vị trí là X(i-1) + 1 <=  Xi  <= n - k + i. (Tức là tùy vào giá trị phía trước mà giá trị phải sau sẽ có khoảng giá trị tương ứng. Các bạn có thể nhìn vào vào ví dụ khi n = 5, k = 3 sẽ thấy rõ điều này.)

Từ nhận xét trên, ta có ý tưởng giải quyết bài toán này bằng thuật toán quay lui.

Ý tưởng code : Nếu các bạn đã đọc bài Liệt kê quay lui dãy nhị phân độ dài n thì bài này cũng tương tự thôi.

Như ở bài kia, tại mỗi vị trí của một dãy nhị phân ta sẽ gán các giá trị có thể nhận được cho nó (0 và 1).

Thì ở bài này, tại mỗi vị trí của một phần tử, ta cũng sẽ gán các giá trị có thể nhận được cho nó. Nhưng các giá trị nhận được lần này sẽ là X(i-1) + 1 <=  Xi  <= n - k + i.

Dễ hiểu là như sau : - ta sẽ gán cho vị trí đầu tiên các giá trị từ 1 đến n - k + 1
                                 - tại mỗi lần gán giá trị cho vị trí đầu tiên, ta sẽ gán giá trị cho vị trí thứ 2 từ X1 + 1 đến n - k + 2
                                 - tại mỗi lần gán giá trị cho vị trí thứ 2, ta sẽ gán giá trị cho vị trí thứ 3 từ X2 + 1 đến n - k +3

                                 ........

Cứ thế khi gán xong giá trị cho phần tử thứ k thì in ra phần tử tìm được. Rồi quay lui lại tìm tiếp các phần tử khác.
 
(Vì vị trí đầu tiên luôn có giá trị nên các vị trí sau cũng sẽ luôn có các giá trị tương ứng.)

Có thể các bạn sẽ thấy hơi khó hiểu, vì thế các bạn hãy đọc bài Liệt kê quay lui dãy nhị phân độ dài n trước, vì bài này có hình mình họa và giải thích rất chi tiết dễ hiểu. Làm tiền đề để tiến tới bài toán hiện tại - nâng cao hơn một chút.

C Code liệt kê quay lui tập con k phần tử :

//Code by KCB:Reb- Rebvn.com

#include<stdio.h>

#include<conio.h>

void quayLui(int n, int k, int X[], int i, int j)
{
    for(j; j < n - k + i + 1; j++)   // gán giá trị từ X[i-1] + 1 tới n - k + i
    {
        X[i] = j + 1;  // i là vị trị đang gán giá trị, j là giá trị đang được gán cho X[i]

        if(i == (k-1))
        {
            int temp;
            for(temp = 0; temp < k; temp++)
            {
                printf("%d  ", X[temp]);
            }
            printf("\n");
        }

        else
        {
            quayLui(n, k, X, i + 1, j + 1);  // thực hiện gán tiếp giá trị chi vị trí i + 1
                                             // vị trí i + 1 có giá trị nhỏ nhất là : X[i+1] >= X[i] + 1 = j + 1
        }
    }
}

int main()
{
    int n, k;
    printf("Nhap n : ");
    scanf("%d", &n);

    printf("Nhap k : ");
    scanf("%d", &k);

    int X[k];   // phần tử X có k vị trí

    quayLui(n, k, X, 0, 0);  // lưu ý : mình khởi tạo giá trị đầu cho i và j là bằng 0 chứ không phải là 1.
                             // vì mảng trong C đếm từ 0 nên cần khởi tạo như vậy

    getch();
}


Ngoài ra, đoạn code bên trên có phần hơi khác so với bản gốc của thầy Lê Minh Hoàng. Đoạn code dưới đây sẽ y hệt ý tưởng của thầy. Như trên mình sẽ cho X1 có giá trị từ 1 đến n - k + 1; còn như ý tưởng gốc của thầy, thì dù X1 cũng sẽ có khoảng giá trị ở mỗi lần gán là từ X0 + 1 tới n - k + 1.

Nhưng vì thế nên khi viết chương trình, ta cần khai báo mảng X có k + 1 phần tử thay vì k phần tử. Vị trí X0 được tạo ra để có thể gán giá trị cho X1 từ X0 + 1. (Nếu chỉ có k phần tử, thì không thể gán giá trị cho vị trí đầu tiên của mảng theo kiểu giá trị trước nó cộng thêm 1 được, vì nó là vị trí đầu rồi thì làm gì có vị trí nào trước nó để lấy giá trị nữa.) Và khi in ra kết quả ta sẽ bỏ qua vị trí X0 chỉ lấy vị trí từ 1 đến k thôi (0 đến k có k + 1 vị trí).

Lưu ý : Mảng trong ngôn ngữ lập trình C sẽ có giá trị mặc định là 0 sau khi khai báo mà chưa gán giá trị cho các vị trí. Vì thế trong bài toán này ta chỉ cần khai báo mà không cần gán.

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

void quayLui(int n, int k, int X[], int i)
{
    int j;
    for(j = X[i - 1] + 1; j <= n - k + i; j++)
    {
        X[i] = j;

        if(i == k)
        {
            int temp;
            for(temp = 1; temp <= k; temp++)
            {
                printf("%d  ", X[temp]);
            }
            printf("\n");
        }
        else
        {
            quayLui(n, k, X, i + 1);
        }
    }
}

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

    printf("nhap vao k : ");
    scanf("%d", &k);

    int X[k + 1];

    quayLui(n, k, X, 1);

    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.