Xem thảo luận Show
Cải thiện bài viết Lưu bài viết Xem thảo luận Cải thiện bài viết Lưu bài viết Đọc  Python3Bàn luận Tower of Hà Nội là một câu đố toán học nơi chúng tôi có ba thanh và đĩa N. Mục tiêu của câu đố là di chuyển toàn bộ ngăn xếp sang một thanh khác, tuân theo các quy tắc đơn giản sau: & nbsp; 1) Chỉ có thể di chuyển một đĩa. các ngăn xếp và đặt nó lên trên một ngăn xếp khác, tức là một đĩa chỉ có thể được di chuyển nếu đó là đĩa trên cùng trên ngăn xếp. & nbsp; 3) không có đĩa nào được đặt trên đầu của một đĩa nhỏ hơn. 1 đĩa từ thanh nguồn đến thanh phụ trợ một lần nữa có thể được coi là một vấn đề mới và có thể được giải quyết theo cách tương tự. & Nbsp;
____10
Các Move disk 1 from source A to destination C Move disk 2 from source A to destination B Move disk 1 from source C to destination B Move disk 3 from source A to destination C Move disk 1 from source B to destination A Move disk 2 from source B to destination C Move disk 1 from source A to destination C Move disk 4 from source A to destination B Move disk 1 from source C to destination B Move disk 2 from source C to destination A Move disk 1 from source B to destination A Move disk 3 from source C to destination B Move disk 1 from source A to destination C Move disk 2 from source A to destination B Move disk 1 from source C to destination B
Đầu raO(n) Độ phức tạp về thời gian: O (2N) Hướng dẫn giải quyết Tháp của Hà Nội bằng cách sử dụng C ++ và PythonHình ảnh của tác giảTháp Hà Nội còn được gọi là Tháp Brahma hoặc Tháp Lucas. Đây là một trò chơi hoặc câu đố toán học bao gồm ba thanh với số lượng đĩa có đường kính khác nhau. Mục tiêu của trò chơi là chuyển toàn bộ chồng đĩa từ thanh này sang thanh khác theo ba quy tắc này:
Logic đằng sau việc giải quyết Tháp Hà Nội cho ba đĩa:Mục tiêu: Để giải quyết Tháp của câu đố Hà Nội có chứa ba đĩa. Hồng của các đĩa phải được chuyển từ que 1 sang que 3 bằng cách tuân thủ tập hợp các quy tắc đã được đề cập ở trên. To solve the Tower of Hanoi puzzle that contains three disks. The stack of disks has to be shifted from Rod 1 to Rod 3 by abiding to the set of rules that has been mentioned above. Hình ảnh của tác giảBước 1: Đĩa màu xanh lá cây nhỏ nhất, đĩa trên cùng trên ngăn xếp được chuyển từ thanh 1 sang que 3. The smallest green disk , the uppermost disk on the stack is shifted from rod 1 to rod 3. Hình ảnh của tác giảBước 2: Tiếp theo đĩa trên cùng trên thanh 1 là đĩa màu xanh được chuyển sang Rod 2.Next the uppermost disk on rod 1 is the blue colored disk which is shifted to rod 2. Hình ảnh của tác giảBước 2: Tiếp theo đĩa trên cùng trên thanh 1 là đĩa màu xanh được chuyển sang Rod 2. The smallest disk placed on rod 3 is shifted back on to the top of rod 2. Hình ảnh của tác giảBước 2: Tiếp theo đĩa trên cùng trên thanh 1 là đĩa màu xanh được chuyển sang Rod 2. So now the largest red disk is allowed to be shifted from rod 1 to its destination rod 3. Hình ảnh của tác giảBước 2: Tiếp theo đĩa trên cùng trên thanh 1 là đĩa màu xanh được chuyển sang Rod 2.Now the two disks on rod 2 has to be shifted to its destination rod 3 on top of the red disk , so first the smallest green disk on top of the blue rod is shifted to rod 1 . Hình ảnh của tác giảBước 2: Tiếp theo đĩa trên cùng trên thanh 1 là đĩa màu xanh được chuyển sang Rod 2.Next the blue disk is permitted to be shifted to its destination rod 3 that will stacked on to the top of the red disk. Hình ảnh của tác giảBước 2: Tiếp theo đĩa trên cùng trên thanh 1 là đĩa màu xanh được chuyển sang Rod 2. Finally , the smallest green colored rod is also shifted to rod 3 , which would now be the uppermost rod on the stack . Hình ảnh của tác giảBước 3: Đĩa nhỏ nhất được đặt trên thanh 3 được chuyển trở lại trên đỉnh của thanh 2. Bước 4: Vì vậy, bây giờ đĩa màu đỏ lớn nhất được phép chuyển từ que 1 sang que 3 đích của nó.Bước 5: Bây giờ, hai đĩa trên thanh 2 phải được chuyển sang que đích của nó 3 trên đầu đĩa màu đỏ, vì vậy đầu tiên đĩa màu xanh lá cây nhỏ nhất trên đỉnh thanh màu xanh được chuyển sang que 1.Bước 6: Tiếp theo đĩa màu xanh được phép chuyển sang que đích của nó 3 sẽ xếp chồng lên đỉnh đĩa màu đỏ.Bước 7: Cuối cùng, thanh màu xanh lá cây nhỏ nhất cũng được chuyển sang que 3, giờ đây sẽ là thanh cao nhất trên ngăn xếp. Vì vậy, Tháp Hà Nội cho ba đĩa đã được giải quyết !!
Hãy để chúng tôi cố gắng giải câu đố Tháp Hà Nội cho n = 4 đĩa. Tín dụng hình ảnh: Blogspot Chúng ta đã thấy cách giải quyết Tháp Hà Nội cho N = 3 đĩa, cách tiếp cận tương tự sẽ được áp dụng ở đây.Chiến lược:hanoi(n,start,end) outputs a sequence of steps to move n disks from the start rod to the end rod. Giải quyết đệ quy câu đố của các đĩa dịch chuyển 1, 2, 3 từ thanh A đến que B. 2. Sau đó di chuyển đĩa lớn nhất 4 từ thanh A đến que đích C. 3. Giải quyết đệ quy câu đố chuyển đĩa 1, 2, 3 từ thanh B sang que C. Giải quyết chương trình Tháp Hà Nội bằng cách sử dụng đệ quy: Chức năng HANOI (N, bắt đầu, kết thúc) tạo ra một chuỗi các bước để di chuyển các đĩa N từ thanh bắt đầu sang thanh cuối. Hà Nội (3,1,3) => Có tổng cộng 3 đĩa trong thanh 1 và nó phải được chuyển từ thanh 1 sang thanh 3 (thanh đích).Giả định: 1≤ bắt đầu ≤3
Đặt f (n) là một hàm đệ quy. Ba quy tắc: Hiển thị F (1) Tác phẩm => Trường hợp cơ sở.Giả sử F (N-1) hoạt động. Hiển thị F (1) hoạt động sử dụng F (N-1).Chúng ta hãy hiểu các quy tắc trên bằng cách lấy các domino làm ví dụ. Hãy tưởng tượng rằng bạn phải hạ gục n-dominos.Tín dụng hình ảnh: Net Clipart Chỉ xem xét Domino đầu tiên, nó sẽ sụp đổ khi nó bị đánh gục. Đây là một sự tương tự để cho thấy rằng F (1) trường hợp cơ sở hoạt động.Hình ảnh của tác giả: F (1) Trường hợp cơ sở hoạt động Bây giờ đặt n-domino trên sàn nhà domino cuối cùng được lấy làm f (n-1) được coi là bị loại khi F (1) Thác domino đầu tiên rơi xuống.Hình ảnh của tác giả: Giả sử F (N-1) hoạt động Nếu chúng ta đặt một domino f (n) khác phía sau f (n-1) thì domino f (n) sẽ rơi ra nếu f (n-1) domino bị đánh gục chứng minh sự tương tự thứ ba mà f (n) hoạt động bằng cách sử dụng f (n- n- 1).Hình ảnh của tác giả: Place F (n) phía sau F (N-1)Điều quan trọng là xác định chính xác mối quan hệ giữa F (N) và F (N-1), ở đây nếu F (N) được giữ im lặng xa F (N-1) thì F (N) sẽ không bao giờ rơi (tức là) Nó sẽ không bao giờ hoạt động. Hình ảnh của tác giả: F (n) hoạt động bằng F (N-1) Tháp Hà Nội có thể được giải quyết bằng cách sử dụng đệ quy không?Giải quyết chương trình Hà Hà sử bằng cách sử dụng đệ quy: Hàm HANOI (N, bắt đầu, kết thúc) tạo ra một chuỗi các bước để di chuyển các đĩa N từ thanh bắt đầu đến thanh cuối. Hà Nội (3,1,3) => Có tổng cộng 3 đĩa trong thanh 1 và nó phải được chuyển từ thanh 1 sang thanh 3 (thanh đích).Function hanoi(n,start,end) outputs a sequence of steps to move n disks from the start rod to the end rod. hanoi(3,1,3) => There are 3 disks in total in rod 1 and it has to be shifted from rod 1 to rod 3(the destination rod).
Làm thế nào để Tháp Hà Nội liên quan đến đệ quy?Trong các tòa tháp của giải pháp Hà Nội của chúng tôi, chúng tôi tái phát trên đĩa lớn nhất sẽ được di chuyển.Đó là, chúng tôi sẽ viết một hàm đệ quy lấy tham số, đĩa là đĩa lớn nhất trong tháp chúng tôi muốn di chuyển.we recurse on the largest disk to be moved. That is, we will write a recursive function that takes as a parameter the disk that is the largest disk in the tower we want to move.
Tháp của vấn đề Hà Nội ở Python là gì?Tower of Hà Nội là một câu đố toán học nơi chúng tôi có ba thanh và đĩa N.Mục tiêu của câu đố là di chuyển toàn bộ ngăn xếp sang một thanh khác, tuân theo các quy tắc đơn giản sau: 1) Chỉ có thể di chuyển một đĩa một lần.a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules: 1) Only one disk can be moved at a time.
Công thức cho Tháp Hà Nội là gì?Tháp ban đầu của câu đố Hà Nội, được phát minh bởi nhà toán học người Pháp Edouard Lucas vào năm 1883, kéo dài "cơ sở 2".Đó là - số lượng di chuyển của số đĩa K là 2^(K -1) và tổng số lượng di chuyển cần thiết để giải câu đố với các đĩa n là 2^n - 1.the number of moves of disk number k is 2^(k-1), and the total number of moves required to solve the puzzle with N disks is 2^N - 1. |
