USACO trainging 2.1 有序分数

题目描述

给定一个整数 N，请你求出所有分母小于或等于 N，大小在 [0,1] 范围内的最简分数，并按从小到大顺序依次输出。

例如，当 N=5 时，所有满足条件的分数按顺序依次为：

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

思路

可利用递归(dfs), 来构造Stern—Brocot Tree求解

两边的分子分母相加：

// 中序遍历树
void dfs(int a, int b, int c, int d)
{
    if (b + d > n) return;
    dfs(a, b, a + c, b + d);
    printf("%d/%d\n", a + c, b + d);
    dfs(a + c, b + d, c, d);
}

int main()
{
    cin >> n;
    puts("0/1");
    dfs(0, 1, 1, 1);
    puts("1/1");
    return 0;
}