知识点 算法案例
知识点—— 算法案例
【常见三大算法】 (1)求最大公约数 (2)秦九韶算法 (3)进位制
算法案例 【常见三大算法】 （1）求最大公约数 （2）秦九韶算法 （3）进位制
【求最大公约数】 (1)短除法 求两个正整数的最大公约数的步骤:先用两个数 公有的质因数连续去除,一直除到所得的商是两 个互质数为止,然后把所有的除数连乘起来 (2)穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤: 从两个数中较小数开始由大到小列举,直到找到 公约数立即中断列举,得到的公约数便是最大公 约数
算法案例 【求最大公约数】 （1）短除法 求两个正整数的最大公约数的步骤：先用两个数 公有的质因数连续去除，一直除到所得的商是两 个互质数为止，然后把所有的除数连乘起来. （2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤： 从两个数中较小数开始由大到小列举，直到找到 公约数立即中断列举，得到的公约数便是最大公 约数
求最大公约数】 (3)辗转相除法 辗转相除法求两个数的最大公约数,其算法可以 描述如下 ①输入两个正整数m和m(m>n); ②求余数r:计算m除以n,将所得余数存放到变 量r中; ③更新被除数和余数:m=n,n=r; ④判断余数r是否为0若r=0,则m,n的最大公约 数等于m;否则转向第②步继续循环执行. 如此循环,直到得到结果为止
算法案例 【求最大公约数】 （3）辗转相除法 辗转相除法求两个数的最大公约数，其算法可以 描述如下： ①输入两个正整数m和n(m>n)； ② 求余数r：计算m除以n，将所得余数存放到变 量r中； ③更新被除数和余数：m=n，n=r； ④判断余数r是否为0.若r=0，则m，n的最大公约 数等于m；否则转向第②步继续循环执行. 如此循环，直到得到结果为止
【求最大公约数】 (4)更相减损术 我国早期也有解决求最大公约数问题的算法,就是更 相减损术,在《九章算术》中记载了更相减损术求最大 公约数的步骤:可半者半之,不可半者,副置分母·子 之数,以少减多,更相减损,求其等也,以等数约之 步骤: I.任意给出两个正数;判断它们是否都是偶数 若是,用2约简;若不是,执行第二步. Ⅱ.以较大的数减去较小的数,接着把较小的数与所 得的差比较,并以大数减小数继续这操作,直到所得 的数相等为止,则这个数(等数)就是所求的最大公 约数
算法案例 【求最大公约数】 （4）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更 相减损术.在《九章算术》中记载了更相减损术求最大 公约数的步骤：可半者半之，不可半者，副置分母•子 之数，以少减多，更相减损，求其等也，以等数约之. 步骤： Ⅰ．任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步. Ⅱ．以较大的数减去较小的数，接着把较小的数与所 得的差比较，并以大数减小数.继续这操作，直到所得 的数相等为止，则这个数（等数）就是所求的最大公 约数