题目大意：
输入一个自然数N,对于一个最简分数a/b（分子和分母互质的分数）,满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。
这有一个例子，当N=5时，所有解为：
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
给定一个自然数N，1<=n<=160，请编程按分数值递增的顺序输出所有解。
注：①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。
解题思路：
/*
ID: wuqi9395@126.com
PROG: frac1
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
/* 暴力枚举
int n, ans = 0;
struct node {
int x, y, id;
double fen;
}e[160 * 160];
bool cmp(node s, node v) {
if (fabs(s.fen - v.fen) > 1e-10) return s.fen < v.fen;
return s.id < v.id;
}
int main ()
{
freopen ("frac1.in", "r", stdin);
freopen ("frac1.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
e[ans].id = ans, e[ans].x = i, e[ans].y = j, e[ans++].fen = (i * 1.0) / j;
}
}
sort(e, e + ans, cmp);
cout<<"0/1"<<endl;
cout<<e[0].x<<"/"<<e[0].y<<endl;
for (int i = 1; i < ans; i++) if (fabs(e[i].fen - e[i - 1].fen) > 1e-10) {
cout<<e[i].x<<"/"<<e[i].y<<endl;
}
return 0;
}
*/
下面是一种递归实现的方法：
http://blog.csdn.net/yuwuc/article/details/4540630
（以下内容来自上述博客）
伪算法：
main:
print(0/1);
printOrderedFraction(0, 1, 1, 1);
print(1/1);
printOrderedFraction(m, n, m', n'):
if (n+n' <= N)
printOrderedFraction(m, n, m+m', n+n');
print(m+m'/n+n')
printOrderedFraction(m+n', n+n', m', n');
end if
算法的正确性证明 [2] ：
1. 为什么按照这种方法生成的数都是真分数 ？
如果能够证明对于任何阶段都有m'n - mn' = 1，那么就得到m和n、m'和n'是互素的，从而m/n和m'/n'是真分数，这样就证明了生成的数都是真分数。
用归纳法证明。
1) 将(0/1, 1/0)代入，得1*1 - 0*0 = 1。命题成立。
2) 假设前面阶段产生的(m/n, m'/n')满足表达式，那么当插入一个新的中间项(m+m')/(n+n')时，有
(m+m')n - m(n+n') = m'n - mn' = 1
m'(n+n') - (m+m')n' = m'n - mn' = 1
综上命题成立。
2. 为什么能产生所有的真分数，是否存在某个真分数a/b被忽略掉 ？
因为对于真分数a/b，初始时它满足
m/n = 0/1 < (a/b) < 1/0 = m'/n'
假设当前阶段有m/n < (a/b) < m'/n'，那么算法添加中间项(m+m')/(n+n')就存在三种情况：
1) 如果a/b = (m+m')/(n+n')，那么命题成立。
2) 如果(m+m')/(n+n') < a/b，那么就令m <- (m+m'),
n <- (n+n')
3) 否则， 令m' <- (m+m'),
n' <- (n+n')
这样一直迭代下去。
由于a/b - m/n > 0 并且 m'/n' - a/b > 0
=> an - bm >= 1 并且 bm' - an' >= 1
因此有 (m'＋n')(an-bm) + (m+n)(bm'-an') >= m'+n'+m+n
化简得到 a(m'n-mn')+b(m'n-mn')=a+b >= m'+n'+m+n
因为每次迭代m, n, m'和n'其中一个递增，因此最多需要a+b步就可以产生a/b。
3. 为什么每个真分数只出现一次，而不会出现两次或者更多 ？
这个个问题可以根据第4个问题的答案来回答。
4. 为什么生成的数列是有序的 ？
同样可以用归纳法证明。如果m/n < m'/n'并且所有的数都是非负的，那么有
m/n < (m+m')/(n+n') < m'/n'
故根据算法构造的数列是递增的。
代码：
// Stern-Brocot树 递归生成0到1之间的所有真分数
int N;
void printOrderedFraction(int m, int n, int mm, int nn) {
if (n + nn <= N) {
printOrderedFraction(m, n, m + mm, n + nn);
printf("%d/%d\n", m + mm, n + nn);
printOrderedFraction(m + mm, n + nn, mm, nn);
}
}
int main () {
freopen ("frac1.in", "r", stdin);
freopen ("frac1.out", "w", stdout);
scanf("%d", &N);
printf("0/1\n");
printOrderedFraction(0, 1, 1, 1);
printf("1/1\n");
return 0;
}