1、第15章 程序設(shè)計(jì)與算法基礎(chǔ),提高篇,15.1 程序設(shè)計(jì)概述,15.2 程序設(shè)計(jì)方法,15.3 算法,15.4 RAPTOR編程基礎(chǔ),當(dāng)今，計(jì)算機(jī)在各個(gè)領(lǐng)域的廣泛應(yīng)用已經(jīng)是眾所周知的事實(shí)了，作為20世紀(jì)最重要的發(fā)明之一，計(jì)算機(jī)對(duì)人類的社會(huì)生活產(chǎn)生的影響越來(lái)越深刻，一方面原因是計(jì)算機(jī)硬件本身越來(lái)越廉價(jià)，更重要的原因是人們?yōu)橛?jì)算機(jī)開(kāi)發(fā)出了大量的、方便的、能指揮計(jì)算機(jī)完成各種簡(jiǎn)單或復(fù)雜工作的程序，正是這些奇妙的程序讓計(jì)算機(jī)越來(lái)越智能化，越來(lái)越具有“生命力”。,15.1 程序設(shè)計(jì)概述,15.1 程序設(shè)計(jì)概述,程序 程序是指完成某項(xiàng)任務(wù)的一系列動(dòng)作執(zhí)行過(guò)程的描述。計(jì)算機(jī)程序是人們?yōu)榻鉀Q某種問(wèn)題用計(jì)算機(jī)可

2、以識(shí)別的語(yǔ)言編排的一系列基本步驟的組合 程序設(shè)計(jì) 程序設(shè)計(jì)又稱編程（Programming）是給出解決特定問(wèn)題程序的過(guò)程，是軟件開(kāi)發(fā)中的重要組成部分。通常，程序設(shè)計(jì)過(guò)程包括四個(gè)主要步驟：分析問(wèn)題、設(shè)計(jì)算法、編寫程序、程序測(cè)試和調(diào)試,15.1 程序設(shè)計(jì)概述,15.1.1 程序與程序設(shè)計(jì),計(jì)算機(jī)語(yǔ)言按照其發(fā)展階段可以分成三大類 低級(jí)語(yǔ)言 機(jī)器語(yǔ)言是指一臺(tái)計(jì)算機(jī)全部的指令集合，指令是由“0”和“1”組成的二進(jìn)制，難記憶、易出錯(cuò) 匯編語(yǔ)言 用一些簡(jiǎn)潔的英文字母、符號(hào)串來(lái)替代一個(gè)特定的指令的二進(jìn)制串 高級(jí)語(yǔ)言 高級(jí)語(yǔ)言是比匯編語(yǔ)言更易于使用的一類語(yǔ)言 目前，高級(jí)語(yǔ)言主要包括有：BASIC、C、C+、PA

3、SCAL、FORTRAN、智能化語(yǔ)言（LISP、Prolog、CLIPS、OpenCyc、Fazzy）、動(dòng)態(tài)語(yǔ)言(Python、PHP、Ruby、Lua)等等,15.1 程序設(shè)計(jì)概述,15.1.2 程序設(shè)計(jì)語(yǔ)言,程序編寫，是軟件開(kāi)發(fā)工程中的一個(gè)關(guān)鍵階段。軟件的質(zhì)量主要通過(guò)程序的質(zhì)量來(lái)體現(xiàn)的，因此，程序設(shè)計(jì)在軟件開(kāi)發(fā)過(guò)程中占有十分重要的地位。為了有效進(jìn)行程序設(shè)計(jì)，除了精心設(shè)計(jì)算法與數(shù)據(jù)結(jié)構(gòu)外，程序設(shè)計(jì)方法也很重要。目前，最常用的是結(jié)構(gòu)化程序設(shè)計(jì)方法和面向?qū)ο蟮某绦蛟O(shè)計(jì)方法。,15.2 程序設(shè)計(jì)方法,15.2 程序設(shè)計(jì)方法,基本思想 結(jié)構(gòu)化程序設(shè)計(jì)的核心思想是：以模塊化設(shè)計(jì)為中心，將待解決的問(wèn)題劃

