算法分析與設計實驗

• （1）蠻力法遍歷搜索
• （2）破案問題

（1）蠻力法遍歷搜索

輸入一個正整數N，輸出所有的子集情況和排列情況。例如，N=3時，所有的子集情況為：（0,0,0）（0,0,1）（0,1,0）（0,1,1）（1,0,0）（1,0,1）（1,1,0）（1,1,1），所有的排列情況為（1,2,3）（1,3,2）（2,1,3）（2,3,1）（3,1,2）（3,2,1）。分別記錄求子集和求排列所用的時間，畫出時間隨N的散點圖或曲線。注意：記錄時間時只記錄計算過程的時間開銷，不要記錄程序輸出時所用的時間。
題目1的實驗執行的結果：

求子集

理論上求子集的時間復雜度O(2^n)，從實驗結果來分析，大體上呈現的是這樣的，這樣推斷出實驗執行結果是正確的。
2. 全排列

理論上全排列的時間復雜度o(n!)，隨著基數的增長，時間的開銷增長巨大，上述實驗結果完全符合這個情況，這里的截圖中的數據最高也是12，運行時間也達到了二十二秒多了，當基數為13時，運行時間就達到6分鐘了，完全符合理論值，所以得出結論正確。

#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<time.h> using namespace std; const int N = 1e5 + 10; int n; int st[N]; bool pt[N]; void dfs(int u) {if(u==n+1){return ;}for(int i = 1 ; i <= n ; i ++ ){if(!pt[i]){pt[i]=true;st[u] = i;dfs(u+1);pt[i]=false;}}} int main() {cin >> n;int x = n;for(int i = 1 ; i <= x ; i ++ ) //求全排列{n = i;clock_t start, ends; //計算時間start = clock();dfs(1);ends = clock();cout <<"i = " << i << "時" << "時間（毫秒）為："<<ends-start <<endl;}/*for(int i = 1 ; i <= x ; i ++) //求子集{n = i;clock_t start, ends; //計算時間start = clock();int w = 0;long long ans =(long long )pow(2,n) - 1;for(int i = 1; i <= ans ; i ++ ){for(int k = 0; k < n ; k ++ ){if(i>>k&1)w++;else w++;}}ends = clock();cout <<"i = " << i << "時" << "時間（毫秒）為："<<ends-start <<endl;}return 0; }

（2）破案問題

某地刑偵大隊對涉及六個嫌疑人的一樁疑案進行分析：（1）A、B至少有一人作案；（2）A、E、F三人中至少有兩人參與作案；（3）A、D不可能是同案犯；（4）B、C或同時作案，或與本案無關；（5）C、D中有且僅有一人作案；（6）如果D沒有參與作案，則E也不可能參與作案。試設計算法將作案人找出來。要求用盡可能少的循環的層數。

一個六個人，分別對應A-F,設置0表示不是本案罪犯，1表示是本案罪犯，用最暴力的做法，從000000到111111一共63種情況，遍歷一遍，只要滿足全部條件，那就得到答案了，而每一個二進制序列都對應一個十進制數字，0~63.然后對每一個數字進行位運算，設x為這個數字 k 表示0~5，x >> k & 1 就可以判斷該位是不是1.進而可以得出結果了，與推理情況相同。

#include<iostream> #include<cstring> #include<algorithm> using namespace std; bool st[10]; char ans[10]; int main() {for(int i = 1; i <= 6; i ++ ) ans[i] = 'A'+i-1;for(int i = 0; i <= 63 ; i ++ ){for(int k = 0; k < 6; k ++ ){st[k+1] = (i>>k&1);//cout << i << ">> "<< k <<"=" <<(i>>k )<< endl;}bool num1 = st[1]||st[2]; //下面是全部的條件bool t = st[1]&&st[5]&&(!st[6]);bool t1 = st[1]&&st[5]&&st[6];bool t2 = (!st[1])&&st[5]&&st[6];bool t3 = st[1]&&(!st[5])&&st[6];bool num2 = t||t1||t2||t3;bool num3 = false;if( (st[1]==0)||(st[4]==0)) num3 = true;bool num4 = (st[2]==st[3]);bool num5 = false;if((st[3]==1&&st[4]==0)||(st[3]==0&&st[4]==1))num5 = true;bool num6 = false;if((st[4]==0&&st[5]==0)||st[4]==1) num6 = true;if(num1&&num2&&num3&&num4&&num5&&num6){cout << "兇手是：";for(int u = 1 ; u <= 6 ; u ++ ){if(st[u]) cout << ans[u] << " ";}cout << endl;}}return 0; }

總結

以上是生活随笔為你收集整理的蛮力法实验的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。