資料結(jié)構(gòu)導(dǎo)論課件

資料結(jié)構(gòu)

DataStructurechapter11.資料結(jié)構(gòu)

DataStructurechapter11.課程資訊Lecturer:江政杰Office:四合院301URL:.tw/plutoMail:pluto@.tw課程網(wǎng)頁URL:.tw/pluto/ds/ds.html教材、補充資訊作業(yè)相關(guān)連結(jié)2.課程資訊Lecturer:江政杰2.課程資訊TextBook:資料結(jié)構(gòu)–使用C語言

李春雄著上奇出版社成績評量期中、期末各佔30%、平時成績佔40%3.課程資訊TextBook:3.課程內(nèi)容資料結(jié)構(gòu)與演算法遞迴Recursion陣列Array堆疊Stack佇列Queue鏈結(jié)串列LinkedList樹狀結(jié)構(gòu)TreeStructure圖形GraphStructure排序Sorting搜尋Search4.課程內(nèi)容資料結(jié)構(gòu)與演算法4.修課基礎(chǔ)程式撰寫對於變數(shù)、函數(shù)、陣列等基本程式語言的使用與掌握對於一個問題，可以在找出解決方法之後，撰寫出程式碼具備邏輯概念學(xué)習(xí)程式除了語法的熟悉外，最重要的是邏輯概念的訓(xùn)練，才有能力學(xué)習(xí)其他語言還無法順利掌握程式撰寫??以資料結(jié)構(gòu)這門課程為程式設(shè)計的進階訓(xùn)練程式設(shè)計能力的再次訓(xùn)練5.修課基礎(chǔ)程式撰寫5.上課方式投影片展示，請自行搭配課本閱讀實例練習(xí)在課程中會搭配一些程式範例，讓同學(xué)實際操作程式之撰寫，以掌握程式撰寫的能力作業(yè)練習(xí)每一段時間，會有一完整的題目要求撰寫程式，計入平時成績內(nèi)期中、期末考試6.上課方式投影片展示，請自行搭配課本閱讀6.學(xué)習(xí)程式入門學(xué)習(xí)VB、DevC++等軟體的使用熟悉VB、C的語法撰寫進階學(xué)習(xí)資料結(jié)構(gòu)與演算法深入最好的練習(xí)就是實際克服困難的題目這學(xué)期的範圍7.學(xué)習(xí)程式入門這學(xué)期的範圍7.程式的組成資料：在程式中以變數(shù)的型態(tài)出現(xiàn)，每個變數(shù)都在記憶體有一席之地，包含變數(shù)型態(tài)：決定所佔記憶體的長度變數(shù)值：實際的變數(shù)資料值變數(shù)位址：系統(tǒng)處理程序：即if、loop等程式語法與流程I/O：輸入與輸出，如scanf與printf輸入處理輸出8.程式的組成資料：在程式中以變數(shù)的型態(tài)出現(xiàn)，每個變數(shù)都在記憶體練習(xí)請撰寫一個程式，可以顯示九九乘法表以兩層迴圈方式處理先能夠顯示正確結(jié)果，才思考如何排的漂亮先示範…9.練習(xí)請撰寫一個程式，可以顯示九九乘法表9.資料與資訊資料是客觀存在的、具體的、事實的記錄資訊經(jīng)過資料處理之後的結(jié)果即為資訊資料資訊p1-210.資料與資訊資料資料資訊p1-210.資料結(jié)構(gòu)的概念當(dāng)我們解決問題時，還沒開始實際寫程式，必須先規(guī)劃程式如何撰寫I/O：輸入輸出的格式與資料內(nèi)容程序：處理的方法(演算法)資料：決定此問題會用到那些類型的資料有效率的程式=資料結(jié)構(gòu)+演算法所謂的資料結(jié)構(gòu)，就是針對一個問題，決定如何設(shè)計資料部份，尤其是適合此問題的特殊資料類型資料在記憶體中的儲存方式11.資料結(jié)構(gòu)的概念當(dāng)我們解決問題時，還沒開始實際寫程式，必須先規(guī)資料結(jié)構(gòu)的概念在任何問題中，資料元素都不是孤立存在，彼此之間存在某些邏輯關(guān)係，這種關(guān)係可稱為結(jié)構(gòu)(structure)，種類有集合：元素間沒有次序性線性結(jié)構(gòu)：陣列、串列、佇列、堆疊樹狀結(jié)構(gòu)圖形結(jié)構(gòu)12.資料結(jié)構(gòu)的概念在任何問題中，資料元素都不是孤立存在，彼此之間範例說明寫一個程式計算五個同學(xué)的平均成績p1-513.範例說明寫一個程式計算五個同學(xué)的平均成績p1-513.演算法的五原則演算法(Algorithm):解決問題的方法輸入(Input)不一定要有輸入?？赡軟]有，也可能是多個資料輸入。p1-7例如(1)：取得系統(tǒng)目前的時間，不須要輸入，只要寫一行now()函數(shù)，就可以輸出系統(tǒng)時間例如(2)：求某數(shù)為奇偶數(shù)時，則必須先要有一個整數(shù)輸入，才能運算輸出(Output)至少要有一個輸出明確性(Definiteness)每一行指令都必須明確，不可模稜兩可「用功的學(xué)生才能領(lǐng)獎學(xué)金」就不具有明確性，因為每一個人對用功的定義可能不盡相同。而如果改為「成績90以上的學(xué)生才能領(lǐng)獎學(xué)金」就是具有明確性，因為90分是一個比較客觀的定義。14.演算法的五原則演算法(Algorithm):解決問題的方法演算法的五原則有限性(Finiteness)演算法不能有無窮迴路，必須能終止執(zhí)行由於演算法並非是真正可以執(zhí)行的程式，而是設(shè)計者所推演出解決問題的步驟，因此，必須在有限的步驟內(nèi)要完成解決問題的程序真正的程式是可以有無窮迴路的動作正確性(Correctness)既然演算法是解決問題的方法，因此正確性是最基本的要求15.演算法的五原則有限性(Finiteness)15.演算法的範例演算法:一組可用來解決特定問題的有限指令或步驟依循這些指令或步驟，可以完成工作案例:做蛋糕16.演算法的範例演算法:16.演算法的範例好吃的蛋糕怎麼來?輸入輸出明確性正確性有限性17.演算法的範例好吃的蛋糕怎麼來?輸入輸出明確性正確性有限描述演算法的三種方法文字採用口語化的文字敘述來加以描述，容易冗長且較不精確，在撰寫、閱讀、會意時可能會有誤差，因此一般較不常用p1-10例如：請利用「文字敘述」使用者登入帳號與密碼時，系統(tǒng)檢查的過程。步驟一：輸入使用者帳號與密碼步驟二：判斷帳號與密碼是否正確步驟三：如果正確時，則可以登入系統(tǒng)否則，就無法登入！18.描述演算法的三種方法文字p1-10例如：請利用「文字敘述」使描述演算法的三種方法流程圖利用圖形方式來表達欲解決問題的步驟19.描述演算法的三種方法流程圖19.描述演算法的三種方法虛擬碼使用文字摻雜程式語言，來描述解題步驟與方法兼具文字描述及流程圖的優(yōu)點//登錄帳號密碼的檢查(1)Input:UserName,Password(2)IF(UserNameAndPassword)ALLTrueOutput:YouCanPass!elseOutput:YouCannotPass!//計算1+2+3+…+10(1)設(shè)Count=1,Total=0;(2)Total=Total+Count;(3)Count=Count+1;(4)若Count>10則至步驟(5)，否則回步驟(2)(5)印出Total不是可以執(zhí)行的指令只是說明程式處理的流程20.描述演算法的三種方法虛擬碼//登錄帳號密碼的檢查//計算1+程式設(shè)計概念p1-1421.程式設(shè)計概念p1-1421.程式設(shè)計概念22.程式設(shè)計概念22.程式設(shè)計概念系統(tǒng)發(fā)展的生命週期與程式設(shè)計之步驟比較23.程式設(shè)計概念系統(tǒng)發(fā)展的生命週期與程式設(shè)計之步驟比較23程式設(shè)計範例題目計算國文與英文的平均成績，並依照平均成績來求顯示「及格」與「不及格」1.分析及定義問題。兩個等級分別如下：(1)及格：60(含)以上。(2)不及格：60以下。2.畫出整合問題的流程圖或撰寫問題的演算法24.程式設(shè)計範例題目1.分析及定義問題。24.3.撰寫及建立程式模組4.對每一個程式模組進行測試及除錯，直到?jīng)]有錯誤為止當(dāng)使用者輸入國文為60分，英文為61分時，是否可以計算出平均成績?yōu)?0.5，如果沒有則必須要進行除錯，亦即要將Average的資料型態(tài)改為float(浮點數(shù))25.3.撰寫及建立程式模組4.對每一個程式模組進行測試及除錯，直結(jié)構(gòu)化程式設(shè)計利用「由上而下」的技巧，將程式分解成多個具有獨立功能的模組強調(diào)任何程式邏輯均可由三種結(jié)構(gòu)組成循序(Sequence)：簡單命令式的指令如X=Y+Z選擇(Condition)：做決策使用if-then-elseselectcase/switch重複(Repetition)：重複執(zhí)行do-whiledo-untilforp1-18循序選擇重複26.結(jié)構(gòu)化程式設(shè)計利用「由上而下」的技巧，將程式分解成多個具有獨演算法、資料結(jié)構(gòu)、程式演算法整個問題的解決方法，以邏輯方式描述以文字、或虛擬碼方式，撰寫整個程式的流程可對應(yīng)到程式的撰寫，但是與程式語言的選擇無關(guān)資料結(jié)構(gòu)要解決問題時所需要的資料，以及資料彼此之間的關(guān)連與結(jié)構(gòu)著重在資料的表現(xiàn)、資料之間的結(jié)構(gòu)關(guān)係程式實際可以執(zhí)行真實的解決問題，以符合程式語言的規(guī)範完成不同程式語言有不同的撰寫方法，但是彼此的基本概念卻很相似27.演算法、資料結(jié)構(gòu)、程式演算法27.演算法、資料結(jié)構(gòu)、程式在討論問題的解決方案時，大多以演算法搭配資料結(jié)構(gòu)為溝通的工具直接以程式語言討論太過於瑣碎程式撰寫是基本的技能，更進階的是針對特定問題採用適當(dāng)?shù)馁Y料結(jié)構(gòu)設(shè)計有效率的演算法解決所面對的問題有效率的演算法用較少的記憶體空間完成處理同一個問題用較少的執(zhí)行時間完成處理同一個問題28.演算法、資料結(jié)構(gòu)、程式在討論問題的解決方案時，大多以演算法搭演算法的時間效率程式的執(zhí)行速度受到哪些因素影響程式需要執(zhí)行的指令數(shù)量CPU的速度電腦架構(gòu)例如記憶體大小等其他例如編譯程式的效率等演算法的設(shè)計並不考慮程式語言與硬體架構(gòu)，因此以指令數(shù)量為評估效率的主要依據(jù)Q:怎麼計算一個演算法的指令數(shù)量基本上是無法精確計算需要之指令數(shù)量，why?那該怎麼評估一個演算法所需的指令數(shù)量p1-2229.演算法的時間效率程式的執(zhí)行速度受到哪些因素影響p1-2229程式中指令數(shù)目的計算循序結(jié)構(gòu)(一般指令)例如:x=x+1每個指令執(zhí)行一次決策分支結(jié)構(gòu)(if)例如:if(x>1)then...只有條件為正時才會執(zhí)行重複結(jié)構(gòu)(loop)例如:fori=1to100迴圈內(nèi)的指令重複100次真正計算指令數(shù)量有困難，但是從以上三個結(jié)構(gòu)來看，顯然迴圈內(nèi)的執(zhí)行數(shù)量是重點Q:計算下列程式中變數(shù)Count被執(zhí)行的次數(shù)為何30.程式中指令數(shù)目的計算循序結(jié)構(gòu)(一般指令)Q:計算下列程式中迴圈敘述的頻率計數(shù)1.先根據(jù)「迴圈計數(shù)器」的範圍算出迴圈重複的次數(shù)2.再乘上迴圈內(nèi)的行數(shù)。下列的程式片段，計算10組整數(shù)除法的商數(shù)及餘數(shù)1. Fori=0To92. Q=m[i]/n[i]3. R=m[i]Modn[i];4. Console.WriteLine(“{0}/{1}={2}…{3}”,m[i],n[i],Q,R)5. Next迴圈重複的次數(shù)為10次，迴圈內(nèi)有3個敘述，因此第2行到第4行（迴圈的主體）的頻率計數(shù)為30(=103)。第1行for迴圈的頭會執(zhí)行11次，前10次造成迴圈主體的重複執(zhí)行，第11次發(fā)現(xiàn)條件不符而離開迴圈。因此整個迴圈（迴圈的頭加上迴圈的主體）的頻率計數(shù)為41(=11+30)。31.迴圈敘述的頻率計數(shù)1.先根據(jù)「迴圈計數(shù)器」的範圍算出迴圈重【舉例1】假設(shè)有一陣列a，其陣列的大小為n，如果要將陣列a的元素相加，請問程式的執(zhí)行次數(shù)為何？【解析】行號04會執(zhí)行n+1次，而前n次會執(zhí)行迴圈主體，但是在第n+1次時沒有符合迴圈的條件，故離開迴圈。32.【舉例1】【解析】行號04會執(zhí)行n+1次，而前n次會執(zhí)行迴圈【舉例2】假設(shè)兩矩陣a,b相加，並且矩陣大小皆為n*n，請計算出下列程式的執(zhí)行次數(shù)？【解析】行號04外層迴圈(for)的計數(shù)器i從0~n-1，共會執(zhí)行n+1次，而行號05內(nèi)層迴圈(for)的計數(shù)器j從0~n-1，也會執(zhí)行n+1次。因此，當(dāng)外層迴圈執(zhí)行1次時，則內(nèi)層迴圈要執(zhí)行一回合，也就是j從0~n-1(共有n次)33.【舉例2】【解析】行號04外層迴圈(for)的計數(shù)器i從0~【舉例3】假設(shè)兩矩陣a,b相乘，並且矩陣大小皆為n*n，相加請計算出下列程式的執(zhí)行次數(shù)34.【舉例3】34.雙層迴圈、內(nèi)圈不固定次數(shù)

