[Thuật toán Đệ quy] Thuật toán phân tích số 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: 677

  1. Trương Minh Dương

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

    Ở bài trước mình đã giới thiệu đến mọi người Thuật toán chỉnh hợp trong C++ bằng cách dùng đệ quy quay lui. Để hiểu rõ hơn về thuật toán đệ quy lui, bài viết này mình sẽ giới thiệu đến mọi người thuật toán phân tích số.


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

    Bài toán

    Cho một số nguyên dương n , hãy tìm tất cả các cách phân tích số n thành tổng của các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là 1 cách.

    [​IMG]

    Ý tưởng:
    • Ta sẽ lưu nghiệm trong mảng a, ngoài ra có một mảng b. Mảng b được xây dựng như sau: b sẽ là tổng các phần tử trong mảng a từ a[1] đến a tức là: b := a[1] + b[2] + ... + a.
    • Khi liệt kê các dãy a có tổng các phần tử đúng bằng n, để tránh sự trùng lặp ta đưa thêm ràng buộc a[i-1] <= a.
    • Vì số phần tử thực sự của mảng a là không cố định nên thủ tục Prin dùng để in ra 1 cách phân tích phải có thêm tham số cho biết sẽ in ra bao nhiêu phần tử.
    • Thủ tục đệ quy Try(i) sẽ thử các giá trị có thể nhận của a (a >= a[i - 1])
    • Vậy thủ tục Try(i) thử các giá trị cho a có thể mô tả như sau:
      Để tổng quát cho i=1, đặt a[0]=1, b[0]=0
      Xét các giá trị của a từ a[i-1] đến (n-b[i-1]) /2, cập nhật b=b[i-1]+a và gọi đệ quy tìm tiếp
      Cuối cùng xét giá trị a=n-b[i-1] và in kết quả trong mảng a.
    Chương trình hoàn chỉnh:

    Mã:
    #include<stdio.h>
    int n;
    int a[100000], b[100000];
    void start(){
        printf("Nhap n="); scanf("%d",&n);
        a[0]=1;
        b[0]=0;
        }
    void prin(int k){
        printf("n %d = ",n);
        for (int i=1;i<=k-1;i++)
            printf("%d + ",a[i]);
        printf("%dn",a[k]);
        }
    void Try(int i){
        for (int j=a[i-1];j<=((n-b[i-1])/2);j++){
            a[i]=j;
            b[i]=b[i-1]+j;
            Try(i+1);     
            }
        a[i]=n-b[i-1];
        prin(i);
        }
    int main(){
        start();
        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