服务器之家

服务器之家 > 正文

java 实现汉诺塔详解及实现代码

时间:2020-09-17 14:54     来源/作者:27905183

java 实现汉诺塔详解及实现代码

汉诺塔问题:有三根柱子A,B,C,其中A上面有n个圆盘,从上至下圆盘逐渐增大,每次只能移动一个圆盘,并且规定大的圆盘不能叠放在小的圆盘上面,现在想要把A上面的n个圆盘全部都移动到C上面,输出移动的总步数以及移动的过程

分析:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//先求出移动的总步数
1,假设g(n)表示n个圆盘时的移动总的步数,当n=1时,g(1)=1;
 
2.现在可以把g(n)进行细分为三步:
  1>先将n-1个圆盘从A通过C移动到B上面,相当于将n-1个圆盘从A移动到C,因此需要g(n-1)步;
  2>然后将剩下的最大的圆盘从A移动到C,需要1步;
  3>最后再将n-1个圆盘从B通过A移动到C上面,相当于将n-1个圆盘从A移动到C,因此也需要g(n-1)步;
因此可以得出递归关系式:g(n) = 2*g(n-1)+1;
 
//现在我们在来求出移动的过程
1.假设hm(m,a,b,c)表示将m个圆盘从a通过b移动到c的过程,假设mv(a,c)输出一次a到c的过程,即print a-->c
 
2.初始化hm,当m=1时,hm(1,a,b,c)=mv(a,c);
2.可以把hm(m,a,b,c)进行细分为三步:
  1>先将n-1个圆盘从A通过C移动到B,此时b和c进行互换,也就是 hm(m-1,a,c,b);
  2>然后将剩下的最大的圆盘从A移动到C,也就是hm(1,a,b,c);
  3>最后将n-1个圆盘从B通过A移动到C,此时b和a进行交换,也就是 hm(m-1,b,a,c);
最终得到过程的递归关系式:hm(m,a,b,c) = hm(m-1,a,c,b)+1+hm(m-1,b,a,c);

实现代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class test{
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    test t = new test();
    //获取总的步数
    System.out.println("需要移动的总步数为:" +t.getSum(n));
    //获取移动的过程
    t.hm(n,'a','b','c');
  }
  //获取总步数
  public int getSum(int n){
    if(n == 1)
      return 1;
    return 2 * getSum(n-1) +1 ;
  }
 
  //获取移动的过程
  public void hm(int m,char a,char b,char c){
    if(m == 1)
      move(a,c);
    hm(m-1,a,c,b);
    move(a,c);
    hm(m-1,b,a,c);
  }
 
  //输出一次移动的过程
  public void move(char a,char c){
    System.out.print(a + "-->" + c + "  ");
  }
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

原文链接:http://blog.csdn.net/qq_27905183/article/details/64123828

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
返回顶部