中国十大网站域名,云空间网站怎么做,2022好项目免加盟费,企业咨询服务是做什么的两个数的最大公约数1.辗转相除法求解两个数的最大公约数2.更相减损术求解两个数的最大公约数3.不严格理解1.辗转相除法求解两个数的最大公约数
辗转相除法#xff1a;两个正整数a和b#xff08;ab#xff09;的最大公约数等于a除以b的余数与b 之间的最大公约数。–如果…
两个数的最大公约数1.辗转相除法求解两个数的最大公约数2.更相减损术求解两个数的最大公约数3.不严格理解1.辗转相除法求解两个数的最大公约数
辗转相除法两个正整数a和bab的最大公约数等于a除以b的余数与b 之间的最大公约数。–如果a能被b整除那么a和b之间的最大公约数为b.
def gcd(a,b):while(a%b!0):ma%babbmreturn b2.更相减损术求解两个数的最大公约数
更相减损术两个正整数a和bab的最大公约数等于a-b的差值c和b的最大公约数。
def gcd(a,b):while(a!b):ca-bamax(c,b)bmin(c,b)return b3.不严格理解
更相减损术原理讲解参看博文http://blog.sina.com.cn/s/blog_5253930a0102y5p8.html
辗转相除法原理: 1.假设ab∗krab*krab∗kr 2.将b拆成最小因数相乘:nc∗d∗enc*d*enc∗d∗e,那么ak∗c∗d∗erak*c*d*erak∗c∗d∗er 3.如果r是b的因数则b中有一个或多个因数乘积可构成r,假设rc*d 4.ak∗c∗d∗erk∗c∗d∗ec∗dc∗d(k∗e1)ak*c*d*erk*c*d*ec*dc*d(k*e1)ak∗c∗d∗erk∗c∗d∗ec∗dc∗d(k∗e1),则r也为a的因数 5.因为(k∗e1)(k*e1)(k∗e1)与k∗ek*ek∗e是相邻的两个数没有除了1之外的公约数所以a和b的最大公约数为r
综上就是通过不断的相除找到是b因数的r.
