算法設計與分析 課件 第一章 緒論 1.1 例1.1

計算機算法設計與分析第1章概述例1.1求兩個正整數(shù)的最大公約數(shù)方法一：利用質因數(shù)分解法求解最大公約數(shù)，其具體步驟描述如下：（1）輸入兩個正整數(shù)a和b。（2）將a和b分別進行質因數(shù)分解，得到它們的所有質因數(shù)的乘積形式。（3）將a和b中相同的所有質因數(shù)乘積計算出來，得到的結果即為a和b的最大公約數(shù)。若a或b無質因數(shù)（除1和該數(shù)本身外），則最大公約數(shù)為1。例1.1求任意兩個正整數(shù)的最大公約數(shù)以具體計算為例，假設需要求解的兩個整數(shù)為42和28，42=2×3×7，28=2×2×7共同的質因數(shù)2和7，因此，42和28的最大公約數(shù)為2×7=14利用方法一可以快速求出兩個整數(shù)的最大公約數(shù)，但方法一的描述過程不能稱為一個正真意義上的算法，因為第(2)步?jīng)]有明確如何將正整數(shù)a和b進行質因數(shù)分解，且質因數(shù)分解是一個NP類問題，目前尚未找到有效的解決方法。第(3)步也沒有明確定義在兩個質因數(shù)序列中如何找到相同的質因數(shù)元素。因此方法一描述不滿足算法的確定性和可行性。例1.1求任意兩個正整數(shù)的最大公約數(shù)方法二：利用蠻力窮舉法求解最大公約數(shù)，具體步驟描述如下：（1）輸入a和b。（2）將a和b中的較小者賦值給r。（3）若a、b除以r的余數(shù)同時等于0，轉（5），否則往下執(zhí)行（4）。（4）執(zhí)行r=r-1，轉（3）。（5）輸出r，執(zhí)行結束。主要思想：是從兩個整數(shù)中較小者開始，去逐步尋找能被兩整數(shù)同時整除的數(shù)，一旦發(fā)現(xiàn)則終止尋找，并將該數(shù)作為兩整數(shù)的最大公約數(shù)。例1.1求任意兩個正整數(shù)的最大公約數(shù)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求任意兩個正整數(shù)的最大公約數(shù)在a=42，b=28的情況下，窮舉法運行了15步才計算出結果。方法二窮舉法非常簡單，計算過程易于理解，但窮舉法的效率非常低。例1.1求任意兩個正整數(shù)的最大公約數(shù)方法三：利用輾轉相除法（也稱歐幾里得算法）求解最大公約數(shù)，具體步驟描述如下：（1）輸入兩個整數(shù)a和b。（2）若a<b則將a，b的值互換，以保持a是兩個整數(shù)中較大者，b為較小者。（3）將a除以b的余數(shù)賦值給r，若余數(shù)r等于0，則執(zhí)行（5），否則往下執(zhí)行（4）（4）將除數(shù)b賦值給a，將余數(shù)r賦值給b，轉（3）重復執(zhí)行（5）b為所求最大公約數(shù)，輸出b，執(zhí)行結束。例1.1求任意兩個正整數(shù)的最大公約數(shù)以具體計算為例，設a=42和b=28，則計算過程為：r=42%28=14,a=28,b=14r=28%14=0輸出b，結果為14。在a=42，b=28的情況下，輾轉相除法只運行了2步就計算出結果。例1.1求任意兩個正整數(shù)的最大公約數(shù)算法：輾轉相除法;輸入：兩個正整數(shù)a,b;

輸出：最大公約數(shù)Max_common_divisor(a,b)be