算法设计与分析 课件全套 第1--8章 绪论、蛮力法 --- 线性规划.pdf

针算机算攸伎什乌兮祈

第1章概述

-r|

例1.1求两个正整数的最大公约数

方法一：利用质因数分解法求解最大公约数，其具

体步骤描述如下：

(1)输入两个正整数a和b。

(2)将a和b分别进行质因数分解，得到它们的所有质因数的

乘积形式。

(3)将a和b中相同的所有质因数乘积计算出来，得到的结果

即为a和b的最大公约数。若a或b无质因数（除1和该数本身外

），则最大公约数为1。

例1.1求任意两个正整数的最大公约数

以具体计算为例，假设需要求解的两个整数为42和28,

42=2XXXX7

37,28=22

共同的质因数2和7,因此，42和28的最大公约数为2X7=14

利用方法一可以快速求出两个整数的最大公约数，但方法一

的描述过程不能称为一个正真意义上的算法，因为第(2)步

没有明确如何将正整数a和b进行质因数分解，且质因数分解

一3

是个NP类问题，目前尚未找到有效的解决方法。第()步

也没有明确定义在两个质因数序列中如何找到相同的质因数

一

元素。因此方法描述不满足算法的确定性和可行性。

例1.1求任意两个正整数的最大公约数

方法二：利用蛮力穷举法求解最大公约数，具体步

骤描述女

主要思想：是从两个整数中较小者开始，去逐步寻找

能被两整数同时整除的数，一旦发现则终止寻找，并

将该数作为两整数的最大公约数。

(4)执行r=r-1,转（3)。

(5)输出r,执行结束。

例1.1求任意两个正整数的最大公约数

以具体计算为例，设a=42和b=28,则计算过程为：

r=28

====

====2742%202,28%208,r20-119

42%2814,28%280,r28-1

42%27=15,28%27=1,r=27-1=2642%19=4,28%19=9,r=l9-1=18

====2542%18=6,28%18=10,r=l8-1=17

42%2616,28%262,r26-1

42%25=17,28%25=3,r=25-1=2442%17=8,28%17=11,r=l7-1=16