找回密碼
 立即注冊

QQ登錄

只需一步，快速開始

搜索
查看: 2723|回復(fù): 0
打印 上一主題 下一主題
收起左側(cè)

計算機(jī)算法基礎(chǔ)實驗程序及運行結(jié)果

[復(fù)制鏈接]
跳轉(zhuǎn)到指定樓層
樓主
ID:632295 發(fā)表于 2019-10-29 21:11 | 只看該作者 回帖獎勵 |正序瀏覽 |閱讀模式
一找最大和最小元素與歸并分類算法實現(xiàn)（用分治法）
一、實驗?zāi)康?br />
1．掌握能用分治法求解的問題應(yīng)滿足的條件；
2．加深對分治法算法設(shè)計方法的理解與應(yīng)用；
3．鍛煉學(xué)生對程序跟蹤調(diào)試能力；
4．通過本次實驗的練習(xí)培養(yǎng)學(xué)生應(yīng)用所學(xué)知識解決實際問題的能力。
二．實驗內(nèi)容

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

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

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

解決問題的策略:

蠻力策略：對金塊逐個進(jìn)行比較查找。（掃描數(shù)組一輪，尋找最大和最小的數(shù)。）該策略需要進(jìn)行（n－1）次的比較才能得到max和min。
分治法（二分法）策略：問題可以簡化為在n個數(shù)里面尋找最大和最小值。
（1）將數(shù)據(jù)等分為兩組(兩組數(shù)據(jù)的個數(shù)可能相差1)，目的是分別選取其中的最大（�。┲�。
（2）遞歸分解直到每組元素的個數(shù)<=2，則可以簡單地找到其中的最大（小）值。
（3）回溯時合并子問題的解，在兩個子問題的解中大者取大，小者取小，即合并為當(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){//如果只有一個元素，則最小最大都是這個元素
  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ù)制代碼

程序運行結(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分成兩個集合
  7.     int b[high];//數(shù)組b為輔助數(shù)組
  8.     while(h <= mid && j <= high){//當(dāng)兩個集合都沒有取盡時
  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){//前一個數(shù)組先取完
  20.         for(k = j;k <= high;k++){
  21.             b[i] = a[k];
  22.             i++;
  23.         }
  24.     }else{//后一個數(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;//求集合的分割點
  39.         mergeSort(low,mid,a);//將前半個集合分類
  40.         mergeSort(mid+1,high,a);//將后半個集合分類
  41.         merge(low,mid,high,a);//歸并兩個已經(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ù)制代碼

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

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

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

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

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。
    貪心算法不是對所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。
基本思路
建立數(shù)學(xué)模型來描述問題；
把求解的問題分成若干個子問題；
對每一子問題求解，得到子問題的局部最優(yōu)解；
把子問題的解局部最優(yōu)解合成原來解問題的一個解。
算法實現(xiàn)
從問題的某個初始解出發(fā)。
采用循環(huán)語句，當(dāng)可以向求解目標(biāo)前進(jìn)一步時，就根據(jù)局部最優(yōu)策略，得到一個部分解，縮小問題的范圍或規(guī)模。
將所有部分解綜合起來，得到問題的最終解。
實例分析
實例1 背包問題
問題描述
有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大，但不能超過總?cè)萘俊?/div>
  • 問題分析
    1.目標(biāo)函數(shù)： ∑pi最大，使得裝入背包中的所有物品pi的價值加起來最大。
    2.約束條件：裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
    3.貪心策略：
    • 選擇價值最大的物品
    • 選擇價值最大的物品
    • 選擇單位重量價值最大的物品
      有三個物品A,B,C，其重量分別為{30,10,20}，價值分別為{60,30,80}，背包的容量為50，分別應(yīng)用三種貪心策略裝入背包的物品和獲得的價值如下圖所示：
三種策略
  • 算法設(shè)計：
  • 計算出每個物品單位重量的價值
  • 按單位價值從大到小將物品排序
  • 根據(jù)背包當(dāng)前所剩容量選取物品
  • 如果背包的容量大于當(dāng)前物品的重量，那么就將當(dāng)前物品裝進(jìn)去。否則，那么就將當(dāng)前物品舍去，然后跳出循環(huán)結(jié)束。

五．源代碼

（1）背包問題
  1. #include <iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. /*定義物品的結(jié)構(gòu)體*/
  5. struct Object{
  6.     double weight;//物品重量
  7.     double value;//物品價值
  8.     double avg;//單位重量價值
  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;//背包中的最大價值
  23.     cout<<"請輸入所有物品數(shù)量和背包容量\n";
  24.     cin>>num>>volume;
  25.     ob = new Object[num];
  26.     /*初始化物品的重量和價值，并計算單位重量價值*/
  27.     for(int i = 0;i<num;i++){
  28.         cout<<"輸入第"<<i+1<<"個物品的重量和價值\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);//物品按單位重量價值降序
  33.     int i;
  34.     /*開始裝入物品*/
  35.     for(i = 0;i<num;i++){
  36.         if(ob[i].weight <= volume){//如果這個物品能全部裝入
  37.             volume =  volume -ob[i].weight;
  38.             ob[i].prop = 1;//表示全部裝入
  39.             maxValue = maxValue + ob[i].value;
  40.         } else{//這個物品已經(jīng)不能全部裝人
  41.             break;
  42.         }
  43.     }
  44.     if(i<num){//有一個物品不能全部裝入
  45.             ob[i].prop = volume/ob[i].weight;//裝入的比例
  46.             volume = 0;
  47.             maxValue = maxValue + ob[i].prop*ob[i].value;
  48.     }
  49.     cout<<"放入的物品的重量，價值，比例\n";
  50.     for(int i = 0;i<num;i++){
  51.         cout<<ob[i].weight<<" "<<ob[i].value<<" "<<ob[i].prop<<"\n";
  52.    }
  53.     cout<<"放入物品的總價值:"<<maxValue;
  54.     return 0;
  55. }
復(fù)制代碼


程序運行結(jié)果：
（2）最小生成樹
  1. /*
  2. S:當(dāng)前已經(jīng)在聯(lián)通塊中的所有點的集合
  3. 1. dist[i] = inf
  4. 2. for n 次
  5.     t<-S外離S最近的點
  6.     利用t更新S外點到S的距離
  7.     st[t] = true
  8. n次迭代之后所有點都已加入到S中
  9. 聯(lián)系：Dijkstra算法是更新到起始點的距離，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. //鄰接矩陣存儲所有邊
  19. //dist存儲其他點到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最近的點
  33.         if(i && dist[t] == INF) return INF;
  34.         //判斷是否連通，有無最小生成樹

  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 << "頂點數(shù)和邊數(shù):" << endl;
  49.     cin >> n >> m;//n=|V|，m=|E|
  50.     int u, v, w;//u，v，w，表示點u和點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<< "兩頂點和邊長：" << 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ù)制代碼

程序運行結(jié)果：

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

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

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

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

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

  6. /**/
  7. void FGRAPH(int n,int k){
  8.     int cost[n];//第n個節(jié)點到最后一個節(jié)點的最端路徑
  9.    for(int i = 0;i<n;i++){
  10.         cost[i] = INFI;//初始化所有節(jié)點的最短路徑為無窮大
  11.     }
  12.     cost[n-1] = 0;
  13.     int j,r;
  14.     int p[k],d[n];//p為段決策，d為節(jié)點決策
  15.     int min;
  16.     /*尋找所有節(jié)點到最后一個節(jié)點的最短路徑和節(jié)點決策）*/
  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é)點的節(jié)點的決策
  23.             }
  24.         }
  25.         cost[j] = min; //j節(jié)點的最短路徑
  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]];//上一個段的段決策的節(jié)點決策即為下一個段的段決策
  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é)點之間距離初始化*/
  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ù)制代碼

