1110: 最近共同祖先（函數專題）
時間限制: 1 Sec 內存限制: 128 MB
提交: 3818 解決: 3290
[提交] [狀態] [討論版] [命題人:admin]
題目描述
如上圖所示，由正整數1, 2, 3, …組成了一棵無限大的二叉樹。從某一個結點到根結
點（編號是1 的結點）都有一條唯一的路徑，比如從10 到根結點的路徑是(10, 5, 2, 1)，
從4 到根結點的路徑是(4, 2, 1)，從該結點到根結點的路徑上的所有結點稱為該結點的祖先。現在的問題就是，給定x 和y，求x和y的最近共同祖先，比如，10和4最近共同祖先是2，10和5的最近共同祖先是5。
定義遞歸函數
int common(int x, int y)
{
如果x==y, return x;
如果x>y，求x/2與y的共同祖先;
否則，求x與y/2的共同祖先;
}
輸入
輸入只有一行，包括兩個正整數x 和y，這兩個正整數都不大于1000。
輸出
輸出只有一個正整數，即x和y的最近共同祖先。
樣例輸入
10 4
樣例輸出
2
來源/分類
**
#include<stdio.h>
int common(int x,int y)
{if(x==y)return x;else if(x>y)common(x/2,y);else common(x,y/2);
}
int main()
{int x,y,z;scanf("%d%d",&x,&y);z=common(x,y);printf("%d",z);
}
)
