標(biāo)題: 計(jì)算機(jī)算法基礎(chǔ)實(shí)驗(yàn)程序及運(yùn)行結(jié)果 [打印本頁(yè)]
作者: HungryTang    時(shí)間: 2019-10-29 21:11
標(biāo)題: 計(jì)算機(jī)算法基礎(chǔ)實(shí)驗(yàn)程序及運(yùn)行結(jié)果
一找最大和最小元素與歸并分類算法實(shí)現(xiàn)（用分治法）
一、實(shí)驗(yàn)?zāi)康?br />
1．掌握能用分治法求解的問題應(yīng)滿足的條件；
2．加深對(duì)分治法算法設(shè)計(jì)方法的理解與應(yīng)用；
3．鍛煉學(xué)生對(duì)程序跟蹤調(diào)試能力；
4．通過(guò)本次實(shí)驗(yàn)的練習(xí)培養(yǎng)學(xué)生應(yīng)用所學(xué)知識(shí)解決實(shí)際問題的能力。
二．實(shí)驗(yàn)內(nèi)容

（1）找最大最小元素：輸入n個(gè)數(shù)，找出最大和最小數(shù)的問題。
（2）歸并分類：對(duì)n個(gè)數(shù)用歸并方法排序。
三．實(shí)驗(yàn)要求

（1）用分治法求解問題
（2）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；
四．實(shí)驗(yàn)過(guò)程設(shè)計(jì)（算法設(shè)計(jì)過(guò)程）

常規(guī)的做法是遍歷一次，分別求出最大值和最小值，但我這里要說(shuō)的是分治法(Divide and couquer)，將數(shù)組分成左右兩部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后綜合起來(lái)求總體的最大值及最小值。這是個(gè)遞歸過(guò)程，對(duì)于劃分后的左右兩部分，同樣重復(fù)這個(gè)過(guò)程，直到劃分區(qū)間內(nèi)只剩一個(gè)元素或者兩個(gè)元素。

解決問題的策略:

蠻力策略：對(duì)金塊逐個(gè)進(jìn)行比較查找。（掃描數(shù)組一輪，尋找最大和最小的數(shù)。）該策略需要進(jìn)行（n－1）次的比較才能得到max和min。
分治法（二分法）策略：?jiǎn)栴}可以簡(jiǎn)化為在n個(gè)數(shù)里面尋找最大和最小值。
（1）將數(shù)據(jù)等分為兩組(兩組數(shù)據(jù)的個(gè)數(shù)可能相差1)，目的是分別選取其中的最大（小）值。
（2）遞歸分解直到每組元素的個(gè)數(shù)<=2，則可以簡(jiǎn)單地找到其中的最大（�。┲怠�
（3）回溯時(shí)合并子問題的解，在兩個(gè)子問題的解中大者取大，小者取小，即合并為當(dāng)前問題的解。

五．源代碼

（1）找最大最小元素：
  1. #include <iostream>
  2. using namespace std;

  4. void findMinMax(int a[],int l,int r,int *maxnum,int *minnum){
  5.    if(l==r){//如果只有一個(gè)元素，則最小最大都是這個(gè)元素
  6.         *maxnum = *minnum = a[l];
  7.         return;
  8.     }
  9.     int mid,lmin,rmin,lmax,rmax;
  10.     mid = (l+r)/2;
  11.     findMinMax(a,l,mid,&lmax,&lmin);//尋找數(shù)組左邊的最大最小元素
  12.     findMinMax(a,mid+1,r,&rmax,&rmin);//尋找數(shù)組右邊的最大最小元素
  13.     *maxnum = lmax>rmax?lmax:rmax;//比較左右邊的最大元素找出更大的
  14.     *minnum = lmin<rmin?lmin:rmin;//比較左右邊的最小元素找出更小的
  15. }
  16. int main()
  17. {
  18.     int a[] = {1,2,3,4,5,6,7,8,9};
  19.     int max,min;
  20.     findMinMax(a,0,8,&max,&min);
  21.     cout<<"max = "<<max<<"\n";
  22.     cout<<"min = "<<min<<"\n";
  23.     return 0;
  24. }
復(fù)制代碼