4、分為若干個(gè)相互獨(dú)立的模塊，采用自頂向下、逐步求精的方法設(shè)計(jì)程序 設(shè)計(jì)原則 自頂向下 逐步細(xì)化 模塊化設(shè)計(jì) 限制使用GOTO語(yǔ)句,15.2 程序設(shè)計(jì)方法,15.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法,三種基本結(jié)構(gòu) 順序結(jié)構(gòu) 各個(gè)操作步驟都是按照它們出現(xiàn)的先后順序依次執(zhí)行的 分支結(jié)構(gòu) 各個(gè)操作步驟都是按照它們出現(xiàn)的先后順序依次執(zhí)行的 循環(huán)結(jié)構(gòu) 各個(gè)操作步驟都是按照它們出現(xiàn)的先后順序依次執(zhí)行的,15.2 程序設(shè)計(jì)方法,15.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法,產(chǎn)生背景 基本概念 面向?qū)ο蟪绦蛟O(shè)計(jì) 是一種建立在“對(duì)象”概念基礎(chǔ)上的方法學(xué)，把面向?qū)ο蟮乃枷霊?yīng)用于軟件開(kāi)發(fā)過(guò)程中，指導(dǎo)開(kāi)發(fā)活動(dòng)的系統(tǒng)方法 對(duì)象 是要研究的任何事

5、物。它不僅能表示有形的實(shí)體，也能表示無(wú)形的（抽象的）規(guī)則、計(jì)劃或事件。對(duì)象由數(shù)據(jù)（事物的屬性）和方法（事物的行為）構(gòu)成一個(gè)相對(duì)獨(dú)立的整體,15.2 程序設(shè)計(jì)方法,15.2.2 面向?qū)ο蟪绦蛟O(shè)計(jì)方法,類 是對(duì)具有相同屬性和相同行為的具體對(duì)象進(jìn)行抽象得到的模板。一個(gè)類所包含的行為和數(shù)據(jù)描述一組對(duì)象的共同屬性和行為。類是對(duì)象的抽象，對(duì)象則是類的實(shí)例。類可有其子類，也可有其它類，形成類層次結(jié)構(gòu) 消息 是對(duì)象之間進(jìn)行通信的一種規(guī)則說(shuō)明。對(duì)象之間可以通過(guò)消息機(jī)制進(jìn)行通信，消息一般由三個(gè)要素：接收消息的對(duì)象名、消息名（接收對(duì)象的方法名稱）和參數(shù)（方法所需的數(shù)據(jù)信息）,15.2 程序設(shè)計(jì)方法,15.2.2 面

6、向?qū)ο蟪绦蛟O(shè)計(jì)方法,計(jì)算機(jī)的發(fā)展靠?jī)蓚€(gè)方面，一個(gè)是硬件，一個(gè)是軟件，但二者的發(fā)展速度很不協(xié)調(diào)。計(jì)算機(jī)誕生后的60多年里，硬件速度已提高了約10億倍，成本也降低了約10億倍，但軟件的發(fā)展卻相對(duì)遲緩，其重要原因就是對(duì)算法的研究不足。算法是計(jì)算學(xué)科中最具方法論性質(zhì)的核心概念，也被譽(yù)為計(jì)算學(xué)科的靈魂。程序最核心的兩個(gè)方面：(1)對(duì)數(shù)據(jù)的描述，包括要使用數(shù)據(jù)的類型和組織方式，即數(shù)據(jù)結(jié)構(gòu)。(2)對(duì)操作的描述，即操作步驟，也就是算法。瑞士著名計(jì)算機(jī)科學(xué)家沃思在1976年曾提出 一個(gè)公式：程序=數(shù)據(jù)結(jié)構(gòu)+算法。其中，算法是程序的靈魂。,15.3 算法,15.3 算法,什么是算法 我們把解決問(wèn)題的若干步驟的有序

7、描述稱為算法。 算法的特征 確定性 有限性 可行性 有零個(gè)或多個(gè)輸入 有一個(gè)或多個(gè)輸出 健壯性 可讀性 經(jīng)濟(jì)性,15.3 算法,15.3.1 算法的概念,用自然語(yǔ)言描述算法 自然語(yǔ)言是人們?nèi)粘Ｋ玫恼Z(yǔ)言，可以使?jié)h語(yǔ)，英語(yǔ)貨其他國(guó)家的語(yǔ)言。使用該方法不用專門訓(xùn)練，通俗易懂。但語(yǔ)句冗長(zhǎng)，不夠簡(jiǎn)潔，容易出現(xiàn)歧義性，導(dǎo)致算法的不確定性。 用偽代碼描述算法 偽代碼是用介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的用文字和符號(hào)來(lái)描述算法的工具?？梢杂酶鞣N符號(hào)和漢字的混合法來(lái)描述算法的基本步驟，使用靈活，書寫方便，格式緊湊，同時(shí)也便于將算法轉(zhuǎn)成相應(yīng)的程序代碼實(shí)現(xiàn)。但不容易規(guī)范，有時(shí)候會(huì)產(chǎn)生理解上的不一致 用流程圖描述算法

