首页 > 试题广场 >

Stern-Brocot tree

[编程题]Stern-Brocot tree
  • 热度指数：364 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
The Stern-Brocot tree is an infinite complete binary tree in which the vertices correspond one-for-one to the positive rational numbers, whose values are ordered from the left to the right as in a search tree.



Figure 1 shows a part of the Stern-Brocot tree, which has the first 4 rows. Each node in the tree is marked in a red cycle. The value in the node is the mediant of the left and right fractions. The mediant of two fractions A/B and C/D is defined as (A+C)/(B+D).
To construct the Stern-Brocot tree, we first define the left fraction of the root node is 0/1, and the right fraction of the root node is 1/0. So the value in the root node is the mediant of 0/1 and 1/0, which is (0+1)/(1+0)=1/1. Then the value of root node becomes the right fraction of the left child, and the left fraction of the right child. For example, the 1st node in row2 has 0/1 as its left fraction and 1/1(which is the value of its parent node) as its right fraction. So the value of the 1st node in row2 is (0+1)/(1+1)=1/2. For the same reason, the value of the 2nd node in row2 is (1+1)/(1+0)=2/1. This construction progress goes on infinitly. As a result, every positive rational number can be found on the Stern-Brocot tree, and can be found only once.

Given a rational number in form of P/Q, find the position of P/Q in the Stern-Brocot Tree.


输入描述:
Input consists of two integers, P and Q (1<=P,Q<=1000), which represent the rational number P/Q. We promise P and Q are relatively prime.


输出描述:
Output consists of two integers, R and C.
R indicates the row index of P/Q in the Stern-Brocot Tree, C indicates the index of P/Q in the row.
Both R and C are base 1.
We promise the position of P/Q is always in the first 12 rows of the Stern-Brocot tree, which means R<=12.
示例1

输入

5 3

输出

4 6
算法知识视频讲解
添加回答
大唐码农头像 大唐码农
c++ 二分查找法 
#include <iostream>
using namespace std;

int main() {
	int m, n;
	cin >> m >> n;
	if (m == 1 && n == 1) {
		cout << "1 1";
		exit(0);
	}
	int left[2], right[2];
	int col = 2, row;
	if ((1.0*m) / (1.0*n) < 1) {
		left[0] = 0;
		left[1] = 1;
		right[0] = 1;
		right[1] = 1;
		row = 1;
	}
	else {
		left[0] = 1;
		left[1] = 1;
		right[0] = 1;
		right[1] = 0;
		row = 2;
	}
	int mid[2];
	while (true) {
		mid[0] = left[0] + right[0];
		mid[1] = left[1] + right[1];
		if (mid[0] == m && mid[1] == n) {
			cout << col << " " << row;
			break;
		}
		else if ((1.0*m) / (1.0*n) < (1.0*mid[0]) / (1.0*mid[1])) {
			right[0] = mid[0];
			right[1] = mid[1];
			row = 2 * row - 1;
		}
		else {
			left[0] = mid[0];
			left[1] = mid[1];
			row = 2 * row;
		}
		col++;
	}
	return 0;
}

发表于 2020-08-31 20:42:13 回复(1)
C/C++
vastina头像 vastina
如果比当前节点大就往右(ans*=2)，否则往左(ans=ans*2-1)。0/1叫root(1/1)的left，1/0叫root的right，往左子节点的right继承父节点的值，left则继承父节点的left，往右刚好相反。最后时间5ms，内存488kb 
#include <iostream>
using namespace std;

struct a{
    int ly, lx;
    int ry, rx;
};

int main() {
    a cmp;
    cmp.ly = 0;    cmp.lx = 1;
    cmp.ry = 1;    cmp.rx = 0;
    int y, x, i=1;   cin>>y>>x;
    long long ans=1;
    while(y!=cmp.ly+cmp.ry || x!=cmp.lx+cmp.rx){
        ++i;
        if(y*(cmp.lx+cmp.rx) > x*(cmp.ly+cmp.ry)){ 
            ans =ans*2;
            cmp.lx = cmp.lx + cmp.rx;
            cmp.ly = cmp.ly + cmp.ry;
        }
        else {
            ans = ans*2 -1;
            cmp.rx = cmp.lx + cmp.rx;
            cmp.ry = cmp.ly + cmp.ry;
        }
    }
    std::cout << i << ' ' <<ans; 
}


编辑于 2023-12-16 00:28:43 回复(0)
Atodush头像 Atodush
完全二叉树的性质啊兄弟们 
#include <iostream>
using namespace std;

