算法设计与分析 课件 第一章 绪论 1.1 例1.1.ppt

计算机算法设计与分析第1章概述例1.1求两个正整数的最大公约数方法一：利用质因数分解法求解最大公约数，其具体步骤描述如下：（1）输入两个正整数a和b。（2）将a和b分别进行质因数分解，得到它们的所有质因数的乘积形式。（3）将a和b中相同的所有质因数乘积计算出来，得到的结果即为a和b的最大公约数。若a或b无质因数（除1和该数本身外），则最大公约数为1。例1.1求任意两个正整数的最大公约数以具体计算为例，假设需要求解的两个整数为42和28，42=2×3×7，28=2×2×7共同的质因数2和7，因此，42和28的最大公约数为2×7=14利用方法一可以快速求出两个整数的最大公约数，但方法一的描述过程不能称为一个正真意义上的算法，因为第(2)步没有明确如何将正整数a和b进行质因数分解，且质因数分解是一个NP类问题，目前尚未找到有效的解决方法。第(3)步也没有明确定义在两个质因数序列中如何找到相同的质因数元素。因此方法一描述不满足算法的确定性和可行性。例1.1求任意两个正整数的最大公约数方法二：利用蛮力穷举法求解最大公约数，具体步骤描述如下：（1）输入a和b。（2）将a和b中的较小者赋值给r。（3）若a、b除以r的余数同时等于0，转（5），否则往下执行（4）。（4）执行r=r-1，转（3）。（5）输出r，执行结束。主要思想：是从两个整数中较小者开始，去逐步寻找能被两整数同时整除的数，一旦发现则终止寻找，并将该数作为两整数的最大公约数。例1.1求任意两个正整数的最大公约数r=2842%28=14,28%28=0,r=28-1=2742%27=15,28%27=1,r=27-1=2642%26=16,28%26=2,r=26-1=2542%25=17,28%25=3,r=25-1=2442%24=18,28%24=4,r=24-1=2342%23=19,28%23=5,r=23-1=2242%22=20,28%22=6,r=22-1=2142%21=0,28%21=7,r=21-1=2042%20=2,28%20=8,r=20-1=1942%19=4,28%19=9,r=19-1=1842%18=6,28%18=10,r=18-1=1742%17=8,28%17=11,r=17-1=1642%16=10,28%16=12,r=16-1=1542%15=12,28%15=13,r=15-1=1442%14=0,28%14=0输出r，结果为14。以具体计算为例，设a=42和b=28，则计算过程为：例1.1求任意两个正整数的最大公约数在a=42，b=28的情况下，穷举法运行了15步才计算出结果。方法二穷举法非常简单，计算过程易于理解，但穷举法的效率非常低。例1.1求任意两个正整数的最大公约数方法三：利用辗转相除法（也称欧几里得算法）求解最大公约数，具体步骤描述如下：（1）输入两个整数a和b。（2）若ab则将a，b的值互换，以保持a是两个整数中较大者，b为较小者。（3）将a除以b的余数赋值给r，若余数r等于0，则执行（5），否则往下执行（4）（4）将除数b赋值给a，将余数r赋值给b，转（3）重复执行（5）b为所求最大公约数，输出b，执行结束。例1.1求任意两个正整数的最大公约数以具体计算为例，设a=42和b=28，则计算过程为：r=42%28=14,a=28,b=14r=28%14=0输出b，结果为14。在a=42，b=28的情况下，辗转相除法只运行了2步就计算出结果。例1.1求任意两个正整数的最大公约数算法：辗转相除法;输入：两个正整数a,b;输出：最大公约数Max_common_divisor(a,b)beginifabthena与b互换endr?amodbwhiler≠0doa?b,b?r,r?amodbendprintbend