[Giải thuật Đệ quy] Thuật toán chỉnh hợp trong C++

Thảo luận trong 'C/C++/C#' bắt đầu bởi Trương Minh Dương, 18/11/15.

Lượt xem: 924

  1. Trương Minh Dương

    Trương Minh Dương Đầy tớ nhân dân

    Thuật toán này là thuật toán cơ bản trong việc sử dụng đệ quy. Việc học thuật toán đệ quy sẽ trở nên đơn giản khi bạn nắm vững được thuật toán cơ bản này. Mời các bạn theo dõi ý tưởng thuật toán và Code hoàn chỉnh của thuật toán chính hợp trong C++.

    [​IMG]

    LIỆT KÊ CÁC TẬP CON K PHẦN TỬ

    Ta sẽ lập chương trình liệt kê các tập con k phần tử của tập {1, 2, ..., n} theo thứ tự từ điền

    Ví dụ: với n = 5, k = 3, ta phải liệt kê đủ 10 tập con:

    1.{1, 2, 3} 2.{1, 2, 4} 3.{1, 2, 5} 4.{1, 3, 4} 5.{1, 3, 5}

    6.{1, 4, 5} 7.{2, 3, 4} 8.{2, 3, 5} 9.{2, 4, 5} 10.{3, 4, 5}

    Như vậy tập con đầu tiên là {1, 2, ..., k}. Tập kết thúc là {n - k + 1, n - k + 2, ..., n}.

    Nhận xét: Ta sẽ in ra tập con bằng cách in ra lần lượt các phần tử của nó theo thứ tự tăng dần. Từ đó, ta có nhận xét nếu x = {x1, x2, ..., xk} và x1 < x2 < ... < xk thì giới hạn trên (giá trị lớn nhất có thể nhận) của xk là n, của xk-1 là n - 1, của xk-2 là n - 2...

    Cụ thể: giới hạn trên của xi = n - k + i;

    Còn tất nhiên, giới hạn dưới của xi (giá trị nhỏ nhất xi có thể nhận) là xi-1 + 1.

    Như vậy nếu ta đang có một dãy x đại diện cho một tập con, nếu x là cấu hình kết thúc có nghĩa là tất cả các phần tử trong x đều đã đạt tới giới hạn trên thì quá trình sinh kết thúc, nếu không thì ta phải sinh ra một dãy x mới tăng dần thoả mãn vừa đủ lớn hơn dãy cũ theo nghĩa không có một tập con k phần tử nào chen giữa chúng khi sắp thứ tự từ điển.


    http://www.mediafire.com/?nh5g8be463brqnb

    Ví dụ n=9,k=6 kỹ thuật sinh tập con kế tiếp từ tập đã có x có thể xây dựng như sau:

    [​IMG]



    Chương trình hoàn chỉnh:

    Mã:
    #include <stdio.h>
    #include <stdlib.h>
    
    int n, k, count;
    int a[100];
    
    void print(){
        count++;
        printf("%dth: ", count);
        for (int i = 1; i<= k; i++)
            printf("%d", a[i]);
        printf("n");
    }
    
    void TRY (int i){
        int v;
        for (v = a[i-1]+1; v <= n-k+i; v++){
            a[i] = v;
            if (i == k) {
                print();
            } else
                TRY(i+1);
        }
    }
    int main(){
        printf("Nhap n va k n");
        scanf("%d",&n);
        scanf("%d",&k);
        count = 0;
        a[0] = 0;
        TRY(1);
    }
    Chúc các bạn học tập tốt !!!
     
    DOWNLOAD BẢN ĐẦY ĐỦ NHẤT TẠI ĐÂY
    download now
    LINK FSHARE Hoặc LINK SHARE.VNN.VN

    Bình Luận Bằng Facebook

Chia sẻ trang này

Text Link: |Ban iPhone cu |Jailbreak iOS 9.3.3 |Tai lieu Swift Tieng Viet |Tao Boot USB |Antamedia Hotspot 4 Full Crack |Proshow Producer 7 Full Crack |Chu ky mau dep |Kiem tien tren mang |Ghost win 7 Full Soft |Ghost win 10 Full Soft |Ghost win XP Full Soft |Game Offline cho PC |Game Sex Offline |Game nhap vai luyen level |Game ban sung Offline |Game dan tran Offline |Game nhap vai hay |Hack Asphalt 8 |Hack ban ga 5 |Hack ban ga 6 |Game dua xe Offline |Tool tăng view Youtube |Kiếm tiền trên Youtube |SEO đề xuất Youtube |Kháng cáo Youtube |Lắp đặt internet viettel giá rẻ |Đăng ký cáp quang viettel miễn phí |lắp đặt Cáp Quang Viettel tại TPHCM |FPlus 4.8 Full Crack |GPlus 4.7 Full Crack |Poke Map |Táo Quân 2017 |Hài Tết 2017 |Sitemap