計(jì)算機(jī)學(xué)習(xí)課件

第六章算法與程序設(shè)計(jì)基礎(chǔ)大學(xué)計(jì)算機(jī)基礎(chǔ)第六章算法與程序設(shè)計(jì)基礎(chǔ)主要內(nèi)容

6.1程序設(shè)計(jì)概述

6.2算法基礎(chǔ)

6.3數(shù)據(jù)的組織結(jié)構(gòu)6.4問題求解與程序設(shè)計(jì)方法6.5Raptor可視化工具

1.什么是程序程序（program）是指按照一定的順序安排工作的操作序列，即完成某些工作的具體步驟。6.1.1程序設(shè)計(jì)的概念6.1程序設(shè)計(jì)概述計(jì)算機(jī)程序是計(jì)算機(jī)為完成某一任務(wù)所必須執(zhí)行的一系列指令的有序集合，是用計(jì)算機(jī)語言對所要解決問題進(jìn)行完整而準(zhǔn)確的描述。程序表達(dá)了人的思想，體現(xiàn)了程序員要求計(jì)算機(jī)執(zhí)行的操作，也是程序設(shè)計(jì)的最終結(jié)果。程序設(shè)計(jì)＝算法＋數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)應(yīng)該包括兩個(gè)方面的內(nèi)容:算法：為解決某個(gè)問題而采取的方法和步驟的描述。數(shù)據(jù)結(jié)構(gòu)：對程序中數(shù)據(jù)的描述。程序設(shè)計(jì)的一般過程:分析問題建立數(shù)據(jù)模型確定數(shù)據(jù)結(jié)構(gòu)和算法編寫程序運(yùn)行和調(diào)試程序目的性

程序有明確的編寫目的，運(yùn)行時(shí)完成賦予它的功能。分步性

程序由一系列計(jì)算機(jī)可執(zhí)行的步驟組成，執(zhí)行這些步驟可以完成其復(fù)雜的功能。有序性

程序的執(zhí)行步驟是有序的，必須嚴(yán)格按其執(zhí)行順序執(zhí)行，不可隨意改變。有限性

程序是有限的指令序列，所包含的步驟是有限的。操作性

有意義的程序能對某些對象進(jìn)行操作，使其改變狀態(tài)，完成其功能。2.程序的特性

3.程序設(shè)計(jì)語言的構(gòu)成（1）變量、運(yùn)算符、表達(dá)式變量：程序中定義的、存儲(chǔ)參與運(yùn)算的數(shù)據(jù)和中間結(jié)果的單元運(yùn)算符：程序中規(guī)定的進(jìn)行各種運(yùn)算的描述符號。如+、-、*、/、<=、==表達(dá)式：程序中由常量、變量、函數(shù)和運(yùn)算符組成的式子。如c=2*3.14*r（2）數(shù)據(jù)類型基本數(shù)據(jù)類型：如整型、實(shí)型、字符型等。復(fù)合數(shù)據(jù)類型：由基本類型組成，如數(shù)組、結(jié)構(gòu)體、文件等。(3)程序的控制結(jié)構(gòu)順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)賦值遷移數(shù)據(jù)數(shù)據(jù)是從一個(gè)變量被復(fù)制到另一個(gè)變量，原來變量仍保存那個(gè)數(shù)據(jù)如果目的變量已經(jīng)保存了數(shù)據(jù)，則遷移過來的數(shù)據(jù)將會(huì)覆蓋舊的數(shù)據(jù)。7關(guān)于數(shù)據(jù)的操作賦值如何將A、B變量的數(shù)據(jù)互換？（用“x=y”表示將變量y的數(shù)據(jù)賦值給變量x）完成移動(dòng)后，T保存什么數(shù)據(jù)？T=AA=BB=T84.程序的三種基本結(jié)構(gòu)（1）順序結(jié)構(gòu)

程序按照語句的書寫次序順序執(zhí)行。

BA

先執(zhí)行A操作，再執(zhí)行B操作，兩者是順序執(zhí)行關(guān)系。如：r=15;s=3.1415*r*r;prints;

（2）選擇結(jié)構(gòu)通過判斷特定條件，選擇一個(gè)分支執(zhí)行。當(dāng)P條件成立時(shí)，執(zhí)行A操作，否則執(zhí)行B操作APB成立不成立

語句不成立

P成立當(dāng)P條件成立時(shí)，執(zhí)行語句操作，否則跳過語句操作如：if(a>10)x=a;printx;

如：if(a>b)x=a;elsex=b;printx;

（3）循環(huán)結(jié)構(gòu)在給定條件下，反復(fù)執(zhí)行循環(huán)體，直到條件不滿足為止。如，重復(fù)做某事，小學(xué)生抄寫單詞。1)當(dāng)型循環(huán)結(jié)構(gòu)不成立PA成立當(dāng)P條件成立時(shí)，反復(fù)執(zhí)行A,直到P不成立為止。如：while(i<=10){s=s+i;i++;}2)直到型循環(huán)結(jié)構(gòu)先執(zhí)行A操作，再判斷P是否成立，若P成立，再執(zhí)行A，直到P不成立為止。AP成立不成立

