有序分数，递归stern-Brocot Tree

题目：

1360. 有序分数

题目
提交记录
讨论
题解
视频讲解

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

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

01,15,14,13,25,12,35,23,34,45,1101,15,14,13,25,12,35,23,34,45,11

输入格式

共一行，包含一个整数 NN。

输出格式

按照从小到大的顺序，输出所有满足条件的分数。

每个分数占一行，格式为 a/ba/b，其中 aa 为分子， bb 为分母。

数据范围

1≤N≤1601≤N≤160

输入样例：

输出样例：

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

代码：

暴力：O（n^2logn）

#include<bits/stdc++.h>
using namespace std;

const int N=200;
typedef pair<int,int> PII;

#define x first
#define y second

PII p[N*N];
int n;

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

bool cmp(PII a,PII b){
    return a.y*b.x<a.x*b.y;//通分后升序排序
}

int  main(){
    scanf("%d",&n);
    int cnt=0;//可以化成分数的个数
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(gcd(i,j)==1){//如果分子分母互质，则是一个，将他存入数组中
                p[cnt++]={i,j};//j:分子,i分母
            }
        }
    }
    
    //进行排序
    sort(p,p+cnt,cmp);
    
    for(int i=0;i<cnt;i++){
        printf("%d/%d\n",p[i].y,p[i].x);
    }
    return 0;
}

递归stern-Brocot Tree：有序输出0~1的所有有理数

递归边界是当前分子分母分别相加

#include<bits/stdc++.h>
using namespace std;

int n;

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

int main(){
    scanf("%d",&n);
    puts("0/1");
    dfs(1,0,1,1);//a,b,c,d   b/a,d/c
    puts("1/1");
    return 0;
}