int main() {
    int P, Q;
    cin >> P >> Q;

    int A = 0, B = 1, C = 1, D = 0;
    int row = 1, col = 1;

    int VU = 1, VD = 1;
    double value = (double) P / Q;
    while (!(VU == P && VD == Q)) {
        double mid = (double) VU / VD;
        if (value > mid) {
            A = VU;
            B = VD;
            col = col * 2;
        } else {
            C = VU;
            D = VD;
            col = col * 2 - 1;
        }
        row += 1;
        VU = A + C;
        VD = B + D;
    }

    cout << row << " " << col << endl;
}
// 64 位输出请用 printf("%lld")


发表于 2025-09-26 12:53:49 回复(0)
Python
greatofdream头像 greatofdream

二分搜索，不考虑互质

import sys
P, Q = map(int, sys.stdin.readline().split())

l_u, l_d, r_u, r_d = 0, 1, 1, 0
c_u, c_d = 1, 1
R, C = 1, 1
while (P != c_u or  Q != c_d) and R<=12:
    R += 1
    if P * c_d < Q * c_u:
        r_u, r_d = c_u, c_d
        C = C*2 -1
    else:
        l_u, l_d = c_u, c_d
        C = C * 2
    c_u, c_d = l_u + r_u, l_d + r_d
print(R, C)
发表于 2025-04-12 00:13:44 回复(0)
牛客129782836号头像 牛客129782836号
#                            1/1
#             1/2                           2/1
#       1/3         2/3              3/2            3/1
#   1/4    2/5   3/5   3/4        4/3   5/3     5/2     4/1
 
 
deffindXY(n, d, xl, yl, x, y, xr, yr, level, posi):
    # print(n, d, x, y, n/d, x/y)
    if(n ==x andd ==y):
        returnlevel, posi
    else:
        # calculate
        if(n/d > x/y):
            returnfindXY(n, d, x, y, x+xr, y+yr, xr, yr, level+1, posi*2)
        elif(n/d < x/y): # (n/d < x/y)
            returnfindXY(n, d, xl, yl, x+xl, y+yl, x, y, level+1, posi*2-1)
        else:
            return[0, 0]
  
if__name__ =="__main__":
    n, d =[int(x) forx ininput().split(" ")]
    rt =findXY(n, d, 0, 1, 1, 1, 1, 0, 1, 1)
    print(str(rt[0]) +" "+str(rt[1]))
发表于 2021-08-05 16:30:40 回复(0)
GirafeeBlue头像 GirafeeBlue 
#include <iostream>
#include <vector>
#include <memory>

struct Pair {
	int x;
	int y;
};

struct TreeNode {
	Pair val;
	Pair left;
	Pair right;

	inline void Calc() {
		val.x = left.x + right.x;
		val.y = left.y + right.y;
	}
};

int main() {
	int P, Q;
	std::cin >> P >> Q;

	std::vector<std::shared_ptr<TreeNode>> nodes;

	auto node = std::make_shared<TreeNode>();
	node->left = { 0, 1 };
	node->right = { 1, 0 };
	nodes.push_back(node);

	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < (1 << i); j++) {
			int index = (1 << i) - 1 + j;
			node = nodes[index];

			node->Calc();
			if (node->val.x == P && node->val.y == Q) {
				std::cout << i + 1 << " " << j + 1;
				return 0;
			}

			auto leftChild = std::make_shared<TreeNode>();
			leftChild->left = node->left;
			leftChild->right = node->val;

			auto rightChild = std::make_shared<TreeNode>();
			rightChild->left = node->val;
			rightChild->right = node->right;

			nodes.push_back(leftChild);
			nodes.push_back(rightChild);
		}
	}


	return 0;
}
C++ 广度边建树边查找
发表于 2021-04-23 12:35:13 回复(0)
butterCat头像 butterCat 
#include<iostream>
#include<list>
#include<cmath>

using namespace std;

//鹅，只想到嗯建树
struct tnode{
    tnode* leftChild;
    tnode* rightChild;
    pair<int,int> left;        //左分母
    pair<int,int> right;       //右分母
    pair<int,int> val;
};

void consturctTree(tnode* root, int level, int maxlevel){
    if(level>=maxlevel) return;
    //左孩子左分母同根节点左分母，左孩子右分母为根节点，右孩子反之
    //左分母为A/B，右分母为C/D，自身则为(A+C)/(B+D)
    tnode* pleft = new tnode;
    pleft->left = root->left;
    pleft->right = root->val;
    pleft->val = make_pair(pleft->left.first + pleft->right.first, pleft->left.second + pleft->right.second);
    tnode* pright = new tnode;
    pright->left = root->val;
    pright->right = root->right;
    pright->val = make_pair(pright->left.first + pright->right.first, pright->left.second + pright->right.second);
    root->leftChild = pleft;
    root->rightChild = pright;
    consturctTree(pleft,level+1,maxlevel);
    consturctTree(pright,level+1,maxlevel);
}