5.程序設(shè)計(jì)語言程序設(shè)計(jì)語言分類:機(jī)器語言匯編語言高級語言面向過程的語言：Basic、C語言、FORTRAN、Pascal面向?qū)ο蟮恼Z言：VB、C++、Java、Delphi、Python語言處理程序高級語言的翻譯程序有兩種工作方式：一種是解釋方式，另一種是編譯方式。（1）解釋方式解釋方式的翻譯工作由解釋程序來完成。在這種方式下，解釋程序?qū)υ闯绦蛑饤l地進(jìn)行分析，若沒有發(fā)現(xiàn)錯(cuò)誤，則將該語句翻譯成一個(gè)或多個(gè)機(jī)器指令，然后立即執(zhí)行這些指令；當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)，會(huì)立即停止并給出錯(cuò)誤提示。解釋方式邊解釋邊執(zhí)行，不產(chǎn)生目標(biāo)程序。其工作過程如圖所示。計(jì)算結(jié)果解釋程序高級語言源程序

（2）編譯方式編譯方式的翻譯工作由編譯程序完成。編譯程序?qū)υ闯绦蜻M(jìn)行編譯處理，產(chǎn)生一個(gè)與源程序等價(jià)的目標(biāo)程序。

目標(biāo)程序不能直接運(yùn)行，需要使用連接程序?qū)⒛繕?biāo)程序與程序中用到一些庫函數(shù)或調(diào)用其他程序段組裝在一起，才能夠形成一個(gè)完整的可執(zhí)行程序。

產(chǎn)生的可執(zhí)行程序可以脫離編譯程序和源程序獨(dú)立存在，并可以反復(fù)運(yùn)行。

編譯方式執(zhí)行速度快，但修改源程序后必須重新編譯。大多數(shù)高級語言都采用編譯方式。高級語言源程序編譯程序機(jī)器語言目標(biāo)程序目標(biāo)程序+運(yùn)行子程序運(yùn)行結(jié)果數(shù)據(jù)

編譯階段

執(zhí)行階段

生成機(jī)器語言目標(biāo)程序的編譯方式（2）編譯方式編譯方式的工作過程示意圖：

1.算法的定義算法(algorithm)是對特定問題求解步驟的一種描述，是一組如何做某件事情的指令，是一組有序的動(dòng)作。算法是處理解決問題的思路及辦法，是程序的靈魂。6.2.1算法的概念與特征6.2算法基礎(chǔ)算法無處不在小學(xué)生作業(yè)DIY家具的組裝說明洗衣機(jī)使用說明飛機(jī)安全出口上的說明問路算法的分類

在計(jì)算機(jī)領(lǐng)域中，將解決不同性質(zhì)問題的算法劃分成為不同的類型。數(shù)值算法：主要解決一些工程上的數(shù)值計(jì)算問題，其特點(diǎn)是運(yùn)算復(fù)雜且有少量的輸入、輸出。例如數(shù)值積分、數(shù)值求解微分方程等。非數(shù)值算法：用于對大量數(shù)據(jù)的處理，其特點(diǎn)是運(yùn)算簡單且有大量的輸入、輸出。例如對圖書檢索、工資管理等。2.算法的基本特征算法是一個(gè)有窮規(guī)則的集合，它產(chǎn)生結(jié)果并在有限的時(shí)間內(nèi)終止。這些規(guī)則確定了解決某類問題的一個(gè)運(yùn)算序列。算法的基本特征：有窮性：算法必須在執(zhí)行有限個(gè)操作后終止；

確定性：算法中每一步的含義必須是確切的，不能出現(xiàn)任何二義性；有效性：算法中的每一步操作都應(yīng)該能有效執(zhí)行，一個(gè)不可執(zhí)行的操作是無效的；有零個(gè)或多個(gè)輸入：執(zhí)行算法時(shí)，從外界獲得必要的信息；有一個(gè)或多個(gè)輸出：算法的結(jié)果就是輸出，可以是返回的數(shù)值，或某些操作（例如打印輸出）。算法的評價(jià)標(biāo)準(zhǔn)正確性(Correctness)-程序中不含語法錯(cuò)誤；

-程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)都能夠得出滿足要求的結(jié)果?？勺x性(Readability)-算法應(yīng)該易于人的理解-晦澀難讀的算法易于隱藏較多錯(cuò)誤而難以調(diào)試。健壯性(Robustness)-當(dāng)輸入數(shù)據(jù)非法時(shí)，算法恰當(dāng)?shù)淖龀龇磻?yīng)或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名其妙的輸出結(jié)果。

-處理出錯(cuò)的方法，不是中斷程序，而是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便進(jìn)行處理。高效率和低存儲(chǔ)量-對于相同規(guī)模的問題，執(zhí)行時(shí)間短、占用空間少。6.2.2算法的性能評價(jià)1.時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是指算法所需的時(shí)間隨著問題規(guī)模n變大而增加的程度，同一問題可用不同算法解決，各種算法中，語句執(zhí)行次數(shù)越多，則該算法耗費(fèi)的時(shí)間越長。一個(gè)算法中語句執(zhí)行的次數(shù)，也稱作語句頻度或時(shí)間頻度，記為T(n)。算法的基本操作重復(fù)執(zhí)行的次數(shù)一般是問題規(guī)模n的一個(gè)函數(shù)f(n)，f(n)是和T(n)同數(shù)量級（同階）的函數(shù)。算法的時(shí)間復(fù)雜度記做：T(n)=O(f(n))隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，f(n)越小，算法的時(shí)間復(fù)雜度越低，效率越高。該方法可獨(dú)立于機(jī)器的軟件、硬件系統(tǒng)來分析算法在效率方面的優(yōu)劣。T(n)的同數(shù)量級（從小到大）：1，Log2n，n，nLog2n，n2，n3，2n，n！算法的性能評價(jià)T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n)例x=0;y=0;for(k=0;k<2*n;k++)x++;for(i=0;i<n;i++)for(j=0;j<n;j++)y++;頻度最大語句重復(fù)執(zhí)行次數(shù)的階數(shù)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)例

：兩個(gè)n×n階矩陣相乘

