USACO备考冲刺必刷题 | P1458 Ordered Fractions

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

【题目描述】

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

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

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

注：

1、0 和任意自然数的最大公约数就是那个自然数。

2、互质指最大公约数等于1的两个自然数。

【输入】

单独的一行一个自然数 nn

【输出】

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

【输入样例】

5

【输出样例】

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

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, mark;
struct node {  // 定义分数结构体
    double res;  // 分数结果，注意是double类型
    int a, b;  // 分子和分母
}fra[25600];  // 按照160*160的最大范围开辟结构体数组
int gcd(int a, int b)  // 最大公约数模板（背就完了！）
{
    int r = a % b;
    while (r!=0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}
bool cmp (node x, node y)  // 比较函数，按照res从小到大排序
{
    return x.res<y.res;
}
int main()
{
    cin >> n;  // 输入n
    fra[0].res = 0;  // 数组第1个res为0
    fra[0].a = 0, fra[0].b = 1;  // 分子为0，分母为1
    mark=1;  // 定义计数器
    for (int i=1; i<=n; i++) {  // 从1遍历至n
        for (int j=i; j<=n; j++) {  // 从i遍历至n
            if (gcd(i,j)==1) {  // 如果分子和分母的最大公约数为1
                fra[mark].res = 1.0*i/j;  // 记录分数结果
                fra[mark].a = i, fra[mark].b = j;  // 以及分子和分母
                mark++;  // 计数器自增1
            }
        }
    }
    sort(fra, fra+mark, cmp);  // 对结构体数组按照res从小到大方式排序
    for (int i=0; i<mark; i++) {  // 依次输出mark-1（因为存完最后一个mark仍自增了1）个分子和分母
        cout << fra[i].a << "/" << fra[i].b << endl;
    }
    return 0;
}

【运行结果】

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