洛谷 P1458 顺序的分数 Ordered Fractions

2019-11-06 06:02:36

字体：大中小

来源：转载

供稿：网友

我写了两种方法：

第一种：(看的别人的）

某种奇怪的奇巧淫技

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

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

上一篇：cookie和session的相关概念

下一篇：opencv学习笔记（三十一）基于块的反向投影