约数与倍数-第12届蓝桥杯选拔赛Python真题精选

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

约数与倍数,本题是2020年11月21日举办的第12届蓝桥杯青少组Python编程选拔赛真题,题目要求编程计算并输出给定两个正整数的最大公约数和最小公倍数。

先来看看题目的要求吧。

一.题目说明

提示信息:

倍数与约数:如果a能被b整除,a就叫做b的倍数,b就叫做a的约数。约数和倍数都表示一个整数与另一个整数的关系,不能单独存在。

最大公约数:几个整数中公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。

举例:12、16的公约数有1、2、4,其中最大的一个是4,所以4是12与16的最大公约数。

最小公倍数:几个自然数公有的倍数,叫做这几个数的公倍数,其中最小的一个,叫做这几个数的最小公倍数。

举例:4的倍数有4、8、12、16,….,6的倍数有6、12、18、24,….,4和6的公倍数有12、24,……其中最小的是12,所以4和6最小公倍数为 12。

编程实现:

分别输入两个正整数(1 < 正整数 < 201),输出这两个正整数的最大公约数M及最小公倍数N(注:M和N之间以一个英文逗号隔开)。

输入描述:

第1行输入第一个正整数

第2行输入第二个正整数

输出描述:

输出这两个正整数的最大公数M及最小公倍数N(M和N之间以一个英文逗号隔开)

样例输入:

4

6

样例输出:

2,12

二.思路分析

这是一道简单的数论题,考查的是最大公约数和最小公倍数算法,涉及的知识点包括循环、余数运算和函数。

最大公约数,也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个,通常称之为GCD(Greatest Common Divisor)。

例如8和12,两个数的公约数分别为1、2、4,其中4为8和12的最大公约数。

图片

计算最大公约数的方法比较多,常见的有如下几种:

  • 枚举算法

  • 欧几里得算法

  • 更相减损术

  • Stein算法

其中最简单的就是枚举算法,其核心思想就是从较小的数字开始,寻找能同时被两个正整数整除的数字,直到1为止,一旦找到了,就结束循环。

欧几里得算法,又称辗转相除法,是一种高效的求解方法。它的基本思想是用两个数的余数进行迭代计算,直到余数为0时,此时的除数即为两个数的最大公约数。

该算法基于一个定理:

两个正整数a和b( a > b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。

我们先来看一看数字1112和695的最大公约数是多少吧,使用欧几里得算法的步骤如下:

图片

与最大公约数相对应的概念是最小公倍数,两个或多个整数公有的倍数叫做它们的公倍数,其中除0以外最小的一个公倍数就叫做最小公倍数,通常称之为LCM(Least Common Multiple)。

比如,要计算15和35的最小公倍数,如下所示:

图片

其计算方式也有多种,典型的有两种,第一种是使用枚举算法,第二种是利用最大公约数来计算。

我们可以利用这样一个事实:两个数的乘积等于它们的最大公约数和最小公倍数的乘积,也就是说:

a * b = GCD(a, b) * LCM(a, b)

因此,我们可以先计算最大公约数,然后用这个公式来获取最小公倍数。

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

三.编程实现

根据上面的思路分析,我们使用两种方式实现:

  • 枚举算法

  • 欧几里得算法

1. 枚举算法

为了方便,我们可以定义函数来获取两个整数的最大公约数和最小公倍数,计算GCD的函数定义如下:

图片

代码不难,简单说明两点:

1). 需要比较a和b的大小,确保 a < b;

2). 注意从较小的a开始,直到1为止,一旦找到第一个公约数,它就是最大的,结束循环,返回即可。

计算LCM的函数定义如下:

图片

同样说明两点:

1). 仍然要比较a和b的大小,确保a < b;

2). 循环的次数无法确定,不能使用for...in循环,使用while更方便。

2. 欧几里得算法

接下来,我们使用欧几里得算法来计算最大公约数,定义函数如下:

图片

代码不多,强调一点,有些同学会先比较a和b的大小,这是可以的。但实际上不需要比较a和b的大小,因为算法本身会处理这种情况。无论a和b的初始大小关系如何,算法都会正确地计算出它们的最大公约数。

在每一次迭代中,我们将较小的数和较大的数除以较小数后的余数进行交换。由于余数总是小于除数,因此这个过程会确保我们总是用较小的数去除以较大的数,直到余数为0。

相应的,计算最小公倍数的函数定义如下:

图片

