我寫了兩種方法：
第一種：(看的別人的）
自己解釋不清楚 手動模擬模擬就明白了
//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); 第二種： 先枚舉分子分母 只要滿足互質就存下來 然后按從小到大的順序排列 （要自定義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);}/*比較分數大?。和ǚ謝1 / 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;}新聞熱點
疑難解答
