最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 辗转相除法的减损法与减损定理的最大公约数思路与解法

    方案一:欧几里得算法(Euclidean algorithm)

    定理:两个正整数a和b的最大公约数(a>b)等于c和b的最大公约数,a除以b的余数

    思路:使用递归算法,结束条件:两个数可以整除用c语言求三个数的最大公约数,或者一个数可以减为1

    测试用例:

    输入有0,输入是非整数公共值(每个交换位置尝试一次)输入值相邻(较大的值是10000, 9999)

    # 辗转相除法(欧几里德算法)Euclidean algorithm
    # 定理:两个正整数 a、b(a>b),它们的最大公约数等于 a除以 b 的余数 c 和 b 之间的最大公约数
    # 使用递归解决
    def euclidean_algo(num1: int, num2: int) -> int:
     assert isinstance(num1, int)
     assert isinstance(num2, int)
     big, small = (num1, num2) if num1 > num2 else (num2, num1)
     # 边界条件
     if small == 0:
     return None
     if big%small == 0: # 结束条件:两个数可以相除,或者某一个数减少到 1
     return small
     return euclidean_algo(small, big%small)
    
    if __name__ == "__main__":
     assert euclidean_algo(10, 0) == None # 测试包含 0 的
     assert euclidean_algo(10, 25) == 5 # 正常数值
     assert euclidean_algo(25, 10) == 5 # 交换一下位置
     assert euclidean_algo(3, 2) == 1 # 较大数值
     euclidean_algo(1.0, 2.0) # 输入非整数,运行出现 AssertionError 代表没错
    

    折腾除法中有a%b的取模运算。当两个整数很大时,性能会很差

    时间复杂度为:大约O(log(max(a,b)))

    解决方案2:更减法

    定理:两个正整数a,b(a>b),它们的最大公约数等于a-b的差c与较小数b的最大公约数

    def get_greatest_commin_divisor(num1: int, num2: int) -> int:
     assert isinstance(num1, int)
     assert isinstance(num2, int)
     big, small = (num1, num2) if num1 > num2 else (num2, num1)
     if small == 0:
     return None
     if big == small: # 两个数相同是终止条件
     return small
     return get_greatest_commin_divisor(small, big-small)
    
    if __name__ == "__main__":
     assert get_greatest_commin_divisor(10, 0) == None # 测试包含 0 的
     assert get_greatest_commin_divisor(10, 25) == 5 # 正常数值
     assert get_greatest_commin_divisor(25, 10) == 5 # 交换一下位置
     assert get_greatest_commin_divisor(3, 2) == 1 # 较大数值
    # get_greatest_commin_divisor(1.0, 2.0) # 输入非整数 
    

    多减法:不稳定,当两个整数相差很大时,比如10000和1,需要递归9999次

    最差时间复杂度:O (max (a, b))

    方案3:将减法与减法和移位运算结合(移位运算性能好)(递归函数下面简称gcd)

    测试用例(增加)

    所有偶数

    def get_greatest_commin_divisor(num1: int, num2: int) -> int:
     # 边界条件
     assert isinstance(num1, int)
     assert isinstance(num2, int)
     big, small = (num1, num2) if num1 > num2 else (num2, num1)
     if small == 0: 
     return None
     if big == small: # 两个数相同是终止条件
     return small
    
     if big&1 ==0 and small&1 == 0: # 如果两个都是偶数
     return get_greatest_commin_divisor(big>>1, small>>1)<>1)
     elif big&1 ==0 and small&1 != 0: # 若 big 为偶数, small 为奇数
     return get_greatest_commin_divisor(big>>1, small)
     elif big&1 !=0 and small&1 != 0: # 若 big, small 都为奇数
     return get_greatest_commin_divisor(big-small, small)
    if __name__ == "__main__":
     assert get_greatest_commin_divisor(10, 0) == None # 测试包含 0 的
     assert get_greatest_commin_divisor(10, 25) == 5 # 正常数值
     assert get_greatest_commin_divisor(25, 10) == 5 # 交换一下位置
     assert get_greatest_commin_divisor(36, 10) == 2
     assert get_greatest_commin_divisor(3, 2) == 1 # 较大数值
    # get_greatest_commin_divisor(1.0, 2.0) # 
    

    避免取模运算,算法性能稳定,时间复杂度为O(log(max(a,b)))用c语言求三个数的最大公约数,只有当两个数比较小时,才能看出计算的优势。

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 辗转相除法的减损法与减损定理的最大公约数思路与解法

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论