程序運行結(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é)點的最后一個節(jié)
  13. //最后返回 最后一個節(jié)點到起點的路徑
  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é)點沒加入且非起始點
  19.         {
  20.             done[i] = 1;   //遞歸調(diào)用時，防止重復(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ù)制代碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三．實驗要求

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

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

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

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

（5）分析所設(shè)計的算法的時間/空間復(fù)雜性。
四．實驗過程設(shè)計（算法設(shè)計過程）

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

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

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

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

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

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

（7）課后寫出實驗報告。

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

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

  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<<"個解："<<endl;
  21.         for (int i = 0; i < n; i ++ ) cout << g[i] << endl;
  22.         cout<<endl;
  23.         return;
  24.     }

  26.    //對n個位置按行搜索
  27.     for (int i = 0; i < n; i ++ )
  28.         // 剪枝(對于不滿足要求的點，不再繼續(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)場 這步很關(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<<"請問這是幾皇后問題："<<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ù)制代碼

運行結(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表示集合元素個數(shù)
  11.               float m; //m表示目標(biāo)和
  12.               cout << "請輸入集合元素個數(shù)：";
  13.               cin >> n;
  14.               cout << "請輸入目標(biāo)和：";
  15.               cin >> m;
  16.               float *arr = new float [n + 1];
  17.               int *x = new int [n + 1]; //求解狀態(tài)
  18.               cout << "請輸入" << n <<"個集合元素(正值)：";
  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)//一個可行解
  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];//計算總值，判斷是否有解
  55.               if(r >= m && w[0] <= m)  sumOfSub(0, 0, r, x, m, w);
  56. }
復(fù)制代碼

運行結(jié)果：

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

評分

參與人數(shù) 1黑幣 +50 收起 理由
admin + 50 共享資料的黑幣獎勵！

查看全部評分

分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏1 分享淘帖 頂頂 踩踩
回復(fù)

使用道具 舉報

您需要登錄后才可以回帖 登錄 | 立即注冊

本版積分規(guī)則

手機(jī)版|小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表