吉林省长春市建设局网站,石家庄市工程勘察设计咨询业协会,企业网站建设的基本标准是,学校校园网网站建设预算二叉树
题目描述 如上图所示#xff0c;由正整数1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点#xff08;编号是1的结点#xff09;都有一条唯一的路径#xff0c;比如从10到根结点的路径是(10, 5, 2, 1)#xff0c;从4到根结点的路径是(4, 2, 1)#x…二叉树
题目描述 如上图所示由正整数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 x1y y1那么必然存在两个正整数i和j使得从xi 和 yj开始有xi yj , xi 1 yj 1, xi 2 yj 2,... 现在的问题就是给定x和y要求xi也就是yj。 关于输入
输入只有一行包括两个正整数x和y这两个正整数都不大于1000。
关于输出
输出只有一个正整数xi。
例子输入
10 4
例子输出
2
解题分析
这个问题的关键在于理解题目中的二叉树的特性。在这个二叉树中每个节点 i 的两个子节点是 2*i 和 2*i1。因此每个节点 i 的父节点是 i/2。这是一个关键的性质因为它意味着我们可以通过除以2来找到任何节点的父节点。
给定两个节点 x 和 y我们的目标是找到他们的最近公共祖先。由于我们可以通过除以2来找到任何节点的父节点因此一个直观的方法是从 x 和 y 开始不断地找他们的父节点直到我们找到一个公共的节点。这个公共的节点就是他们的最近公共祖先。
在具体实现上我们定义了一个函数findCommonAncestor它接受两个整数 x 和 y 作为输入返回这两个整数在二叉树中的最近公共祖先。在这个函数中我们使用了一个循环不断地将较大的数除以2直到 x 和 y 相等。这是因为在这个二叉树中一个节点的父节点总是它的一半所以我们可以通过不断地将较大的数除以2来找到两个节点的最近公共祖先。
在main函数中我们从用户那里获取输入的 x 和 y调用findCommonAncestor函数找到他们的最近公共祖先并打印出结果。
这个算法的时间复杂度是 O(log n)其中 n 是输入的节点的编号。这是因为在最坏的情况下我们需要找到节点 1这需要做 log n 次除法操作。因此这个算法是非常高效的。
代码实现
#include stdio.hint findCommonAncestor(int x, int y) {while (x ! y) {if (x y) {x / 2;} else {y / 2;}}return x;
}int main() {int x, y;scanf(%d %d, x, y);printf(%d\n, findCommonAncestor(x, y));return 0;
}
