OpenJudge 2756ツリー

1.リンク先:
http://bailian.openjudge.cn/practice/2756/
2.タイトル:
合計時間制限:
1000ms
メモリの制限:
65536kB
説明

上図に示すように、正の整数1,2,3,...から無限大の二叉木が構成されています.あるノードからルートノード(番号が1のノード)までの唯一のパスがあります.例えば、10からルートノードへのパスは(10,5,2,1)、4からルートノードへのパスは(4,2,1)、ルートノード1からルートノードへのパスには1つのノード1しか含まれていないので、パスは(1)です.2つのノードxとyについて,ルートノードへの経路がそれぞれ(x
1, x
2,...,1)と(y
1, y
2,...,1)(ここでは明らかにx=x
1,y = y
1)では、xから
iとy
jからxがある
i = y
j , x
i + 1 = y
j + 1, x
i + 2 = y
j+2,...現在の問題は,xとyを与え,xを要求することである.
i(つまりy
j).
入力
入力は1行のみで、2つの正の整数xとyを含み、この2つの正の整数はいずれも1000を超えない.
しゅつりょく
出力は正の整数xのみ
i.
サンプル入力

10 4

サンプル出力

2

3.考え方:
再帰
4.コード:

 1 #include <iostream>

 2 

 3 using namespace std;

 4 

 5 int f(int x,int y)

 6 {

 7     if(x == y) return x;

 8     else if(x > y) return f(x/2,y);

 9     else return f(x,y/2);

10 }

11 

12 int main()

13 {

14     int x,y;

15     cin>>x>>y;

16     cout<<f(x,y)<<endl;

17     return 0;

18 }