專題八之算法初步知識(shí)點(diǎn)總結(jié)及分析

專題八之法初步知識(shí)總結(jié)及分析【知識(shí)概一、算的定義對(duì)一類問題的機(jī)械的統(tǒng)一的求解方法稱為算法算法是對(duì)特定問題求解步驟的一種描述.現(xiàn)代意義的“算法”通常是指可以用計(jì)算機(jī)來解決的某一類問題的程序或步驟。二、算的五個(gè)特征●確定性：算法的每一步必須是確切定義的，且無二義性，算法只有唯一的執(zhí)行路徑，對(duì)于相同的輸入只能得出相同的輸出?！裼邢扌裕阂粋€(gè)算法必須在執(zhí)行有限次運(yùn)算后結(jié)束.在所規(guī)定的時(shí)間和空間內(nèi)，若不能獲得正確結(jié)果，其算法也是不能被采用的。●可行性算法中的每一個(gè)步驟必須能用實(shí)現(xiàn)算法的工具——可執(zhí)行指令精確表達(dá)，并在有限步驟內(nèi)完成，否則這種算法也是不會(huì)被采納的?！袼惴ㄒ欢ㄒ鶕?jù)輸入的初始數(shù)據(jù)或給定的初值才能正確執(zhí)行它的每一步驟。●有輸出:算法一定能得到問題的解，有一個(gè)或多個(gè)結(jié)果輸出，達(dá)到求解問題的目的，沒有輸出結(jié)果的算法是沒有意義的。三、算的描述描述算法可以有不同的方式，常用的有自然語言、框圖、偽代碼、程序設(shè)計(jì)語言等?！褡匀徽Z言：自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，如漢語、英語或數(shù)學(xué)語言等使用自然語言描述算法的優(yōu)點(diǎn)是通俗易懂當(dāng)算法中的操作步驟都是順序執(zhí)行時(shí)比較容易理解點(diǎn)是如果算法中包括判斷和轉(zhuǎn)向且操作步驟較多時(shí)，就不那么直觀清晰了?！窨驁D（流程圖順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)三種結(jié)構(gòu)）程序框圖又稱流程圖是一種用規(guī)定的圖形指向線及文字說明來準(zhǔn)確直觀地表示算法的圖形。畫程序框圖的規(guī)則：（1）使用標(biāo)準(zhǔn)的框圖符號(hào)。（2）框圖一般按從上到下、從左到右的方向畫。（3）除判斷框外，大多數(shù)框圖符號(hào)只一個(gè)進(jìn)入點(diǎn)和一個(gè)退出點(diǎn)。判斷框是具有超過一個(gè)退出點(diǎn)的唯一符號(hào)。（4）在圖形符號(hào)內(nèi)描述的語言要非常簡練清楚。壹

（5）流程線必須畫箭頭，因?yàn)樗欠从沉鞒痰膱?zhí)行的先后次序的。順序結(jié)構(gòu)順序結(jié)構(gòu)是由若干個(gè)依次執(zhí)行的處理步驟組成的這是任何一個(gè)算法結(jié)構(gòu)都離不開的最簡單、最基本的結(jié)構(gòu)。其流程圖如圖所示。選擇結(jié)構(gòu)先進(jìn)行判斷判斷的結(jié)果決定后面的步驟這樣的結(jié)構(gòu)稱為選擇結(jié)構(gòu)，或稱為條件分支結(jié)構(gòu)。其流程圖如圖所示。循環(huán)結(jié)構(gòu)：循環(huán)結(jié)構(gòu)（重復(fù)結(jié)構(gòu)）是指按照一定條件，反復(fù)執(zhí)行某一操作的算法結(jié)構(gòu)。在循環(huán)結(jié)構(gòu)中，反復(fù)執(zhí)行的處理步驟稱為循環(huán)體。需要注意的是，循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu)。其流程圖如圖、圖所示。A

N

P

B圖1

A

B圖2AAN

P

P

N圖3

圖4圖3、圖4為循環(huán)結(jié)構(gòu)，只是圖3表示直到型循環(huán)，圖表示當(dāng)型循環(huán)。當(dāng)型循環(huán)（型）和直到型（until型）循環(huán)的區(qū)別是：當(dāng)型循環(huán)是先判斷（條件）再執(zhí)行，而直到型循環(huán)是先執(zhí)行后判斷；當(dāng)型循環(huán)是條件滿足時(shí)執(zhí)行有關(guān)操作直到型循環(huán)是滿足了條件就不再執(zhí)行的有關(guān)操作對(duì)同一個(gè)問題既可以用當(dāng)型循環(huán)來處理，也可以用直到型循環(huán)來處理。偽代碼們在研究算法的時(shí)候以采用與程序設(shè)計(jì)語言類似的形式，我們稱之為偽代碼它有5種語句輸入語句輸出語句賦值語句條件語句、循環(huán)語句。（1）賦值語句：在表述一個(gè)算法時(shí)，經(jīng)常要引入變量，并賦給變量一個(gè)值，用來表明賦給某一個(gè)變量一個(gè)具體的確定值的語句叫做賦值語句。賦值語句用符號(hào)“或xy”等表示。（2）輸入語句：用來實(shí)現(xiàn)算法的輸入信息，本質(zhì)是通過計(jì)算機(jī)的外設(shè)（如鍵盤等）把數(shù)據(jù)送到計(jì)算機(jī)內(nèi)存。輸入語句用符號(hào)“Reada,b等表示。（3輸出句用來輸出算法的結(jié)果本質(zhì)是從計(jì)算機(jī)向外部輸出設(shè)如貳

顯示器、打印機(jī)、磁盤等）輸出數(shù)據(jù)。輸出語句用符號(hào)“Printx”等表示。（4）條件語句：一個(gè)選擇結(jié)構(gòu)，執(zhí)行此算法時(shí)，要根據(jù)條件選擇流程線的方向.我們用條件語句來實(shí)現(xiàn)這一過程.其一般形式是圖5：

NAIfthenBif圖（5）循環(huán)語句：一個(gè)循環(huán)結(jié)構(gòu)，可以用循環(huán)語句來實(shí)現(xiàn)?！?dāng)循環(huán)次數(shù)已定，可用“For”語句.“For”語句的形式為：FIfro值“終值”“步長”Endfor▲當(dāng)循環(huán)次數(shù)不能確定時(shí)，可用“While”語句來實(shí)現(xiàn)循環(huán)While”語句的形式為圖6WhilePA

…P

Endwhile四、算案例

N

圖6●輾轉(zhuǎn)相除法與更相減損術(shù)（）輾轉(zhuǎn)相除法：歐幾里德輾轉(zhuǎn)相除法找到ab最大公約數(shù)的步驟是：計(jì)算出a的余r，若r0，為a,b的最大公約數(shù)；若r0則把前面的除b作為新的被除數(shù)，把余r作為新的除數(shù)，繼續(xù)運(yùn)算，直到余數(shù)為零，此時(shí)的除數(shù)即為自然b的最大公約數(shù)。（2更相減損術(shù)：我們以11985這兩個(gè)數(shù)的最大公約數(shù)加以說明：以兩數(shù)中較大的數(shù)減去較小的數(shù)即

1934

以差數(shù)34和較小