问题描述
由正整数 1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点(编号是 1 的结点)都有一条唯一的路径,比如从10到根结点的路径是(10,5,2,1),从4到根结点的路径是(4,2,1),从根结点1到根结点的路径上只包含一个结点1,因此路径就是(1)。对于两个结点x和y,假设他们到根结点的路径分别是(x1, x2, ... ,1)和(y1,y2, ... ,1)(这里显然有 x=x1,y=y1),那么必然存在两个正整数i和 j,使得从xi和yj开始,有 xi=yj ,x(i+1) = y(j + 1),x(i+2) = y(j + 2),... 现在的问题就是,给定 x 和 y,要求xi(也就是 yj) 。
输入
输入只有一行,包括两个正整数x和y,这两个正整数都不大于1000。
输出
输出只有一个正整数 xi。
输入样列
10 4
输出样例
2
算法实现
using System;
namespace Questions{
class Program{
public static void Main(string[] args){
string input = Console.ReadLine();
string[] data = input.Split(' ');
int x = int.Parse(data[0]);
int y = int.Parse(data[1]);
int[] dataX = BinaryTree(x);
int[] dataY = BinaryTree(y);
bool flag = false;
for (int i = 0; i <= dataX.Length - 1; i++)
{
for (int j = 0; j <= dataY.Length - 1; j++)
{
if (dataX[i] == dataY[j])
{
Console.WriteLine(dataX[i]);
flag = !flag;
break;
}
if (dataX[i] > dataY[j])
continue;
}
if (flag) break;
}
Console.ReadKey();
}
public static int[] BinaryTree(int num)
{
int[] data = new int[12];
int i = 0;
while (num != 1)
{
data[i++] = num;
num = num / 2;
}
data[i++] = 1;
return data;
}
}
}