贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的的时在某种意义上的局部最优解。 贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。
欧几里得算法的目标是找到两个数的最大公约数。计算两个非负整数p和q的最大公约数：若q是0，则最大公约数为p。
计算最大公因数的欧几里得算法最大公因数最大公因数，也称最大公约数，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b）。求最大公约数有多种方法，常见的有质因数分解法、辗转相除法等等。应用领域有数学和计算机两个方面。计算公式gcd(a,b)
递归边界：当 b为 0时，此时的 a就等于 gcd，显然有 a*1+b*0=gcd成立，此时 x=1,y=0；递推公式：设当计算 gcd(a,b)时，有 ax1 + by1 = gcd成立；而在下一步计算gcd时，又有bx2+ (a%b)y2= gcd成立
x0 = x*(b/d)%n; //x0为方程的一个特解，可以为正也可以为负。题目要求的是最小的非负数
安科网(Ancii)，中国第一极客网
Copyright © 2013 - 2019 Ancii.com
京ICP备18063983号-5 京公网安备11010802014868号