蓝桥杯每日一题：有序分数（递归）

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

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

0/1,1/5,1/4,1/3,2/5,12/,35,2/3,3/4,4/5,1/1

输入格式

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

输出格式

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

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

数据范围

1≤N≤160

输入样例：

5

输出样例：

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

参考代码：

1.暴力求解参考代码：

/*
暴力枚举i,1-i中与i gcd=1的数
*/
#include<iostream>
#include<algorithm>#define x first
#define y secondusing namespace std;
const int N = 200;
typedef pair<int,int>PII;
PII q[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()
{cin>>n;int cnt = 0;for(int i=0;i<=n;i++)for(int j=0;j<=i;j++){if(gcd(i,j)==1) q[cnt++] = {j,i};}sort(q,q+cnt,cmp);for(int i=0;i<cnt;i++) printf("%d/%d\n",q[i].x,q[i].y);return 0;
}

 2.递归：

stern brocot tree原理：Stern–Brocot 树与 Farey 序列 - OI Wiki (oi-wiki.org)

#include<iostream>
#include<algorithm>using namespace std;
int n;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;
}