导语:
本文主要介绍了关于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中对数字进行排序11/24
- ♥ python装饰器的实现方法12/23
- ♥ 如何检查你的计算机上是否安装了python08/27
- ♥ 为什么python中没有执行import语句11/12
- ♥ python有哪些转义字符串10/04
- ♥ 解决python中json.dumps中文乱码问题11/09
内容反馈