问题标题: 酷町堂：2638 分数排序

2638   分数排序经验值：1200

题目描述 Description

输入一个自然数N，对于一个最简分数a/b（分子和分母互质的分数），满足1≤b≤N，0≤a/b≤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，1≤N≤160，请编程按分数值递增的顺序输出所有解。

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

输入描述 Input Description

一行，一个自然数，N

输出描述 Output Description

每行一个分数，按从小到大的顺序出现

样例输入 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

-----------------------------------------------------------------------------------------------------------------------------------

求大佬来帮助，采纳时加到70酷町豆！

#include<iostream>
#include<algorithm>
using namespace std;
struct dddd{
    int m,z,s;
}a[111111];
bool gcd(int x,int y){
    int s;
    for(int i=1;i<=max(x,y);++i)
    {
        if(x%i==0&&y%i==0)
            s=i;
    }
    if(s==1) return true;
    return false; 
}
bool cmp(dddd x,dddd y){
    return x.s<y.s;
}
int main(){
    int n,x=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(gcd(i,j)){
                x++;
                a[x].m=i;
                a[x].z=j;
                a[x].s=j*1.0/i;
            }
        }
    }
    sort(a+1,a+x,cmp);
    for(int i=1;i<x;i++){
        cout<<a[i].z<<"/"<<a[i].m<<endl;
    }
    return 0;
}//我是按照李鑫羽的核心写的

@李鑫羽@柯以成      帮我看看！！！

李瑞曦在2020-07-14 17:30:38追加了内容

😭😭😭😭我太难了

李瑞曦在2020-07-14 17:40:26追加了内容

#include<iostream>
#include<algorithm>
using namespace std;
int cnt;
int gcd(int x,int y){ 
    int r;
    while(x%y!=0){
        r=x%y;
        x=y;
        y=r;
    }
    return y;
}
struct fs{
    int jg,fm,fz;
}a[10070];
bool cmp(fs s,fs d){
    return s.jg<d.jg;
}
int main(){
    int n;
    cin>>n;
    cout<<0<<"/"<<1<<endl;
    for(int i=1;i<=n;i++){
        for(int j=n;j>=i+1;j--){
            double k=i*1.0/j;
            if(i==1){
                cnt++;
                a[i].jg=1.0*i/j;
                a[i].fm=i;
                a[i].fz=j;
            }
            else if(gcd(i,j) && k<=1){
                cnt++;
                a[i].jg=1.0*i/j;
                a[i].fm=i;
                a[i].fz=j;
            }
        }
    }
    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=cnt;i++){
        cout<<a[i].fz<<"/"<<a[i].fm<<endl;
    }
    cout<<1<<"/"<<1; 
    return 0;
}

李瑞曦在2020-07-14 17:40:51追加了内容

@柯以成 

李瑞曦在2020-07-14 17:44:09追加了内容

#include<iostream>
#include<algorithm>
using namespace std;
struct dddd{
    int m,z,s;
}a[111111];
bool gcd(int x,int y){
    int s;
    for(int i=1;i<=max(x,y);++i)
    {
        if(x%i==0&&y%i==0)
            s=i;
    }
    if(s==1) return true;
    return false; 
}
bool cmp(dddd x,dddd y){
    return x.s<y.s;
}
int main(){
    int n,x=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(gcd(i,j)){
                x++;
                a[x].m=i;
                a[x].z=j;
                a[x].s=j*1.0/i;
            }
        }
    }
    sort(a+1,a+1+x,cmp);
    for(int i=1;i<=x;i++){
        cout<<a[i].z<<"/"<<a[i].m<<endl;
    }
    return 0;
}

李瑞曦在2020-07-14 18:12:27追加了内容

啊啊啊啊啊啊啊啊

我要残了！！！！！555~