Python基于辗转相除法求解最大公约数的方法示例
作者：grey_csdn 发布时间：2023-08-24 19:47:35
标签：Python,最大公约数
本文实例讲述了Python基于辗转相除法求解最大公约数的方法。分享给大家供大家参考，具体如下：
之前总结过一次高德纳TAOCP中的最大公约数求解，其实课后题中的算法修改要求实现的是辗转相除法求解最大公约数。
这个题目我最初的理解理解错了，自然也没有做出标准答案。现在按照标准答案的解答写一下相应的代码实现：
# -*- coding:utf-8 -*-
#! python2
def MaxCommDivisor(m,n):
while m * n != 0:
m = m ％ n
if m == 0:
return n
else:
n = n ％ m
if n == 0:
return m
print(MaxCommDivisor(55,120))
程序的执行结果：
交换一下两个数字的位置，代码如下：
# -*- coding:utf-8 -*-
#! python2
def MaxCommDivisor(m,n):
while m * n != 0:
m = m ％ n
if m == 0:
return n
else:
n = n ％ m
if n == 0:
return m
print(MaxCommDivisor(120,55))
程序的执行结果：
题目提示中提到了会降低效率，通过上面的代码来看，效率的损失应该是在除法以及判断上。在此，把之前算法的代码拿过来对比一下：
def CommDevisor(m,n):
r = m ％ n
while r != 0:
m = n
n = r
r = m ％ n
return n
print(CommDevisor(120,25))
运行结果：
新算法在循环中，多了一个除法以及比较操作。其实，比较的效率还是不错的，但是除法的运算会导致效率的降低。
PS：这里再为大家推荐几款计算工具供大家进一步参考借鉴：
在线一元函数（方程）求解计算工具：
http://tools.jb51.net/jisuanqi/equ_jisuanqi
科学计算器在线使用_高级计算器在线计算：
http://tools.jb51.net/jisuanqi/jsqkexue
在线计算器_标准计算器：
http://tools.jb51.net/jisuanqi/jsq
希望本文所述对大家Python程序设计有所帮助。
来源：https://blog.csdn.net/grey_csdn/article/details/77414949
0
投稿猜你喜欢
最近在学习python，之前一直用notepad++作为编辑器，偶然发现了VScode便被它的颜值吸引。用过之后发现它启动快速，插件丰富，下- 本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下：#!/usr/bin/env python # find an
- 当你标记了翻译字符串，你就需要写出（或获取已有的）对应的语言翻译信息。 这里就是它如何工作的。地域限制Django不支持把你的应用本地化到一
- 1）正则表达式的使用。 #正则表达式的模块 import re #正则表达式 rePattern = '.*[0-9]{4}'
- 前言本人因为比较喜欢看漫画和动漫, 所以总会遇到一些问题, 因为订阅的漫画或者动漫太多, 总会忘记自己看到那一章节或者不知道什么时候更新.
- 运行环境：Windows 8.1Python：2.7.6在安装的时候，我使用的pip来进行安装,命令如下：pip install beaut
- composer是PHP中非常优秀的一个包管理工具，可以帮助我们来管理项目所需要依赖的所有包以及插件，也可以用来从packagist中创建一
- 在python中。布尔值有 Ture False 两种。Ture等于对，False等于错。要注意在python中对字母的大小写要求非常严格。
- 1.认证与授权1.验证：身份验证是验证个人或设备标识的过程。身份验证过程之一是登录过程。注册网站后，您的信息（ID，密码，名称，电子邮件等）
- 直接update的弊端最近做一个需求，更新3w条数据，一个一个update去更新的，结果花了80分钟，这样性能上很差，也容易阻塞，所以就找了
- 很多人可能发现，无论是在sql 2000， 还是在 sql 2005 中，都没有提供字符串的聚合函数， 所以， 当我们在处理下列要求时，会比
- 通常情况睛，SQLServer2000正在使用的数据库(有数据库连接)，是不能删除或被恢复的，可以将数据库设置为单用户模式，即可删除： AL
- 后台管理配置动态路由菜单前段时间做一个后台管理项目，因为超级管理员可以给普通管理员动态更改权限，所以vue-element-admin里的写
- encode() 方法返回字符串的编码版本。默认编码是当前的默认字符串编码。可给予设置不同的错误处理机制。语法以下是encode
- 本文分析了MySQL中字符串索引对update的影响。分享给大家供大家参考，具体如下：对某一个类型为varchar的字段添加前缀索引后，基于
- 轮播图的根本其实就是缓动函数的封装，如果说轮播图是一辆跑动的汽车，那么缓动函数就是它的发动机，今天本文章就带大家由简入繁，封装属于自己的缓动
- 前言：由于很多业务表因为历史原因或者性能原因，都使用了违反第一范式的设计模式。即同一个列中存储了多个属性值（具体结构见下表）。这种模式下，应
- 开发Web应用时，你经常要加上搜索功能。甚至还不知能要搜什么，就在草图上画了一个放大镜。搜索是项非常重要的功能，所以像elasticsear
- 1、什么是超链接图标规范超链接图标规范是我根据《Iconize Textlinks with CSS》修改调整完成的。主要是整理出常用到的一
- Tensorflow二维、三维、四维矩阵运算（矩阵相乘，点乘，行/列累加）1. 矩阵相乘 根据矩阵相乘的匹配原则，左乘矩阵的列数要等于右乘矩
