0033-二叉树

问题描述

由正整数 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;
        }
    }
}