int main(){
    int p,q;    //求出p/q的节点位置（第几行第几个）
    cin >> p >> q;
    //建树
    tnode* root = new tnode;
    root->val = make_pair<int,int>(1,1);
    root->left = make_pair<int,int>(0,1);
    root->right = make_pair<int,int>(1,0);
    consturctTree(root,1,12);
    //层次遍历
    int seqNum = 0;
    int row = 1;
    int index = 0;
    list<tnode*> lt;
    lt.push_back(root);
    while(!lt.empty()){
        if(lt.front()->leftChild){
            lt.push_back(lt.front()->leftChild);
        }
        if(lt.front()->rightChild){
            lt.push_back(lt.front()->rightChild);
        }
        ++seqNum;
        if(lt.front()->val.first==p && lt.front()->val.second==q){
            int mySeq = seqNum;
            while(mySeq/=2) ++row;
            //2^(层数-1)是该层第一项的下标
            index = seqNum-pow(2,row-1)+1;
            cout << row << " " << index;
            break;
        }
        lt.pop_front();
    }
}


发表于 2021-04-01 17:32:36 回复(0)
绯村拔刀齐头像 绯村拔刀齐
只有我一个憨憨没注意到二分法，然后直接把这棵树建起来了么🙄🙄 
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

struct SBNode
{
	int numerator;//分子
	int Denominator;//分母

	SBNode(int n, int d) :numerator(n), Denominator(d)
	{
	}

	friend SBNode operator+(const SBNode& ancestor, const SBNode& parent);
};

SBNode operator+(const SBNode& ancestor, const SBNode& parent)
{
	return SBNode(ancestor.numerator + parent.numerator, ancestor.Denominator + parent.Denominator);
}

constexpr bool IsLChild(const int& index)//完全二叉树判断这个节点是否为左孩子
{
	return index % 2;
}

constexpr bool IsRChild(const int& index)//完全二叉树判断这个节点是否为右孩子
{
	return (index != 0) && (!(index % 2));//排除掉根节点的情况
}

int FindPreNode(int index)//找当前节点的前驱，由于此题在建立树的过程中，当前建立的节点必然是叶节点，所以不需要考虑其子节点的情况。
{
	while (IsLChild(index))//判断其是否为左孩子，直到找到一个并非左孩子的祖先。
	{
		index = (index - 1) / 2;//父亲节点对应的序号
	}

	if (index==0)
	{
		return -1;//若已经遍历到了根节点，则说明这个节点没有前驱。即其前驱为0/1.
	}
	else
	{
		return (index - 1) / 2;//这个祖先的父亲即为这个节点的前驱。
	}
}

int FindNextNode(int index)//找当前节点的后继，由于此题在建立树的过程中，当前建立的节点必然是叶节点，所以不需要考虑其子节点的情况。
{
	while (IsRChild(index))//判断其是否为右孩子，直到找到一个并非右孩子的祖先。
	{
		index = (index - 1) / 2;//父亲节点对应的序号
	}

	if (index == 0)
	{
		return -1;//若已经遍历到了根节点，则说明这个节点没有后继。即其前驱为1/0.
	}
	else
	{
		return (index - 1) / 2;//这个祖先的父亲即为这个节点的后继。
	}
}

int main()
{
	int P, Q;
	cin >> P >> Q;

	int row = std::max(P, Q);//需要建立的二叉树的行数
	if (row > 12)
	{
		row = 12;
	}

	int SBTreeNumber = static_cast<int>(pow(2, row)) - 1;//需要建立的完全二叉树节点数

	SBNode LNode(0, 1);
	SBNode RNode(1, 0);

	vector<SBNode> SBTree;
	SBTree.push_back(SBNode(1,1));

	SBNode PreNode(0, 1);//循环外创建类
	SBNode NextNode(1, 0);
	for (int i = 1; i < SBTreeNumber; ++i)
	{
		int PreIndex = FindPreNode(i);//找这个叶节点的前驱和后继的序号
		int NextIndex = FindNextNode(i);

		if (PreIndex==-1)//没有前驱节点
		{
			PreNode = LNode;//有默认拷贝赋值，则不需要额外写
		}
		else
		{
			PreNode = SBTree[PreIndex];
		}

		if (NextIndex==-1)//没有后继节点
		{
			NextNode = RNode;
		}
		else
		{
			NextNode = SBTree[NextIndex];
		}

		SBTree.push_back(PreNode + NextNode);
	}

	//for (const auto& node : SBTree)
	//{
	//	cout << "分子为：" << node.numerator << "  " << "分母为：" << node.Denominator << endl;
	//}

	
	for (int j = 0; j < SBTreeNumber; j++)
	{
		if (P == SBTree[j].numerator && Q == SBTree[j].Denominator)
		{
			int R = static_cast<int>(floor(log(j + 1) / log(2))) + 1;//判断节点所在行数，需要用floor函数。
			int C = j + 2 - static_cast<int>(pow(2, R - 1));//判断节点所在行数的序号。
			cout << R << " " << C << endl;
			break;
		}
	}
	return 0;
}
发表于 2020-10-12 23:09:28 回复(0)
没有出口的迷宫头像 没有出口的迷宫
做这题的时候注意到了每一层是有序的（直接二分），没注意到可以直接利用有序进行DFS，当然也AC了，毕竟题目写着不超过12层
def binary_search(ls, x1, x2):
    start = 0
    end = len(ls) - 1
    while start <= end:
        mid = (start + end) // 2
        if x1 * ls[mid][1] == x2 * ls[mid][0]:
            return mid
        elif x1 * ls[mid][1] < x2 * ls[mid][0]:
            end = mid - 1
        else:
            start = mid + 1
    return None
 
