题目：
给定一个整数 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
输入格式
共一行，包含一个整数 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
枚举版：
由于此题数据量很小只有160，O(N^2)解决此问题完全没问题，具体思路外循环枚举分母，内循环枚举分子。只要没有最大公约数，就存取下来，然后针对于分数进行排序输出即是答案。分数排序如下图：
#include<iostream> #include<algorithm> using namespace std; int n; typedef pair<int,int> PII; PII p[50000];//至少要开到N*N int gcd(int a,int b){//最大公约数 return b?gcd(b,a%b):a; } int cmp(PII a,PII b){//a.second/a.first<b.second/b.first,分母同时同分就得到下面式子 return a.first*b.second>b.first*a.second; } int main(){ cin>>n; int k=0; for(int i=0;i<=n;i++){ for(int j=0;j<=i;j++){ if(gcd(i,j)==1){//只要没有最大公约数就往里面放 p[k++]={i,j}; } } } sort(p,p+k,cmp);//由小到大排序 for(int i=0;i<k;i++){//second是分子，first是分母 cout<<p[i].second<<"/"<<p[i].first<<endl; } return 0; }
递归版（Stern-Brocot Tree）：
Stern-Brocot Tree：
Stern-Brocot Tree主要思想就是不断递归分裂，对于本题而言，就是第二张图，开始[0/1,1/1],找到mid=0+1/1+1,区间分裂[0/1,1/2]与[1/2,1/1]，[0/1,1/2]再分裂mid=0+1/1+2，区间分裂为[0/1,1/3]与[1/3,1/2]，[1/2,1/1]再分裂mid=1+1/1+2，
区间分裂为[1/2,2/3]与[2/3,1/1]，以此类推……这样就得到了答案，用一个递归函数，不断往下找即可。
#include<iostream> using namespace std; int n; //递归做法 void dfs(int a,int b,int c,int d){//a第一个数分母，b第一个数分子，c第二个数分母，d第二个数分子 if(a+c>n)return;//如果分母之和大于n了就返回 dfs(a,b,a+c,b+d);//左区间[b/a,b+d/a+c] cout<<b+d<<"/"<<a+c<<endl;//中间数b+d/a+c dfs(a+c,b+d,c,d);//右区间[b+d/a+c,d/c] } int main(){ cin>>n; cout<<"0/1"<<endl;//第一个数0单独输出 dfs(1,0,1,1);//从[0/1,1/1]开始 cout<<"1/1"<<endl;//最后一个数单独输出 return 0; }
总结：
在做此题时，很容易想到第一种方法，第二种Stern-Brocot Tree第一次了解，顺便学习一下，在算法思想上比较简单了，也比较容易理解。大家都可以学习一下，虽然运行效率差不多，但是使用Stern-Brocot Tree的代码很简单。冲刺蓝桥杯路上会遇到各种各样的方法，大家选择自己擅长的即可，只要能ac题目的算法都是好算法。博主水平有限，文章写的一般，在描述上可能不是很清楚，若有不明白的地方，可评论，看到必回复。若文章有错误的地方，请大家指出，纠正错误，规范自己，大家一起加油。
