Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

Vấn đề tháp Hà Nội

In lại Tác giả: Người biết Thời gian cập nhật: 2024-03-13 07:29:36 29 4
mua khóa gpt4 Nike

Nguồn gốc của bài toán Tháp Hà Nội

Theo truyền thuyết, trong các ngôi chùa cổ của Ấn Độ có một trò chơi tên là Hà Nội. Trò chơi diễn ra trên một thiết bị tấm đồng có ba cọc (được đánh số A, B, C). Trên cột A, 64 đĩa vàng được xếp theo thứ tự từ dưới lên trên và từ lớn đến nhỏ. Mục tiêu của trò chơi là di chuyển tất cả các đĩa vàng từ cực A sang cực C và giữ chúng xếp chồng lên nhau theo thứ tự ban đầu. Quy tắc vận hành: Mỗi lần chỉ được di chuyển một tấm, trong quá trình di chuyển, tấm lớn luôn ở phía dưới và tấm nhỏ ở trên cùng của ba thanh. Trong quá trình vận hành, tấm có thể được đặt trên bất kỳ thanh nào. của các thanh A, B, C.

Phân tích ý tưởng

Nếu chỉ có một đĩa, chỉ cần di chuyển đĩa trực tiếp từ cột ban đầu sang cột đích.

Khi số lượng đĩa là 2 thì di chuyển đĩa nhỏ sang cột phụ rồi di chuyển đĩa lớn sang cột đích.

Nếu có n đĩa, chúng ta có thể coi n đĩa này là 2 đĩa - đĩa dưới cùng và tất cả các đĩa ở trên.
(1) Di chuyển n-1 đĩa ở trên sang cột B (lúc này cột A là cột đầu, cột B là cột đích, cột C là cột phụ)
(2) Di chuyển đĩa dưới cùng sang cột mục tiêu (lúc này cột A là cột ban đầu, cột C là cột mục tiêu và cột B là cột phụ)
(3) Di chuyển tất cả các đĩa trên cột phụ sang đĩa đích (lúc này cột B là cột ban đầu, cột C là cột đích và cột A là cột phụ)

public class HanoiTower { public static void main(String[] args) { hanoiTower(4,'A','B','C'); } /** * * @param num Số lượng đĩa* @param a Bắt đầu cột* @param b Cột phụ* @param c Cột mục tiêu*/ public static void hanoiTower(int num,char a,char b,char c){ /*Nếu chỉ có một đĩa, bạn có thể di chuyển trực tiếp đĩa từ cột a sang cột c*/ if (num == 1){ System.out.println("Đĩa đầu tiên bắt đầu từ " + a + "-> " + c); }else{ /*Số lượng đĩa lớn hơn 1*/ /*Đầu tiên di chuyển tất cả các đĩa ở trên từ A đến B và C làm cột phụ*/ hanoiTower(num-1,a,c ,b ); /*Di chuyển đĩa dưới cùng sang cột C*/ System.out.println("Đĩa thứ "+num+"bắt đầu từ " + a + "->" + c); /*Di chuyển đĩa trên cột B Di chuyển đến cột C và cột A là cột phụ*/ hanoiTower(num-1,b,a,c);

Kết quả chạy

Đĩa thứ nhất từ ​​A->B Đĩa thứ hai từ A->C Đĩa thứ nhất từ ​​B->C Đĩa thứ ba từ A->B Đĩa thứ nhất từ ​​C->A Đĩa thứ 2 từ C->B Đĩa thứ nhất là từ A->B Đĩa thứ 4 là từ A->C Đĩa thứ nhất là từ B->C Đĩa thứ 2 là từ B->A Đĩa thứ nhất là từ C->A Đĩa thứ 3 là từ B->C Đĩa thứ nhất là từ A->B Đĩa thứ 2 là từ A->C Đĩa thứ nhất là từ B->C Quá trình hoàn tất với mã thoát 0
29 4 0
Bài viết khuyến nghị: Kiểm tra thâm nhập---Bảo mật cơ sở dữ liệu: Giải thích chi tiết về nguyên tắc tiêm SQL vào cơ sở dữ liệu
Bài viết khuyến nghị: Cuộc thi hàng tuần lần thứ 280 của LeetCode
Bài viết khuyến nghị: Dự án triển khai Docker dockerfile chiến đấu thực tế SpringBoot, jar
Bài viết khuyến nghị: Mạng máy tính Giao thức tin nhắn điều khiển Internet ICMP
người biết
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress