Giải bài toán tháp Hà nội bằng đệ qui và phương pháp lặp

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)

Code

/*********************************************
 * Author: VietVH
 * Date: 04/09/2016
 *********************************************/

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ả: