生成分母為1-n的所有分?jǐn)?shù)，然后排序，去重，輸出即可。
#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)
????//數(shù)據(jù)都很小，不需要考慮相乘溢出問(wèn)題
{
????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?{
????? //這里多此一舉了，不需要計(jì)算最小公倍數(shù)的。直接分子分母交叉相乘再比較即可
???????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.