[USACO 2.1.2]顺序的分数（枚举+快排）-白红宇

[USACO 2.1.2]顺序的分数（枚举+快排）

阅读量：7050 次

发布时间：2019-06-28

本文共 997 字，大约阅读时间需要 3 分钟。

题目：http://hustoj.sinaapp.com/problem.php?id=1838

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

思路：将分子分母和值存入结构体根据值对结构体排序

#include 
     
      #include 
      
       #include 
       
        using namespace std;struct fraction{    int numerator;    int denominator;    float value;}f[10000];int cmp(const void *a,const void *b){    return ((fraction *)a)->value-((fraction *)b)->value>0?1:-1;}int gcd(int j,int i){    int r;    while(j>0)    {        r=i%j;        i=j;        j=r;    }    if(i==1) return 1;    else return 0;}int main(){    int n;    cin >> n;    int c=0;    for(int i=1;i<=n;i++)    {        for(int j=0;j<=i;j++)        {            if(gcd(j,i)||j==1)            {                f[c].denominator=i;                f[c].numerator=j;                f[c].value=float(f[c].numerator)/float(f[c].denominator);                c++;            }        }    }    qsort(f,c,sizeof(fraction),cmp);    for(int i=0;i