程序運(yùn)行結(jié)果如下圖所示：
（2）歸并分類：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void merge(int low,int mid,int high,int a[]){
  4.     int h,i,j,k;
  5.     h = i = low;
  6.     j = mid+1;//把數(shù)組a從mid分成兩個(gè)集合
  7.     int b[high];//數(shù)組b為輔助數(shù)組
  8.     while(h <= mid && j <= high){//當(dāng)兩個(gè)集合都沒有取盡時(shí)
  9.         if(a[h] <= a[j]){
  10.             b[i] = a[h];
  11.             h++;
  12.         }else{
  13.             b[i] = a[j];
  14.             j++;
  15.         }
  16.         i++;
  17.     }
  18.     /*處理剩余的元素*/
  19.     if(h > mid){//前一個(gè)數(shù)組先取完
  20.         for(k = j;k <= high;k++){
  21.             b[i] = a[k];
  22.             i++;
  23.         }
  24.     }else{//后一個(gè)數(shù)組先取完
  25.         for(k = h;k <= mid;k++){
  26.             b[i] = a[k];
  27.             i++;
  28.         }
  29.     }
  30.     /*將已經(jīng)合并的集合從輔助數(shù)組復(fù)制到原數(shù)組*/
  31.     for(k = low;k <= high;k++){
  32.         a[k] = b[k];
  33.     }
  34. }

  36. void mergeSort(int low,int high,int a[]){
  37.     if(low < high){
  38.         int mid = (low+high)/2;//求集合的分割點(diǎn)
  39.         mergeSort(low,mid,a);//將前半個(gè)集合分類
  40.         mergeSort(mid+1,high,a);//將后半個(gè)集合分類
  41.         merge(low,mid,high,a);//歸并兩個(gè)已經(jīng)分類的集合
  42.     }
  43. }

  45. int main()
  46. {
  47.     int a[] = {2,4,3,6,1,7,8,5,9};
  48.     mergeSort(0,8,a);
  49.     for(int i = 0;i <= 6;i++){
  50.         printf("\t%d\n",a[i]);
  51.     }
  52.     return 0;
  53. }
復(fù)制代碼

程序運(yùn)行結(jié)果如下圖所示：

實(shí)驗(yàn)二 背包問題和最小生成樹算法實(shí)現(xiàn)（用貪心法）
一、實(shí)驗(yàn)?zāi)康?br />
1．掌握能用貪心法求解的問題應(yīng)滿足的條件；
2．加深對(duì)貪心法算法設(shè)計(jì)方法的理解與應(yīng)用；
3．鍛煉學(xué)生對(duì)程序跟蹤調(diào)試能力；
4．通過(guò)本次實(shí)驗(yàn)的練習(xí)培養(yǎng)學(xué)生應(yīng)用所學(xué)知識(shí)解決實(shí)際問題的能力。
二．實(shí)驗(yàn)內(nèi)容

有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘俊?br /> 三．實(shí)驗(yàn)要求

（1）用貪心法求解背包問題；
（2）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；
四．實(shí)驗(yàn)過(guò)程設(shè)計(jì)（算法設(shè)計(jì)過(guò)程）

貪心算法（又稱貪婪算法）是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。
    貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無(wú)后效性，即某個(gè)狀態(tài)以前的過(guò)程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。
基本思路
建立數(shù)學(xué)模型來(lái)描述問題；
把求解的問題分成若干個(gè)子問題；
對(duì)每一子問題求解，得到子問題的局部最優(yōu)解；
把子問題的解局部最優(yōu)解合成原來(lái)解問題的一個(gè)解。
算法實(shí)現(xiàn)
從問題的某個(gè)初始解出發(fā)。
采用循環(huán)語(yǔ)句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局部最優(yōu)策略，得到一個(gè)部分解，縮小問題的范圍或規(guī)模。
將所有部分解綜合起來(lái)，得到問題的最終解。
實(shí)例分析
實(shí)例1 背包問題
問題描述
有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘俊?/div>
三種策略

五．源代碼

（1）背包問題
  1. #include <iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. /*定義物品的結(jié)構(gòu)體*/
  5. struct Object{
  6.     double weight;//物品重量
  7.     double value;//物品價(jià)值
  8.     double avg;//單位重量?jī)r(jià)值
  9.     double prop;//放入比例：0表示沒有放入,1表示全部放入
  10. };

  12. /*定義物品排序的標(biāo)準(zhǔn)*/
  13. bool cmp(Object a,Object b){
  14.     return a.avg>b.avg;
  15. }

  17. int main()
  18. {
  19.     Object *ob;
  20.     double volume;//背包容量
  21.     int num;//物品種類
  22.     double maxValue = 0;//背包中的最大價(jià)值
  23.     cout<<"請(qǐng)輸入所有物品數(shù)量和背包容量\n";
  24.     cin>>num>>volume;
  25.     ob = new Object[num];
  26.     /*初始化物品的重量和價(jià)值，并計(jì)算單位重量?jī)r(jià)值*/
  27.     for(int i = 0;i<num;i++){
  28.         cout<<"輸入第"<<i+1<<"個(gè)物品的重量和價(jià)值\n";
  29.         cin>>ob[i].weight>>ob[i].value;
  30.         ob[i].avg = ob[i].value/ob[i].weight;
  31.     }
  32.     sort(ob,ob+num,cmp);//物品按單位重量?jī)r(jià)值降序
  33.     int i;
  34.     /*開始裝入物品*/
  35.     for(i = 0;i<num;i++){
  36.         if(ob[i].weight <= volume){//如果這個(gè)物品能全部裝入
  37.             volume =  volume -ob[i].weight;
  38.             ob[i].prop = 1;//表示全部裝入
  39.             maxValue = maxValue + ob[i].value;
  40.         } else{//這個(gè)物品已經(jīng)不能全部裝人
  41.             break;
  42.         }
  43.     }
  44.     if(i<num){//有一個(gè)物品不能全部裝入
  45.             ob[i].prop = volume/ob[i].weight;//裝入的比例
  46.             volume = 0;
  47.             maxValue = maxValue + ob[i].prop*ob[i].value;
  48.     }
  49.     cout<<"放入的物品的重量，價(jià)值，比例\n";
  50.     for(int i = 0;i<num;i++){
  51.         cout<<ob[i].weight<<" "<<ob[i].value<<" "<<ob[i].prop<<"\n";
  52.    }
  53.     cout<<"放入物品的總價(jià)值:"<<maxValue;
  54.     return 0;
  55. }
復(fù)制代碼


程序運(yùn)行結(jié)果：
（2）最小生成樹
  1. /*
  2. S:當(dāng)前已經(jīng)在聯(lián)通塊中的所有點(diǎn)的集合
  3. 1. dist[i] = inf
  4. 2. for n 次
  5.     t<-S外離S最近的點(diǎn)
  6.     利用t更新S外點(diǎn)到S的距離
  7.     st[t] = true
  8. n次迭代之后所有點(diǎn)都已加入到S中
  9. 聯(lián)系：Dijkstra算法是更新到起始點(diǎn)的距離，Prim是更新到集合S的距離
  10. */
  11. #include <iostream>
  12. #include <cstring>
  13. using namespace std;
  14. const int N = 510, INF = 0x3f3f3f3f;

  16. int n, m;//n=|V|，m=|E|
  17. int g[N][N], dist[N];
  18. //鄰接矩陣存儲(chǔ)所有邊
  19. //dist存儲(chǔ)其他點(diǎn)到S的距離
  20. bool st[N];

  22. int prim() {
  23.     //如果圖不連通返回INF, 否則返回res
  24.     memset(dist, INF, sizeof dist);
  25.     int res = 0;

  27.     for(int i = 0; i < n; i++) {
  28.         int t = -1;
  29.         for(int j = 1; j <= n; j++)
  30.             if(!st[j] && (t == -1 || dist[t] > dist[j]))
  31.                 t = j;
  32.         //尋找離集合S最近的點(diǎn)
  33.         if(i && dist[t] == INF) return INF;
  34.         //判斷是否連通，有無(wú)最小生成樹

  36.         if(i) res += dist[t];
  37.         //cout << i << ' ' << res << endl;
  38.         st[t] = true;
  39.         //更新最新S的權(quán)值和

  41.         for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
  42.     }

  44.     return res;
  45. }

  47. int main() {
  48.     cout << "頂點(diǎn)數(shù)和邊數(shù):" << endl;
  49.     cin >> n >> m;//n=|V|，m=|E|
  50.     int u, v, w;//u，v，w，表示點(diǎn)u和點(diǎn)v之間存在一條權(quán)值為w的邊

  52.     for(int i = 1; i <= n; i++)
  53.         for(int j = 1; j <= n; j++)
  54.             if(i ==j) g[i][j] = 0;
  55.             else g[i][j] = INF;

  57.     while(m--) {
  58.         cout<< "兩頂點(diǎn)和邊長(zhǎng)：" << endl;
  59.         cin >> u >> v >> w;
  60.         g[u][v] = g[v][u] = min(g[u][v], w);
  61.     }
  62.     int t = prim();
  63.     cout <<"最小生成樹的樹邊權(quán)重之和:"<< t << endl;
  64. }
復(fù)制代碼

程序運(yùn)行結(jié)果：

實(shí)驗(yàn)三 多段圖和貨郎擔(dān)問題算法實(shí)現(xiàn)（用動(dòng)態(tài)規(guī)劃方法）
一．實(shí)驗(yàn)?zāi)康?br />
1．掌握能用動(dòng)態(tài)規(guī)劃方法求解的問題應(yīng)滿足的條件；
2．加深對(duì)動(dòng)態(tài)規(guī)劃方法的理解與應(yīng)用；
3．鍛煉學(xué)生對(duì)程序跟蹤調(diào)試能力；
4．通過(guò)本次實(shí)驗(yàn)的練習(xí)培養(yǎng)學(xué)生應(yīng)用所學(xué)知識(shí)解決實(shí)際問題的能力。
二．實(shí)驗(yàn)內(nèi)容

              (1)多段圖：對(duì)于任意數(shù)目的n個(gè)節(jié)點(diǎn)，分別用1～n編號(hào)，對(duì)于k段，分別用1～k編號(hào)，則這個(gè)問題歸結(jié)為在k段n個(gè)節(jié)點(diǎn)的帶權(quán)圖中尋找從節(jié)點(diǎn)1到節(jié)點(diǎn)n的最短路徑。（自己添加的內(nèi)容）
              (2)貨郎擔(dān)：對(duì)于任意數(shù)目的n個(gè)城市，分別用1～n編號(hào)，則這個(gè)問題歸結(jié)為在有向帶權(quán)圖中，尋找一條路徑最短的哈密爾頓回路問題。
三．實(shí)驗(yàn)要求

（1）用動(dòng)態(tài)規(guī)劃方法貨郎擔(dān)問題；實(shí)現(xiàn)多段圖問題
（2）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；
四．實(shí)驗(yàn)過(guò)程設(shè)計(jì)（算法設(shè)計(jì)過(guò)程）

動(dòng)態(tài)規(guī)劃的思想實(shí)質(zhì)是分治思想和解決冗余。 與分治法類似的是，將原問題分解成若干個(gè)子問題，先求解子問題，再?gòu)倪@些子問題的解得到原問題的解。與分治法不同的是，經(jīng)分解的子問題往往不是互相獨(dú)立的。若用分治法來(lái)解，有些共同部分（子問題或子子問題）被重復(fù)計(jì)算了很多次。如果能夠保存已解決的子問題的答案，在需要時(shí)再查找，這樣就可以避免重復(fù)計(jì)算、節(jié)省時(shí)間。動(dòng)態(tài)規(guī)劃法用一個(gè)表來(lái)記錄所有已解的子問題的答案。
動(dòng)態(tài)規(guī)劃方法的基本思想是，把求解的問題分成許多階段或多個(gè)子問題，然后按順序求解各子問題。最后一個(gè)子問題就是初始問題的解。
由于動(dòng)態(tài)規(guī)劃的問題有重疊子問題的特點(diǎn)，為了減少重復(fù)計(jì)算，對(duì)每一個(gè)子問題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。
五．源代碼

（1）多段圖
  1. #include <iostream>
  2. using namespace std;
  3. #define INFI 65535 //定義兩節(jié)點(diǎn)之間的最大路徑
  4. int c[12][12]; //兩節(jié)點(diǎn)之間路徑長(zhǎng)度的數(shù)組

  6. /**/
  7. void FGRAPH(int n,int k){
  8.     int cost[n];//第n個(gè)節(jié)點(diǎn)到最后一個(gè)節(jié)點(diǎn)的最端路徑
  9.    for(int i = 0;i<n;i++){
  10.         cost[i] = INFI;//初始化所有節(jié)點(diǎn)的最短路徑為無(wú)窮大
  11.     }
  12.     cost[n-1] = 0;
  13.     int j,r;
  14.     int p[k],d[n];//p為段決策，d為節(jié)點(diǎn)決策
  15.     int min;
  16.     /*尋找所有節(jié)點(diǎn)到最后一個(gè)節(jié)點(diǎn)的最短路徑和節(jié)點(diǎn)決策）*/
  17.     for(j = n-2;j>=0;j--){
  18.         min = INFI;
  19.         for(r = 0;r<=n-1;r++){
  20.             if(c[j][r]+cost[r]<min){
  21.                 min = c[j][r] + cost[r];
  22.                 d[j] = r; //r即為j節(jié)點(diǎn)的節(jié)點(diǎn)的決策
  23.             }
  24.         }
  25.         cost[j] = min; //j節(jié)點(diǎn)的最短路徑
  26.     }
  27.     p[0] = 0;
  28.     p[k-1] = n-1;
  29.     for(int j = 1;j<=k-1;j++){
  30.         p[j] = d[p[j-1]];//上一個(gè)段的段決策的節(jié)點(diǎn)決策即為下一個(gè)段的段決策
  31.     }
  32.     for(int j = 0;j<=k-1;j++){
  33.         cout<<p[j]<<"\n";
  34.     }
  35. }
  36. int main()
  37. {
  38.     int N = 12;
  39.     /*節(jié)點(diǎn)之間距離初始化*/
  40.     for(int i = 0;i<N;i++){
  41.         for(int j = 0;j<N;j++){
  42.             if(i == j)
  43.                 c[i][j] = 0;
  44.             else{
  45.                 c[i][j] = INFI;
  46.                 c[j][i] = INFI;
  47.             }

  49.         }
  50.     }
  51.     c[0][1] = 9;
  52.     c[0][2] = 7;
  53.     c[0][3] = 3;
  54.     c[0][4] = 2;
  55.     c[1][5] = 4;
  56.     c[1][6] = 2;
  57.     c[1][7] = 1;
  58.    c[2][5] = 2;
  59.     c[2][6] = 7;
  60.     c[3][7] = 11;
  61.     c[4][6] = 11;
  62.     c[4][7] = 8;
  63.     c[5][8] = 6;
  64.     c[5][9] = 5;
  65.     c[6][8] = 4;
  66.     c[6][9] = 3;
  67.     c[7][9] = 5;
  68.     c[7][10] = 6;
  69.     c[8][11] = 4;
  70.     c[9][11] = 2;
  71.     c[10][11] = 5;
  72.     FGRAPH(N,5);//調(diào)用多段圖函數(shù)
  73.     return 0;
  74. }
復(fù)制代碼

程序運(yùn)行結(jié)果如下圖所示：

(2) 貨郎擔(dān)
  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;

  5. int n;
  6. int cost[20][20];
  7. bool done[20]={1};
  8. int start = 0; //從城市0開始
  9. int imin(int num, int cur)
  10. {
  11.     if(num==1) //遞歸調(diào)用的出口
  12.         return cost[cur][start];  //所有節(jié)點(diǎn)的最后一個(gè)節(jié)
  13. //最后返回 最后一個(gè)節(jié)點(diǎn)到起點(diǎn)的路徑
  14.     int  mincost = 10000;
  15.     for(int i=0; i<n; i++)
  16.     {
  17.         cout<<i<<"  i:"<<done[i]<<endl;  
  18.         if(!done[i] && i!=start) //該結(jié)點(diǎn)沒加入且非起始點(diǎn)
  19.         {
  20.             done[i] = 1;   //遞歸調(diào)用時(shí)，防止重復(fù)調(diào)用
  21.             int value = cost[cur][i] + imin(num-1, i);
  22.             if(mincost > value)
  23.             {
  24.                 mincost = value;
  25.                 cout<<mincost<<endl;
  26.             }
  27.             done[i] = 0;//本次遞歸調(diào)用完畢，讓下次遞歸調(diào)用
  28.         }
  29.     }
  30.     return mincost;
  31. }

  33. int main()
  34. {   
  35.     n=4;
  36.     int cc[4][4]={{0,4,1,3},{4,0,2,1},{1,2,0,5},{3,1,5,0}};
  37.     for(int i=0; i<n; i++)
  38.    {
  39.         for(int j=0; j<n; j++)
  40.         {
  41.             cost[i][j]=cc[i][j];
  42.         }
  43.     }
  44.     cout << imin(n, start) << endl;
  45.     return 0;
  46. }
復(fù)制代碼

程序運(yùn)行結(jié)果如下圖所示：
   
實(shí)驗(yàn)四 皇后與子集和數(shù)問題算法實(shí)現(xiàn)（用回溯法）
一、實(shí)驗(yàn)?zāi)康?/div>

1．掌握能用回溯法求解的問題應(yīng)滿足的條件；

