欧几里得算法

来自计算思维百科
跳转至: 导航搜索
欧几里得算法.jpg

欧几里得(德)算法(Euclidean Algorithm),又称辗转相除法,用于计算两个不全为0的非负整数的最大公约数。

基本概念

算法描述:

第一步:如果n=0,返回m的值作为结果,同时过程结束;否则进入第二步。

第二步:m除以n,将余数赋给r。

第三步:将n的值赋给m,将r的值赋给n,返回第一步。


算法运用举例:

如果我们想计算60和24的最大公约数,就执行gcd(60,24)函数,gcd是函数名,60和24是参数,因为60 mod 24=12,所以gcd(60,24)=gcd(24,12),又因为24 mod 12=0,所以gcd(24,12)=gcd(12,0)=12,所以gcd(60,24)=gcd(24,12)=gcd(12,0)=12。

应用范围

最大公约数常常在生产材料划分问题中涉及到,如何在多块材料中寻找相同大小的子块,同时要求子块尽可能大。

使用方法及步骤

  1. 将问题抽象成”求两数最大公约数”问题;
  2. 按照算法基本步骤解出答案。

应用案例

应用1-寻找最佳分割方法

一张长方形的纸板,长75厘米、宽60厘米。现在要把它切割成若干块小正方形,要求正方形的边长为整厘米数,请问共有几种切割法?如果要使切割的正方形面积是最大的,共可以切成多少块? 

解决步骤:

(1)问题抽象:“将长方形切割成若干块小正方形”要求切割的正方形边长必须能同时整除75厘米和60厘米,这就是求75和60的“公约数”的问题;“使切割的正方形面积最大”,也就是要使它的边长最大,这就是求75和60的“最大公约数”的问题。

(2)75和60的公约数有:3、5、15,所以有3种切法;

75和60的最大公约数为:gcd(75,60) = gcd(60,15) =gcd(15,0)=15,所以可以切成60/15=4块。

应用2-寻找最大利用率

在零件制作中有两根材料,一根长25米,一根长30米,为了尽可能不浪费材料制作更多零件,需要先剪成最长的相同段,一共可以剪成多少段?

解决步骤:

(1)问题抽象:在这个问题中,材料要划分为相同的段,而且每段要尽可能长,这就是在25和30之间寻找最大公约数的问题,在实际的生产工作中,这是一个常见的问题。

(2)30和25最大公约数为:gcd(30,25) = gcd(25,5) =gcd(5,0)=5,所以一共可以剪25/5+30/5=11段。

可以体现的计算思维

最大公约数的算法将两个数的最大公约数问题变为一个更简单的实例,例如60与24的最大公约数变成了24与12的最大公约数,其中24与12 的最大公约数比原始问题要更简单。按照这个思路继续下去,24与12 的最大公约数可以变成更简单的问题,直至这个问题直接可解,例如求12与0的最大公约数。体现了计算思维的规约特点。