题目
题目描述
给定一个数N(1<=N<=160)，需要产生所有的分数，这些分数的值必须要在0~1之间。而且每个分数的分母不能超过N。如下例所示：
N = 5
产生所有的分数：0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
样例输入
5
样例输出
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
解题思路
这个题目最一开始我走了一些弯路，想得太复杂，结果第一发就超时了。后来静下心来算了想了下，发现枚举加排序速度就已经很快了。所以就实现了一下，通过。
解题代码
/*
ID: yinzong2
PROG: frac1
LANG: C++11
*/
#define MARK
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 170;
int N;
struct Frac {
int num;
int deno;
};
vector<Frac> lst;
bool cmp(Frac A, Frac B) {
int temp1 = A.num*B.deno;
int temp2 = A.deno*B.num;
return temp1 < temp2;
}
int GCD(int x, int y) {
if (0 == y) return x;
return GCD(y, x%y);
}
Frac afterGCD(Frac f) {
int gcd = GCD(f.num, f.deno);
f.num /= gcd;
f.deno /= gcd;
return f;
}
int main() {
#ifdef MARK
freopen("frac1.in", "r", stdin);
freopen("frac1.out", "w", stdout);
#endif // MARK
while (cin >> N) {
cout << "0/1" << endl;
if (N != 1) {
lst.clear();
for (int i = N; i >= 2; --i) {
for (int j = 1; j < i; ++j) {
Frac f;
f.num = j;
f.deno = i;
lst.push_back(f);
}
}
sort(lst.begin(), lst.end(), cmp);
int len = lst.size();
Frac pre;
pre = afterGCD(lst[0]);
cout << pre.num << "/" << pre.deno << endl;
// 对于排序后的数据进行去重
for (int i = 1; i < len; ++i) {
lst[i] = afterGCD(lst[i]);
if (lst[i].num == pre.num && lst[i].deno == pre.deno) continue;
cout << lst[i].num << "/" << lst[i].deno << endl;
pre = lst[i];
}
}
cout << "1/1" << endl;
}
}
/*
Executing...
Test 1: TEST OK [0.000 secs, 4180 KB]
Test 2: TEST OK [0.000 secs, 4180 KB]
Test 3: TEST OK [0.000 secs, 4180 KB]
Test 4: TEST OK [0.014 secs, 4180 KB]
Test 5: TEST OK [0.014 secs, 4180 KB]
Test 6: TEST OK [0.014 secs, 4180 KB]
Test 7: TEST OK [0.028 secs, 4180 KB]
Test 8: TEST OK [0.070 secs, 4180 KB]
Test 9: TEST OK [0.056 secs, 4180 KB]
Test 10: TEST OK [0.056 secs, 4188 KB]
Test 11: TEST OK [0.140 secs, 4188 KB]
All tests OK.
*/
解题思路（type2）
之后看了看官方的题解，发现第一个解法就是用的枚举加排序，但是有个优化的地方我之前没有考虑。我们最终枚举出来的所有的分数，分子分母应该都是互质的。所以我们对于所有分子分母互质的分数进行排序输出即可。
解题代码
/*
ID: yinzong2
PROG: frac1
LANG: C++11
*/
#define MARK
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 170;
int N;
struct Frac {
int num;
int deno;
};
vector<Frac> lst;
bool cmp(Frac A, Frac B) {
int temp1 = A.num*B.deno;
int temp2 = A.deno*B.num;
return temp1 < temp2;
}
int GCD(int x, int y) {
if (0 == y) return x;
return GCD(y, x%y);
}
int main() {
#ifdef MARK
freopen("frac1.in", "r", stdin);
freopen("frac1.out", "w", stdout);
#endif // MARK
while (cin >> N) {
cout << "0/1" << endl;
if (N != 1) {
lst.clear();
for (int i = N; i >= 2; --i) {
for (int j = 1; j < i; ++j) {
Frac f;
f.num = j;
f.deno = i;
if (GCD(f.num, f.deno) != 1) continue;
lst.push_back(f);
}
}
sort(lst.begin(), lst.end(), cmp);
int len = lst.size();
for (int i = 0; i < len; ++i) {
cout << lst[i].num << "/" << lst[i].deno << endl;
}
}
cout << "1/1" << endl;
}
}
/*
Executing...
Test 1: TEST OK [0.000 secs, 4180 KB]
Test 2: TEST OK [0.000 secs, 4180 KB]
Test 3: TEST OK [0.000 secs, 4180 KB]
Test 4: TEST OK [0.000 secs, 4180 KB]
Test 5: TEST OK [0.000 secs, 4180 KB]
Test 6: TEST OK [0.000 secs, 4180 KB]
Test 7: TEST OK [0.000 secs, 4180 KB]
Test 8: TEST OK [0.014 secs, 4180 KB]
Test 9: TEST OK [0.028 secs, 4180 KB]
Test 10: TEST OK [0.056 secs, 4180 KB]
Test 11: TEST OK [0.140 secs, 4188 KB]
All tests OK.
*/
解题思路（type3）
官方第二个解法很巧妙。是找到一个数学规律，直接可以打印所有的数字，时间复杂度为O(N)。具体可以看这里。
解题代码
/*
ID: yinzong2
PROG: frac1
LANG: C++11
*/
#define MARK
#include <iostream>
#include <cstdio>
using namespace std;
int N;
void generateFrac(int num1, int denom1, int num2, int denom2) {
if (denom1 + denom2 > N) return ;
generateFrac(num1, denom1, num1+num2, denom1+denom2);
cout << num1+num2 << "/" << denom1+denom2 << endl;
generateFrac(num1+num2, denom1+denom2, num2, denom2);
}
int main() {
#ifdef MARK
freopen("frac1.in", "r", stdin);
freopen("frac1.out", "w", stdout);
#endif // MARK
while (cin >> N) {
cout << "0/1" << endl;
generateFrac(0, 1, 1, 1);
cout << "1/1" << endl;
}
return 0;
}
/*
Executing...
Test 1: TEST OK [0.000 secs, 4176 KB]
Test 2: TEST OK [0.000 secs, 4176 KB]
Test 3: TEST OK [0.000 secs, 4176 KB]
Test 4: TEST OK [0.000 secs, 4176 KB]
Test 5: TEST OK [0.000 secs, 4176 KB]
Test 6: TEST OK [0.000 secs, 4176 KB]
Test 7: TEST OK [0.000 secs, 4176 KB]
Test 8: TEST OK [0.014 secs, 4176 KB]
Test 9: TEST OK [0.028 secs, 4176 KB]
Test 10: TEST OK [0.056 secs, 4176 KB]
Test 11: TEST OK [0.140 secs, 4176 KB]
All tests OK.
*/