代码更为简单,注意使用的是整除运算符,确保得到的结果是整数。

有了前面定义的函数,接下来就简单了,代码如下:

图片

代码非常简单,说明两点:

1). 前面给出了两种算法,你只需要使用其中一种即可;

2). 最后输出的使用,需要使用逗号隔开,使用sep参数最简单,效果也最好。

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

四.总结与思考

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

  • 输入输出;

  • 循环编程,包括for和while;

  • 余数运算;

  • 自定义函数;

本题难度一般,关键是要理解最大公约数和最小公倍数的含义,快速找到解决方案。

枚举算法是最简单的,也是我们解决大部分问题的首选,但是随着数字或者数据规模的增加,枚举算法的效率就会大大降低。

以上面的代码为例,假设我们有两个整数a和b(假设a <= b),使用枚举算法来计算它们的最大公约数的复杂度可以这样分析:

在最坏情况下,我们需要尝试从a(较小数)递减到1,检查每个数是否是a和b的公约数,因此,需要进行的比较次数是a次。

所以,枚举算法计算GCD的时间复杂度是O(a)。这个复杂度是线性的,意味着随着输入数a的增大,所需的时间也会线性地增长。

使用欧几里得算法时,我们是通过余数来不断减小数字的,其时间复杂度与a和b中较小者的值成对数关系,即O(log(min(a, b))),这在处理大整数时具有显著的优势。

超平老师给你留一道思考题,除了本文介绍的枚举算法和欧几里得算法,其它几种算法思想是怎样的,又该如何编写代码呢?

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

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519581.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

rust 面向对象编程特性、模式与模式匹配、高级特征

面向对象编程OOP 学习了结构体、枚举&#xff0c;它们可以包含自定义数据字段&#xff0c;也可以定义内部方法&#xff0c;它们提供了与对象相同的功能。 面向对象的四大特征&#xff1a;封装、继承、多态 通过pub标记为公有的结构体&#xff0c;在其他模块中可以访问使用这…

python爬虫———post请求方式(第十四天)

&#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; &#x1f388;&#x1f388;所属专栏&#xff1a;python爬虫学习&#x1f388;&#x1f388; ✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天…

C语言【编译和链接】

1.程序执行过程 C语言的编译和链接是将源代码转换为可执行程序的过程。下面是C语言编译和链接的基本步骤&#xff1a; 预处理&#xff1a;在编译前&#xff0c;预处理器会对源代码进行。它会处理以"#"开头的预处理指令&#xff0c;#include和#define&#xff0c;并将…

算法笔记————ST表

运用了倍增思想&#xff0c;从小到大处理 1.【模板】ST 表 // Problem: // P3865 【模板】ST 表 // // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3865 // Memory Limit: 125 MB // Time Limit: 800 ms // // Powered by CP Editor (https://cpedi…

Kotlin学习日志(一)TextView、Button、Toast的使用(1)

android:layout_width“wrap_content” android:layout_height“wrap_content”/> import kotlinx.android.synthetic.main.activity_main.* 这句话的意思是引进Kotlin的的控件变量自动映射功能&#xff0c;接下来只要是这个activity_main.xml文件中的控件&#xff0c;我…

非关系型数据库——Redis基本操作

目录 一、Redis数据库常用命令 1.Set——存放数据 2.Get——获取数据 3.Keys——获取符合条件的键值 4.Exists——判断键值是否存在 5.Del——删除指定键值 6.Type——获取键值对应的类型 7.Rename——对已有键值重命名&#xff08;覆盖&#xff09; 8.Renamenx——对…

160 Linux C++ 通讯架构实战14,epoll 反应堆模型

到这里&#xff0c;我们需要整理一下之前学习的epoll模型&#xff0c;并根据之前的epoll模型&#xff0c;提出弊端&#xff0c;进而整理epoll反应堆模型&#xff0c;进一步深刻理解&#xff0c;这是因为epoll实在是太重要了。 复习之前的epoll的整体流程以及思路。 参考之前写…

虚幻UE5智慧城市全流程开发教学

一、背景 这几年&#xff0c;智慧城市/智慧交通/智慧水利等飞速发展&#xff0c;骑士特意为大家做了一个这块的学习路线。 二、这是学习大纲 1.给虚幻UE5初学者准备的智慧城市/数字孪生蓝图开发教程 https://www.bilibili.com/video/BV1894y1u78G 2.UE5数字孪生蓝图开发教学…

