江西省遂川二中高中數(shù)學(xué) 算法的基本思想課件（1） 北師大版必修3

第二章第二章 算法初步算法初步第一個算學(xué)家第一個算學(xué)家劉徽祖沖之祖沖之第二個算學(xué)家第二個算學(xué)家1算法的基本思想算法的基本思想(1)一、算法概念的理解一、算法概念的理解1.提出問題提出問題:（1）解二元一次方程組有幾種方法）解二元一次方程組有幾種方法?代入消元法和加減消元法代入消元法和加減消元法.（2）結(jié)合實例總結(jié)用加減消元法解二元一次方程）結(jié)合實例總結(jié)用加減消元法解二元一次方程組的步驟組的步驟.2121xyxy 第一步第一步, +2,得得5x=1. 第二步第二步, 解解, 得得.x51第三步第三步, 2, 得得 5y=. 第四步第四步, 解解, 得得.35y 第五步第五步, 得到方程組的解為得到方程組的解為.yx5351（3）結(jié)合實例總結(jié)用代入消元法解二元一次方）結(jié)合實例總結(jié)用代入消元法解二元一次方程組的步驟程組的步驟.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）根據(jù)上述實例談?wù)勀銓λ惴ǖ睦斫猓└鶕?jù)上述實例談?wù)勀銓λ惴ǖ睦斫?算法的定義算法的定義: 廣義的算法是指完成某項工作的方法和步驟廣義的算法是指完成某項工作的方法和步驟,在數(shù)學(xué)中在數(shù)學(xué)中, 算法通常是指按照一定規(guī)則解決某一類問題的明確算法通常是指按照一定規(guī)則解決某一類問題的明確有限的步驟有限的步驟.（6）總結(jié)算法的特征）總結(jié)算法的特征.確定性確定性: 算法的每一步都應(yīng)當做到準確無誤、算法的每一步都應(yīng)當做到準確無誤、“不重不漏不重不漏”.邏輯性邏輯性:算法從開始的算法從開始的“第一步第一步”直到直到“最后一步最后一步”之間做之間做到環(huán)環(huán)相扣到環(huán)環(huán)相扣, 分工明確分工明確, “前一步前一步”是是“后一步后一步”的前提的前提, “后一后一步步”是是“前一步前一步”的繼續(xù)的繼續(xù).有窮性有窮性:算法要有明確的開始和結(jié)束算法要有明確的開始和結(jié)束, 當?shù)竭_終止步驟時所當?shù)竭_終止步驟時所要解決的問題必須有明確的結(jié)果要解決的問題必須有明確的結(jié)果, 即必須在有限步內(nèi)完成任務(wù)即必須在有限步內(nèi)完成任務(wù), 不能無限制地持續(xù)進行不能無限制地持續(xù)進行.（7）學(xué)習(xí)算法的意義）學(xué)習(xí)算法的意義.在解決某些問題時在解決某些問題時, 需要設(shè)計出一系列可需要設(shè)計出一系列可操作或可計算的步驟來解決問題操作或可計算的步驟來解決問題, 這些步驟稱為解決這些問題這些步驟稱為解決這些問題的算法的算法. 它的優(yōu)點是一種通法它的優(yōu)點是一種通法, 只要按部就班地去做只要按部就班地去做, 總能得到總能得到結(jié)果結(jié)果. 因此算法是計算機科學(xué)的重要基礎(chǔ)因此算法是計算機科學(xué)的重要基礎(chǔ).二、算法案例分析二、算法案例分析例例1.在給定素數(shù)表的前提下在給定素數(shù)表的前提下, 設(shè)計算法設(shè)計算法, 將將936分解成素因素的分解成素因素的乘積乘積.(4000以內(nèi)的素數(shù)表見書以內(nèi)的素數(shù)表見書P161附錄附錄1)分析理解分析理解:1. 查表判斷查表判斷936是否是素數(shù)是否是素數(shù):（1）如果）如果963是素數(shù)是素數(shù), 則分解結(jié)束則分解結(jié)束;（2）如果）如果963不是素數(shù)不是素數(shù), 則進行第則進行第2步步.2. 確定確定936的最小素因素的最小素因素:2.46829363. 查表判斷查表判斷468是否是素數(shù)是否是素數(shù):（1）如果）如果468是素數(shù)是素數(shù), 則分解結(jié)束則分解結(jié)束;（2）如果）如果468不是素數(shù)不是素數(shù), 則重復(fù)上述步驟則重復(fù)上述步驟, 確定確定468的最小素的最小素因素因素.重復(fù)進行上述步驟重復(fù)進行上述步驟, 直到找出直到找出936的所有素因素的所有素因素.二、算法案例分析二、算法案例分析例例1.在給定素數(shù)表的前提下在給定素數(shù)表的前提下, 設(shè)計算法設(shè)計算法, 將將936分解成素因素的分解成素因素的乘積乘積.(4000以內(nèi)的素數(shù)表見書以內(nèi)的素數(shù)表見書P161附錄附錄1)解解算法步驟如下算法步驟如下:1.判斷判斷936是否是素數(shù)是否是素數(shù):否否.2.確定確定936最小素因素最小素因素: 2.46829363.判斷判斷468是否是素數(shù)是否是素數(shù):否否.4.確定確定468最小素因素最小素因素: 2.9362 2 234 5.判斷判斷234是否是素數(shù)是否是素數(shù):否否.6.確定確定234最小素因素最小素因素: 2.9362 2 2 117 7.判斷判斷117是否是素數(shù)是否是素數(shù):否否.8.確定確定117最小素因素最小素因素: 3.9362 2 2 3 39 9.判斷判斷39是否是素數(shù)是否是素數(shù):否否.10.確定確定39最小素因素最小素因素:3.9362 2 2 3 3 13 11.判斷判斷13是否是素數(shù)是否是素數(shù):是是,分解結(jié)束分解結(jié)束.分解結(jié)果是分解結(jié)果是:.9362 2 2 3 3 13 短除法短除法例例2.設(shè)計一個算法設(shè)計一個算法, 求求840與與1764的最大公因數(shù)的最大公因數(shù).解解算法步驟如下算法步驟如下:1.先將先將840進行素因素分解進行素因素分解:;384023 5 7 2.然后將然后將1764進行素因素分解進行素因素分解:;22217642373.確定它們的公共素因素確定它們的公共素因素:, , ;2 3 74.確定公共素因素的指數(shù)確定公共素因素的指數(shù):公共素因素公共素因素2, 3, 7的指數(shù)分別為的指數(shù)分別為2, 1, 1;5.最大公因數(shù)為最大公因數(shù)為.21123784三、課堂練習(xí)三、課堂練習(xí)練習(xí)練習(xí)1.設(shè)計一個算法設(shè)計一個算法, 求求324, 440, 556的最大公因數(shù)的最大公因數(shù).練習(xí)練習(xí)2.設(shè)計一個算法設(shè)計一個算法, 求求1356和和2400的最小公倍數(shù)的最小公倍數(shù).四、課堂小結(jié)四、課堂小結(jié)1.正確掌握算法的步驟正確掌握算法的步驟;2.能夠?qū)懗龀Ｒ妴栴}的算法能夠?qū)懗龀Ｒ妴栴}的算法.