Anqin1995
Anqin1995
关注数: 0
粉丝数: 8
发帖数: 4,941
关注贴吧数: 0
问一道有关计算最大公约数的算法题，和拓展欧几里得算法 现在已知二进制最大公约数算法（称之为f) 如下： f(a, b): 给定正整数a, b （假设a>=b) 如果a等于b, 返回a 如果a和b都是偶数，递归调用f(a/2, b/2)，将结果记为g，返回2g 如果a和b都是奇数，递归调用f((a-b)/2, b), 将结果记为g, 返回g 否则（这种情况下a和b一奇一偶），假设a是偶数b是奇数，递归调用f(a/2, b)，将结果记为g，返回g. 问题是如何修改此算法，使其同时返回s和t, 使得sa+tb=g，g是原算法返回的a与b的最大公约数. 我知道拓展欧几里得算法可以计算s和t，但是如果将之运用到此算法呢？ 谢谢
问一道有关计算最大公约数的算法题，和拓展欧几里得算法 现在已知二进制最大公约数算法（称之为f) 如下： f(a, b): 给定正整数a, b （假设a>=b) 如果a等于b, 返回a 如果a和b都是偶数，递归调用f(a/2, b/2)，将结果记为g，返回2g 如果a和b都是奇数，递归调用f((a-b)/2, b), 将结果记为g, 返回g 否则（这种情况下a和b一奇一偶），假设a是偶数b是奇数，递归调用f(a/2, b)，将结果记为g，返回g. 问题是如何修改此算法，使其同时返回s和t, 使得sa+tb=g，g是原算法返回的a与b的最大公约数. 我知道拓展欧几里得算法可以计算s和t，但是如果将之运用到此算法呢？ 谢谢
1
下一页