【软件工程】测试规格

1. 引言 1.1简介 本次的测试用例是基于核心代码基本开发完毕&#xff0c;在第一代系统基本正常运行后编写的&#xff0c;主要目的是为了后续开发与维护的便利性。 该文档主要受众为该系统后续开发人员&#xff0c;并且在阅读此文档前最后先阅读本系统的需求文档、概要设计文…

海外视频网站推广实战需掌握的10个关键性数据指标-华媒舍

在海外视频网站推广实战中&#xff0c;了解和掌握一些关键性数据指标是非常重要的。这些指标可以帮助我们评估视频网站的推广效果&#xff0c;优化推广策略&#xff0c;提升用户体验。以下是推广人员在实战中应该了解和关注的十个关键性数据指标&#xff1a; 1. 视频创意点击率…

PS入门|规规矩矩的图形怎么抠出来?

前言 上一次讲解到用魔棒工具蒙版可以把需要的区域抠出来&#xff0c;但仅适用于边缘锐利的类型。 但魔棒工具并不适用于边缘区域有过渡色的内容&#xff0c;比如下面这张照片&#xff1a; 如果直接使用魔棒工具进行选择&#xff0c;就会出现下面这种情况&#xff1a; 在边界…

数据挖掘入门项目二手交易车价格预测之建模调参

文章目录 目标步骤1. 调整数据类型&#xff0c;减少数据在内存中占用的空间2. 使用线性回归来简单建模3. 五折交叉验证4. 模拟真实业务情况5. 绘制学习率曲线与验证曲线6. 嵌入式特征选择6. 非线性模型7. 模型调参&#xff08;1&#xff09; 贪心调参&#xff08;2&#xff09;…

内表GROUP BY

内表GROUP BY REPORT z_test_table_lhy. DATA: price TYPE sflight-price. SELECT MIN( price ) AS m,carridINTO DATA(t_temp)FROM sflightGROUP BY carridHAVING MAX( price ) > 10. "Having从句中比较统计结果时&#xff0c;需要将统计函数重写一遍&#xff0c;而不…

Android数据存储技术

一、文件存储 <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android"android:orientation"vertical"android:layout_width"match_parent"android:layout_height"match_parent" ><EditTextandroid:id&qu…

树莓派安装Windows搭建网盘和下载机

0 需求分析 在同一个局域网内&#xff0c;同时有多种设备&#xff08;Windows&#xff0c;Linux&#xff0c;Android&#xff09;需要进行大量的数据共享。另外&#xff0c;还时常需要从百度网盘/夸克网盘等网盘下载文件。不难看出&#xff0c;我的需求很简单&#xff0c;就是…

异常的处理

异常处理概述 在编写程序时&#xff0c;经常要在可能出现错误的地方加上检测的代码&#xff0c;如进行x/y运算时&#xff0c;要检测分母为0&#xff0c;数据为空&#xff0c;输入的不是数据而是字符等。过多的if-else分支会导致程序的代码加长、臃肿&#xff0c;可读性差&…

论文笔记:Large Language Models as Analogical Reasoners

iclr 2024 reviewer打分5558 1 intro 基于CoT prompt的大模型能够更好地解决复杂推理问题 然而传统CoT需要提供相关的例子作为指导&#xff0c;这就增加了人工标注的成本——>Zero-shot CoT避免了人工标注来引导推理 但是对于一些复杂的任务难以完成推理&#xff0c;例如c…

Ubuntu22.04中基于Qt开发Android App

文章目录 前言在Ubuntu22.04中配置开发环境案例测试参考 前言 使用Qt开发手机应用程序是一种高效且灵活的选择。Qt作为一个跨平台的开发框架&#xff0c;为开发者提供了统一的开发体验和丰富的功能库。首先&#xff0c;Qt的跨平台性让开发者可以使用相同的代码库在不同的操作系…

SSM项目实战——哈哈音乐(四)前台模块开发

1、项目准备 ①导入依赖和前端资源 <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.x…

路由策略与路由控制之双点双向重发布(OSPF-ISIS)实验

双点双向重发布在路由协议中&#xff0c;特别是在OSPF&#xff08;开放式最短路径优先&#xff09;与IS-IS&#xff08;中间系统到中间系统&#xff09;等协议之间&#xff0c;指的是在两个协议间或者两个进程间进行路由信息共享的机制。这种机制涉及到在两个不同的协议区域使用…