算法與數(shù)據(jù)結(jié)構(gòu)第1章算法與程序ppt(已修改)
2024-11-15 15:48 本頁(yè)面
【正文】 算法與數(shù)據(jù)結(jié)構(gòu) 第 1章 算法與程序 第 2章 常用數(shù)據(jù)結(jié)構(gòu) 第 3章 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu) 第 4章 樹(shù)和二叉樹(shù) 第 5章 圖與網(wǎng) 第 6章 數(shù)據(jù)結(jié)構(gòu)的程序?qū)崿F(xiàn) 第 7章 檢索及基本算法 第 8章 排序及基本算法 算法與數(shù)據(jù)結(jié)構(gòu) 第 1章 算法與程序 第 1章 算法與程序 算法的基本概念 算法的表示 算法的設(shè)計(jì)與評(píng)價(jià) 算法與程序 算法的基本概念 什么是算法 算法的基本特性 什么是算法 早在公元前 300年左右出現(xiàn)的著名的歐幾里德算法 ，就描述了求解兩個(gè)整數(shù)的最大公因子的解題步驟 。要求解的問(wèn)題描述為： “ 給定兩個(gè)正整數(shù) m和 n， 求它們的最大公因子 ， 即能同時(shí)整除 m和 n的最大整數(shù) ” 。 歐幾里德當(dāng)時(shí)給出的算法如下： ⑴ 以 n除 m， 并令所得余數(shù)為 r（ 必有 rn） ； ⑵ 若 r=0， 輸出結(jié)果 n， 算法結(jié)束；否則繼續(xù)步驟 ⑶ ； ⑶ 令 m=n和 n=r， 返回步驟 ⑴ 繼續(xù)進(jìn)行 。 什么是算法（續(xù)） 由此 ， 我們可以得出這樣的結(jié)論 ， 算法 就是求解問(wèn)題的 方法和步驟 。 這里的方法和步驟是一組嚴(yán)格定義了運(yùn)算順序的規(guī)則；每一個(gè)規(guī)則都是有效的 ， 且是明確的；按此順序?qū)⒃谟邢薮螖?shù)下終止 。 有關(guān)算法 （ Algorithm） 一詞的定義不少 ， 但其內(nèi)涵基本上是一致的 。 最為著名的定義是計(jì)算機(jī)科學(xué)家 《 計(jì)算機(jī)程序的藝術(shù) 》 （ Art of Computer Program） 第一卷中所做的有關(guān)描述 。 其非形式化的定義 是： 一個(gè)算法 ， 就是一個(gè)有窮規(guī)則的集合 ， 其中之規(guī)則定義了一個(gè)解決某一特定類型問(wèn)題的運(yùn)算序列 。 什么是算法（續(xù)） 算法的 形式化定義 如下所述： 算法是一個(gè)四元組 ， 即 （ Q， I， Ω， F） 。 其中： ? Q是一個(gè)包含子集 I和 Ω的集合 ， 它表示計(jì)算的狀態(tài)； ? I表示計(jì)算的輸入集合； ? Ω表示計(jì)算的輸出集合； ? F表示計(jì)算的規(guī)則 ， 它是由 Q至它自身的函數(shù) ， 且具有自反性 ， 即對(duì)任何一個(gè)元素 q∈ Q， 有 F(q)=q。 什么是算法（續(xù)） ?一個(gè)算法是對(duì)于任何的輸入元素 x， 都在有窮步驟內(nèi)終止的一個(gè)計(jì)算方法 。 ?在算法的形式化定義中 ， 對(duì)任何一個(gè)元素 x∈ I， x均滿足性質(zhì) x0=x， xk+1=F(xk)， （ k≥ 0） 該性質(zhì)表示任何一個(gè)輸入元素 x均為一個(gè)計(jì)算序列 ，即 x0， x1， x2， … ， xk；該序列在第 k步結(jié)束計(jì)算 。 算法的基本概念 什么是算法 算法的基本特性 算法的基本特性 ?輸入 （ Input） ?輸出 （ Output） ?確定性 （ Definiteness） ?有窮性 （ Finiteness） ?有效性 （ Effectiveness） 第 1章 算法與程序 算法的基本概念 算法的表示 算法的設(shè)計(jì)與評(píng)價(jià) 算法與程序 算法的表示 自然語(yǔ)言表示 流程圖表示 N—S圖表示 偽代碼表示 程序語(yǔ)言表示 自然語(yǔ)言表示 自然語(yǔ)言即人們?nèi)粘Ｊ褂玫恼Z(yǔ)言 ， 如漢語(yǔ) 、 英語(yǔ) 、日語(yǔ) 、 法語(yǔ) 、 德語(yǔ)等等 。 使用自然語(yǔ)言描述算法 ，人們比較容易接受和理解 。 如前面的歐幾里德算法就是用自然語(yǔ)言描述的 。 然而 ， 自然語(yǔ)言也具有許多缺點(diǎn) ， 在使用自然語(yǔ)言描述算法時(shí)一定要引起注意： ?自然語(yǔ)言存在著歧義性 ， 容易導(dǎo)致算法的不確定性； ?自然語(yǔ)言容易冗長(zhǎng) ， 使得描述不夠簡(jiǎn)潔； ?自然語(yǔ)言的表示形式是順序的 ， 描述分支選擇和轉(zhuǎn)移時(shí)不夠直觀； ?自然語(yǔ)言與計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的差別較大 ， 不易轉(zhuǎn)換為程序 。 算法的表示 自然語(yǔ)言表示 流程圖表示 N—S圖表示 偽代碼表示 程序語(yǔ)言表示 流程圖表示 流程圖是描述算法的圖形工具 ， 它采用如下所示的一組圖形符號(hào)來(lái)表示算法： 起止框，表示算法的開(kāi)始或結(jié)束；只有一個(gè)入口或一個(gè)出口。 輸入輸出框，表示算法中數(shù)據(jù)信息的輸入和輸出；有一個(gè)入口和一個(gè)出口。 判斷框，表示條件判斷；有一個(gè)入口和多個(gè)出口。 處理框，表示算法中的一個(gè)（或一組）運(yùn)算或處理；有一個(gè)入口和一個(gè)出口。 流程線，表示算法中各步驟之間的次序關(guān)系。 連接點(diǎn)，表示算法中的連接位置，主要用于同一算法在不同頁(yè)描述時(shí)的接續(xù)等情況。 注釋框，用于對(duì)算法中某些操作的注釋說(shuō)明。 流程圖表示舉例 歐幾里德算法的流程圖描述如圖 11所示 圖 11 歐幾里德算法的流程圖表示 no yes m mod n→r end 讀入 m,n r=0 begin N→m, r→n 輸出 n m,n為正整數(shù) ， 算法求其最大公因子 流程圖表示（續(xù)） 同自然語(yǔ)言相比 ， 用流程圖描述算法直觀 ， 可以一目了然；算法步驟間用流程線連接 ， 次序關(guān)系清楚 ， 容易理解；可以很方便地表示順序 、 選擇和循環(huán)結(jié)構(gòu) ， 不依賴于任何計(jì)算機(jī)和計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言 ， 有利于不同環(huán)境下的程序設(shè)計(jì) 。 但是 ， 流程圖也還存在一些缺點(diǎn) ， 諸如： ?不易于表示算法的層次結(jié)構(gòu)； ?不易于表示數(shù)據(jù)結(jié)構(gòu)和模塊調(diào)用關(guān)系等重要信息； ?容易使人過(guò)早地考慮算法的控制流程 ， 而忽視算法的全局結(jié)構(gòu)； ?用流程線代表控制流 ， 控制轉(zhuǎn)移隨意性較大 。 若對(duì)流程線的使用不加限制 ， 隨著求解問(wèn)題規(guī)模和復(fù)雜度的增加 ， 流程圖會(huì)變得很復(fù)雜 ， 使人難以閱讀 、 理解和修改 ， 從而使算法的可靠性難以保證 。 算法的表示 自然語(yǔ)言表示 流程圖表示 N—S圖表示 偽代碼表示 程序語(yǔ)言表示 N—S圖表示 為了克服傳統(tǒng)流程圖的缺點(diǎn) ， 1973年美國(guó)學(xué)者納斯（ ） 和施內(nèi)德曼 （ ） 提出了一種表示算法的較好工具 ——NS圖 。 ?它獨(dú)立于任何計(jì)算機(jī)和計(jì)算機(jī)語(yǔ)言 ， 又能很方便地轉(zhuǎn)換為計(jì)算機(jī)語(yǔ)言程序； ?它去掉了流程線全部用矩形方框來(lái)描述 ， 限制了算法流程轉(zhuǎn)移控制的隨意性 ， 又節(jié)省了篇幅； ?它很容易表示算法中的嵌套關(guān)系和模塊中的層次關(guān)系 ，功能域可以從框圖中直接反映出來(lái)； ?它仍是圖形工具 ， 閱讀起來(lái)直觀 、 明確 、 容易理解 。 N—S圖表示（續(xù)） NS圖的基本圖形符號(hào)如下： A B T F P A B 當(dāng) P A A 直到 P 順序結(jié)構(gòu)，由兩個(gè)或多個(gè)矩形框組成。其中 A和 B可以是基本操作，也可以是其它基本結(jié)構(gòu)（如選擇結(jié)構(gòu)，循環(huán)結(jié)構(gòu)）。 選擇結(jié)構(gòu)，當(dāng)條件 P成立時(shí)執(zhí)行操作 A，否則執(zhí)行操作 B。 當(dāng)型循環(huán)結(jié)構(gòu)。當(dāng)條件 P成立時(shí)反復(fù)執(zhí)行操作 A，直到條件 P不成立時(shí)止。 直到型循環(huán)結(jié)構(gòu)。反復(fù)執(zhí)行操作 A，直到條件 P成立時(shí)止。 N—S圖表示舉例 由于 NS圖象一個(gè)多層的盒子 ， 所以也稱作盒圖 。用 NS圖表示歐幾里德算法如圖 12所示 。 讀入正整數(shù) m,n 讀入正整數(shù) m,n m mod n→r m→r 當(dāng) r≠ 0反復(fù)做 n→m, r→n n→m, r→n m mod n→r m mod n→r 直到 r=0時(shí)止 輸出最大公因子 n 輸出最大公因子 n (a)當(dāng)型循環(huán)結(jié)構(gòu)實(shí)現(xiàn) (b)直到型循環(huán)結(jié)構(gòu)實(shí)現(xiàn) 圖 12 歐幾里德算法的 NS圖表示 算法的表示 自然語(yǔ)言表示 流程圖表示 N—S圖表示 偽代碼表示 程序語(yǔ)言表示 偽代碼表示 ?偽代碼是介乎于自然語(yǔ)言和計(jì)算機(jī)程序語(yǔ)言之間的一種表示算法的工具 。 ? 它用文字和符號(hào)描述問(wèn)題的求解方法和步驟而不使用圖形符號(hào) 。 ? 如同一篇文章自上而
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1