欧几里得算法 介绍 欧几里德算法,又叫做辗转相除法,用于计算两个正整数a,b的最大公约数(the greatest common divisor)。 计算公式 gcd(a,b)=gcd(b,amod b)gcd(a,b)=gcd(b,a\mod b) gcd(a,b)=gcd(b,amodb) 证明 第一步:不妨假设 c=gcd(a,b)c=gcd(a,b)c=gcd(a,b),则 a=mca=mca=mc, 2023-11-18 算法 #算法
贪心算法 介绍 贪心算法(英语:greedy algorithm),又称贪婪算法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。 贪心法是解决问题的一种策略。如果策略正确,那么贪心法往往是易于描述、易于实现的。 经典问题 1 2023-11-11 算法 #算法