2．加深對(duì)回溯法算法設(shè)計(jì)方法的理解與應(yīng)用；

3．鍛煉學(xué)生對(duì)程序跟蹤調(diào)試能力；

4．通過(guò)本次實(shí)驗(yàn)的練習(xí)培養(yǎng)學(xué)生應(yīng)用所學(xué)知識(shí)解決實(shí)際問題的能力。

二．實(shí)驗(yàn)內(nèi)容
(1)n皇后問題

由N2個(gè)方塊排成N行N列的正方形，稱為N元棋盤，在N元棋盤上放置N個(gè)皇后，如果某兩個(gè)皇后位于N元棋盤的同一行或同一列或同一斜線（斜率為±1）上，則稱它們?cè)诨ハ喙�，試設(shè)計(jì)算法找出使N個(gè)皇后互不攻擊的所有布局。

(2)子集和數(shù)問題

子集和數(shù)問題是假定有n個(gè)不同的正數(shù)(通常稱為權(quán)),要求找出這些數(shù)中所有事的某和數(shù)為M的組合。

（1）我們假設(shè)一個(gè)前提條件：這些正數(shù)是按照非降次序排列的。

（2）引入一個(gè)記號(hào)：B(X(1)，...，X(k))表示是否可以把第K個(gè)正數(shù)加入進(jìn)來(lái)，所以它的取指為true或者false。

那么當(dāng)我們考慮是否要把第K個(gè)正數(shù)加入到解向量中的時(shí)候，我們就能找到兩個(gè)條件組成這個(gè)限界函數(shù)了：

（1）這個(gè)公式的含義是：當(dāng)你考慮是否要把第K個(gè)正數(shù)加入到解向量的時(shí)候，不管你要加進(jìn)來(lái)或者是不打算把它加進(jìn)來(lái)，前K個(gè)解向量的和（包括第K個(gè)，當(dāng)然X(k)可能是0或者1），加上后面所有的數(shù)的和一定要大于等于M，否則你把剩下的數(shù)都加了進(jìn)來(lái)還比M小，這次的決策X(k)=0或者1肯定得不到滿足條件的解向量。所以也就沒有必要擴(kuò)展這個(gè)結(jié)點(diǎn)的左兒子或者右兒子了。

（2）這個(gè)公式的含義是，當(dāng)你考慮是否要把第K個(gè)正數(shù)加入到解向量的時(shí)候，不管你要加進(jìn)來(lái)或者是不打算把它加進(jìn)來(lái)，提前往后看一步，判斷如果把第K+1個(gè)正數(shù)算進(jìn)來(lái)后的值大于M，就不把第K個(gè)正數(shù)加進(jìn)來(lái)。也就是說(shuō)不生成第K-1個(gè)節(jié)點(diǎn)的兒子。

三．實(shí)驗(yàn)要求

（1）用回溯法算法設(shè)計(jì)方法求解N元皇后問題；

（2）找出N皇后問題的互不攻擊的所有解；

（3）皇后數(shù)N由鍵盤動(dòng)態(tài)輸入；

（4）上機(jī)實(shí)現(xiàn)所設(shè)計(jì)的算法；

（5）分析所設(shè)計(jì)的算法的時(shí)間/空間復(fù)雜性。
四．實(shí)驗(yàn)過(guò)程設(shè)計(jì)（算法設(shè)計(jì)過(guò)程）

（1）分析N皇后問題的約束條件，并將其顯示化，選擇存儲(chǔ)結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型；

（2）根據(jù)所建立的數(shù)學(xué)模型，設(shè)計(jì)求解該問題的粗略算法；

（3）對(duì)所設(shè)計(jì)的粗略算法求精，得具體算法；

（4）在C/C++下實(shí)現(xiàn)所設(shè)計(jì)的算法；

（5）分析運(yùn)行結(jié)果的正確性；

（6）進(jìn)行算法效率分析；

（7）課后寫出實(shí)驗(yàn)報(bào)告。

