# 2.1.2 Ordered Fractions 顺序的分数

2.1.2 Ordered Fractions 顺序的分数

``5``

``````0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1``````

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n;
void dfs(int n1, int d1, int n2, int d2)
{
if(d1+d2 > n)
return;
dfs(n1,d1, n1+n2,d1+d2);
printf("%d/%d\n", n1+n2, d1+d2);
dfs(n1+n2,d1+d2, n2,d2);
}
int main()
{
scanf("%d", &n);
printf("0/1\n");
dfs(0,1, 1,1);
printf("1/1\n");
return 0;
}``````

``````#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include<iostream>
using namespace std;

#define N 10000
struct f{
int x,y;
}num[N];

int cmp(struct f c,struct f d){
return d.y*c.x<c.y*d.x;
}
/*
int cmp(const void *a,const void *b){
struct f *c=(struct f *)a;
struct f *d=(struct f *)b;
return d->y*c->x-c->y*d->x;
}
*/
int gcd(int a,int b){
if(b==0)
return a;
return gcd(b,a%b);
}

void solve(int n){
int i,j,len=0;
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++)
if(gcd(i,j)==1){
num[len].x=i;
num[len].y=j;
len++;
}
}
//    qsort(num,len,sizeof(num[0]),cmp);
sort(num,num+len,cmp);
printf("0/1\n");
for(i=0;i<len;i++)
printf("%d/%d\n",num[i].x,num[i].y);
printf("1/1\n");
}

int main(){
int n;
cin>>n;
solve(n);
return 0;
}
``````