問題描述

由正整數(shù) 1, 2, 3, ...組成了一棵無限大的二叉樹。從某一個(gè)結(jié)點(diǎn)到根結(jié)點(diǎn)(編號(hào)是 1 的結(jié)點(diǎn))都有一條唯一的路徑,比如從10到根結(jié)點(diǎn)的路徑是(10,5,2,1),從4到根結(jié)點(diǎn)的路徑是(4,2,1),從根結(jié)點(diǎn)1到根結(jié)點(diǎn)的路徑上只包含一個(gè)結(jié)點(diǎn)1,因此路徑就是(1)。對(duì)于兩個(gè)結(jié)點(diǎn)x和y,假設(shè)他們到根結(jié)點(diǎn)的路徑分別是(x1, x2, ... ,1)和(y1,y2, ... ,1)(這里顯然有 x=x1,y=y1),那么必然存在兩個(gè)正整數(shù)i和 j,使得從xi和yj開始,有 xi=yj ,x(i+1) = y(j + 1),x(i+2) = y(j + 2),... 現(xiàn)在的問題就是,給定 x 和 y,要求xi(也就是 yj) 。

輸入

輸入只有一行,包括兩個(gè)正整數(shù)x和y,這兩個(gè)正整數(shù)都不大于1000。

輸出

輸出只有一個(gè)正整數(shù) xi。

輸入樣列

10 4

輸出樣例

2

算法實(shí)現(xiàn)

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;
        }
    }
}