小球下落

题目：

有一颗二叉树，最大深度为d，且所有叶子的深度都相同。所有节点从上到下从左到右编号为1,2,3,...,2^d-1。

他的状态都会改变。当小球到达一个内节点时，如果该节点上的开关关闭，则往左走，否则往右走，直到走到叶子节点。

如图：

现在有一些小球从节点1处一次开始下落，最后一个小球将会落在哪里呢？输入叶子深度d和小球个数num，输出第num个小球最后所在的叶子编号。
假设num不超过整棵树的叶子个数，d<=20，最多输入包含1000组数据。

样例输入：

4 2

3 4

16 12345

样例输出：

12

7

36358

分析：
 * 1，利用二叉树的特性，一个节点k的左子节点是2k,右子节点是2k+1。
 * 2，num不超过整棵树的叶子个数，即num要小于二叉树的节点树，满二叉树的节点数是：2^层数-1

public class Test9 {
	private static final int MAXD = 20;
	private static int[] s = new int[1<<MAXD];//初始化保存节点的数组
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int d = scan.nextInt();//输入层数
		int num = scan.nextInt();//输入小球个数
		int result = getResult(d,num);
		System.out.println(result);
	}
	public static int getResult(int d,int num) {
		int k = 1,n = (1 << d) - 1;//k是当前节点，n是二叉树节点个数。
		for (int i = 0; i < num; i++) {//num个小球下落
			k = 1;
			for(;;) {
				//0代表关闭，1代表开启
				if(s[k] == 0) {
					s[k] = 1;
				} else {
					s[k] = 0;
				}
				/*
				由于提前做了置换状态的操作，而这里需要根据置换之前的状态判断小球往哪里落，
				所以这里判断是0，则表示置换前是1，向右走，如果是1则表示置换前是0，向左走。
				*/
				k = s[k] == 0 ? k*2+1 : k*2;
				if(k > n)
					break;
			}
		}
		return k/2;
	}
}

其中一种优化方案的解决思路：

每个小球都会落在根节点上，因此前两个小球必然一个在左子树，一个在右子树。一般的，只需要看小球编号的奇偶性，就能知道它最终在哪颗子树中。对于那些落入根节点左子树的小球来说，只需要知道该小球是第几个落在根的左子树里的，就可以知道它下一步往左还是往右了。依次类推，直到小球落在叶子上。

如果使用题目中给出的编号num，则当num是奇数时，他是往左走的第(num+1)/2个小球；当num是偶数时，他是往右走的第num/2个小球。这样，可以直接模拟最后一个小球的路线：

public class Test9_1 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String src = scan.nextLine();
		String[] ss = src.split(" ");
		int d = Integer.parseInt(ss[0]);
		int num = Integer.parseInt(ss[1]);
		int result = getResult(d,num);
		System.out.println(result);
	}
	public static int getResult(int d,int num) {
		int k = 1;
		for(int i=0;i<d-1;i++) {
			if(num%2 == 1) {
				k = k * 2;
				num = (num + 1) / 2;
			} e lse {
				k = k * 2 + 1;
				num /= 2;
			}
		}
		return k;
	}
}

小球下落

原文：http://blog.csdn.net/xzm_rainbow/article/details/18311695