[Problem]
现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的： 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … 3/1 3/2 3/3 … 4/1 4/2 … 5/1 … … 我们以Z字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，…
[Solution]
#include <iostream> using namespace std;int main(){int n, i, j, k, max_j = 0;// get datacin >> n;if(n == 1){cout << "1/1" << endl;}else{// get the max jwhile(max_j * (max_j + 1) / 2 < n){max_j++;}// create arrayint **data = new int*[max_j+2];for(i = 0; i < max_j+2; ++i){data[i] = new int[max_j+2];}// calculatei = 1, k = max_j;while(k > 0){data[i][1] = i*(i+1)/2;for(j = 2; j <= k; ++j){data[i][j] = data[i][j-1] + (j+i-2);}k--;i++;}// swapk = max_j;for(i = 1; i <= max_j/2; ++i){for(j = i+2; j <= k; j += 2){if((i%2 == 1 && j%2 == 0) || (i%2 == 0 && j%2 == 1))continue;int tmp = data[i][j];data[i][j] = data[j][i];data[j][i] = tmp;}k--;}// output resultk = max_j;for(i = 1; i <= max_j; ++i){for(j = 1; j <= k; ++j){if(data[i][j] == n){cout << i << "/" << j << endl;return 0;}}k--;}}return 0; }