1

Fori=1Ton 2 Forj=i+1Ton 3result+=14Next5Next

由於內(nèi)圈迴圈計數(shù)器j的範圍，是隨著外圈迴圈計數(shù)器i的範圍改變的，因此我們針對迴圈計數(shù)器i的變化來分析：

35.雙層迴圈、內(nèi)圈不固定次數(shù)35.數(shù)學(xué)式：總次數(shù)＝i的值j的範圍第3行執(zhí)行次數(shù)12……nn-123……nn-234……nn-3……

n-1n……n1nn+1……n0總次數(shù)＝(n-1)+(n-2)+…+1=n*(n-1)/2

=

=

=

n2–

=36.數(shù)學(xué)式：i的值j的範圍第3行執(zhí)行次數(shù)1n-123……範例：計算n階乘(n!)的函式

1Functionfactor(ByValnAsInteger)AsInteger 2 Dimi,resultAsInteger 3

result=1 4

i=1 5

Dowhilei<=n 6

result=result*i; 7

i+=1; 8

Loop 9

Returnresult 10EndFunction37.範例：計算n階乘(n!)的函式37.我們計算每一行敘述被執(zhí)行的次數(shù)：行號n>0時n<=0時1112113n+115n06n0811總次數(shù)3n+44

如果n>0，頻率計數(shù)為3n+4次，如果n<=0，頻率計數(shù)為4次多1次為最後一次比較條件不成立如果更複雜的程式，似乎很難真的計算出指令的數(shù)量仔細觀察，3n+4的值重點在n是多少，當(dāng)n很大時，4其實不重要一般計算時，主要依據(jù)n的狀況，也就是迴圈的層次38.我們計算每一行敘述被執(zhí)行的次數(shù)：行號n>0時n<=0Big-OBig-O符號的數(shù)學(xué)定義為：若且唯若f(n)=O(g(n))則存在大於0的常數(shù)c和n0，使得對所有的n值，當(dāng)n≧n0時，f(n)≦c*g(n)均成立。用數(shù)學(xué)式表示為：f(n)=O(g(n))

