生成分母为1-n的所有分数，然后排序，去重，输出即可。
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
if(a<b){
swap(a,b);
}
if(b==0) return a;
return gcd(b,a%b);
}
int lcm(int a,int b)
//数据都很小，不需要考虑相乘溢出问题
{
return a*b/gcd(a,b);
}
struct fraction{
int num,denom;
fraction(int n,int d){
num = n;
denom = d;
int g = gcd(num,denom);
num/=g;
denom/=g;
}
bool operator<(const fraction&f2) const {
//这里多此一举了，不需要计算最小公倍数的。直接分子分母交叉相乘再比较即可
int l = lcm(this->denom,f2.denom);
return this->num*l/this->denom < f2.num*l/f2.denom;
}
bool operator==(const fraction&f2) const{
return this->num==f2.num&&this->denom==f2.denom;
}
};
int n;
void solve()
{
#ifndef _DEBUG
freopen("frac1.in","r",stdin);
freopen("frac1.out","w",stdout);
#endif
scanf("%d",&n);
vector<fraction> res;
for(int i=2;i<=n;++i){
for(int j=1;j<i;++j){
res.push_back(fraction(j,i));
}
}
sort(res.begin(),res.end());
vector<fraction>::iterator endi = unique(res.begin(),res.end());
printf("0/1\n");
for(vector<fraction>::iterator i = res.begin();
i!=endi;
++i){
printf("%d/%d\n",i->num,i->denom);
}
printf("1/1\n");
}
int main(int argc,char *argv[])
{
solve();
return 0;
}
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 2720 KB]
Test 2: TEST OK [0.011 secs, 2848 KB]
Test 3: TEST OK [0.011 secs, 2852 KB]
Test 4: TEST OK [0.011 secs, 2848 KB]
Test 5: TEST OK [0.000 secs, 2848 KB]
Test 6: TEST OK [0.000 secs, 2848 KB]
Test 7: TEST OK [0.011 secs, 2848 KB]
Test 8: TEST OK [0.000 secs, 2848 KB]
Test 9: TEST OK [0.011 secs, 2848 KB]
Test 10: TEST OK [0.011 secs, 2848 KB]
Test 11: TEST OK [0.065 secs, 2848 KB]
All tests OK.