汉诺塔 问题 VIII
题目链接: 汉诺塔问题VIII.
题目:
分析:
与汉诺塔VII类似 .
题目要求找出当前步数下的状态
我们知道:
N个圆盘的总移动次数
=2的n次方-1
=(2的(n-1)次方-1)+ 1 +(2的(n-1)次方-1);
所以我们可以采用递归运算的方式,
根据步数确定当前最大的圆盘所在的位置
当步数>=2的(n-1)次方时,圆盘在末位置
否则,圆盘在初位置
AC代码
package Two;
import java.util.*;
public class 汉诺塔VIII {
public static ArrayList<Integer>[] arr=new ArrayList[3];
public static void dfs(int n,long m,int from,int mid,int to){
if(n<=0)return ;
//为了避免出现精度不够的问题+0.000001
if(m>=(long)(Math.pow(2, n-1)+0.000001)){
arr[to].add(n);
m-=(long)(Math.pow(2, n-1)+0.000001);
dfs(n-1,m,mid,from,to);
}else{
arr[from].add(n);
dfs(n-1,m,from,to,mid);
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
long m=sc.nextLong();
for(int i=0;i<3;i++){
arr[i]=new ArrayList<Integer>();
}
dfs(n,m,0,1,2);
for(int i=0;i<3;i++){
System.out.print(arr[i].size());
for(int tt:arr[i]){
System.out.print(" "+tt);
}
System.out.println();
}
}
}
}
还没有评论,来说两句吧...