3.2算法及其描述

3.2算法及其描述課堂導(dǎo)入想一想：1、生活中哪些算法.？2、算法（algorithm）是什么？算法的概述算法就是在有限步驟內(nèi)求解某一問題所使用的的一組定義明確的規(guī)則，通俗的講就是用計(jì)算機(jī)解決某一問題的方法，是能被機(jī)械的執(zhí)行的動(dòng)作或指令的有限集合。簡答地說，算法就是解決問題的具體方法和步驟。靈魂發(fā)問：我們可以毫無章法的設(shè)計(jì)算法嗎？算法有沒有屬于他的特征呢？算法的特征：（1）有窮性一個(gè)算法在執(zhí)行有窮步驟之后必須結(jié)束，即一個(gè)算法所包含的步驟是有限的。(2)確定性算法出現(xiàn)的每一個(gè)步驟必須有一個(gè)明確的定義，不能出現(xiàn)模棱兩可的情況。（3）數(shù)據(jù)輸入一個(gè)算法必須有0個(gè)或者多個(gè)輸入，以刻畫運(yùn)算對象的初始情況。（4）數(shù)據(jù)輸出一個(gè)算法必須有1個(gè)或者多個(gè)輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果，沒有輸出的算法是毫無意義的。（5）可行性算法中執(zhí)行的任何計(jì)算步驟都可以被分解為基本的可執(zhí)行的操作步驟，即每個(gè)計(jì)算步驟都可以在有限的時(shí)間內(nèi)完成。思考一下：算法是解題過程的精準(zhǔn)描述，我們可以用哪些方法來描述他？算法描述的方法1、自然語言描述算法用自然語言描述算法，就是用人們?nèi)粘Ｋ玫恼Z言，如漢語、英語等來描述算法。例：找到兩個(gè)數(shù)中較大的數(shù)。自然語言表示的話就是：如果a大于b,那么把a(bǔ)的值賦值給max。古典問題------韓信點(diǎn)兵韓信點(diǎn)兵問題：相傳漢高祖劉邦問大將軍韓信統(tǒng)御士兵多少，韓信回答說，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人、17人一列余8人，劉邦聽后茫然而不知其數(shù)。你能說出有多少士兵嗎？古典故事：韓信是我國西漢初著名的軍事家，劉邦得天下，軍事上全依靠他。韓信點(diǎn)兵，多多益善，不僅如此，還能經(jīng)常以少勝多，以弱勝強(qiáng)。在與楚軍決戰(zhàn)時(shí)韓信指揮諸侯聯(lián)軍，在垓下十面埋伏，擊敗楚軍，楚霸王項(xiàng)羽因此自殺。用自然語言描述算法（解決韓信點(diǎn)兵問題）1.將N的初始值賦為1；2.如果N<700并且N除以3、5、7后余數(shù)都是1則

輸出N,轉(zhuǎn)到第4步；3.將N的值加1，轉(zhuǎn)到第2步；4.結(jié)束程序。2、流程圖描述算法用程序框圖來描述算法的一種表示方法。流程圖的基本圖形及其功能。流程圖描述算法（韓信點(diǎn)兵為例）開始N←1N除以3、5、7后余數(shù)都為1（N<700）N←N+1輸出N值結(jié)束YN偽代碼描述算法用偽代碼描述算法就是用介于自然語言和計(jì)算機(jī)語言之間的文字和符號來描述算法。偽代碼描述（解決韓信點(diǎn)兵問題）ForN←1to700IFN%3==1andN%5==1andN%7==1PrintNElseN←N+1討論交流：算法三種描述方法的優(yōu)勢和不足算法描述的方法優(yōu)

勢不

足自然語言表示法用人們?nèi)粘Ｋ玫恼Z言，比較容易掌握。由于自然語言的歧義性，容易導(dǎo)致算法執(zhí)行的不確定性。流程圖表示法清晰簡潔所占篇幅較大，由于允許使用流程線，過于靈活，不受約束。偽代碼表示法書寫方便，格式緊湊，易于理解，便于向計(jì)算機(jī)程序設(shè)計(jì)語言過渡。偽代碼的語句不規(guī)范，有時(shí)會(huì)產(chǎn)生誤解。三種基本控制結(jié)構(gòu)1、順序結(jié)構(gòu)2、選擇結(jié)構(gòu)3、循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)表示程序中的各個(gè)操作步驟按出現(xiàn)的先后順序執(zhí)行。代碼段1代碼段2選擇結(jié)構(gòu)選擇結(jié)構(gòu)表示程序的處理步驟出現(xiàn)了分支，需要根據(jù)某一特定的條件選擇其中的一個(gè)分支執(zhí)行。條件代碼段1代碼段2True