问题描述

汉诺塔是一个古老的数学问题：
　　有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：
　　每次只能移动一个圆盘；
　　大盘不能叠在小盘上面。

问：n个盘子最少要移动多少次？
输入一个数字n，打印出一个数字表示移动的次数

问题分析

首先将问题从简单到复杂分析，找出规律

设步数为f(n)

当n = 1时，只需要1步，直接将圆盘从A移动到C

当n = 2时，先将1个小圆盘从A移动到B，再将大圆盘从A移动到C，最后将小圆盘从B移动到C，需要3步

当n = 3 时，也可以理解成需要3步，先将2个小圆盘从A移动到B，再将大圆盘从A移动到C，最后将2个小圆盘从B移动到C，由上述可知，移动2个圆盘到指定位置需要3步，因此当n=3时需要 f(3) = 3+1+3=7步

同理，当n = 4时，将问题拆分成3个小圆盘和一个大圆盘的移动，需要 f(4) = 7+1+7=15步

…
故，f(n) = 2f(n-1)+1
递推得到

有规律便可以求通项公式
f(n) = 2f(n – 1) + 1
f(n) + 1 = 2f(n – 1) + 2
列出关系式
f(n) + 1 = 2(f(n – 1)+1)
f(n – 1) + 1 = 2(f(n – 2)+1)
f(n – 2) + 1 = 2(f(n – 3)+1)
…
f(3) + 1 = 2(f(2)+1)
f(2) + 1 = 2(f(1)+1)
左右两边分别相乘得
f(n) + 1 = 2^(n-1) * (f(1)+1)=2^(n-1) * 2 = 2ⁿ
故，f(n) = 2ⁿ – 1
n个盘子最少要移动2ⁿ – 1次

代码实现

1.通项公式法

import java.util.Scanner; public class HanNuoTa { public static void main(String[] args) {   Scanner sc = new Scanner(System.in); int n = sc.nextInt();   System.out.println((int)Math.pow(2, n) - 1); } } 

2.递推法

import java.util.Scanner; public class HanNuoTa { public static void main(String[] args) {   Scanner sc = new Scanner(System.in); int n = sc.nextInt();   System.out.println(f(n)); } private static int f(int n) { if (n == 1) { return 1; } return f(n - 1) + 1 + f(n - 1); } } 

3.递归打印步骤

import java.util.Scanner; public class HanNuoTa { static int cut; //计数器 public static void main(String[] args) {   Scanner sc = new Scanner(System.in); int n = sc.nextInt(); f("A", "B", "C", n);   System.out.println("将"+n+"个圆盘从A移动到C需要"+cut+"步"); } private static void f(String from, String temp, String to, int n) { if (n < 1) { return; } f(from, to, temp, n - 1); //先将n-1个小圆盘从A移动到B   cut ++; //记录移动的步数   System.out.println(from + " -> " + to); f(temp, from, to, n - 1); //再将将n-1个小圆盘从B移动到C } }