学步园

这个题需要用到的还是递归.从最大的那个开始判断,是否满足题目中的条件.简单的说就是如果最大的那个在编号是3上,那么我们就不需要移动了,如果不在编号3的针上,则需要移动2^(n-1)次.其他的金片依此类推````````

汉诺塔（二）

描述

汉诺塔的规则这里就不再多说了，详见题目：汉诺塔（一）

现在假设规定要把所有的金片移动到第三个针上，给你任意一种处于合法状态的汉诺塔，你能计算出从当前状态移动到目标状态所需要的最少步数吗？

输入

第一行输入一个整数N，表示测试数据的组数(0<N<20)
每组测试数据的第一行是一个整数m表示汉诺塔的层数(0<m<32)，随后的一行有m个整数Ai,表示第i小的金片所在的针的编号。（三根针的编号分别为1，2，3）

输出

输出从当前状态所所有的金片都移动到编号为3的针上所需要的最少总数

样例输入

2
3
1 1 1
3
1 1 3

样例输出

7
3

代码1：

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	static int result[]=new int[40]; 
	public static int hanno(int a,int b,int c,int m)
	{
		 if(m==1)
		 {
			 if(result[m]==c) return 0;
			 else return 1;
		 }
		 else if(result[m]==c) return hanno(a, b, c, m-1);
		 else if(result[m]==a) return hanno(a, c, b, m-1)+(1<<(m-1));
		 else{
		    return hanno(b, c, a, m-1)+(1<<(m-1));
		 }
	}
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int cases=scanner.nextInt();
		while(cases--!=0)
		{
		   Arrays.fill(result, 0);
		   int number=scanner.nextInt();
		   for(int i=1;i<=number;i++)
		   {
			   int x=scanner.nextInt();
			   result[i]=x;
		   }
		   System.out.println(hanno(1,2,3,number));
		}
	}
}

代码2：还有别人的代码，其中没有弄懂其中的一行代码

#include<stdio.h>
#include<string.h>
int step[33],num[33];
void find()
{
	step[0]=1;
	for(int i=1;i<=33;i++)
		step[i]=step[i-1]*2;
}
int main()
{
	find();
	int t,n,m;
	scanf("%d",&t);
	while(t--)
	{
		int t=3,i,sum=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		for(i=n-1;i>=0;i--)
		{
			if(num[i]!=t)
			{
				sum+=step[i];
				t=6-num[i]-t;//当n-1时，如果第n-1小的（也就是最大的）不在3号针上，比如在2上，则会把小于第n-1个盘的其他盘移到1号针上去
                                //然后判断第n-2小的盘在不在1号针上，依次类推......也就是针的总和数6减去num[i]所在的号数，减去n-1个盘所在的位置（自己模拟画画图）
			}
		}
		printf("%d\n",sum);
	}
}