Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.

Here is the set when N = 5: :

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


Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

## INPUTFORMAT

One line with a single integer N.

## OUTPUTFORMAT

One fraction per line, sorted in order of magnitude.

## SOLUTION

0/1                                                             1/1
1/2
1/3                       2/3
1/4              2/5          3/5              3/4
1/5      2/7     3/8    3/7    4/7   5/8     5/7        4/5


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int n;
FILE *fout;

/* 打印在n1/d1和n2/d2之间且分母小于等于n的分数*/
void
genfrac(int n1, int d1, int n2, int d2)
{
if(d1+d2 > n)  /*跳出递归*/
return;

genfrac(n1,d1, n1+n2,d1+d2);
fprintf(fout, "%d/%d\n", n1+n2, d1+d2);
genfrac(n1+n2,d1+d2, n2,d2);
}

void
main(void)
{
FILE *fin;

fin = fopen("frac1.in", "r");
fout = fopen("frac1.out", "w");
assert(fin != NULL && fout != NULL);

fscanf(fin, "%d", &n);

fprintf(fout, "0/1\n");
genfrac(0,1, 1,1);
fprintf(fout, "1/1\n");
}


Update: 据查，这个解法利用了法里数列及其相关性质。详见：资料1 资料2