Cantor表(NOIP1999)解题报告

这是我第一个真正意义上的真正NOIP题目的解题报告。虽然这道题很简单,但我做了近两节课,因为书上有解法,所以我顺着它的解法,突发奇想,想出了另外两个解法。

Description

现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的:

cantor表

我们以Z字形给上表的每一项编号。第一项是1/1,然后是1/2,2/1,3/1,2/2,…

Input

输入整数N(1≤N≤10000000)

Output

输出表中的第N项

Sample Input

Sample Output

 

 

利用的规律:
第i行有i个元素。
奇数行i从左下到右上,第j个的值为(i-j+1)/j ;
偶数行i从右上到左下,第j个的值为j/(i-j+1)。

算法描述:

1、输入n。
2、找到第n个元素所在行。
(1)可以用n去减1,减2……一直减到负,使它变负的那个数。
(2)可以用An=n的前n项和Sn=n(n+1)/2去减,使差为最小正整数的n即为所在行。
(3)对(2)的改进:解不等式Sn<m得n<(-1+√(8m+1))/2,由此可省去循环减的步骤直接得所在行。
3、根据所在行数的奇偶,判断值。
4、输出。
说明:2(1)效率略高于(2),循环次数一样,(2)运算较复杂。由(2)可以引出(3),
(3)不需要循环,效率较高,但需要深入思考才可以得到此方法。

代码如下:

 

 

《Cantor表(NOIP1999)解题报告》有一个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注