输入数据包括多行,每行给出一组测试数据,包括两个整数m,n (1 <= m <= n <= 1000000000)。
对于每一组测试数据,输出一行,该行包含一个整数,给出结点m所在子树中包括的结点的数目。
3 12 0 0
4
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static int count = 0; //孩子的总结点数 public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextInt()) { int m = in.nextInt();//求m结点一共有多少个结点 int n = in.nextInt();//总结点数 if (m == 0 && n == 0) break; //解题思路:分别求该结点的左右孩子有多少个结点即可 getCount(m, n); System.out.println(count); } } public static void getCount(int i, int n) { //i表示第i个结点 n表示总结点数 if (i > n) //递归退出条件 return; count++; //结点总数+1 getCount(i * 2, n); //递归求左孩子结点总数 getCount(i * 2 + 1, n); //递归求右孩子结点总数 } }
import java.util.Scanner; public class Main { static int count=0; static int n; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int m = scanner.nextInt(); n = scanner.nextInt(); fun(m); System.out.println(count); } static void fun(int m){ if (m<=n){ count++; fun(m*2); fun(m*2+1); } } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int m = scanner.nextInt(); int n = scanner.nextInt(); System.out.println(findSubTree(m, n) - 1); } scanner.close(); } static int findSubTree(int x, int n) { if (x > n) return 1; return findSubTree(2 * x, n) + findSubTree(2 * x + 1, n); } } /* * 递归部分实际求的是树的虚拟叶结点数,所谓虚拟叶结点,是指把一棵树补成完全二叉树而 * 新添加的虚拟叶结点。 可以证明,虚拟叶结点数=树结点数+1。证明如下: * 设虚拟叶结点数为x,有x = 2*n0 + n1, 设树总结点数为n,有n = n0 + n1 + n2。 * 树同时具有性质n0 = n2+1, 所以,x = n0 * + n1 + n2 + 1 = n+1。 注:上述ni是度为i的结点 */