c,n0>0

n≧n0,f(n)≦c*g(n)用口語解釋為：f(n)取Big-O符號為O(g(n))，當(dāng)n夠大的時候，g(n)相當(dāng)於是f(n)的上限

nn0f(n)c*g(n)用圖示可表達為：

39.Big-OBig-O符號的數(shù)學(xué)定義為：若且唯若f(n)=◎5n2+6n+9＝O(n2)→f(n)=5n2+6n+9,g(n)=n2→f函數(shù)取Big-O符號為g函數(shù)→5n2+6n+9取Big-O符號為O(n2)◎

3nlgn+9n+10=O(nlgn)，因為nlgn的次數(shù)比n大，取最高次項而不計係數(shù)時，自然取到nlgn(lgn=log2n)◎9n2+6nlgn+9=O(n2)，因為n2的次數(shù)最大，取最高次項而不計係數(shù)時，自然取到n2

◎

19n3+9n2+6n+9=O(n3)，因為n3的次數(shù)最大，取最高次項而不計係數(shù)時，自然取到n340.◎5n2+6n+9＝O(n2)◎3nl41.41.2nn3n2nlgnnlgn1248163264128將各種複雜度隨n值變化的結(jié)果繪成圖表，以便了解複雜度對程式效能的影響有多大：(X軸代表n值的成長，Y軸代表g(n)值的成長)2521021522022523042.2nn3n2nlgnnlgn1248163264128將各種資料結(jié)構(gòu)

