输入一个自然数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
// 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;
}
[USACO Section 2.1] Ordered Fractions (生成0到1之间的所有真分数）
原文：http://blog.csdn.net/sio__five/article/details/19764105