辗转相除法的证明
证明 除法
2023-09-14 09:11:46 时间
描述
给出两个整数 a
和 b
,请计算 a
和 b
的最大公约数,通过 print
语句输出。
1≤b≤a≤1000
样例
评测机将通过执行命令 python main.py {a} {b}
来执行你的代码,并将 a
和 b
作为命令行参数传入。
样例一
当 a = 15
, b = 12
时,程序执行打印出的结果为:
3
样例二
当 a = 10
, b = 7
时,程序执行打印出的结果为:
1
挑战
你可以用时间复杂度比 O(n)
更小的方法来解决该问题吗?
import sys a = int(sys.argv[1]) b = int(sys.argv[2]) # write your code here # please print the greatest common divisor of a and b def gcd(a, b): if a % b == 0: return b return gcd(b, a % b) print(gcd(a, b))
如何证明辗转相除法的正确呢???
我自己想到的一个思路,假设a,b的最大公约数是k,则有a=mk, b=nk;当然,m<n
为了找到k,采用mk%nk=?k,?肯定是小于n的,如果能够使用迭代算法,让?=1,则两个求余结果就是k,也就是要找的最大公约数了。
好,迭代如下:
mk%nk=?k
nk%?k=??k
?k%??k=???k
??%???k=....
则?一直迭代下去肯定会为1。因为两个不断变小的整数相除求余一定会迭代终止,终止条件势必被除数是1.
相关文章
- 【数字信号处理】线性常系数差分方程 ( 根据 “ 线性常系数差分方程 “ 与 “ 边界条件 “ 确定系统是否是 “ 线性时不变系统 “ 案例 | 使用递推方法证明 )
- 【数字信号处理】离散时间系统因果性 ( 因果性概念 | 充要条件及证明 )
- 【数字信号处理】傅里叶变换性质 ( 序列傅里叶变换共轭对称性质示例 | 证明 共轭对称序列 x_e(n) 的 傅里叶变换 是 原序列傅里叶变换 的实部 )
- 轻松理解零知识证明
- lotus 关闭 证明预检查 Proving pre-checks
- lotus windowPoSt 手动触发时空证明计算
- lotus 64GB 扇区 复制证明参数
- 签证存款证明——如果在签证前不久刚存入的资金,最好能够提供资金来源的证明,强调资金肯定不是借来的,是自己家的,这样的证明包括企业的营业执照和盈利的证明(账本),炒股的进出账单、有活期进出帐的存折,父母亲的收入证明等
- 斐波那契数列重要恒等式的简单推导及应用(非严格证明)
- 欧拉公式证明过程
- 学习区块链的基础知识--工作量证明