def find_in_layer(x1, x2):
    if x1 == 0&nbs***bsp;x2 == 0:
        return None
    _layer = [(0, 1), (1, 1), (1, 0)]
    _depth = 1
    while True:
        _search = binary_search(_layer, x1, x2)
        if _search is not None:
            return _depth, (_search + 1) // 2
        new_layer = [(0, 1)]
        for i in range(len(_layer) - 1):
            new_layer.append((_layer[i][0] + _layer[i + 1][0], _layer[i][1] + _layer[i + 1][1]))
            new_layer.append(_layer[i + 1])
        _layer = new_layer
        _depth += 1
 


发表于 2020-08-23 17:53:54 回复(0)
是哥哥啊头像 是哥哥啊 
def search(P, Q, X, Y, Row, Col, Lx, Ly, Rx, Ry):

    # 终止条件
    if P == X and Q == Y:
        return Row, Col

    # 向左搜索   
    if P / Q < X / Y:
        r, c = search(P, Q, X + Lx, Y + Ly, Row + 1, 2 * Col - 1, Lx, Ly, X, Y)

    # 向右搜索
    else:
        r, c = search(P, Q, X + Rx, Y + Ry, Row + 1, 2 * Col, X, Y, Rx, Ry)

    return r, c

getNumsFromString = lambda x: list(map(int, x.strip().split()))
P, Q = getNumsFromString(input())
R, C = search(P, Q, 1, 1, 1, 1, 0, 1, 1, 0)
print(R, C)
发表于 2020-07-18 19:29:10 回复(0)
RicardoSaudade头像 RicardoSaudade
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
typedef pair<int, int> P;
vector<P> vec;
void dfs_left(int l1, int l2, int r1, int r2, int depth) //l1/l2 , r1/r2
{
    if (depth >= n) return;
    //Stern-Brocot树 左侧总是最小的，右侧最大的，那么总是优先输入左侧，再输入中间的，最后输入右侧的数
    dfs_left(l1, l2, l1 + r1, l2 + r2, depth + 1);
    vec.push_back(P(l1 + r1, l2 + r2));
    dfs_left(l1 + r1, l2 + r2, r1, r2, depth + 1);
}

void dfs_right(int l1, int l2, int r1, int r2, int depth) //l1/l2 , r1/r2
{
    if (depth >= n) return;
    //Stern-Brocot树 左侧总是最小的，右侧最大的，那么总是优先输入左侧，再输入中间的，最后输入右侧的数
    dfs_right(l1, l2, l1 + r1, l2 + r2, depth + 1);
    vec.push_back(P(l2 + r2, l1 + r1));
    dfs_right(l1 + r1, l2 + r2, r1, r2, depth + 1);
}




int main() {
    int p, q;
    cin >> p >> q;
    n = p / q > 1 ? p / q : q / p;
    n = n - 1;
    P tar = make_pair(p, q);
    vector<P>::iterator it;

    if (p == q && p == 1)
    {

        cout << 1 << " " << 1;
        return 0;
    }
    do {
    vec.clear();
    n++;
    vec.push_back(P(0, 1));
    dfs_left(0, 1, 1, 1, 1);
    vec.push_back(P(1, 1));
    dfs_right(1, 1, 0, 1, 1);
    vec.push_back(P(1, 0));
    it = find(vec.begin(), vec.end(), tar);

    } while (it == vec.end());


    cout << n << " " << ((int)(it - vec.begin()) + 1) / 2;



    return 0;
}


发表于 2020-06-08 14:39:10 回复(0)
提交观点

问题信息

游戏研发工程师 网易游戏雷火
上传者：小小
难度：
11条回答 4200浏览

热门推荐

通过挑战的用户

相关试题

Stern-Brocot tree

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号