《算法設計與分析》第4章窮舉法概要課件

第4章窮舉法2022/11/101成都學院計算機系第4章窮舉法2022/11/91成都學院計算機系4.1窮舉法的設計思想4.2漸近表示法

4.3算法分析2022/11/102成都學院計算機系4.1窮舉法的設計思想2022/11/92成都學院計算機主要知識點掌握好算法的評價標準;了解影響程序運行時間的因素;掌握算法的評價標準:時間復雜度和空間復雜度的概念;掌握漸近時間復雜度的幾種表示方式;掌握常見時間復雜度漸近表示之間的關系.2022/11/103成都學院計算機系主要知識點掌握好算法的評價標準;2022/11/93成都學院4.1窮舉法思想2022/11/104成都學院計算機系4.1窮舉法思想2022/11/94成都學院計算機系一、窮舉法定義是一種簡單而直接地解決問題的方法，常常直接基于問題的描述。是最容易應用的方法，其時間性能比較低。通常典型的指數(shù)時間算法一般都是通過窮舉法搜索而得到的。2022/11/105成都學院計算機系一、窮舉法定義是一種簡單而直接地解決問題的方法，常二、設計思想采用的基本技術是掃描技術，即使用一定的策略將待求解問題的所有元素依次處理一次，從而找到問題的解。為了避免重復試探，在基本的數(shù)據(jù)結(jié)構中采用遍歷來處理每一個元素。2022/11/106成都學院計算機系二、設計思想采用的基本技術是掃描技術，即使用一定的策略將待求（1）集合的遍歷按照元素序號的順序依次處理每個元素。（2）線性表的遍歷元素序號，如數(shù)組是按元素的下標來處理。（3）樹的遍歷先序、中序、后序2022/11/107成都學院計算機系（1）集合的遍歷2022/11/97成都學院計算機系三、采用窮舉法的原因理論上可以解決可計算領域的各種問題。經(jīng)常用來解決一些較小規(guī)模的問題。對一些重要問題（排序、查找、字符串匹配等）有一些實用價值，且不受問題規(guī)模的限制?？勺鳛槟愁悊栴}時間性能下限，進行高效算法的比較。2022/11/108成都學院計算機系三、采用窮舉法的原因理論上可以解決可計算領域的各種問題。204.2查找問題中的窮舉法順序查找思想：從表的一端向另一端逐個將元素與給定值進行比較，若相等，查找成功，給出該元素的具體位置；若整個表檢測完仍未找到與給定值相等的元素，則查找失??！2022/11/109成都學院計算機系4.2查找問題中的窮舉法順序查找2022/11/99成假設以n個數(shù)放入數(shù)組r[1]～r[n]中，查找值k的算法。

intSeqsearch(intr[],intn,intk){i=n;while(i>0&&r[i]!=k)i--;returni;}2022/11/1010成都學院計算機系假設以n個數(shù)放入數(shù)組r[1]～r[n]中，查找值k的算法。2其基本語句i>0和r[i]!=k，其執(zhí)行次數(shù)缺陷：每次都要判斷下標i是否越界。2022/11/1011成都學院計算機系其基本語句i>0和r[i]!=k，其執(zhí)行次數(shù)2022/11改進方法：哨兵將k放入到r[0]中，每次將r[1]～r[n]中的值與r[0]進行比較。intSeqsearch(intr[],intn,intk){i=n;r[0]=k;while(r[i]!=k)i--;returni;}2022/11/1012成都學院計算機系改進方法：哨兵將k放入到r[0]中，每次將r[1]～r其基本語句i>0和r[i]!=k，其執(zhí)行次數(shù)比較順序查找方法，減少了系數(shù)。2022/11/1013成都學院計算機系其基本語句i>0和r[i]!=k，其執(zhí)行次數(shù)2022/114.3排序問題中的窮舉法一、選擇排序思想：開始掃描整個序列，找到最小記錄和序列中的第一個記錄交換，再從第二個記錄掃描，找到最小記錄與第二個記錄交換，直到掃描第n-1個記錄與第n個記錄進行交換，使得整個序列有序。2022/11/1014成都學院計算機系4.3排序問題中的窮舉法一、選擇排序2022/11/914一般情況，第i趟排序從第i個記錄開始掃描序列，在n-i+1(1≤i≤n)個記錄中找最小記錄，并與第i個記錄進行交換。2022/11/1015成都學院計算機系一般情況，第i趟排序從第i個記錄開始掃描序列，在n-i+1(VoidSelectsort(intr[],intn){for(i=1;i<=n-1;i++){index=i;for(j=i+1;j<=n;j++)//找最小記錄if(r[j]<r[index])index=j;if(index!=i)r[j]>r[index];}}2022/11/1016成都學院計算機系VoidSelectsort(intr[],intn)基本語句內(nèi)層循環(huán)中的r[j]<r[index]，其執(zhí)行次數(shù)為：選擇排序最多交換n-1次數(shù)據(jù)。

2022/11/1017成都學院計算機系基本語句內(nèi)層循環(huán)中的r[j]<r[index]，其執(zhí)行次數(shù)二、冒泡排序一開始就掃描整個序列，在掃描的過程中兩兩比較相鄰記錄，如反序則交換，最終將最大記錄置于最后一個記錄位置，第二大記錄置于倒數(shù)第二個記錄位置，重復至整個序列有序。2022/11/1018成都學院計算機系二、冒泡排序2022/11/918成都學院計算機系VoidBubblesort(intr[],intn){for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++)//找最小記錄if(r[j]<r[j+1])r[j]>r[j+1];}

2022/11/1019成都學院計算機系VoidBubblesort(intr[],intn)基本語句內(nèi)層循環(huán)中的r[j]<r[j+1]，其執(zhí)行次數(shù)為：不足：如果整個序列已經(jīng)有序，還是要直接整個外循環(huán)執(zhí)行完。思想有沒有改進的辦法？有則寫出算法。2022/11/1020成都學院計算機系基本語句內(nèi)層循環(huán)中的r[j]<r[j+1]，其執(zhí)行次數(shù)為：4.5幾何問題中的窮舉法最近對問題要求找出一個包含n個點的集合中距離最近的兩個點。應用實例：空中交通2022/11/1021成都學院計算機系4.5幾何問題中的窮舉法最近對問題2022/11/921前提假設

1.二維空間中的點，并且點的坐標形式(x,y)給出的。

2.若Pi=(xi,yi),Pj=(xj,yj)，則其間距離d:

最近對問題的求解過程：分別計算每一對點之間的距離，然后找出距離最小的那一對，只考慮i<j的那些點對。

2022/11/1022成都學院計算機系前提假設2022/11/922成都學院計算機系intclosetpoint(intn,intx[],inty[],int&index1,int&index2){mindist=+∞;for(i=1;i<n;i++)for(j=i+1;j<=n;j++){d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);if(d<mindist){mindist=d;index1=i;index2=j;}}returnmindist;}2022/11/1023成都學院計算機系intclosetpoint(intn,intx[],實驗—串匹配題目：給定一個文本，在該文本中查找并定位任意給定字符串實驗目的：理解并掌握窮舉法的設計思想；實驗要求：

1.實現(xiàn)BF算法及對其的改進算法BM算法

2.對BF、BM進行時間復雜度的分析并編程驗證。2022/11/1024成都學院計算機系實驗—串匹配題目：給定一個文本，在該文本中查找并定位任意給定BM算法基本思想：假設將主串中自位置i起往左的一個子串與模式進行從右到左的匹配過程中，若發(fā)現(xiàn)不匹配，則下次應從主串的i+dist(si)位置開始重新進行新一輪的匹配，其效果相當于把模式和主串均右滑過一段距離dist(si),即跳過dist(si)個字符而無需進行比較。2022/11/1025成都學院計算機系BM算法基本思想：假設將主串中自位置i起往左的一個子串與模式假設字符表{a,b,c,……,z}，BM算法對給定的模式T=“t1t2…tm”,定義一個從字符到正整數(shù)的映射：

dist:c{1,2,…，m},c屬于字符表滑動函數(shù)給出了正文中可能出現(xiàn)的任意字符在模式中的位置，定義如下：

m-jj=max{j|tj=c且1≤j≤m-1

dist(c)=c若c不出現(xiàn)在模式中或tm=c2022/11/1026成都學院計算機系假設字符表{a,b,c,……,z}，BM算法對給定的模式T=IntBM(chars[],chart[],intn,intm){i=m;//模式串長度

while(i<=n){j=m;while(j>0&&s[i]==t[j]){j--;i--;}if(j==0)returni+1;elsei=i+dist(s[i]);}return0;}2022/11/1027成都學院計算機系IntBM(chars[],chart[],intn第4章窮舉法2022/11/1028成都學院計算機系第4章窮舉法2022/11/91成都學院計算機系4.1窮舉法的設計思想4.2漸近表示法

4.3算法分析2022/11/1029成都學院計算機系4.1窮舉法的設計思想2022/11/92成都學院計算機主要知識點掌握好算法的評價標準;了解影響程序運行時間的因素;掌握算法的評價標準:時間復雜度和空間復雜度的概念;掌握漸近時間復雜度的幾種表示方式;掌握常見時間復雜度漸近表示之間的關系.2022/11/1030成都學院計算機系主要知識點掌握好算法的評價標準;2022/11/93成都學院4.1窮舉法思想2022/11/1031成都學院計算機系4.1窮舉法思想2022/11/94成都學院計算機系一、窮舉法定義是一種簡單而直接地解決問題的方法，常常直接基于問題的描述。是最容易應用的方法，其時間性能比較低。通常典型的指數(shù)時間算法一般都是通過窮舉法搜索而得到的。2022/11/1032成都學院計算機系一、窮舉法定義是一種簡單而直接地解決問題的方法，常二、設計思想采用的基本技術是掃描技術，即使用一定的策略將待求解問題的所有元素依次處理一次，從而找到問題的解。為了避免重復試探，在基本的數(shù)據(jù)結(jié)構中采用遍歷來處理每一個元素。2022/11/1033成都學院計算機系二、設計思想采用的基本技術是掃描技術，即使用一定的策略將待求（1）集合的遍歷按照元素序號的順序依次處理每個元素。（2）線性表的遍歷元素序號，如數(shù)組是按元素的下標來處理。（3）樹的遍歷先序、中序、后序2022/11/1034成都學院計算機系（1）集合的遍歷2022/11/97成都學院計算機系三、采用窮舉法的原因理論上可以解決可計算領域的各種問題。經(jīng)常用來解決一些較小規(guī)模的問題。對一些重要問題（排序、查找、字符串匹配等）有一些實用價值，且不受問題規(guī)模的限制?？勺鳛槟愁悊栴}時間性能下限，進行高效算法的比較。2022/11/1035成都學院計算機系三、采用窮舉法的原因理論上可以解決可計算領域的各種問題。204.2查找問題中的窮舉法順序查找思想：從表的一端向另一端逐個將元素與給定值進行比較，若相等，查找成功，給出該元素的具體位置；若整個表檢測完仍未找到與給定值相等的元素，則查找失?。?022/11/1036成都學院計算機系4.2查找問題中的窮舉法順序查找2022/11/99成假設以n個數(shù)放入數(shù)組r[1]～r[n]中，查找值k的算法。

intSeqsearch(intr[],intn,intk){i=n;while(i>0&&r[i]!=k)i--;returni;}2022/11/1037成都學院計算機系假設以n個數(shù)放入數(shù)組r[1]～r[n]中，查找值k的算法。2其基本語句i>0和r[i]!=k，其執(zhí)行次數(shù)缺陷：每次都要判斷下標i是否越界。2022/11/1038成都學院計算機系其基本語句i>0和r[i]!=k，其執(zhí)行次數(shù)2022/11改進方法：哨兵將k放入到r[0]中，每次將r[1]～r[n]中的值與r[0]進行比較。intSeqsearch(intr[],intn,intk){i=n;r[0]=k;while(r[i]!=k)i--;returni;}2022/11/1039成都學院計算機系改進方法：哨兵將k放入到r[0]中，每次將r[1]～r其基本語句i>0和r[i]!=k，其執(zhí)行次數(shù)比較順序查找方法，減少了系數(shù)。2022/11/1040成都學院計算機系其基本語句i>0和r[i]!=k，其執(zhí)行次數(shù)2022/114.3排序問題中的窮舉法一、選擇排序思想：開始掃描整個序列，找到最小記錄和序列中的第一個記錄交換，再從第二個記錄掃描，找到最小記錄與第二個記錄交換，直到掃描第n-1個記錄與第n個記錄進行交換，使得整個序列有序。2022/11/1041成都學院計算機系4.3排序問題中的窮舉法一、選擇排序2022/11/914一般情況，第i趟排序從第i個記錄開始掃描序列，在n-i+1(1≤i≤n)個記錄中找最小記錄，并與第i個記錄進行交換。2022/11/1042成都學院計算機系一般情況，第i趟排序從第i個記錄開始掃描序列，在n-i+1(VoidSelectsort(intr[],intn){for(i=1;i<=n-1;i++){index=i;for(j=i+1;j<=n;j++)//找最小記錄if(r[j]<r[index])index=j;if(index!=i)r[j]>r[index];}}2022/11/1043成都學院計算機系VoidSelectsort(intr[],intn)基本語句內(nèi)層循環(huán)中的r[j]<r[index]，其執(zhí)行次數(shù)為：選擇排序最多交換n-1次數(shù)據(jù)。

2022/11/1044成都學院計算機系基本語句內(nèi)層循環(huán)中的r[j]<r[index]，其執(zhí)行次數(shù)二、冒泡排序一開始就掃描整個序列，在掃描的過程中兩兩比較相鄰記錄，如反序則交換，最終將最大記錄置于最后一個記錄位置，第二大記錄置于倒數(shù)第二個記錄位置，重復至整個序列有序。2022/11/1045成都學院計算機系二、冒泡排序2022/11/918成都學院計算機系VoidBubblesort(intr[],intn){for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++)//找最小記錄if(r[j]<r[j+1])r[j]>r[j+1];}

2022/11/1046成都學院計算機系VoidBubblesort(intr[],intn)基本語句內(nèi)層循環(huán)中的r[j]<r[j+1]，其執(zhí)行次數(shù)為：不足：如果整個序列已經(jīng)有序，還是要直接整個外循環(huán)執(zhí)行完。思想有沒有改進的辦法？有則寫出算法。2022/11/1047成都學院計算機系基本語句內(nèi)層循環(huán)中的r[j]<r[j+1]，其執(zhí)行次數(shù)為：4.5幾何問題中的窮舉法最近對問題要求找出一個包含n個點的集合中距離最近的兩個點。應用實例：空中交通2022/11/1048成都學院計算機系4.5幾何問題中的窮舉法最近對問題2022/11/921前提假設

1.二維空間中的點，并且點的坐標形式(x,y)給出的。

2.若Pi=(xi,yi),Pj=(xj,yj)，則其間距離d:

最近對問題的求解過程：分別計算每一對點之間的距離，然后找出距離最小的那一對，只考慮i<j的那些點對。

2022/11/1049成都學院計算機系前提假設2022/11/922成都學院計算機系intclosetpoint(intn,intx[],inty[],int&index1,int&index2){mindist=+∞;for(i=1;i<n;i++)for(j=i+1;j<=n;j++){d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);if(d<mindist){mindist=d;index1=i;index2=j;}}returnmindist;}2022/11/1050成都學院計算機系intclosetpoint(intn,intx[],實驗—串匹配題目：給定一個文本，在該文本中查找并定位任意給定字符串實驗目的：理解并掌握窮舉法的設計思想；