2017-8-6
题目描述
按分数值递增的顺序输出所有解解答
求出所有情况再排序即可代码
/* ID: 18795871 PROG: frac1 LANG: C++ */ #include<iostream> #include<cstring> #include<fstream> #include<cstdlib> using namespace std; const int N = 10000; ifstream fin("frac1.in"); ofstream fout("frac1.out"); int n; struct fs{ int x,y; }s[N+1]; int cmp(const void *a,const void *b){ struct fs *k1=(struct fs *)a; struct fs *k2=(struct fs *)b; return k1->x*k2->y-k1->y*k2->x; } int res(int p,int q){ int r; while (q){ r=p%q; p=q; q=r; } return p; } int main() { int i,j,k; fin>>n; k=0; for (i=1;i<=n;i++){ for (j=0;j<=i;j++){ if (res(i,j)==1){ s[k].x=j; s[k].y=i; k++; } } } qsort(s,k,sizeof(s[0]),cmp); for (i=0;i<k;i++){ fout<<s[i].x<<"/"<<s[i].y<<endl; } return 0; }为了避免重复，应该把最大公约数不为1的给去掉，因为约去之后会发现我们已经有了，上面我是在cmp函数里面进行通分然后再排序的，或者你也可以将其计算出来然后再进行排序。
/* ID: 18795871 PROG: frac1 LANG: C++ */ #include<iostream> #include<fstream> #include<algorithm> using namespace std; ifstream fin("frac1.in"); ofstream fout("frac1.out"); const int N = 160; int n; struct fs{ int a,b; double p; }x[N*N+1]; bool cmp(struct fs a,struct fs b){ return a.p<b.p; } bool gcd(int i,int j){ while (j){ int t=i%j; i=j; j=t; } if (i==1) return true; return false; } int main(){ int cnt=0; while (fin>>n){ for (int i=0;i<=n;i++){ for (int j=i+1;j<=n;j++){ if (gcd(i,j)){ x[cnt].a=i;x[cnt].b=j;x[cnt].p=1.0*i/j; cnt++; } } } sort(x,x+cnt,cmp); for (int i=0;i<cnt;i++){ fout<<x[i].a<<"/"<<x[i].b<<endl; } fout<<1<<"/"<<1<<endl; } return 0; }