[Thuật toán Đệ quy] Bài toán Tháp Hà Nội (Hanoi Tower) sử dụng 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: 1,496

  1. Trương Minh Dương

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

    Mình đã giới thiệu tới các bạn một số bài toán sử dụng thuật toán đệ quy để giải. Bài toán tháp Hà Nội (Hanoi tower) cũng là bài toán sử dụng giải thuật đệ quy điển hình. Mời bạn theo dõi ý tưởng thuật toán và code hoàn chình của bài toán tháp hà nội sử dụng C++ nhé !!!




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

    [​IMG]

    Ý TƯỞNG THUẬT TOÁN

    Quy ước

    • Đặt tên các cọc là A, B, C (Những tên này có thể thay đỏi ở các bước di chuyển khác nhau)
    • Ở đây: A = Cọc nguồn, B = Cọc đích, C = Cọc trung gian
    • Gọi N là tổng số đĩa
    • Đánh số đĩa từ 1 (đĩa nhỏ nhất ở trên cùng) đến N (đĩa lớn nhất ở dưới cùng)
    Ý tưởng thực hiện thuật toán

    Để chuyển N đĩa từ cọc A sang cọc B thì cần:

    • Chuyển (N-1) đĩa từ cọc A sang cọc C. Chỉ còn lại đĩa N (đĩa lớn nhất) trên cọc A
    • Chuyển đĩa N (đĩa lớn nhất) từ cọc A sang cọc B
    • Chuyển (N-1) đĩa từ cọc C sang cọc B cho chúng nằm trên đĩa N (đĩa lớn nhất).
    Phương pháp giải trên được gọi là thuật giải đệ quy: để tiến hành bước 1 và 3, áp dụng lại thuật giải cho N-1. Toàn bộ quá trình là một số hữu hạn các bước, vì đến một lúc nào đó thuật giải sẽ áp dụng cho N = 1. Bước này chỉ đơn giản là chuyển một đĩa duy nhất từ cọc A sang cọc B.

    [​IMG]
    Thap Ha Noi C++

    Code hoàn chỉnh của bài toán Tháp Hà Nội (Hanoi Tower)
    Mã:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define A 0
    #define B 1
    #define C 2
    int count;
    void hanoitower (int from, int to, int disk){
        int tmp;
        if (disk == 1){
            printf ("Step %d: ",count++);
        printf ("Move disk from %c to %cn",'A'+from,'A'+to);}
        else {
            if ((from == A && to == C) || (from == C && to == A))
                tmp = B;
            else if ((from == A && to == B) || (from == B && to == A))
                tmp = C;
            else if ((from == C && to == B) || (from == B && to == C))
                tmp = A;
            hanoitower (from, tmp, disk - 1);
            hanoitower (from, to, 1);
            hanoitower (tmp, to, disk - 1);
        }
    }
    int main(int argc, char** argv){
        int n = atoi (argv [1]);
        hanoitower (A, C, n);
        int count = 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