Bài toán tháp Hà Nội

Bài toán tháp thành phố hà nội là một trò nghịch toán học khôn cùng phổ biến. Nó đơn giản dễ dàng chỉ là việc dịch chuyển các đĩa từ bỏ cột này thanh lịch cột khác. Nhưng mà để thành thạo chế độ chơi của chính nó thì vô cùng khó.

Bạn đang xem: Bài toán tháp hà nội c++

Luật chơi được bộc lộ như sau:

Trò đùa này có một bộ những đĩa size khác nhau, gồm lỗ ở giữa, nằm xuyên trên ba cái cột. Vấn đề đố ban đầu bằng phương pháp sắp xếp các đĩa theo đơn lẻ tự kích cỡ vào một cột, làm sao để cho đĩa bé dại nhất nằm ở vị trí trên cùng, có nghĩa là tạo thành một hình nón.

Yêu ước của trò nghịch là di chuyển toàn bộ số đĩa sang 1 cột khác, tuân theo những quy tắc sau:

Một lần chỉ gồm 3 cột nhằm di chuyển
Chỉ dịch rời một đĩa trên thuộc (không được di chuyển đĩa nằm giữa hay nằm cuối).Một đĩa chỉ có thể bỏ trên một đĩa to hơn (không nhất thiết nhị đĩa này cần có form size liền kề, có nghĩa là đĩa bé dại nhất vẫn đang còn thể để lên trên đĩa lớn nhất).

Ý tưởng đệ quy:

Dựa vào mức sử dụng chơi của trò chơi, bọn họ sẽ áp dụng nó vào đệ quy nhằm giải việc này bằng ngôn ngữ C++ nhé.

rong vấn đề này họ cần nhiệt tình 4 vấn đề: số đĩa N, cột A, cột B, cột C.

Nhiệm vụ của họ là chuyển N số đĩa từ cột A quý phái cột C, rước cột B có tác dụng cột tạm.

Ý tưởng:

Nếu đã biết phương pháp chuyển N - 1 đĩa từ cột A quý phái cột B, ta chỉ việc chuyển đĩa sản phẩm N (đĩa cuối cùng) từ cột A thanh lịch cột C, rồi gửi N - 1 đĩa từ bỏ cột B thanh lịch cột C.Giải thuật không còn đệ quy khi chỉ có một đĩa, vì chưng ta gửi trực tiếp trường đoản cú cột A sang trọng cột C luôn mà không cần thông qua cột B.Độ phức hợp của nó là:2n- 1(lần dịch chuyển).

Giải vấn đề tháp thành phố hà nội bằng C++

Chúng ta sẽ có phát minh giải bài bác toán, chỉ việc dựa vào kia và áp dụng thêm kiến thức và kỹ năng về đệ quy để hợp tác vào câu hỏi giải thôi nào.

Giải thuật

void move(int n,char A,char B,char C) if(n==1) cout " C else // giả dụ n > 1 thì thực hiện lần lượt công việc move(n - 1, A, C, B); // 1. Di chuyển n-1 đĩa trường đoản cú A -> B cout " C move(n - 1, B, A, C); // 3. Dịch rời n-1 đĩa trường đoản cú B -> C Như chúng ta thấy bọn họ cần truyền 4 tham số đến hàm move() là: số đĩa n, cột A, cột B, cột C.

Nếu như n == 1 (chỉ có một đĩa) thì họ chỉ phải chuyển đĩa đó từ cột A quý phái cột C là xong.

Trường hợp số đĩa n lớn hơn 1 thì chúng ta cần thực hiện dịch chuyển ba lần:

Chuyển n - 1 đĩa từ bỏ cột A thanh lịch cột B ->move(n - 1, A, C, B);Chuyển đĩa còn sót lại (đĩa trang bị n) từ bỏ cột A thanh lịch cột C ->cout "Chuyển n - 1 đĩa tự cột B quý phái cột C ->move(n - 1, B, A, C);

Giả sử bọn họ cón = 3thì mốc giới hạn thực hiện dịch chuyển bằng2n- 1 = 23- 1 = 7(lần).

Hàm main()

#include using namespace std; void move(int n,char A,char B,char C) if(n==1) cout " C else //// nếu n > 1 thì triển khai lần lượt quá trình move(n - 1, A, C, B); // 1. Di chuyển n-1 đĩa tự A -> B cout " C move(n - 1, B, A, C); // 3. Di chuyển n-1 đĩa từ B -> C int main() { int n; cout>n; coutKết quả:

Bài toán

