原題鏈接：PAT (Basic Level) Practice （中文）1062 最簡(jiǎn)分?jǐn)?shù)
做前思考
1减余、首先N1/M1不一定比N2/M2小，所以以防萬一先排個(gè)序绵脯。
2佳励、再找出在兩正分?jǐn)?shù)之間的分子分母最大公約數(shù)為1的分?jǐn)?shù)休里，用一下輾轉(zhuǎn)相除法。
做后總結(jié)
1赃承、本人感覺應(yīng)該還有更好的方法妙黍，后續(xù)再想想。
#include<stdio.h>
int com(const void* a,const void* b)
{
return *(double*)a>*(double*)b?1:-1;
}
int gcd(int i,int k)
{
int x;
while((x=i%k))
{
i=k;
k=x;
}
if(k==1)
{
return 1;
}else{
return 0;
}
}
int main()
{
int i;
double x[2];
int n1,n2,m1,m2,k;
scanf("%d/%d %d/%d %d",&n1,&m1,&n2,&m2,&k);
x[0]=(double)n1/m1;
x[1]=(double)n2/m2;
qsort(x,2,sizeof(double),com);
for(i=1;(double)i/k<x[1];i++)
{
if((double)i/k>x[0])
{
if(gcd(i,k)==1)
{
printf("%d/%d",i,k);
if((double)(i+1.0)/k>=x[1])
{
printf("\n");
}else{
printf(" ");
}
}
}
}
return 0;
}
