Python如何用欧几里得求逆元
【摘要】Python用欧几里得求逆元的方法:建立一个带参数返回值的函数,编写求逆元的一次算法,采用递归的方式循环调用函数,递归直至余数等于零。调
Python用欧几里得求逆元的方法:
建立一个带参数返回值的函数,编写求逆元的一次算法,采用递归的方式循环调用函数,递归直至余数等于零。调用该函数,将需要求的数值带入进去,执行该函数就可以了
示例代码如下:
def ext_gcd(a, b): #扩展欧几里得算法
if b == 0:
return 1, 0, a
else:
x, y, gcd = ext_gcd(b, a % b) #递归直至余数等于0(需多递归一层用来判断)
x, y = y, (x - (a // b) * y) #辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立
return x, y, gcd
执行结果如下:
ext_gcd(1848,701)
>>> (-11, 29, 1)
更多Python知识,请关注:Python自学网!!
上一篇:python爬虫的工作步骤
下一篇:如何在服务器上跑python程序
就业培训申请领取
环球青藤
官方QQ群扫描上方二维码或点击一键加群,免费领取大礼包,加群暗号:青藤。 一键加群
最新文章
Python编程各地入口
环球青藤官方微信服务平台
刷题看课 APP下载
免费直播 一键购课
代报名等人工服务
Python编程热点排行