资料结构导论课件

資料結構

DataStructurechapter11.資料結構

DataStructurechapter11.課程資訊Lecturer:江政杰Office:四合院301URL:.tw/plutoMail:pluto@.tw課程網頁URL:.tw/pluto/ds/ds.html教材、補充資訊作業相關連結2.課程資訊Lecturer:江政杰2.課程資訊TextBook:資料結構–使用C語言

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

1

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

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

35.雙層迴圈、內圈不固定次數35.數學式：總次數＝i的值j的範圍第3行執行次數12……nn-123……nn-234……nn-3……

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

=

=

=

n2–

=36.數學式：i的值j的範圍第3行執行次數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.我們計算每一行敘述被執行的次數：行號n>0時n<=0時1112113n+115n06n0811總次數3n+44

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

c,n0>0

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

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

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

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

◎

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

DataStructurechapter143.資料結構

DataStructurechapter11.課程資訊Lecturer:江政杰Office:四合院301URL:.tw/plutoMail:pluto@.tw課程網頁URL:.tw/pluto/ds/ds.html教材、補充資訊作業相關連結44.課程資訊Lecturer:江政杰2.課程資訊TextBook:資料結構–使用C語言

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

1

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

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

77.雙層迴圈、內圈不固定次數35.數學式：總次數＝i的值j的範圍第3行執行次數12……nn-123……nn-234……nn-3……

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

=

=

=

n2–

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

1Functionfactor(ByValnAsInteger)AsInteger 2 Dimi,re