for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];基本語句，執(zhí)行次數(shù)是n3}算法的基本操作應(yīng)選擇重復(fù)執(zhí)行次數(shù)最多的基本語句，一般情況下是最深層循環(huán)內(nèi)的基本語句。

T(n)=O

(n3)

即算法的執(zhí)行時(shí)間與問題規(guī)模n的三次方同階。一般情況下，隨n的增大，T(n)的增長較慢（執(zhí)行次數(shù)最少）的算法為最優(yōu)算法。2.空間復(fù)雜度

S(n)=O(f(n))算法的空間復(fù)雜度是指算法執(zhí)行時(shí)存儲(chǔ)空間需求的度量。通常算法的空間復(fù)雜度是指算法中所需的輔助空間單元，并不包括原始輸入數(shù)據(jù)所占的單元，因?yàn)樗鼈冎慌c問題本身有關(guān)，而與算法無關(guān)。以n×n階矩陣相乘為例，輔助空間為變量i,j,k，因?yàn)樗鼈兣c問題的規(guī)模n無關(guān)，所以上述算法的空間復(fù)雜度S(n)=O(1)。其中n為問題的規(guī)模，S(n)表示空間復(fù)雜度。算法的時(shí)間的耗費(fèi)和所占存儲(chǔ)空間的耗費(fèi)是矛盾的，難以兼得。一般情況，常常以算法的執(zhí)行時(shí)間作為算法優(yōu)劣的主要衡量指標(biāo)。6.2.3算法的描述方法可以用不同的方法表示算法，常用方法有：自然語言專用工具計(jì)算機(jī)語言

（1）自然語言自然語言即是使用漢語、英語或其他語言去描述算法。[例]有50名學(xué)生的成績，要求將他們之中80分以上的成績打印出來。設(shè)用g代表學(xué)生成績，gi代表第i個(gè)學(xué)生成績。算法可以表示如下：1）使i=1

；2）如果gi80，則打印gi，否則不打印；3）使i的值加1；4）如果i50,返回步驟2，繼續(xù)執(zhí)行；否則，算法結(jié)束。特點(diǎn)：描述算法通俗易懂，但容易產(chǎn)生歧義。對復(fù)雜問題，語句繁瑣、冗長，并且很難清楚地表達(dá)算法的邏輯流程，往往需要根據(jù)上下文判別其含義，尤其對描述含有選擇、循環(huán)結(jié)構(gòu)的算法，不太方便和直觀，一般不常使用。(2)專用工具1）流程圖

美國國家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號起止框判斷框處理框輸入/輸出框注釋框流向線連接點(diǎn)程序流程圖表示:打印80分以上的學(xué)生成績開始1

igi>=80輸出gii+1

ii>50結(jié)束成立不成立不成立成立傳統(tǒng)流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴(yán)格限制。2）N–S流程圖N—S流程圖由美國學(xué)者I.Nassi和B.Shneiderman提出表示算法的圖形工具?；締卧蔷匦慰?用不同的形狀線分割,表示三種結(jié)構(gòu)。只有一個(gè)入口,一個(gè)出口,沒有流程線。N--S圖的優(yōu)點(diǎn)比文字描述直觀、形象、易于理解；比傳統(tǒng)流程圖緊湊易畫。尤其是它廢除了流程線，整個(gè)算法結(jié)構(gòu)是由各個(gè)基本結(jié)構(gòu)按順序組成的，N--S流程圖中的上下順序就是執(zhí)行時(shí)的順序。三種基本程序結(jié)構(gòu)的N–S流程圖條件TF語句1語句2選擇結(jié)構(gòu)語句1語句2順序結(jié)構(gòu)循環(huán)結(jié)構(gòu)循環(huán)體循環(huán)體當(dāng)條件成立時(shí)直到條件成立循環(huán)結(jié)構(gòu)一循環(huán)結(jié)構(gòu)二0t,1ii+1i

t+it直到i>100輸出t的值傳統(tǒng)流程圖與N-S流程圖的比較i>100

NY開始

0t,1ii+1i

t+it輸出t的值結(jié)束例1：1+2+3+……+加到100為止3）偽代碼偽代碼是介于自然語言和計(jì)算機(jī)語言之間的、用文字和符號來描述算法的工具。偽代碼不能被計(jì)算機(jī)理解，但接近某種語言編寫的程序，便于轉(zhuǎn)換為編程語言。根據(jù)編程語言的不同，有不同的描述語言。例：求用VB的偽代碼。

ProcPsumInputn0=>sum1=>iWhilei<=n{i+sum=>sumi+1=>i}PrintsumEnd6.2.4典型算法設(shè)計(jì)1.基本算法

為了進(jìn)一步理解算法和設(shè)計(jì)算法，本節(jié)介紹求和、乘積、最大、最小、排序、查找?guī)讉€(gè)基本算法。（1）求和算法在用計(jì)算機(jī)解決實(shí)際問題中，經(jīng)常涉及到求一系列數(shù)之和，例如求學(xué)生成績的平均值，首選就需要把所有學(xué)生成績累加起來。

求和算法是計(jì)算機(jī)科學(xué)中經(jīng)常用到的一種算法，為了把一系列數(shù)據(jù)加起來，需要重復(fù)進(jìn)行加法操作，即在循環(huán)中使用加法操作。求和算法可分為如下的三個(gè)邏輯部分：①將存儲(chǔ)和值的變量（sum）初始化。②循環(huán)，在每次迭代中將一個(gè)新數(shù)加到和（sum）上。③退出循環(huán)后返回結(jié)果。求和算法流程圖（2）乘積算法與求和類似，乘積也是常用算法。例如求整數(shù)的階乘、求xn。其方法就是在循環(huán)中使用乘法操作。乘積算法可分為三個(gè)邏輯部分：①將存儲(chǔ)乘積值的變量（product）初始化。②循環(huán)，在每次迭代中將一個(gè)新數(shù)與乘積（product）相乘。③退出循環(huán)后返回結(jié)果。乘積算法流程圖（3）求最大值和求最小值算法有很多問題需要求最大值和最小值。例如大獎(jiǎng)賽評分問題，需要求最高分和最低分。

