Bài học
Lưu code
Refresh
Xoay
Xem kết quả
/* Bài toán Tháp Hà Nội: “Có 3 cọc A, B, C. Trên cọc A có 1 chồng gồm N đĩa đường kính giảm dần từ trên xuống dưới. Cần phải chuyển chồng đĩa từ cọc A sang cọc C tuân thủ theo quy tắc: mỗi lần chỉ chuyển 1 đĩa và chỉ được xếp đĩa có đường kính nhỏ hơn lên đĩa có đường kính lớn hơn. Trong quá trình chuyển được phép dùng cọc B làm cọc trung gian.” Yêu cầu: Tìm cách chơi đòi hỏi số lần chuyển đĩa là ít nhất. Giải thuật: Lập luận sau đây được sử dụng để xây dựng thuật toán đặt ra: Nếu N = 1 thì ta chỉ cần chuyển 1 đĩa từ cọc A sang cọc C Nếu N >= 2. Việc di chuyển đĩa gồm các bước sau: (i) Chuyển N-1 đĩa từ cọc A đến cọc B sử dụng cọc C làm trung gian. Bước này phải thực hiện số lần di chuyển là nhỏ nhất, nghĩa là ta phải giải quyết bài toán tháp Hà nội với N-1 đĩa (ii) Chuyển 1 đĩa (đường kính lớn nhất) từ cọc A đến cọc C. (iii) Chuyển N-1 đĩa từ cọc B đến cọc C (sử dụng cọc A làm trung gian). Bước này cũng phải được thực hiện với số lần di chuyển đĩa nhỏ nhất, nghĩa là ta phải giải quyết bài toán tháp Hà Nội với N-1 đĩa. Bước (i) và (iii) đòi hỏi giải bài toán tháp Hà nội với N-1 đĩa, vì vậy số lần di chuyển đĩa ít nhất cần thực hiện trong hai bước này là 2H(n-1). Do đó, nếu gọi H(n) là số lần di chuyển đĩa ít nhất, ta có công thức đệ quy sau: H(1) = 1, H(n) = 2H(n-1) + 1 (n >= 2) */ package vncoding; import java.util.Scanner; public class JavaCore { static int total = 0; public static void main(String args[]) { int n; Scanner sc = new Scanner(System.in); do{ System.out.print("n = "); n = sc.nextInt(); }while(n <= 0); move(n, 'A' , 'C', 'B'); System.out.format("The total number of moving: %d", total); } /* * n: number of disk * start: source column * finish: destination column * spare: spare column */ public static void move(int n, char start, char finish, char spare) { if(n == 1){ System.out.format("Move a disk from '%c' to '%c'\n", start, finish); total++; return; } else{ move(n-1, start, spare, finish); move(1, start, finish, spare); move(n-1, spare, finish, start); } } }
kết quả: