farey sequence(递归造树).cpp

来自「杭电acm解题报告2001---2099.」· C++ 代码 · 共 31 行

//tju Pid: 2798     Time: 1.23 sec.     Memory: 744 K.     Code Length: 0.5 K.
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
const int NMAX = 3000000;
int total;
int n;
bool flag;

void make_farey_seq(int x1,int y1,int x2, int y2)
{
	if(x1+x2 > n || y1+y2 > n) return;
	make_farey_seq(x1, y1,x1+x2, y1+y2);
	if(flag) putchar(',');
	printf("%d/%d", x1+x2, y1+y2);
	flag = true;
	make_farey_seq(x1+x2, y1+y2,x2,y2);
}

int main() {
	int t;
	scanf("%d", &t);
	while(t --) {
		scanf("%d", &n);
		flag = false;
		make_farey_seq(0,1,1,1);
		puts("");
	}
}