11249: 【原1249】有序分数序列

题目

题目描述

author: yixi 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1249

Description

请输出[0,1]之间且分母小于等于N的所有简分数。

比如N=5时：0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1

Input Format

一个正整数N。

对于100%的数据，1 <= N <= 100。

Output Format

从小到大输出，每行一个分数。

Sample Input

5

Sample Output

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

FineArtz's solution

/* 有序分数数列 */
#include <iostream>
using namespace std;

int a[10000] = {0}, b[10000] = {0};
double c[10000] = {0.0};

int gcd(int x, int y){
    if (x % y == 0) return y;
    return gcd(y, x % y);
}

inline void swap(int &x, int &y){ int t = x; x = y; y = t; }
inline void swap(double &x, double &y) { double t = x; x = y; y = t; }

void qsort(int low, int high){
    if (low >= high) return;
    int i = low, j = high, keya = a[i], keyb = b[i];
    double key = c[i];
    while (i < j){
        while (i < j && c[j] >= key) --j;
        a[i] = a[j];
        b[i] = b[j];
        c[i] = c[j];
        while (i < j && c[i] <= key) ++i;
        a[j] = a[i];
        b[j] = b[i];
        c[j] = c[i];
    }
    a[i] = keya;
    b[i] = keyb;
    c[i] = key;
    qsort(i + 1, high);
    qsort(low, j - 1);
}

int main(){
    int n, cnt = 0;
    cin >> n;
    a[0] = 0;
    b[0] = 1;
    //cout << gcd(3, 2) << endl;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j){
            if (gcd(i, j) == 1){
                ++cnt;
                a[cnt] = j;
                b[cnt] = i;
                c[cnt] = double(j) / double(i);
            }
        }
    qsort(1, cnt);
    a[++cnt] = 1;
    b[cnt] = 1;
    c[cnt] = 1.0;
    for (int i = 0; i <= cnt; ++i){
        cout << a[i] << '/' << b[i] << endl;
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

bool visited[109][109] = { 0 };

class nums {
public:
    int m = 0, n = 0;
    double val = 0.0;
};

nums num[10009];

template <class T, class T_val = decltype(*declval<T>()),
    class Compare = bool (*)(T_val, T_val)>
    void quick_sort(T start, T end,
        Compare cmp = [](T_val a, T_val b) {return a < b; }) {
    if (start == end)
        return;
    auto i = start, j = end;
    --j;
    if (i == j)
        return;
    //交换
    auto key = *start;
    for (bool status = true; i != j;) {
        if (status) {
            if (cmp(*j, key)) {
                *i = *j;
                ++i;
                status = false;
            }
            else
                --j;
        }
        else {
            if (cmp(key, *i)) {
                *j = *i;
                --j;
                status = true;
            }
            else
                ++i;
        }
    }
    *i = key;
    //递归
    quick_sort(start, ++i, cmp);
    quick_sort(i, end, cmp);
}

int main() {
    int n;
    cin >> n;

    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            if (visited[i][j])
                continue;
            //加入集合
            num[cnt].m = i;
            num[cnt].n = j;
            num[cnt++].val = double(j) / double(i);

            //访问其倍数
            for (int k = 2; k * i <= n; ++k)
                visited[k * i][k * j] = true;
        }
    }

    //排序
    quick_sort(num, num + cnt, [](nums a, nums b) {return a.val < b.val; });

    //输出
    printf("0/1\n");
    for (int i = 0; i < cnt; ++i)
        printf("%d/%d\n", num[i].n, num[i].m);
    printf("1/1");

    return 0;
}

skyzh's solution

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct Rational {
    int a, b;
};

bool cmp(const Rational& a, const Rational& b) {
    return a.a * b.b - a.b * b.a < 0;
}

int gcd(int a, int b) {
    if (a < b) swap (a, b);
    while (b > 0) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
} 
int main() {
    int N;
    Rational data[10000];
    int dN = 0;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            if (gcd(i, j) == 1) {
                data[dN].a = j;
                data[dN++].b = i;
            }
        }
    }
    data[dN].a = 0; data[dN].b = 1; dN++;
    data[dN].a = 1; data[dN].b = 1; dN++;
    sort(data, data + dN, cmp);
    for (int i = 0; i < dN; i++) {
        printf("%d/%d\n", data[i].a, data[i].b);
    }
    return 0;
}