其方法就是在循環(huán)中使用選擇結(jié)構(gòu)，而通過選擇結(jié)構(gòu)，可以找到兩個(gè)數(shù)中的較大值（或較小值）。（3）求最大值和求最小值算法在n個(gè)數(shù)中找最大值算法可分為三個(gè)邏輯部分：將最大值變量（max）初始化:將最大值設(shè)為第一個(gè)數(shù)。循環(huán)n-1次：如果當(dāng)前數(shù)比最大值大，將最大值設(shè)為當(dāng)前數(shù)。退出循環(huán)后返回結(jié)果。在n個(gè)數(shù)中找最小值算法可分為三個(gè)邏輯部分：將最小值變量（min）初始化:將最小值設(shè)為第一個(gè)數(shù)。循環(huán)n-1次：如果當(dāng)前數(shù)比最小值小，將最小值設(shè)為當(dāng)前數(shù)。退出循環(huán)后返回結(jié)果。（4）排序計(jì)算機(jī)科學(xué)中一個(gè)最普遍的應(yīng)用是排序，即根據(jù)數(shù)據(jù)的值對它們進(jìn)行排列，一個(gè)有序的數(shù)列更便于查找。排序算法有的比較簡單但效率低，如插入排序、選擇排序、冒泡排序。

有的排序算法效率高，屬于高級排序算法，如快速排序、堆排序、希爾排序、桶式排序、合并排序等。插入排序在插入排序中，排序列表被分為兩部分：已排序的和未排序的。在每次掃描過程中，未排序子列表中的第一個(gè)元素被取出來，在已排序子列表中找到插入位置，使得插入后的序列仍然保持按值有序。具體方法是：待排序的元素，從已排序子列表的末端開始，由后向前，依次與已排序子列表中的元素進(jìn)行比較，直到找到合適的插入位置。插入排序示例（5）查找查找又稱為檢索，是計(jì)算機(jī)的最重要的應(yīng)用之一。所謂查找就是在列表中確定目標(biāo)所在位置的算法。對于列表有兩種基本的查找方法：順序查找和折半查找。

順序查找可以在任何列表中查找，折半查找則要求列表的數(shù)據(jù)元素是有序的。查找

順序查找

順序查找又稱線性查找。順序查找的過程是：對給定的目標(biāo)元素，從列表的一端開始，逐個(gè)與目標(biāo)元素比較，直到找到或到達(dá)表尾時(shí)結(jié)束。折半查找如果列表很大，高效的查找方法是首先把列表排序，然后采用折半查找的方法。折半查找是從一個(gè)列表的中間元素開始測試，判斷要找的元素是在列表的前半部分還是后半部分，以便在縮小列表的一半范圍內(nèi)查找，提高了查找效率。重復(fù)這個(gè)過程直到找到目標(biāo)或目標(biāo)不在這個(gè)列表里，查找結(jié)束。折半查找n比較次數(shù)順序查找折半查找算法設(shè)計(jì)非常重要！時(shí)間復(fù)雜度順序查找：T(n)=O(n)折半查找：T(n)=O(Log2n)2.窮舉法算法窮舉法也叫枚舉法，它的基本思想是：

根據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對所有可能的情況逐一驗(yàn)證，直到所有情況均通過驗(yàn)證。

若某個(gè)情況符合題目條件，則為本題的一個(gè)答案；若全部情況驗(yàn)證完后均不符合題目的條件，則問題無解。特點(diǎn):算法簡單，容易理解，運(yùn)算量大。窮舉法（枚舉法）如：百元買百雞問題。假定小雞每只0.5元，公雞每只2元，母雞每只3元?，F(xiàn)在有100元錢要求買100只雞，問共有幾種購雞方案？根據(jù)題目，設(shè)母雞、公雞、小雞各為x,y,z只，列出方程為：x+y+z=100，3x+2y+0.5z=100

利用窮舉法，將各種可能的組合一一測試，輸出符合條件的組合。即在各個(gè)變量的取值范圍內(nèi)不斷變化x,y,z的值，窮舉x,y,z全部可能的組合，若滿足方程組則是一組解。

偽代碼如下:Exhaustion()

{x

0while(x<=33){y

0while(y<=50){z

100-x-yif((3*x+2*y+0.5*z)=100)

printxyzy

y+1}x

x+1}}窮舉法：百元買百雞問題#include"stdio.h"main(){intx,y,z;printf("母雞公雞小雞");for(x=0;x<=33;x++) for(y=0;y<=50;y++){z=100-x-y; if((3*x+2*y+0.5*z)==100) printf("\n%-6d%-6d%-6d",x,y,z);}}百元買百雞C語言程序：

3.遞推法（迭代法）基本思想：

利用問題本身所具有的某種遞推關(guān)系求解問題。從初值出發(fā)，歸納出新值與舊值間直到最后值為止存在的關(guān)系，從而把一個(gè)復(fù)雜的計(jì)算過程轉(zhuǎn)換為簡單過程的多次重復(fù)，每次重復(fù)都從舊值的基礎(chǔ)上遞推出新值，并由新值代替舊值。如：猴子吃桃子問題，求高次方程的近似解問題。

