顺序的分数 Ordered Fractions

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

题目描述

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

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

$$\frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1}$$

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

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

输入格式

单独的一行一个自然数 $n$

输出格式

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

样例 #1

样例输入 #1

5
1

样例输出 #1

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
1
2
3
4
5
6
7
8
9
10
11

提示

【数据范围】
对于 $100\%$ 的数据，$1\le n\le 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 num1<mu2;
}
int main(){
	vector<Node> 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"<<endl;
	for(auto i=v.begin();i!=v.end();++i){
		cout<<i->fz<<"/"<<i->fm<<endl;
	} 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35