洛谷 P1458 顺序的分数 Ordered Fractions

3/8/2017来源:ASP.NET技巧人气:3422

我写了两种方法:

第一种:(看的别人的)

某种奇怪的奇巧淫技

自己解释不清楚 手动模拟模拟就明白了

//P1458 顺序的分数 Ordered Fractions //用了某种很迷的奇巧淫技 //2017.3.6 #include <iostream> #include <cstdio> using namespace std; int n; void f(int x1, int y1, int x2, int y2){ //x1 / y1 与 x2 / y2 int midx = x1 + x2, midy = y1 + y2; //分子分母分别相加 if (midy > n || midx > n) return ; f(x1, y1, midx, midy); PRintf("%d/%d\n", midx, midy); f(midx, midy, x2, y2); } int main(){ scanf("%d", &n); printf("0/1\n"); f(0, 1, 1, 1); printf("1/1\n"); return 0; }

第二种: 先枚举分子分母 只要满足互质就存下来 然后按从小到大的顺序排列 (要自定义sort中的cmp)

//P1458 顺序的分数 Ordered Fractions //2017.3.7 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 162 * 162; int n, m; struct fraction{ int x, y; }; struct fraction p[MAXN]; int gcd(int x, int y){ return y == 0 ? x : gcd(y, x % y); } /* 比较分数大小:通分 x1 / y1 < x2 / y2 ==> x1 * y2 < x2 * y1 */ bool cmp(fraction a, fraction b){ return a.x * b.y < b.x * a.y; } int main(){ scanf("%d", &n); for (int i = 0; i <= n; i++) //枚举分子i for (int j = i; j <= n; j++) //枚举分母j (j一定大于i) if (gcd(i, j) == 1){ p[m].x = i; p[m].y = j; m++; } sort(p, p + m, cmp); for (int i = 0; i < m; i++) printf("%d/%d\n", p[i].x, p[i].y); return 0; }