Description

输入一个自然数N  请写一个程序来增序输出分母小于等于N的既约真分数

Input

单独的一行 一个自然数N(1..160)

Output

每个分数单独占一行

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

解题思路:这题题意清晰明了,只是这个排序问题让我纠结了long long time;最后好不容易有点小小的思路,死在qsort上,我就不明白了,为什么用sort就可以,用qsort就错呢,又没有相同的值,所以应该无所谓稳定排序以及不稳定排序吧,可是木有办法呀~~
核心部分:两个for循环,查找互为质数的两个数,最后排序输出。。

————————我是华丽丽的分割线—————-

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

#define N 7000
struct f{
    int x,y;
}num[N];

int cmp(struct f c,struct f d){
    return d.y*c.x<c.y*d.x;
}
/*
int cmp(const void *a,const void *b){
    struct f *c=(struct f *)a;
    struct f *d=(struct f *)b;
    return d->y*c->x-c->y*d->x;
}
*/
int gcd(int a,int b){
    if(b==0)
        return a;
    return gcd(b,a%b);
}

void solve(int n){
    int i,j,len=0;
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++)
            if(gcd(i,j)==1){
                num[len].x=i;
                num[len].y=j;
                len++;
            }
    }
//    qsort(num,len,sizeof(num[0]),cmp);
    sort(num,num+len,cmp);
    printf(“0/1\n”);
    for(i=0;i<len;i++)
        printf(“%d/%d\n”,num[i].x,num[i].y);
    printf(“1/1\n”);
}

int main(){
    int n;
    while(scanf(“%d”,&n)!=EOF){
        solve(n);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation