️️️️- 2022-06-19 14:09 采纳率: 100%
浏览 851
已结题

编写函数,接收两个整数,求最大公约数和最小公倍数,并从键盘上输入两个整数,调用该函数计算两个整数的最大公约数和最小公倍数。

img


可以讲解一下解题思路吗
编写函数,接收两个整数,求最大公约数和最小公倍数,并从键盘上输入两个整数,调用该函数计算两个整数的最大公约数和最小公倍数。

  • 写回答

1条回答 默认 最新

  • A Python 萌新花花 2022-06-19 15:07
    关注

    一、辗转相除法可以求两个因数的最大公因数。(欧几里德算法)

    1.我们可以用列举法、筛选法及短除法求得,如:6和9的最大公因数(6,9)=3

    2.辗转相除法。

    9÷6=1……3

    6÷3=2

    3就是9和6的最大公因数。

    再如:30和80的最大公因数。

    80÷30=2……20

    30÷20=1……10

    20÷10=2

    10就是30和80的最大公因数。

    辗转相除法优点是可以求出两个大数的最大公因数

    二、辗转相除法求最大公因数的原理

    如果我们要求8251与6105的最大公因数的话,假设8251是这个数x的a倍,再假设6105是x的b倍,那么2146=8251-6105,是x的(a-b)倍,也是x的倍数,而无论这几个数如何加减,甚至相乘,都还是最大公约数的倍数,我们就可以把求8251与6105的最大公约数简化成求2146和6105的最大公约数,再把求2146与6105的最大公约数简化为求3959(=6105-2146)与2146的最大公约数,如此相减往复几次后,会发现两个数变相等了37=37,这个数就是两个原来数的最大公因数。  举个例子9和69-6=3,保留6,36-3=3,保留3,3发现两数相等,为3所以最大公因数为3

    9和6的最大公因数,我们知道是3。9是3的倍数,6是3的倍数,那3也一定是3的倍数。

    30和80的公因数为m,30是m的倍数,80是m的倍数。80里有的两个30也肯定是m的倍数,剩下的20也会是m倍数。10也会是m的倍数。10=10=m。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 6月28日
  • 已采纳回答 6月20日
  • 创建了问题 6月19日

悬赏问题

  • ¥20 树莓派5做人脸情感识别与反馈系统
  • ¥15 selenium 控制 chrome-for-testing 在 Linux 环境下报错 SessionNotCreatedException
  • ¥15 使用pyodbc操作SQL数据库
  • ¥15 MATLAB实现下列
  • ¥30 mininet可视化打不开.mn文件
  • ¥50 C# 全屏打开Edge浏览器
  • ¥80 WEBPACK性能优化
  • ¥30 python拟合回归分析
  • ¥500 metaswitch 6010
  • ¥15 关于#分类#的问题:不用人工智能的算法