演算法整数及矩阵课件.ppt

Discrete MathematicsChapter3TheFundamentals:Algorithms,theIntegers,andMatrices大葉大學大葉大學 資訊工程系資訊工程系 黃鈴玲黃鈴玲Ch3-23.1 Algorithms(演算法演算法)Def 1.Analgorithmisafinitesequenceofpreciseinstructionsforperformingacomputationorforsolvingaproblem.nExample 1.Describeanalgorithmforfindingthemaximumvalueinafinitesequenceofintegers.(假設給定的整數序列是a1,a2,an，求最大值)Ch3-3Solution:(Englishlanguage)1.Setthetemporarymaximumequaltothefirstintegerinthesequence.2.Comparethenextintegerinthesequencetothetemporarymaximum,andifitislargerthanthetemporarymaximum,setthetemporarymaximumequaltothisinteger.3.Repeatthepreviousstepiftherearemoreintegersinthesequence.4.Stopwhentherearenointegersleftinthesequence.Thetemporarymaximumatthispointisthelargestintegerinthesequence.Ch3-4procedure 表示開始一個副程式:=用來表示指定 max:=a1表示指定max變數的值等於a1大括號用來存放註解，此處標示輸出變數是maxAlgorithm 1.Finding the Maximum Elementprocedure max(a1,a2,an:integers)max:=a1for i:=2 to n if max ai then max:=ai max is the largest elementSolution(pseudo-code虛擬碼)演算法名稱輸入變數名稱輸入變數型別Ch3-5Thereareseveralpropertiesthatalgorithmsgenerallyshare:nInputnOutputnDefiniteness:Thestepsofanalgorithmmustbedefinedprecisely.nCorrectness:producecorrectoutputvaluesnFiniteness:producethedesiredoutputafterafinitenumberofstep.nEffectivenessnGenerality:Theprocedureshouldbeapplicableforallproblemsofthedesiredform,notjustforaparticularsetofinputvalues.Exercise3.13.設計一個演算法，找出某個整數集合中所有數目的總和。

Ch3-6參考找最大值的演算法做修改：參考找最大值的演算法做修改：procedure max(a1,a2,an:integers)max:=a1for i:=2 to n if max ai then max:=ai max is the largest elementprocedure sum(a1,a2,an:integers)sum:=for i:=to sum is the largest elementCh3-7Problem:Locateanelementxinalistofdistinctelementsa1,a2,an,ordeterminethatitisnotinthelist.做法:linearsearch(線性搜尋),binarysearch(二元搜尋)Algorithm 2.The linear search algorithmprocedure linear_search(x:integer,a1,a2,an:distinct integers)i:=1While (i n and xai)i:=i+1if i n then location:=i else location:=0 location=j if x=aj;location=0 if x is not found.Searching(搜尋)AlgorithmsExercise3.113(a).列出線性搜尋用來從序列1,3,4,5,6,8,9,11中尋找9的步驟。

Ch3-8參考：procedure linear_search(x:integer,a1,a2,an:distinct integers)i:=1While (i n and xai)i:=i+1if i n then location:=i else location:=0 location=j if x=aj;location=0 if x is not found.Ch3-9n兩種search方式的概念:Linear Search:從a1開始，逐一比對x 是否等於ai，若找到則location=i,若到an比完後還找不到，則location=0Binary Search:(必須具備a1a2am表示x應在右半，否則在左半2)重覆上一步驟至list只剩一個元素ai，若x=ai則location=i，否則location=0Ch3-10Example 3.Search 19 from a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22 12 13 15 16 18 19 20 22 18 19 20 22 18 19 191.切兩半切兩半,m=8 因因 x=19 a8=10，取右半，取右半，i=9 2.再切二半再切二半,m=12 因因 x=19 a12=16，取右半，取右半,i=133.再切二半再切二半,m=14 因因 x=19 a14=19，取左半，取左半,j=144.再切二半再切二半,m=13 因因 x=19 a13=18，取右半，取右半,i=145 此時此時 i=j=14,數列只剩一個元素數列只剩一個元素 a14=19 因因 x=19=a14，故，故 location=14Note:ai,ai+1,aj 數列的切法數列的切法:令令 m=則則 am 即切開紅線左邊那點。

即切開紅線左邊那點x正在搜尋 x 的數列為 ai,ai+1,aj 一開始 i=1,j=16 Ch3-11Algorithm 3.The Binary Search Algorithmprocedure binary_search(x:integer,a1,a2,an:increasing integers)i:=1 i is left endpoint of search interval j:=n j is right endpoint of search interval while i am then i:=m+1 else j:=m endif x=ai then location:=i else location:=0 location=i if x=ai,location=0 if xai,i Exercise3.113(b).列出二元搜尋用來從序列1,3,4,5,6,8,9,11中尋找9的步驟Ch3-12參考：參考：procedure binary_search(x:integer,a1,a2,an:increasing integers)i:=1 i is left endpoint of search interval j:=n j is right endpoint of search interval while i am then i:=m+1 else j:=m endif x=ai then location:=i else location:=0 location=i if x=ai;location=0 if xai,i 13(補充).列出二元搜尋用來從序列2,4,6,8,10,12,14中尋找3的步驟。

Ch3-13參考：參考：procedure binary_search(x:integer,a1,a2,an:increasing integers)i:=1 i is left endpoint of search interval j:=n j is right endpoint of search interval while i am then i:=m+1 else j:=m endif x=ai then location:=i else location:=0 location=i if x=ai;location=0 if xai,i Ch3-14nProblem:Supposethatwehavealistofelements,asortingisputtingtheseelementsintoalistinwhichtheelementsareinincreasingorder.neg.7,2,1,4,5,9=1,2,4,5,7,9d,t,c,a,f=a,c,d,f,tn解法有很多，此處僅介紹:bubblesort(氣泡排序法)，及insertionsort(插入排序法)。

nBubbleSort概念:設原list為a1,an從a1,a2開始，向後兩兩比較，若aiai+1則交換，當檢查完an時，an必定是最大數再從a1,a2開始向後比較，若aiai+1則交換，此時只需檢查到an-1即可依此類推SortingAlgorithms(跳過)Ch3-15nExample 4.Usethebubblesorttoput3,2,4,1,5intoincreasingorder.nSol:32415First pass(i=1):234152341523145Second pass(i=2):Third pass(i=3):Fourth pass(i=4):12345231452314521345213452314521345123451234512345(跳過)Ch3-16 Algorithm 4 The Bubble Sort procedure bubble_sort(a1,an)for i:=1 to n-1 for j:=1 to n-i if aj aj+1 then interchange aj and aj+1 a1,a2,an is in increasing order(跳過)Ch3-17nInsertionSort的概念:從j=2開始，將aj 插入已排序好的a1,aj-1間的位置，使得a1,aj都由小大排好。

j 逐次遞增，重複上一步驟至做完跳過)Ch3-18nExample 5.Useinsertionsorttosort3,2,4,1,5nSol:(j=2時，a1=3可看成已經排序好的數列，此時要插入a2):3 2,4 3 4的位置不變 2,3,4,1,5 (j=4時，a1,a2,a3已經排序好，此時要插入a4):1 1,5 2,5 3,5 4 5不變 1,2,3,4,5a1 a2 a3 a4 a5(跳過)Ch3-19Algorithm 5 The Insertion Sortprocedure insertion_sort(a1,an:real numbers with n 2)for j:=2 to n begin i:=1 while aj ai。