Tháp thủ đô là một bài toán kinh khủng có thể giải bằng đệ quy. Đó là một câu đố bao hàm ba cọc và một số trong những đĩa có kích cỡ khác nhau, rất có thể đặt lên bất kỳ cọc nào. Câu đố bước đầu với các đĩa xếp thành ông xã theo máy tự form size tăng dần trên một cọc, nhỏ nhất sinh hoạt trên cùng, cho nên vì thế tạo thành những hình nón.Mục tiêu của câu đố là di chuyển toàn bộ đĩa qua 1 cọc khác, theo đúng quy tắc đơn giản sau:Mỗi lần chỉ rất có thể di gửi một đĩa.Mỗi lần dịch rời : lấy đĩa xuất phát điểm từ một cọc nguồn cùng đặt nó lên một cọc đích. Ở cọc đích rất có thể đã gồm sẵn các đĩa.Không có đĩa nào rất có thể được bỏ lên một đĩa nhỏ dại hơn.Có thể đưa đĩa vào cọc trung gian miễn là vâng lệnh 3 luật lệ trên.

Xem thêm: Người vợ câm lặng trước lời đề nghị của chồng ở phương xa, bảo lãnh định cư mỹ theo diện kết hôn

Kn
Cl alt="Hanoi Tower">

Giải bằng cơm trước khi code

Để dễ tưởng tượng hơn công việc giải, bọn họ sẽ đem ví dụ chũm thể. Trả sử họ có 3 cọc A, B, C tương trưng mang đến 3 tháp và gồm 3 đĩa.Ảnh bên dưới là trạng trái ban đầuIJWZ alt=Hanoi
Tower1>Để đưa cục bộ 3 đĩa ở cọc A cho tới cọc C, các bạn cần:Chuyển đĩa 1 và 2 sang trọng cọc trung gian B.Di gửi đĩa 3 lịch sự cọc CChuyển đĩa 1 và 2 lịch sự cọc CBước 1: chuyển đĩa 1 tự cọc A quý phái cọc CFBl
Topw alt=Hanoi
Tower2>Bước 2: chuyển đĩa 2 trường đoản cú cọc A lịch sự cọc BXWh alt=Hanoi
Tower3>Bước 3: chuyển đĩa 1 từ cọc C quý phái cọc BMục đích đoạn này để dành khu vực ở cọc C chuyển đĩa 3 từ bỏ cọc A sangFV alt=Hanoi
Tower4>Bước 4: gửi đĩa 3 từ bỏ cọc A lịch sự cọc CHanoi<brTower5>Bước 5: chuyển đĩa 1 từ cọc B sang trọng cọc AY alt=Hanoi
Tower6>Bước 6: đưa đĩa 2 trường đoản cú cọc B sang cọc CHanoi<brTower6>Bước 7: đưa đĩa 1 từ cọc A thanh lịch cọc CĐến công đoạn này ta đã xong nhiệm vụSr
XJEr alt=Hanoi
Tower7>

Thuật toán đệ quy

Di đưa n-1 đĩa trên cùng từ cọc nguồn sang cọc trung gian.Di chuyển đĩa sản phẩm n từ bỏ cọc nguồn đến cọc đích.Di đưa n-1 đĩa từ cọc trung gian lịch sự cọc đích, sử dụng cọc nguồn làm cho trung gian.Trường thích hợp cơ bạn dạng của đệ quy là khi chỉ bao gồm một đĩa để di chuyển. Vào trường vừa lòng này, bọn họ chỉ cần dịch chuyển đĩa từ bỏ cọc nguồn mang lại cọc đích.
public class Hanoi
Tower public static void solve
Hanoi(int n, char source, char destination, char auxiliary) if (n == 1) System.out.println("Move disk 1 from " + source + " to " + destination); return; solve
Hanoi(n-1, source, auxiliary, destination); System.out.println("Move disk " + n + " from " + source + " lớn " + destination); solve
Hanoi(n-1, auxiliary, destination, source); public static void main(String<> args) int n = 3; solve
Hanoi(n, 'A', 'C', 'B');
package leetcode;import org.junit.jupiter.api.Test;public class Hanoi
Tower public static void solve
Hanoi(int n, char source, char destination, char auxiliary) if (n == 1) System.out.println("Move disk 1 from " + source + " lớn " + destination); return; solve
Hanoi(n - 1, source, auxiliary, destination); System.out.println("Move disk " + n + " from " + source + " khổng lồ " + destination); solve
Hanoi(n - 1, auxiliary, destination, source);
Test void test() int n = 3; solve
Hanoi(n, 'A', 'C', 'B');
java
Kết quả in ra màn hình các bước
Move disk 1 from A khổng lồ CMove disk 2 from A khổng lồ BMove disk 1 from C khổng lồ BMove disk 3 from A lớn CMove disk 1 from B lớn AMove disk 2 from B to CMove disk 1 from A to lớn C