[USACO2.1]顺序的分数 Ordered Fractions

题目描述

输入一个自然数 nnn，对于一个最简分数 a/ba/ba/b（分子和分母互质的分数），满足 1≤b≤n,0≤a/b≤11 \le b \le n,0 \le a/b \le 11≤b≤n,0≤a/b≤1，请找出所有满足条件的分数。

这有一个例子，当 n=5n=5n=5 时，所有解为：

01,15,14,13,25,12,35,23,34,45,11\frac01,\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34 ,\frac45,\frac1110​,51​,41​,31​,52​,21​,53​,32​,43​,54​,11​

给定一个自然数 nnn，请编程按分数值递增的顺序输出所有解。

注：
1、000 和任意自然数的最大公约数就是那个自然数。
2、互质指最大公约数等于1的两个自然数。

输入格式

单独的一行一个自然数 nnn

输出格式

每个分数单独占一行，按照大小次序排列

样例 #1

样例输入 #1

5

样例输出 #1

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

提示

【数据范围】
对于 100%100\%100% 的数据，1≤n≤1601\le n \le 1601≤n≤160。

USACO 2.1

翻译来自NOCOW

题解：
直接采用暴力枚举的方式，__gcd是求最大公约数的函数，其返回值为最大公约数。
建立一个结构体，保存分子分母，因为要按照递增顺序输出，所以我想的是利用sort排序函数，但是因为是类类型，所以要提供排序函数，需要自己写一个cmp函数， 排完序后，就可以直接输出了。

#include
using namespace std;
struct Node{double fz;double fm;Node(double fz1,double fm1):fz(fz1),fm(fm1){}
};bool cmp(Node a,Node b){double num1=a.fz/a.fm;double mu2=b.fz/b.fm;return num1vector v;int n=0;cin>>n;for(int i=1;i<=n;++i){for(int j=i;j<=n;++j){if(__gcd(i,j)==1){Node node(i,j);v.push_back(node);}}}sort(v.begin(),v.end(),cmp);cout<<"0/1"<cout<fz<<"/"<fm<