cantor表分析和总结.docx

【题02】cantor表

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

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...

输入：整数n(1≤n≤10)

输出：表中的第N项样例：

input：n=7output：1/4题解

cantor表的特点

cantor表中数据的“走势”如图9.1.1所示：

图9.1.1

元素的特征为行号（自上而下）

列号（由左而右）

第i条右对角线有i个元素

第奇数条对角线方向向上、第偶数条对角线方向向下；

计算第n项的前一行序号l

1+2+?+ln≤1+2+?+l+(l+1)

计算过程如下：

l←1；

while (l?1)*lndol←l+1；

2

l←l-1；

计算第n项在第l+1条对角线的位置

（n-(l?1)*l，l+2-n+(l?1)*l） l为奇数

2 2

（l+2-n+(l?1)*l，n-(l?1)*l） l为偶数

2 2

由此得出算法：

l←1； ｛计算第n项的前一行序号l｝

while (l?1)*lndol←l+1；

2

l←l-1；

n←n-(l 1)*l-1； ｛计算第n项在第l+1条对角线的位置｝

2

ifodd(l)thenbegin

x←1+n；y←l+1-n；

end{then}elsebegin

y←1+n；x←l+1-n；

end；{else}writeln(x，’，/’y)；