第二章第二章 算法初步算法初步第一個算學家第一個算學家劉徽祖沖之祖沖之第二個算學家第二個算學家1算法的基本思想算法的基本思想(1)一、算法概念的理解一、算法概念的理解1.提出問題提出問題:（1）解二元一次方程組有幾種方法）解二元一次方程組有幾種方法?代入消元法和加減消元法代入消元法和加減消元法.（2）結合實例總結用加減消元法解二元一次方程）結合實例總結用加減消元法解二元一次方程組的步驟組的步驟.2121xyxy 第一步第一步, +2,得得5x=1. 第二步第二步, 解解, 得得.x51第三步第三步, 2, 得得 5y=. 第四步第四步, 解解, 得得.35y 第五步第五步, 得到方程組的解為得到方程組的解為.yx5351（3）結合實例總結用代入消元法解二元一次方）結合實例總結用代入消元法解二元一次方程組的步驟程組的步驟.2121xyxy 第一步第一步, 由由得得.yx12 第二步第二步, 把把代入代入, 得得.yy1)12(2第三步第三步, 解解得得.35y 第四步第四步, 把把代入代入, 得得.x511532第五步第五步, 得到方程組的解為得到方程組的解為.yx5351（4）寫出一般二元一次方程組的求解步驟）寫出一般二元一次方程組的求解步驟.111222a xb yca xb yc 122 1(0)a ba b第一步第一步, ,得得2b1b.122 12 112()a ba b xb cb c第二步第二步, 解解, 得得.babacbcbx12212112第三步第三步, , 得得1a 2a 第四步第四步, 解解, 得得.122 1122 1a ca cya ba b .122 1122 1()a ba b ya ca c第五步第五步, 得到方程組的解為得到方程組的解為.2 112122 1122 1122 1b cb cxa ba ba ca cya ba b （5）根據上述實例談談你對算法的理解）根據上述實例談談你對算法的理解.算法的定義算法的定義: 廣義的算法是指完成某項工作的方法和步驟廣義的算法是指完成某項工作的方法和步驟,在數學中在數學中, 算法通常是指按照一定規(guī)則解決某一類問題的明確算法通常是指按照一定規(guī)則解決某一類問題的明確有限的步驟有限的步驟.（6）總結算法的特征）總結算法的特征.確定性確定性: 算法的每一步都應當做到準確無誤、算法的每一步都應當做到準確無誤、“不重不漏不重不漏”.邏輯性邏輯性:算法從開始的算法從開始的“第一步第一步”直到直到“最后一步最后一步”之間做之間做到環(huán)環(huán)相扣到環(huán)環(huán)相扣, 分工明確分工明確, “前一步前一步”是是“后一步后一步”的前提的前提, “后一后一步步”是是“前一步前一步”的繼續(xù)的繼續(xù).有窮性有窮性:算法要有明確的開始和結束算法要有明確的開始和結束, 當到達終止步驟時所當到達終止步驟時所要解決的問題必須有明確的結果要解決的問題必須有明確的結果, 即必須在有限步內完成任務即必須在有限步內完成任務, 不能無限制地持續(xù)進行不能無限制地持續(xù)進行.（7）學習算法的意義）學習算法的意義.在解決某些問題時在解決某些問題時, 需要設計出一系列可需要設計出一系列可操作或可計算的步驟來解決問題操作或可計算的步驟來解決問題, 這些步驟稱為解決這些問題這些步驟稱為解決這些問題的算法的算法. 它的優(yōu)點是一種通法它的優(yōu)點是一種通法, 只要按部就班地去做只要按部就班地去做, 總能得到總能得到結果結果. 因此算法是計算機科學的重要基礎因此算法是計算機科學的重要基礎.二、算法案例分析二、算法案例分析例例1.在給定素數表的前提下在給定素數表的前提下, 設計算法設計算法, 將將936分解成素因素的分解成素因素的乘積乘積.(4000以內的素數表見書以內的素數表見書P161附錄附錄1)分析理解分析理解:1. 查表判斷查表判斷936是否是素數是否是素數:（1）如果）如果963是素數是素數, 則分解結束則分解結束;（2）如果）如果963不是素數不是素數, 則進行第則進行第2步步.2. 確定確定936的最小素因素的最小素因素:2.46829363. 查表判斷查表判斷468是否是素數是否是素數:（1）如果）如果468是素數是素數, 則分解結束則分解結束;（2）如果）如果468不是素數不是素數, 則重復上述步驟則重復上述步驟, 確定確定468的最小素的最小素因素因素.重復進行上述步驟重復進行上述步驟, 直到找出直到找出936的所有素因素的所有素因素.二、算法案例分析二、算法案例分析例例1.在給定素數表的前提下在給定素數表的前提下, 設計算法設計算法, 將將936分解成素因素的分解成素因素的乘積乘積.(4000以內的素數表見書以內的素數表見書P161附錄附錄1)解解算法步驟如下算法步驟如下:1.判斷判斷936是否是素數是否是素數:否否.2.確定確定936最小素因素最小素因素: 2.46829363.判斷判斷468是否是素數是否是素數:否否.4.確定確定468最小素因素最小素因素: 2.9362 2 234 5.判斷判斷234是否是素數是否是素數:否否.6.確定確定234最小素因素最小素因素: 2.9362 2 2 117 7.判斷判斷117是否是素數是否是素數:否否.8.確定確定117最小素因素最小素因素: 3.9362 2 2 3 39 9.判斷判斷39是否是素數是否是素數:否否.10.確定確定39最小素因素最小素因素:3.9362 2 2 3 3 13 11.判斷判斷13是否是素數是否是素數:是是,分解結束分解結束.分解結果是分解結果是:.9362 2 2 3 3 13 短除法短除法例例2.設計一個算法設計一個算法, 求求840與與1764的最大公因數的最大公因數.解解算法步驟如下算法步驟如下:1.先將先將840進行素因素分解進行素因素分解:;384023 5 7 2.然后將然后將1764進行素因素分解進行素因素分解:;22217642373.確定它們的公共素因素確定它們的公共素因素:, , ;2 3 74.確定公共素因素的指數確定公共素因素的指數:公共素因素公共素因素2, 3, 7的指數分別為的指數分別為2, 1, 1;5.最大公因數為最大公因數為.21123784三、課堂練習三、課堂練習練習練習1.設計一個算法設計一個算法, 求求324, 440, 556的最大公因數的最大公因數.練習練習2.設計一個算法設計一個算法, 求求1356和和2400的最小公倍數的最小公倍數.四、課堂小結四、課堂小結1.正確掌握算法的步驟正確掌握算法的步驟;2.能夠寫出常見問題的算法能夠寫出常見問題的算法.