例：猴子吃桃子問題。小猴在一天內(nèi)摘了若干個(gè)桃子，當(dāng)天吃掉一半多一個(gè)；第二天吃掉剩下的一半桃子多一個(gè)；以后每天都吃尚存桃子的一半零一個(gè)。直到第7天早上要吃時(shí)，只剩下一個(gè)了，問小猴共摘了多少個(gè)桃子？問題分析：先從最后一天推出倒數(shù)第二天的桃子，再從倒數(shù)第二天推出倒數(shù)第三天的桃子，……

設(shè)第n天的桃子為x,它是前一天的桃子數(shù)的一半少一個(gè)，即xn=xn-1-1

前一天的桃子數(shù)為：xn-1=(xn+1)×2(遞推公式）

遞推法偽代碼如下:Monkey-peach(){xn

1i

6while(i>=1){xn-1

(xn+1)*2;xn

xn-1printxn-1/*第i天的桃子數(shù)*/i

i-1}}#include"stdio.h"main(){inti,x;x=1;printf("第7天的桃子數(shù)為：1只\n");for(i=6;i>=1;i--){x=(x+1)*2;printf("第%d天的桃子數(shù)為：%d只",i,x);printf("\n");}}猴子吃桃子C語言程序：4.遞歸法遞歸是算法自我調(diào)用的過程，將問題逐層分解，將復(fù)雜問題歸結(jié)為一些最簡單的問題進(jìn)行處理，然后再沿著分解的逆過程逐步進(jìn)行綜合。如根據(jù)求n!的定義n!=n(n-1)!，進(jìn)行求解。該定義可給出具體形式如下:1(n=0,1)n!=n(n-1)！(n>1)從求n!逐層遞推為求(n-1)!，求(n-2)!...最后成為求1!這個(gè)簡單問題，再沿著原來分解地逆過程逐層相乘進(jìn)行回歸，得出結(jié)果。遞歸求階乘（3?。┑倪^程階乘遞歸算法的偽代碼Factorial(n){if((n=0)||(n=1))return1elsereturnn*Factorial(n-1)}遞歸法與迭代法的對比階乘遞歸算法的偽代碼Factorial(n){if((n=0)||(n=1))return1elsereturnn*Factorial(n-1)}階乘迭代算法的偽代碼Factorial(n){F=1i=1while(i<=n){F=F*ii=i+1}returnF}

5.回溯法（試探法）基本思想：

按優(yōu)選條件向前搜索，當(dāng)探索到某一步時(shí)發(fā)現(xiàn)達(dá)不到目標(biāo)就退回一步重新選擇，即“走不通就回退再走”。如：N皇后問題（同一行、列、對角線上不允許有兩個(gè)皇后）QQQQ4皇后問題的一組解數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合精心選擇的數(shù)據(jù)結(jié)構(gòu)可以有更高的運(yùn)行和存儲(chǔ)效率596.3數(shù)據(jù)的組織結(jié)構(gòu)6.3.1

數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)結(jié)構(gòu)相關(guān)術(shù)語解釋數(shù)據(jù)是指所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號的集合。如數(shù)值、字符、聲音、圖像等。數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行處理。一個(gè)數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是有獨(dú)立含義的數(shù)據(jù)的最小單位，也稱為結(jié)點(diǎn)或記錄。例如學(xué)生學(xué)籍表是數(shù)據(jù)，每一名學(xué)生的記錄就是一個(gè)數(shù)據(jù)元素。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如，集合N={0，±1，±2，…}表示的數(shù)據(jù)對象是全體整數(shù)。數(shù)據(jù)類型是指一個(gè)值的集合和定義在該集合上的一組操作的總稱。例如C語言中的整數(shù)類型，其值集為某一區(qū)間的整數(shù)，定義在其上的一組操作為：加、減、乘、除和取余等算術(shù)運(yùn)算。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合。在任何問題中，數(shù)據(jù)元素都不是孤立存在的，在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系就是結(jié)構(gòu)。6.3.1

數(shù)據(jù)結(jié)構(gòu)的基本概念2.數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)

（1）數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)，反映數(shù)據(jù)元素之間的相互關(guān)系。主要有四種邏輯結(jié)構(gòu)：①集合：數(shù)據(jù)元素之間同屬于一個(gè)集合，別無其他關(guān)系；②線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的線性關(guān)系；③樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對多的層次關(guān)系；④圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。6.3.1

數(shù)據(jù)結(jié)構(gòu)的基本概念2.數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)

（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)元素在計(jì)算機(jī)中以什么方式存儲(chǔ)，也稱為物理結(jié)構(gòu)，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)映像和實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有兩大類:順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）。63元素n……..元素i……..元素2元素1L0L0+mL0+(i-1)*mL0+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=L0+（i-1)*m順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)是指用一組連續(xù)的存儲(chǔ)單元來存放具有某種結(jié)構(gòu)的數(shù)據(jù)元素，也稱為結(jié)點(diǎn)。它把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在地址連續(xù)的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。641536元素21400元素11346元素3∧元素41345存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

h非順序存儲(chǔ)結(jié)構(gòu)通常采用鏈?zhǔn)酱鎯?chǔ)形式，用任意的存儲(chǔ)單元來存放結(jié)點(diǎn)，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。數(shù)據(jù)域指針域6.3.2

常用數(shù)據(jù)結(jié)構(gòu)常用的數(shù)據(jù)結(jié)構(gòu)包括：線性表數(shù)組棧隊(duì)列樹圖線性表是n個(gè)元素的有限序列，是最常用最簡單的數(shù)據(jù)結(jié)構(gòu),長度可增長或縮短。它們之間的關(guān)系可以排成一個(gè)線性序列：

