最小质数对-第12届蓝桥杯国赛Python真题解析

admin2024-05-15  0

最小质数对-第12届蓝桥杯国赛Python真题解析,第1张

[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第63讲。

最小质数对,本题是2021年5月29日举办的第12届蓝桥杯青少组Python编程全国总决赛真题编程部分第4题。题目要求给定一个大于2的偶数,编程找出质数差最小的一对,并输出其差值。

先来看看题目的要求吧。

一.题目说明

提示信息:

质数:是一个大于1的自然数,且除了1和它本身外,不能被其他自然数整除的数。最小的质数是2,1不是质数。

大于2的偶数有一个特点,任意一个大于2的偶数可以由一对质数相加得到,但有的偶数不止有一对这样的质数对。

如偶数6,有一对质数相加得6,为(3,3)

如偶数14,有两对质数相加得14,分别是(3,11),(7,7)

编程实现:

给定一个大于2的偶数,在所有满足“任意一个大于2的偶数可以由两个质数相加得到”这个特点的质数对中,找出两个质数差值最小的一对,并将差值输出(差值为大数减小数的值,两个质数相等时差值为0)。

例如:偶数16,满足特点的质数对有(5,11)和(3,13),差值最小的一对是(5,11),11减5,差值为6。

输入描述:

输入一个大于2的偶数N

输出描述:

输出满足“任意一个大于2的偶数可以由两个质数相加得到”这个特点的所有质数对中,差值最小的那一对的差值

样例输入:

16

样例输出:

6

二.思路分析

这是一道简单的枚举算法题,考查的知识点主要包括循环、条件、函数和素数等。

这就是一个典型的枚举场景,将和为n的所有质数对枚举出来,比较它们的差值,找到最小的差值即可。

我们可以分两个步骤来实现:

1). 自定义函数判断素数

2). 枚举所有质数对,获取最小差值

关于素数的判断,使用的也是枚举算法,之前已经介绍过,具体可以参考《包含3的数字-第10届蓝桥杯省赛Python真题精选》这篇教程。

对于数字n而言,假设其中一个加数为i,则另外一个加数为 n - i。

很显然,这两个加数,一个位于 n // 2的左边,一个位于n // 2的右边,最极端的情况是重叠。

因此,我们在枚举的时候,只需要将范围限定在[2, n // 2]之间就可以了,这样可以减少循环的次数,提升效率。

思路有了,接下来,我们就进入具体的编程实现环节。

三.编程实现

根据上面的思路分析,我们分两步来编写程序:

  • 定义函数判断素数

  • 枚举所有质数对,获取最小差值

1. 定义函数判断素数

这是一段经典的代码,直接编写代码如下:

最小质数对-第12届蓝桥杯国赛Python真题解析,图片,第2张

代码非常简单,强调两点:

1). 为了确保完整性,对于n < 2的数字,都返回False,即不是素数;

2). 在获取n的算术平方根时,除了可以使用sqrt()函数外,直接使用**0.5 是最简洁的写法。

2. 枚举所有质数对,获取最小差值

根据前面的思路分析,编写代码如下:

最小质数对-第12届蓝桥杯国赛Python真题解析,图片,第3张

代码不多,说明4点:

1). 在获取最值时,通常需要定义最值的初始值,在Python编程中,可以使用正无穷大float('inf')表示最大值,相应的使用负无穷大float('-inf')表示最小值;

2). 在使用range()函数时,第二个参数要设置为 n // 2 + 1;

3). 在获取较小值时,直接使用了min()函数,方便快捷,也可以使用if语句来比较;

4). 第9行代码中,一个质数是n - i,一个是i,其差为 n - i - i,也就是n - 2 * i了。

至此,整个程序就全部完成了,你也可以输入不同的数字来测试效果啦。

四.总结与思考

本题代码在13行左右,涉及到的知识点包括:

  • 循环语句;

  • 条件语句;

  • 自定义函数;

  • 枚举算法;

作为本次国赛的第4题,本题难度一般。关键点有两个,一是熟悉素数的判断,二是如何优化代码结构,让代码变得更加简单,更加高效。

尤其是第二点,良好的代码结构可以让复杂问题变得简单,也可以减少出错的概率,那什么才算是好的代码结构呢?

一般来说,凡是具有独立功能或者重复使用的地方,就可以运用函数的编程思想,将其独立出来,自定义成一个函数。

在学习编程的时候,我们应该秉持”Write less,do more“的思想,用尽量少的代码,实现更多的功能和效果。

超平老师给你留一道思考题,本题中设置min_diff时使用了float('inf'),为什么要设置为最大值?如果不使用float('inf'),还可以设置为多少,为什么?

你还有什么好的想法和创意吗,也非常欢迎和超平老师分享探讨。

如果你觉得文章对你有帮助,别忘了点赞和转发,予人玫瑰,手有余香😄

需要源码的,可以移步至”超平的编程课“gzh。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!