n的n次方-2022年全国青少年信息素养大赛Python国赛第8题

全国青少年信息素养大赛（原全国青少年电子信息智能创新大赛）是“世界机器人大会青少年机器人设计与信息素养大赛”赛事之一，由中国电子学会主办，包含很多赛项，大赛自2013年举办，已连续成功举办八届，已正式入围“2022-2025学年面向中小学生的全国性竞赛活动名单”。 大赛旨在激发广大青少年的科学兴趣和想象力，培养钻研探究、创新创造的科学精神和实践能力，促进青少年科技创新活动的广泛开展，发现和培养一批具有科研潜质和创新精神的青少年科技创新后备人才。 大赛主要竞赛类别包括电子科技、智能机器人、软件编程三类，全国青少年Python编程挑战赛就属于其中的软件编程类。

一.赛事说明

2021-2022年（第8届）Python挑战赛赛程分为初赛、复赛和总决赛三个阶段。初赛是资格赛，复赛是地方选拔赛，总决赛是全国各地选拔的精英汇聚在一起进行PK。2021-2022年全国青少年Python编程挑战全国总决赛于2022年8月27日正式举行。一共是10道编程题，每道题100分，满分1000分，考试时间是120分钟。 10道编程题分别如下：

• 分苹果
• 韩信点兵
• 借书问题
• 四位数密码
• 邮票面值
• 组合取球
• 统计连续字符
• n的n次方
• 海盗搜身
• 父与子

超平老师将分10讲对每道题进行详细的解读和剖析，今天要解读的是第8题，n的n次方。

二.题目描述

题目背景： 当数字的位数高达上百位时，这样庞大的数字在计算机中的计算已经完全不能用简单的加减乘除来实现了，但是有时候对于这种高精度数字的处理也是编程中必不可缺的。 任意输入―个数字n (99999 < n < 999999)，计算n的n次方（即连续n个n相乘）计算之后，最后的3位数字是多少。 输入描述： ―个数字n (99999 < n < 999999) 输出描述： 计算n的n次方（即连续n个n相乘）之后,最后的3位数字是多少 样例输入： 123456 样例输出： 856 注意： input()内不添加任何参数 只有完全正确才可提交，若无法点击提交说明答题存在错误，可及时进行检查并修改

三.思路分析

Python是一门支持大整数的编程语言。在Python中，整数的表示并不受限于某个固定的范围，其限制是计算机内存的大小，具体来说是运行时的内存大小。 举例说明：

从上面的代码可以看出，Python支持大整数的运算，即便是两个非常大的整数也能够进行加减乘除等运算，其结果也会以大整数的形式输出。 对于本题而言，可以直接计算n的n次方，然后通过余数运算取后3位即可。 但是，我们需要考虑一个问题，就是程序执行的时间（通常称之为算法的时间复杂度）。如果数字比较大，程序执行的时间就长，有可能超出题目的时间限制。 因此，我们需要简化算法，以减少程序执行的时间。 在数学乘法运算中，都是从低位开始相乘，如果乘积大于10，则向高位进位。由此可以看出，低位数字会影响高位的结果，但高位数字不会影响低位的结果。 由于我们只需要乘积的最后3位数字，所以在计算乘方的过程中，每次只需要保留后3位即可，这样可以极大降低程序的运行时间。 接下来，我们进入具体的编程实现环节。

四.编程实现

根据上面的思路分析，我们分如下两种方法来编写代码：

• 常规方法
• 数学方法

1.常规方法 根据上面的思路分析，常规方法就是直接计算乘方，然后取余数，代码如下：  

  需要注意的是，对于乘方的结果，要考虑0的特殊情况，比如n = 100000，后三位是000，如果直接取余的话，结果为0，实际上后3位应该是000。 所以，这里使用了左侧补0的编程技巧。在Python编程中，如果是字符串，左侧补0，可以使用rjust和zfill两个函数，对于纯数字而言，使用格式化字符串即可。 2.数学方法 使用数学方法，就是重复累乘，每次只取后3位，其代码如下：

同理，后3位数字可能包含0，也需要进行补0操作。

五.总结与思考

本题难度中等，考查的知识点主要包括：

• 输入输出函数，尤其是格式化输出；
• 算术运算，包括**和%；
• Python对大整数的支持；
• 时间复杂度的概念；

解决本题的关键在对整数范围的理解，Python是支持大整数的，与之对应的。在C/C++中，整数的范围是有限的，不同类型的整数的范围也各不相同。 尽管可以直接使用乘方运算来计算n的n次方，但超平老师更推荐第二种方式，即数学方法，因为数学方法可以极大的提升程序效率，降低时间复杂度。 同时，我们还要养成细心的习惯，代码写好之后，多测试几次，尤其是一些特殊的情况，这也才能做到尽善尽美。