C code:

#include <stdio.h>
#include <math.h>

/* Prints the n-th fraction in Cantor's enumeration. */ void print_fraction(int n) { int d = (-1 + sqrt(1 + 8 * n)) / 2; /* Diagonals to skip */ int e = n - d * (d + 1) / 2; /* Extra steps after the skip. */ int v1 = e <= 1 ? d + e : d + 2 - e; int v2 = e <= 1 ? 1 : e;

printf("%d / %d\n", d % 2 == 0 ? v1 : v2, d % 2 == 0 ? v2 : v1); }

int main() { size_t i; for (i = 1; i < 20; i++) { print_fraction(i); } }

Output:
1 / 1
1 / 2
2 / 1
3 / 1
2 / 2
1 / 3
1 / 4
2 / 3
3 / 2
4 / 1
5 / 1
4 / 2
3 / 3
2 / 4
1 / 5
1 / 6
2 / 5
3 / 4
4 / 3

1 comment

Prunthaban said:

http://www.spoj.pl/problems/CANTON

Post a comment

RSS