DataStructurechapter143.資料結(jié)構(gòu)

DataStructurechapter11.課程資訊Lecturer:江政杰Office:四合院301URL:.tw/plutoMail:pluto@.tw課程網(wǎng)頁URL:.tw/pluto/ds/ds.html教材、補充資訊作業(yè)相關(guān)連結(jié)44.課程資訊Lecturer:江政杰2.課程資訊TextBook:資料結(jié)構(gòu)–使用C語言

李春雄著上奇出版社成績評量期中、期末各佔30%、平時成績佔40%45.課程資訊TextBook:3.課程內(nèi)容資料結(jié)構(gòu)與演算法遞迴Recursion陣列Array堆疊Stack佇列Queue鏈結(jié)串列LinkedList樹狀結(jié)構(gòu)TreeStructure圖形GraphStructure排序Sorting搜尋Search46.課程內(nèi)容資料結(jié)構(gòu)與演算法4.修課基礎(chǔ)程式撰寫對於變數(shù)、函數(shù)、陣列等基本程式語言的使用與掌握對於一個問題，可以在找出解決方法之後，撰寫出程式碼具備邏輯概念學(xué)習(xí)程式除了語法的熟悉外，最重要的是邏輯概念的訓(xùn)練，才有能力學(xué)習(xí)其他語言還無法順利掌握程式撰寫??以資料結(jié)構(gòu)這門課程為程式設(shè)計的進階訓(xùn)練程式設(shè)計能力的再次訓(xùn)練47.修課基礎(chǔ)程式撰寫5.上課方式投影片展示，請自行搭配課本閱讀實例練習(xí)在課程中會搭配一些程式範例，讓同學(xué)實際操作程式之撰寫，以掌握程式撰寫的能力作業(yè)練習(xí)每一段時間，會有一完整的題目要求撰寫程式，計入平時成績內(nèi)期中、期末考試48.上課方式投影片展示，請自行搭配課本閱讀6.學(xué)習(xí)程式入門學(xué)習(xí)VB、DevC++等軟體的使用熟悉VB、C的語法撰寫進階學(xué)習(xí)資料結(jié)構(gòu)與演算法深入最好的練習(xí)就是實際克服困難的題目這學(xué)期的範圍49.學(xué)習(xí)程式入門這學(xué)期的範圍7.程式的組成資料：在程式中以變數(shù)的型態(tài)出現(xiàn)，每個變數(shù)都在記憶體有一席之地，包含變數(shù)型態(tài)：決定所佔記憶體的長度變數(shù)值：實際的變數(shù)資料值變數(shù)位址：系統(tǒng)處理程序：即if、loop等程式語法與流程I/O：輸入與輸出，如scanf與printf輸入處理輸出50.程式的組成資料：在程式中以變數(shù)的型態(tài)出現(xiàn)，每個變數(shù)都在記憶體練習(xí)請撰寫一個程式，可以顯示九九乘法表以兩層迴圈方式處理先能夠顯示正確結(jié)果，才思考如何排的漂亮先示範…51.練習(xí)請撰寫一個程式，可以顯示九九乘法表9.資料與資訊資料是客觀存在的、具體的、事實的記錄資訊經(jīng)過資料處理之後的結(jié)果即為資訊資料資訊p1-252.資料與資訊資料資料資訊p1-210.資料結(jié)構(gòu)的概念當(dāng)我們解決問題時，還沒開始實際寫程式，必須先規(guī)劃程式如何撰寫I/O：輸入輸出的格式與資料內(nèi)容程序：處理的方法(演算法)資料：決定此問題會用到那些類型的資料有效率的程式=資料結(jié)構(gòu)+演算法所謂的資料結(jié)構(gòu)，就是針對一個問題，決定如何設(shè)計資料部份，尤其是適合此問題的特殊資料類型資料在記憶體中的儲存方式53.資料結(jié)構(gòu)的概念當(dāng)我們解決問題時，還沒開始實際寫程式，必須先規(guī)資料結(jié)構(gòu)的概念在任何問題中，資料元素都不是孤立存在，彼此之間存在某些邏輯關(guān)係，這種關(guān)係可稱為結(jié)構(gòu)(structure)，種類有集合：元素間沒有次序性線性結(jié)構(gòu)：陣列、串列、佇列、堆疊樹狀結(jié)構(gòu)圖形結(jié)構(gòu)54.資料結(jié)構(gòu)的概念在任何問題中，資料元素都不是孤立存在，彼此之間範例說明寫一個程式計算五個同學(xué)的平均成績p1-555.範例說明寫一個程式計算五個同學(xué)的平均成績p1-513.演算法的五原則演算法(Algorithm):解決問題的方法輸入(Input)不一定要有輸入?？赡軟]有，也可能是多個資料輸入。p1-7例如(1)：取得系統(tǒng)目前的時間，不須要輸入，只要寫一行now()函數(shù)，就可以輸出系統(tǒng)時間例如(2)：求某數(shù)為奇偶數(shù)時，則必須先要有一個整數(shù)輸入，才能運算輸出(Output)至少要有一個輸出明確性(Definiteness)每一行指令都必須明確，不可模稜兩可「用功的學(xué)生才能領(lǐng)獎學(xué)金」就不具有明確性，因為每一個人對用功的定義可能不盡相同。而如果改為「成績90以上的學(xué)生才能領(lǐng)獎學(xué)金」就是具有明確性，因為90分是一個比較客觀的定義。56.演算法的五原則演算法(Algorithm):解決問題的方法演算法的五原則有限性(Finiteness)演算法不能有無窮迴路，必須能終止執(zhí)行由於演算法並非是真正可以執(zhí)行的程式，而是設(shè)計者所推演出解決問題的步驟，因此，必須在有限的步驟內(nèi)要完成解決問題的程序真正的程式是可以有無窮迴路的動作正確性(Correctness)既然演算法是解決問題的方法，因此正確性是最基本的要求57.演算法的五原則有限性(Finiteness)15.演算法的範例演算法:一組可用來解決特定問題的有限指令或步驟依循這些指令或步驟，可以完成工作案例:做蛋糕58.演算法的範例演算法:16.演算法的範例好吃的蛋糕怎麼來?輸入輸出明確性正確性有限性59.演算法的範例好吃的蛋糕怎麼來?輸入輸出明確性正確性有限描述演算法的三種方法文字採用口語化的文字敘述來加以描述，容易冗長且較不精確，在撰寫、閱讀、會意時可能會有誤差，因此一般較不常用p1-10例如：請利用「文字敘述」使用者登入帳號與密碼時，系統(tǒng)檢查的過程。步驟一：輸入使用者帳號與密碼步驟二：判斷帳號與密碼是否正確步驟三：如果正確時，則可以登入系統(tǒng)否則，就無法登入！60.描述演算法的三種方法文字p1-10例如：請利用「文字敘述」使描述演算法的三種方法流程圖利用圖形方式來表達欲解決問題的步驟61.描述演算法的三種方法流程圖19.描述演算法的三種方法虛擬碼使用文字摻雜程式語言，來描述解題步驟與方法兼具文字描述及流程圖的優(yōu)點//登錄帳號密碼的檢查(1)Input:UserName,Password(2)IF(UserNameAndPassword)ALLTrueOutput:YouCanPass!elseOutput:YouCannotPass!//計算1+2+3+…+10(1)設(shè)Count=1,Total=0;(2)Total=Total+Count;(3)Count=Count+1;(4)若Count>10則至步驟(5)，否則回步驟(2)(5)印出Total不是可以執(zhí)行的指令只是說明程式處理的流程62.描述演算法的三種方法虛擬碼//登錄帳號密碼的檢查//計算1+程式設(shè)計概念p1-1463.程式設(shè)計概念p1-1421.程式設(shè)計概念64.程式設(shè)計概念22.程式設(shè)計概念系統(tǒng)發(fā)展的生命週期與程式設(shè)計之步驟比較65.程式設(shè)計概念系統(tǒng)發(fā)展的生命週期與程式設(shè)計之步驟比較23程式設(shè)計範例題目計算國文與英文的平均成績，並依照平均成績來求顯示「及格」與「不及格」1.分析及定義問題。兩個等級分別如下：(1)及格：60(含)以上。(2)不及格：60以下。2.畫出整合問題的流程圖或撰寫問題的演算法66.程式設(shè)計範例題目1.分析及定義問題。24.3.撰寫及建立程式模組4.對每一個程式模組進行測試及除錯，直到?jīng)]有錯誤為止當(dāng)使用者輸入國文為60分，英文為61分時，是否可以計算出平均成績?yōu)?0.5，如果沒有則必須要進行除錯，亦即要將Average的資料型態(tài)改為float(浮點數(shù))67.3.撰寫及建立程式模組4.對每一個程式模組進行測試及除錯，直結(jié)構(gòu)化程式設(shè)計利用「由上而下」的技巧，將程式分解成多個具有獨立功能的模組強調(diào)任何程式邏輯均可由三種結(jié)構(gòu)組成循序(Sequence)：簡單命令式的指令如X=Y+Z選擇(Condition)：做決策使用if-then-elseselectcase/switch重複(Repetition)：重複執(zhí)行do-whiledo-untilforp1-18循序選擇重複68.結(jié)構(gòu)化程式設(shè)計利用「由上而下」的技巧，將程式分解成多個具有獨演算法、資料結(jié)構(gòu)、程式演算法整個問題的解決方法，以邏輯方式描述以文字、或虛擬碼方式，撰寫整個程式的流程可對應(yīng)到程式的撰寫，但是與程式語言的選擇無關(guān)資料結(jié)構(gòu)要解決問題時所需要的資料，以及資料彼此之間的關(guān)連與結(jié)構(gòu)著重在資料的表現(xiàn)、資料之間的結(jié)構(gòu)關(guān)係程式實際可以執(zhí)行真實的解決問題，以符合程式語言的規(guī)範完成不同程式語言有不同的撰寫方法，但是彼此的基本概念卻很相似69.演算法、資料結(jié)構(gòu)、程式演算法27.演算法、資料結(jié)構(gòu)、程式在討論問題的解決方案時，大多以演算法搭配資料結(jié)構(gòu)為溝通的工具直接以程式語言討論太過於瑣碎程式撰寫是基本的技能，更進階的是針對特定問題採用適當(dāng)?shù)馁Y料結(jié)構(gòu)設(shè)計有效率的演算法解決所面對的問題有效率的演算法用較少的記憶體空間完成處理同一個問題用較少的執(zhí)行時間完成處理同一個問題70.演算法、資料結(jié)構(gòu)、程式在討論問題的解決方案時，大多以演算法搭演算法的時間效率程式的執(zhí)行速度受到哪些因素影響程式需要執(zhí)行的指令數(shù)量CPU的速度電腦架構(gòu)例如記憶體大小等其他例如編譯程式的效率等演算法的設(shè)計並不考慮程式語言與硬體架構(gòu)，因此以指令數(shù)量為評估效率的主要依據(jù)Q:怎麼計算一個演算法的指令數(shù)量基本上是無法精確計算需要之指令數(shù)量，why?那該怎麼評估一個演算法所需的指令數(shù)量p1-2271.演算法的時間效率程式的執(zhí)行速度受到哪些因素影響p1-2229程式中指令數(shù)目的計算循序結(jié)構(gòu)(一般指令)例如:x=x+1每個指令執(zhí)行一次決策分支結(jié)構(gòu)(if)例如:if(x>1)then...只有條件為正時才會執(zhí)行重複結(jié)構(gòu)(loop)例如:fori=1to100迴圈內(nèi)的指令重複100次真正計算指令數(shù)量有困難，但是從以上三個結(jié)構(gòu)來看，顯然迴圈內(nèi)的執(zhí)行數(shù)量是重點Q:計算下列程式中變數(shù)Count被執(zhí)行的次數(shù)為何72.程式中指令數(shù)目的計算循序結(jié)構(gòu)(一般指令)Q:計算下列程式中迴圈敘述的頻率計數(shù)1.先根據(jù)「迴圈計數(shù)器」的範圍算出迴圈重複的次數(shù)2.再乘上迴圈內(nèi)的行數(shù)。下列的程式片段，計算10組整數(shù)除法的商數(shù)及餘數(shù)1. Fori=0To92. Q=m[i]/n[i]3. R=m[i]Modn[i];4. Console.WriteLine(“{0}/{1}={2}…{3}”,m[i],n[i],Q,R)5. Next迴圈重複的次數(shù)為10次，迴圈內(nèi)有3個敘述，因此第2行到第4行（迴圈的主體）的頻率計數(shù)為30(=103)。第1行for迴圈的頭會執(zhí)行11次，前10次造成迴圈主體的重複執(zhí)行，第11次發(fā)現(xiàn)條件不符而離開迴圈。因此整個迴圈（迴圈的頭加上迴圈的主體）的頻率計數(shù)為41(=11+30)。73.迴圈敘述的頻率計數(shù)1.先根據(jù)「迴圈計數(shù)器」的範圍算出迴圈重【舉例1】假設(shè)有一陣列a，其陣列的大小為n，如果要將陣列a的元素相加，請問程式的執(zhí)行次數(shù)為何？【解析】行號04會執(zhí)行n+1次，而前n次會執(zhí)行迴圈主體，但是在第n+1次時沒有符合迴圈的條件，故離開迴圈。74.【舉例1】【解析】行號04會執(zhí)行n+1次，而前n次會執(zhí)行迴圈【舉例2】假設(shè)兩矩陣a,b相加，並且矩陣大小皆為n*n，請計算出下列程式的執(zhí)行次數(shù)？【解析】行號04外層迴圈(for)的計數(shù)器i從0~n-1，共會執(zhí)行n+1次，而行號05內(nèi)層迴圈(for)的計數(shù)器j從0~n-1，也會執(zhí)行n+1次。因此，當(dāng)外層迴圈執(zhí)行1次時，則內(nèi)層迴圈要執(zhí)行一回合，也就是j從0~n-1(共有n次)75.【舉例2】【解析】行號04外層迴圈(for)的計數(shù)器i從0~【舉例3】假設(shè)兩矩陣a,b相乘，並且矩陣大小皆為n*n，相加請計算出下列程式的執(zhí)行次數(shù)76.【舉例3】34.雙層迴圈、內(nèi)圈不固定次數(shù)

1

Fori=1Ton 2 Forj=i+1Ton 3result+=14Next5Next

由於內(nèi)圈迴圈計數(shù)器j的範圍，是隨著外圈迴圈計數(shù)器i的範圍改變的，因此我們針對迴圈計數(shù)器i的變化來分析：

77.雙層迴圈、內(nèi)圈不固定次數(shù)35.數(shù)學(xué)式：總次數(shù)＝i的值j的範圍第3行執(zhí)行次數(shù)12……nn-123……nn-234……nn-3……

n-1n……n1nn+1……n0總次數(shù)＝(n-1)+(n-2)+…+1=n*(n-1)/2

=

=

=

n2–

=78.數(shù)學(xué)式：i的值j的範圍第3行執(zhí)行次數(shù)1n-123……範例：計算n階乘(n!)的函式

1Functionfactor(ByValnAsInteger)AsInteger 2 Dimi,re