2017-8-6

題目描述

按分?jǐn)?shù)值遞增的順序輸出所有解

解答

求出所有情況再排序即可

代碼

/* 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; }

為了避免重復(fù)，應(yīng)該把最大公約數(shù)不為1的給去掉，因?yàn)榧s去之后會(huì)發(fā)現(xiàn)我們已經(jīng)有了，上面我是在cmp函數(shù)里面進(jìn)行通分然后再排序的，或者你也可以將其計(jì)算出來(lái)然后再進(jìn)行排序。

/* 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; }

總結(jié)

以上是生活随笔為你收集整理的USACO-Section2.1 Ordered Fractions（简单数据处理）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。