8、 流程圖是描述算法的常用工具，它采用美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(American National Standard Institute)規(guī)定的一組圖形符號(hào)來(lái)表示算法。它是一種用程序框、流程線及文字說(shuō)明來(lái)準(zhǔn)確、直觀地表示算法的圖形工具,15.3 算法,15.3.2 算法的表示,排序算法 將一組無(wú)序的數(shù)據(jù)（或依記錄的關(guān)鍵字）按遞增或遞減的順序排列起來(lái) 和選擇排序 查找算法 在計(jì)算機(jī)許多應(yīng)用領(lǐng)域中，查找操作都是十分重要的一項(xiàng)研究技術(shù)。查找算法效率的好壞直接影響應(yīng)用軟件的性能 順序查找、折半查找 窮舉搜索算法 通常在找不到解決問(wèn)題的規(guī)律時(shí)對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從中找出

9、那些符合要求的候選解作為問(wèn)題的解 遞推算法 即通過(guò)已知條件，利用特定關(guān)系得出中間推論，直至得到結(jié)果的算法 順推、逆推,15.3 算法,15.3.3 典型算法,初學(xué)者在學(xué)習(xí)程序設(shè)計(jì)時(shí)，要先熟練掌握某種高級(jí)編程語(yǔ)言，但高級(jí)語(yǔ)言的語(yǔ)法規(guī)則比較瑣碎和復(fù)雜，初學(xué)者常常會(huì)在語(yǔ)言語(yǔ)法的使用上面臨很多困難，以至于影響到對(duì)程序設(shè)計(jì)思路的學(xué)習(xí)和掌握。 RAPTOR（The Rapid Algorithmic Prototyping Tool for Ordered Reasoning）簡(jiǎn)稱為快速算法模型工具，專門用于解決非可視化的環(huán)境的句法困難和缺點(diǎn)，可以在最大限度地減少語(yǔ)法要求的情形下，幫助學(xué)生編寫出正確的程序

10、。,15.4 RAPTOR編程基礎(chǔ),15.4 RAPTOR編程基礎(chǔ),RAPTOR是一種可視化的程序設(shè)計(jì)環(huán)境，它允許使用連接基本流程圖符號(hào)來(lái)創(chuàng)建算法，然后可以在其環(huán)境下直接調(diào)試和運(yùn)行算法，包括單步執(zhí)行或連續(xù)執(zhí)行的模式，該環(huán)境可以直觀地顯示當(dāng)前執(zhí)行符號(hào)所在的位置，以及所有變量的內(nèi)容，調(diào)試程序非常方便 基本符號(hào) 數(shù)據(jù)及其類型 運(yùn)算符及其表達(dá)式,15.4 RAPTOR編程基礎(chǔ),15.4.1 RAPTOR編程環(huán)境,RAPTOR中的語(yǔ)句包括三大類 基本語(yǔ)句 輸入語(yǔ)句、賦值語(yǔ)句、輸出語(yǔ)句 選擇控制語(yǔ)句 根據(jù)某個(gè)條件，有選擇地執(zhí)行相關(guān)步驟，這時(shí)就要使用選擇控制語(yǔ)句 循環(huán)控制語(yǔ)句 循環(huán)控制語(yǔ)句允許根據(jù)循環(huán)的條件，重復(fù)執(zhí)行某些指令。在循環(huán)控制語(yǔ)句中，有個(gè)控制循環(huán)是否繼續(xù)的條件，稱為循環(huán)條件，重復(fù)執(zhí)行的一系列操作，稱為循環(huán)體 當(dāng)循環(huán)條件的值為真時(shí)，重復(fù)執(zhí)行循環(huán)體，當(dāng)循環(huán)條件為假時(shí)，結(jié)束整個(gè)循環(huán) 循環(huán)條件的描述與選擇條件的描述類似，即：使用關(guān)系表達(dá)式或邏輯表達(dá)式進(jìn)行描述,15.