生成0到n之間的所有有理數并按遞增順序輸出

e.g. n=5�：
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

我�人的做法是：暴力做。
�足�大的��，然後生成所有有理�，排序，�出（注意判�重�）。

但是看答案���了一�很nb的方法……
发觉是一个很出名的东西：Stern-Brocot tree
http://en.wikipedia.org/wiki/Stern-Brocot_tree


--------------------------------------------------------

Here's a super fast solution from Russ:

We notice that we can start with 0/1 and 1/1 as our ``endpoints'' and recursively generate the middle points by adding numerators and denominators.

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

Each fraction is created from the one up to its right and the one up to its left. This idea lends itself easily to a recursion that we cut off when we go too deep.

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

int n;
FILE *fout;

/* print the fractions of denominator <= n between n1/d1 and n2/d2 */
void
genfrac(int n1, int d1, int n2, int d2)
{
if(d1+d2 > n) /* cut off recursion */
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");
}


------------------------------
本文原文�表于：
http://iveney.blogspot.com