汉诺塔 问题 VIII

小灰灰 2023-07-05 13:13 28阅读 0赞

题目链接: 汉诺塔问题VIII.

题目:

在这里插入图片描述

分析:

与汉诺塔VII类似 .

题目要求找出当前步数下的状态

  1. 我们知道:
  2. N个圆盘的总移动次数
  3. =2n次方-1
  4. =(2的(n-1)次方-1)+ 1 +(2的(n-1)次方-1);

所以我们可以采用递归运算的方式,

根据步数确定当前最大的圆盘所在的位置

当步数>=2的(n-1)次方时,圆盘在末位置
否则,圆盘在初位置

AC代码

  1. package Two;
  2. import java.util.*;
  3. public class 汉诺塔VIII {
  4. public static ArrayList<Integer>[] arr=new ArrayList[3];
  5. public static void dfs(int n,long m,int from,int mid,int to){
  6. if(n<=0)return ;
  7. //为了避免出现精度不够的问题+0.000001
  8. if(m>=(long)(Math.pow(2, n-1)+0.000001)){
  9. arr[to].add(n);
  10. m-=(long)(Math.pow(2, n-1)+0.000001);
  11. dfs(n-1,m,mid,from,to);
  12. }else{
  13. arr[from].add(n);
  14. dfs(n-1,m,from,to,mid);
  15. }
  16. }
  17. public static void main(String[] args) {
  18. Scanner sc=new Scanner(System.in);
  19. int t=sc.nextInt();
  20. while(t-->0){
  21. int n=sc.nextInt();
  22. long m=sc.nextLong();
  23. for(int i=0;i<3;i++){
  24. arr[i]=new ArrayList<Integer>();
  25. }
  26. dfs(n,m,0,1,2);
  27. for(int i=0;i<3;i++){
  28. System.out.print(arr[i].size());
  29. for(int tt:arr[i]){
  30. System.out.print(" "+tt);
  31. }
  32. System.out.println();
  33. }
  34. }
  35. }
  36. }

发表评论

表情:
评论列表 (有 0 条评论,28人围观)

还没有评论,来说两句吧...

相关阅读

    相关 问题

    1.汉诺塔问题:如果将n个盘子(由小到大)从a通过b,搬到c,搬运过程中不能出现小盘子在大盘子下面的情况。 分析:这个一个递归问题。只要将n-1个盘子从a通过c(没有中间点肯

    相关 问题

    汉诺塔 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵

    相关 问题

    问题描述: 相传在[古印度][Link 1]圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺

    相关 问题

    汉诺塔问题是经典的递归问题,它的递归类型是:求解问题的方法是递归的。 解题思路: 1. 首先将n-1个盘子从X借助Z移动到Y。 2. 将第n个盘子从X移动到Z。 3.

    相关 问题

    汉诺塔(Tower of Hanoi)源于印度传说中,大梵天创造世界时造了三根金钢石柱子,其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新