a1，a2，...，ai，...，an線性結(jié)構(gòu)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼在線性表上常用的運(yùn)算有：初始化、求長度、取元素、定位、插入及刪除等。線性表中的數(shù)據(jù)元素有不同含義的，同一線性表中的元素必定具有相同的特性，即屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。1.線性表例1:

英文26個(gè)字母表的數(shù)據(jù)結(jié)構(gòu)是一個(gè)線形表a,b,c,·······

，x,y,z此例數(shù)據(jù)元素是簡單項(xiàng)。學(xué)號姓名成績9861109張卓1009861107劉忠賞959861103胡孝臣86例2:

學(xué)生成績表（復(fù)雜的線性表）數(shù)據(jù)元素是由若干個(gè)數(shù)據(jù)項(xiàng)組成，如每個(gè)學(xué)生的情況，稱為記錄（Record）；由多個(gè)記錄組成的線性表稱為文件（File).線性表的順序存儲(chǔ)結(jié)構(gòu)就是把線性表中的元素按照邏輯順序依次存放到一組連續(xù)的存儲(chǔ)單元中。數(shù)組就是典型的線性結(jié)構(gòu)。特點(diǎn)：每個(gè)數(shù)據(jù)元素對應(yīng)一個(gè)存儲(chǔ)單元，可以依據(jù)數(shù)據(jù)在線性表中的位置來訪問這些數(shù)據(jù)。線性表中數(shù)據(jù)元素類型一致，占用相同大小的存儲(chǔ)單元。存儲(chǔ)空間利用率高。做插入、刪除時(shí)需移動(dòng)大量元素。空間估計(jì)不明時(shí)，按最大空間分配。

線性表中第i個(gè)元素ai的存儲(chǔ)地址為：LOC(ai)=d+(i-1)*m12361016725811dd+md+2*m……d+(i-1)*m……d+(10-1)*m內(nèi)存地址（1）線性表的順序存儲(chǔ)結(jié)構(gòu)（2）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈表是一種常用的數(shù)據(jù)存儲(chǔ)方式，它用動(dòng)態(tài)管理的方式，通過“鏈”建立起數(shù)據(jù)元素之間的邏輯關(guān)系。鏈表用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，每一元素對應(yīng)一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)使用連續(xù)的存儲(chǔ)空間，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息。鏈表利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素。數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?。a1a2∧ana3h…..帶頭結(jié)點(diǎn)的線性鏈表數(shù)據(jù)域指針域abP插入前abxPS插入一個(gè)結(jié)點(diǎn)abPc刪除一個(gè)結(jié)點(diǎn)鏈表的特點(diǎn)：插入、刪除靈活方便，不需要移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可。適用于動(dòng)態(tài)變化的線性表,不進(jìn)行頻繁查找操作、但經(jīng)常進(jìn)行插入刪除時(shí)使用。鏈表的查找只能從頭指針開始順序查找。

a1

a2

….

an進(jìn)棧出棧棧頂棧底棧的定義：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表。特點(diǎn)：后進(jìn)先出(LastInFirstOut,LIFO)/先進(jìn)后出（FirstInLastOut,FILO)。設(shè)棧s=（a1，a2，...,ai，...，an），其中a1是棧底元素，an是棧頂元素，其原理示意圖為:棧頂（top)：允許插入和刪除的一端；棧底（bottom):不允許插入和刪除的一端。凡是對數(shù)據(jù)處理具有“后進(jìn)先出”的特點(diǎn)，都可以用棧來操作。2.棧棧的操作：設(shè)置一個(gè)空棧、插入一個(gè)新的棧頂元素（入棧）、刪除棧頂元素（退棧）、讀取棧頂元素。由于棧的后進(jìn)先出的運(yùn)算原則，常常用于檢索次序與存儲(chǔ)次序相反的存儲(chǔ)數(shù)據(jù)項(xiàng)的問題處理中，即常被用于“回溯”求解的一類問題中。某些問題的求解過程是采用試探方法，當(dāng)某一路徑受阻時(shí)，需要逆序退回，重新選擇新路徑，這樣必須用棧記下曾經(jīng)到達(dá)的每一狀態(tài)，棧頂狀態(tài)即是回退的第一站。隊(duì)列的主要運(yùn)算（1）設(shè)置一個(gè)空隊(duì)列；（2）插入一個(gè)新的隊(duì)尾元素，稱為進(jìn)隊(duì)；（3）刪除隊(duì)頭元素，稱為出隊(duì)；（4）讀取隊(duì)頭元素；定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。隊(duì)尾

a1,

a2,

a3,

a4,…………

an-1,

an

隊(duì)列示意圖隊(duì)頭先進(jìn)先出FIFO隊(duì)列常用作緩沖區(qū)、進(jìn)程的各種狀態(tài)等的結(jié)構(gòu)3.隊(duì)列

A

C

G

T2D

H

I

T3J

M

B

E

L

KT1

F樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，元素結(jié)點(diǎn)間存在明顯的分支和層次關(guān)系?，F(xiàn)實(shí)世界中，能用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。定義：是n(n≥0)個(gè)結(jié)點(diǎn)組成的有限集合,結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系，n=0時(shí)，稱為空樹。特點(diǎn)：非空的樹中至少有且僅有一個(gè)結(jié)點(diǎn)——根,樹中各子樹是互不相交的集合.4.樹形結(jié)構(gòu)樹結(jié)構(gòu)中的常用術(shù)語：結(jié)點(diǎn)（Node）：樹中的每一個(gè)位置稱為結(jié)點(diǎn)。根結(jié)點(diǎn)（Root）：樹頂部的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。葉子結(jié)點(diǎn)（Leaf）：度為零的結(jié)點(diǎn)，也稱端結(jié)點(diǎn)。樹的度數(shù)：樹中最大結(jié)點(diǎn)的度數(shù)稱為。結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始算起，根為第一層。深度（Depth)：根到葉子的最長路徑上的節(jié)點(diǎn)數(shù)，即樹中結(jié)點(diǎn)的最大層次數(shù)。子結(jié)點(diǎn)（Child）：一個(gè)結(jié)點(diǎn)的直接下層結(jié)點(diǎn)為它的子結(jié)點(diǎn)。父結(jié)點(diǎn)（Parent）：子結(jié)點(diǎn)的上層結(jié)點(diǎn)，稱為它的父結(jié)點(diǎn)。兄弟結(jié)點(diǎn)（Sibling）：同一父節(jié)點(diǎn)的子結(jié)點(diǎn)之間為兄弟結(jié)點(diǎn)。結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)擁有的子樹（分支）數(shù)。森林（Forest）：M棵互不相交的樹的集合。ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子結(jié)點(diǎn)：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的子結(jié)點(diǎn)：B，C，D結(jié)點(diǎn)B的子結(jié)點(diǎn)：E，F(xiàn)結(jié)點(diǎn)I的父結(jié)點(diǎn)：D結(jié)點(diǎn)L的父結(jié)點(diǎn)：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)結(jié)點(diǎn)K，L為兄弟結(jié)點(diǎn)樹的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先因?yàn)闃涞拿總€(gè)結(jié)點(diǎn)的度不同，存儲(chǔ)困難，使對樹的處理算法很復(fù)雜，所以引出二叉樹的討論。二叉樹（BinaryTree）二叉樹的五種基本形態(tài)空二叉樹僅有根結(jié)點(diǎn)右子樹為空左子樹為空左右子樹均非空定義：二叉樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。任何一顆樹都可以轉(zhuǎn)換成二叉樹來處理。特點(diǎn)：每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn))二叉樹的子樹有左、右之分，且其次序不能任意顛倒二叉樹的遍歷遍歷二叉樹是指按某條搜索路線巡訪樹中每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)只被訪問一次。二叉樹的遍歷可以分為三種：先序遍歷(DLR)：先訪問根結(jié)點(diǎn),然后分別先序遍歷左子樹、右子樹中序遍歷(LDR)：先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹后序遍歷(LRD)：先后序遍歷左、右子樹，然后訪問根結(jié)點(diǎn)DRLADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:二叉樹的遍歷ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:二叉樹的遍歷ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B二叉樹的遍歷二叉樹的遍歷DLR:ABCDEFLDR:CBEDFALRD:CEFDBAFBADCE中序遍歷序列：CBEDFAABCDEF結(jié)束圖是一種比線性表和樹更為復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。圖在實(shí)際中有廣泛的應(yīng)用，在數(shù)學(xué)、化學(xué)、物理、工程和計(jì)算機(jī)科學(xué)中有大量使用圖來表示的關(guān)系。例如，著名的格尼斯堡“七橋”問題就是將連接兩個(gè)島嶼和陸地的七座橋的地圖抽象為點(diǎn)與線連接的圖，將如何判斷不重復(fù)走遍所有道路的問題轉(zhuǎn)換為圖的形式的數(shù)學(xué)問題進(jìn)行處理。又如，最優(yōu)郵遞路線問題也是采用圖的方式進(jìn)行處理。一個(gè)郵遞員從郵局出發(fā)，到所管轄的街道投遞郵件，最后返回郵局，若必須走遍所轄各街道中每一條至少一次，則怎樣選擇投遞路線使所走的路程最短。在計(jì)算機(jī)網(wǎng)絡(luò)中的搜索引擎通常采用網(wǎng)絡(luò)爬蟲，爬蟲所走的路線是在網(wǎng)絡(luò)中的各網(wǎng)站進(jìn)行搜索，也是要考慮經(jīng)過的路線問題。5.圖形結(jié)構(gòu)6.4.1問題的描述與抽象6.4問題求解-基于計(jì)算機(jī)的問題求解策略要借助于計(jì)算機(jī)解決問題，必須要對問題進(jìn)行清晰的描述和抽象。在現(xiàn)實(shí)生活中，有不少問題可以利用圖形化方法進(jìn)行抽象，把實(shí)際問題抽象成數(shù)學(xué)問題，從而利用數(shù)學(xué)方法解決實(shí)際問題.歐拉解決哥尼斯堡七橋問題就是應(yīng)用圖形化方法的典型范例.BDACABCD6.4.1問題的描述與抽象6.4問題求解-基于計(jì)算機(jī)的問題求解策略著名的四色定理的證明也是典型的抽象例子。即“每幅地圖都可以用4種顏色著色，使得相鄰的國家或行政區(qū)不重色”。四色問題用地圖表示現(xiàn)實(shí)中的不同區(qū)域，忽略區(qū)域中的人、物、房屋、道路等因素，得到只有區(qū)域邊界的地圖，然后對地圖再進(jìn)行抽象，用圓圈表示區(qū)域，用線表示區(qū)域之間的相鄰關(guān)系，就得到了問題的圖形表示。6.4.1問題的描述與抽象6.4問題求解-基于計(jì)算機(jī)的問題求解策略在現(xiàn)實(shí)生活中，有不少問題可以利用方程化函數(shù)化的數(shù)學(xué)方法進(jìn)行抽象，然后通過方程組或函數(shù)圖來解決實(shí)際問題.

