codeVS 1083 cantor表（1999年NOIP全国联赛普及组）

时间限制：1s 空间限制：128000KB  题目等级：白银silver

题目描述 Description

现代数学的著名证明之一是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，…

输入描述 Input Description

  整数N（1≤N≤10000000）

样例输出 Sample Output

  1/4 模拟思想：沿图示轨迹斜着看，左上角部分，前 i 个斜行有1+2+...+i 项（即i*(i+1)/2），以此判断第n项在第几斜行。再根据奇数斜行从左下到右上、偶数斜行从右上到左下，判断出第n项在该斜行的什么位置，然后就可以推断出第n项的数值。 #include <iostream> #include <math.h> using namespace std; int main() { int n; cin>>n; /*找出第n项所在的“斜行”*/ int i=0; while( 1 ) { i++; if( i*(i+1)>=2*n ) break; } /* 1.第n项恰好是第i斜行的端点 */ if( i*(i+1)==2*n ) { if( i%2==1 ) { cout<<"1/"<<i<<endl; return 0; } else { cout<<i<<"/1"<<endl; return 0; } } /* 2.第n项在第i斜行的内部 */ else { int d=i*(i+1)/2-n; //d是n与斜行端点的差值（可理解为“第n项离斜行末的距离”） if( i%2==1 ) { cout<<1+d<<"/"<<i-d<<endl; //奇数斜行分母从1加到i，分子从i减到1 } else { cout<<i-d<<"/"<<1+d<<endl; //偶数斜行分子从1加到i，分母从i减到1 } } return 0; }