2.1.2 Ordered Fractions 顺序的分数

2.1.2 Ordered Fractions 顺序的分数

时间： 1ms        内存：64M

描述：

输入一个自然数N　
请写一个程序来增序输出分母小于等于N的既约真分数

输入：

单独的一行　一个自然数N(1..160)

输出：

每个分数单独占一行

示例输入：

5

示例输出：

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

提示：

参考答案（内存最优[748]）：

#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;
}

参考答案（时间最优[4]）：

#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; 
} 

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。