第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （普及组）答案及解析.pdfVIP

一、实操题

1、Cantor表

现代数学的著名证明之一是Georg

Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

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

输入：整数N（1≤N）输出：表中的第N项

样例：INPUTOUTPUT

N=71/4

参考答案：对于输入的整数N，我们需要找到表中的第N项。首先，我们需要确定

第N项位于表中的哪一行。由于表中的项是按照Z字形排列的，因此我们可以使用

以下公式来确定第N项所在的行数：行数=floor(sqrt(2N)+

0.5)然后，我们需要确定第N项在该行中的位置。由于每一行的项是按照递增的顺

序排列的，因此我们可以使用以下公式来确定第N项在该行中的位置：位置=

2*(行数-1)*行数+(N-(行数-

1)*行数)最后，我们需要确定第N项的具体值。由于表中的项是按照分数形式表示

的，因此我们可以使用以下公式来确定第N项的具体值：分子=位置分母=行数

解析：【喵呜刷题小喵解析】：

对于输入的整数N，我们需要找到表中的第N项。由于表中的项是按照Z字形排列

的，因此我们需要先确定第N项所在的行数，然后再确定第N项在该行中的位置，

最后确定第N项的具体值。

首先，我们可以使用公式“行数=floor(sqrt(2N)+

0.5)”来确定第N项所在的行数。这个公式是根据Z字形的排列规律推导出来的，它

可以帮助我们快速确定第N项所在的行数。

然后，我们可以使用公式“位置=2*(行数-1)*行数+(N-(行数-

1)*行数)”来确定第N项在该行中的位置。这个公式是根据每一行的项是按照递增的

顺序排列的规律推导出来的，它可以帮助我们快速确定第N项在该行中的位置。

最后，我们可以使用公式“分子=位置”和“分母=

行数”来确定第N项的具体值。由于表中的项是按照分数形式表示的，因此我们可

以直接根据第N项在该行中的位置和行数来确定第N项的具体值。

需要注意的是，由于表中的项是按照Z字形排列的，因此我们需要使用“行数=

floor(sqrt(2N)+0.5)”这个公式来确定第N项所在的行数，而不是直接使用“行数=

N”这个公式。这是因为直接使用“行数=

N”这个公式可能会导致计算出错，因为Z字形的排列规律并不是简单的递增规律。

2、回文数

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文

数。

例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回

文数。

又如：对于10进制数87：

STEP1：87+78=165STEP2：165+561=726

STEP3：726+627=1353STEP4：1353+3531=4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2=N=10，N=16）进制数M，求最少经过几步可以得

到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！

”

样例：INPUTOUTPUT

N=9M=87STEP=6

参考答案：对于给定的N进制数M，我们可以按照以下步骤来求解最少经过几步可

以得到回文数：1.将M从N进制转换为10进制。2.

从M的10进制表示开始，不断将其与它的逆序数相加，直到得到回文数或者步数超

过30步。3.

如果在30步以内得到了回文数，则返回步数；否则输出“Impossible！”。

解析：【喵呜刷题小喵解析】：

对于这个问题，最直接的方法是尝试从给定的N进制数M开始，不断将其与它的逆

序数相加，直到得到回文数或者步数超过30步。但是这种方法的时间复杂度较高，

因为每次相加都需要将两个数从N进制转换为10进制，然后再进行加法运算，最后

再将结果从10进制转换回N进制。

为了优化算法，我们可以考虑将M从N进制转换为10进制后，直接进行加法运算，

而不需要每次都进行进制转换。具体来说，我们可以将M的每一位数字提