五．源代碼
(1) n皇后問題
  1. #include <iostream>
  2. using namespace std;
  3. const int N = 20;

  5. // bool數(shù)組用來(lái)判斷搜索的下一個(gè)位置是否可行
  6. // col列，dg對(duì)角線，udg反對(duì)角線
  7. // g[N][N]用來(lái)存路徑
  8. //count表示第幾個(gè)解

  10. int n;
  11. char g[N][N];
  12. bool col[N], dg[N], udg[N];
  13. int count = 0;
  14. void dfs(int u)
  15. {
  16.     // u == n 表示已經(jīng)搜了n行，故輸出這條路徑
  17.     if (u == n)
  18.     {
  19.         count++;
  20.         cout<<"第"<<count<<"個(gè)解："<<endl;
  21.         for (int i = 0; i < n; i ++ ) cout << g[i] << endl;
  22.         cout<<endl;
  23.         return;
  24.     }

  26.    //對(duì)n個(gè)位置按行搜索
  27.     for (int i = 0; i < n; i ++ )
  28.         // 剪枝(對(duì)于不滿足要求的點(diǎn)，不再繼續(xù)往下搜索)
  29.         //udg[n - u + i]，+n是為了保證大于0
  30.         if (!col[i] && !dg[u + i] && !udg[n - u + i])
  31.         {
  32.             g[u][i] = 'Q';
  33.             col[i] = dg[u + i] = udg[n - u + i] = true;
  34.             dfs(u + 1);
  35.             // 恢復(fù)現(xiàn)場(chǎng) 這步很關(guān)鍵
  36.             col[i] = dg[u + i] = udg[n - u + i] = false;
  37.             g[u][i] = '.';

  39.         }
  40. }

  42. int main()
  43. {
  44.     cout<<"請(qǐng)問這是幾皇后問題："<<endl;
  45.     cin >> n;
  46.     cout<<endl;
  47.     for (int i = 0; i < n; i ++ )
  48.        for (int j = 0; j < n; j ++ )
  49.             g[i][j] = '.';

  51.     dfs(0);
  52.     return 0;
  53. }
復(fù)制代碼

運(yùn)行結(jié)果：

(2) 子集和數(shù)問題

  1. #include <iostream>
  2. using namespace std;

  4. //求解函數(shù)
  5. void sumOfSub(float s, int k, float r, int *x, float m, float *w);
  6. void sumOfSub(int *x, int n, float m, float *w);

  8. int main()
  9. {
  10.               int n; //n表示集合元素個(gè)數(shù)
  11.               float m; //m表示目標(biāo)和
  12.               cout << "請(qǐng)輸入集合元素個(gè)數(shù)：";
  13.               cin >> n;
  14.               cout << "請(qǐng)輸入目標(biāo)和：";
  15.               cin >> m;
  16.               float *arr = new float [n + 1];
  17.               int *x = new int [n + 1]; //求解狀態(tài)
  18.               cout << "請(qǐng)輸入" << n <<"個(gè)集合元素(正值)：";
  19.               for(int i=0; i < n; i++)
  20.               {
  21.                             cin >> arr[i];
  22.               }
  23.               cout << "可行解：\n";
  24.               sumOfSub(x, n, m, arr);

  26.               return 0;
  27. }

  29. void sumOfSub(float s, int k, float r, int *x, float m, float *w)
  30. {
  31.               x[k] = 1;
  32.               if(s + w[k] == m)//一個(gè)可行解
  33.               {
  34.                             for(int j = 0;j <= k; j++)//兩種輸出方式任選
  35.                             {
  36.                                           if(x[j] == 1)  //完成輸出，輸出選取的元素
  37.                                             cout << w[j] << " ";
  38.                             }
  39.                             cout << endl;
  40.               }
  41.               else if(s + w[k] + w[k+1] <= m)
  42.               {
  43.                             sumOfSub(s+w[k], k+1, r-w[k], x, m, w);//搜索左子樹
  44.               }
  45.               if((s + r - w[k] >= m)&&(s + w[k]+1 <= m))
  46.               {
  47.                             x[k] = 0;
  48.                             sumOfSub(s, k+1, r - w[k], x, m, w); //搜索右子樹
  49.               }
  50. }
  51. void sumOfSub(int *x, int n, float m, float *w)
  52. {
  53.               float r = 0;
  54.               for(int i = 0; i < n; i++)  r += w[i];//計(jì)算總值，判斷是否有解
  55.               if(r >= m && w[0] <= m)  sumOfSub(0, 0, r, x, m, w);
  56. }
復(fù)制代碼

運(yùn)行結(jié)果：

完整的Word格式文檔51黑下載地址：
計(jì)算機(jī)算法基礎(chǔ)實(shí)驗(yàn)指導(dǎo)201909.doc (416.5 KB, 下載次數(shù): 8)





歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1