例如，假定小雞每只0.5元，公雞每只2元，母雞每只3元。現(xiàn)在有100元錢要求買100只雞，問共有幾種購雞方案？

分析：根據(jù)題目，設(shè)母雞、公雞、小雞各為x,y,z只，列出方程為：x+y+z=1003x+2y+0.5z=1006.4.2基于程序設(shè)計(jì)的問題求解6.4問題求解-基于計(jì)算機(jī)的問題求解策略求三角形面積為例，介紹基于程序設(shè)計(jì)求解問題的一般過程。例：編寫程序計(jì)算三角形面積。要求先輸入三條邊的長度，然后求由這三條邊所構(gòu)成的三角形的面積。6.4.2基于程序設(shè)計(jì)的問題求解（1）問題分析

根據(jù)題意分析，采用計(jì)算三角形面積公式進(jìn)行計(jì)算，計(jì)算過程中要求程序中輸入三條邊的值。設(shè)a，b，c為任意三角形的三條邊，d為三角形周長的一半。（2）確定數(shù)學(xué)模型采用計(jì)算三角形面積公式，即可得到計(jì)算的數(shù)學(xué)模型。

d=(a+b+c)/2（3）算法描述（自然語言描述）S1：輸入三條邊長度a，b，c；S2：判斷三條邊長度是否均大于零。是，則執(zhí)行S3，否則執(zhí)行S6；S3：判斷是否兩邊之和大于第三邊。是，則執(zhí)行S4，否則執(zhí)行S6；S4：根據(jù)公式求三角形面積S；S5：輸出三角形面積，轉(zhuǎn)S7；S6：打印“無解”；S7：結(jié)束。（4）編寫程序

采用C語言編寫的程序

#include<stdio.h>#include<math.h>intmain(){ inta,b,c; doubled,area;

scanf("%d%d%d",&a,&b,&c);

d=(a+b+c)/2.0; area=sqrt(d*(d-a)*(d-b)*(d-c)); printf("area=%6.2f",area);return0；}（5）調(diào)試運(yùn)行程序在VC++6.0環(huán)境輸入程序，編譯源程序，修改語法錯(cuò)誤，連接并運(yùn)行程序，輸入a,b,c三條邊的值，檢查程序結(jié)果是否正確，不正確，修改源程序，再進(jìn)行編譯、連接、運(yùn)行，結(jié)果正確，結(jié)束程序運(yùn)行。程序設(shè)計(jì)的步驟分析問題，建立數(shù)學(xué)模型確定數(shù)據(jù)結(jié)構(gòu)確定算法，描述算法編制程序，調(diào)試程序運(yùn)行結(jié)果6.4.3程序設(shè)計(jì)方法1．結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為:自頂向下，逐步求精，模塊化，限制使用goto語句。自頂向下:程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié);先考慮全局目標(biāo)，后考慮局部目標(biāo)。避免一開始就過多的考慮細(xì)節(jié)，應(yīng)先從頂層開始設(shè)計(jì)，逐步使問題具體化。逐步求精:對復(fù)雜問題，應(yīng)確定一些子目標(biāo)作為過渡，然后逐步細(xì)化。模塊化:一個(gè)復(fù)雜問題，一定是由若干稍簡單的問題組成。模塊化是把程序要解決的總目標(biāo)分解成為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。限制使用GOTO語句。6.4.3程序設(shè)計(jì)方法2．面向?qū)ο蟪绦蛟O(shè)計(jì)用面向?qū)ο蟮姆椒ń鉀Q問題，是將問題分解為對象。將對象的屬性和方法封裝成一個(gè)整體稱為類，通過發(fā)消息來實(shí)現(xiàn)對象之間的相互聯(lián)系和作用。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法日益受到人們的重視和使用，成為流行的軟件開發(fā)方法，源于面向?qū)ο蠓椒ㄓ幸韵峦怀龅膬?yōu)點(diǎn)：①與人們習(xí)慣的思維方法一致，便于解決復(fù)雜問題。②軟件的可維護(hù)性好。③可重用性好，能用繼承的方式縮短程序開發(fā)所花的時(shí)間。④穩(wěn)定性好，易修改?？梢暬诹鞒虉D無需編程算法設(shè)計(jì)和運(yùn)行驗(yàn)證可生成c++、Java等高級語言代碼可導(dǎo)出流程圖初學(xué)者的好幫手95RAPTOR（theRapidAlgorithmicPrototypingToolforOrderedReasoning--用于有序推理的快速算法原型工具）6.5Raptor可視化工具96Raptor語句/符號初始界面6種Raptor基本符號運(yùn)行逐句運(yùn)行Raptor只支持英文字符，不支持中文字符程序由Start模塊開始運(yùn)行至End模塊結(jié)束作用是為一個(gè)變量賦一個(gè)特定值或?qū)⒆兞恐蹈臑橐粋€(gè)新的值圖例是一個(gè)矩形，內(nèi)有賦值語句，語法為

Variable

←

Expression

97Raptor語句/符號賦值（Assignment）語句/符號對變量進(jìn)行賦值，可以是數(shù)值也可以是公式作用是將用戶輸入的數(shù)據(jù)賦值給變量圖例是一個(gè)平行四邊形，在左邊有一個(gè)指向其的箭頭形內(nèi)是將要接收用戶輸入值的變量98Raptor語句/符號輸入（Input）語句/符號輸入提示文本時(shí)要加雙引號，提示信息中的變量不需要加引號，文本和變量可以用+連接99Raptor語句/符號調(diào)用（Call）語句/符號既可以調(diào)用個(gè)人創(chuàng)建的子圖（subchart），也可以對Raptor自帶的過