太原理工大学算法设计实验报告

1、实验1 分治法实验目的： 1. 掌握合并排序的基本思想 2. 掌握合并排序的实现方法 3. 学会分析算法的时间复杂度 4. 学会用分治法解决实际问题实验内容：分治法求几个大小不同整数的最大最小元。主要仪器设备：华硕笔记本、visual stdio2013上机调试修改源程序：#include<iostream>#include<time.h>#define N 5using namespace std;void getData(int a, int n)time_t t;srand(unsigned)time(&t);int i;for (i = 0; i <

2、; n; i+)ai = rand() % 100;void MaxMin(int i, int j, int l,int &max, int &min)int maxl, minl;if (i = j)max = min = lj;else if (i = j - 1)if (li < lj)max = lj;min = li;elsemax = li;min = lj;elseint m = (i + j) / 2;MaxMin(i, m, l, max, min);MaxMin(m + 1, j, l, maxl, minl);if (max < maxl)m

3、ax = maxl;if (min>minl)min = minl;void main()int lN, max, min;getData(l,N);for (int i = 0; i < N; i+)cout << li << " "cout << endl;MaxMin(0, 4, l, max, min);cout << "MAX=" << max << " " << "MIN=" << min <

4、;< endl;输出结果：讨论、心得（可选）:分治算法是很有用的算法效率很高，分治法的设计一般是递归的。两路合并排序是一个典型的分治算法，其基本运算为元素比较，最坏情况下的时间为W(n)=O(nlogn)，在排序过程中需要使用与原序列相同长度的辅助数组temp，因此它所需的额外空间为O(n)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题划分为彼此独立的、规模较小而结构相同的子问题。实验2贪心法实验目的：1.掌握贪心算法的基本思想2.掌握贪心算法的典型问题求解3.进一步多级调度的基本思想和算法设计方法4.学会用贪心法分析和解决实

5、际问题实验内容：利用贪心法来解决背包问题，使得具有有限空间的背包具有最大的价值。主要仪器设备：华硕笔记本、visual stdio2013上机调试修改源程序：#include<iostream>using namespace std;void DP(int c5050,int w50,int v50,int n,int C) for(int i=0;i<=C;i+) c0i=0; for(int t=1;t<=n;t+) ct0=0; for(int j=1;j<=C;j+) if(wt<=j) if(vt+ct-1j-wt>ct-1j)ctj=vt+

6、ct-1j-wt;else ctj=ct-1j; else ctj=ct-1j; void Output(int c5050,int x50,int w50,int n,int C) for(int k=n;k>=2;k-) if(ckC=ck-1C) xk=0; else xk=1;C=C-wk; x1=c1C?1:0;int main() int c5050; int w50,v50,x50,C,n; cout<<"输入物品总个数:" cin>>n; cout<<"输入背包的总容量：" cin>>

7、C; cout<<"依次输入物品的重量："<<endl; for(int i=1;i<=n;i+) cin>>wi; cout<<"依次输入物品的价值："<<endl; for(int t=1;t<=n;t+) cin>>vt; DP(c,w,v,n,C); Output(c,x,w,n,C); cout<<"最优解为："<<endl; for(int e=1;e<=n;e+) cout<<xe<<

8、" " cout<<endl<<"最大容量为："<<endl; cout<<cnC<<endl; return 0; 输出结果：讨论、心得（可选）:贪心法是一种求解组合优化问题的算法设计技术它可用于求背包问题、带时限的作业进行排序问题等，其求解过程由一些列决策构成。贪心算法的关键在于贪心策略，两要素是：最优子结构和贪心策略，背包问题是一个典型的贪心算法。通过编写贪心法处理背包问题，我对于贪心法的解决问题的思路更熟悉了。实验3回溯法实验目的：1.掌握回溯算法的基本思想2.通过n皇后问题求解熟悉回溯

9、法 3. 使用蒙特卡洛方法分析算法的复杂度实验内容：要求在一个8*8的棋盘上放置8个皇后，使得它们彼此不受“攻击”。两个皇后位于棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现在要找出使得棋盘上8个皇后互不攻击的布局。主要仪器设备：华硕笔记本、visual stdio2013上机调试修改源程序：#include <iostream>#include<cmath>using namespace std;bool Place(int k, int i, int *x)for (int j = 0; j<k; j+)if (xj = i)

10、 | (abs(xj - i) = abs(j - k)return 0;return 1;void NQueen(int k, int n, int *x)int a100100 = ;for (int i = 0; i<n; i+)if (Place(k, i, x) = 1)xk = i;if (k = n - 1)for (int i = 0; i<n; i+)cout << xi << " "aixi = 1;cout << endl << "如下图示" << endl;f

11、or (int i = 0; i<n; i+)for (int j = 0; j<n; j+)cout << aij << " "cout << endl;cout << endl;else NQueen(k + 1, n, x);void NQueen(int n, int *x)NQueen(0, n, x);int main()int n;cin >> n;int k100;NQueen(n, k);return 0;输出:讨论、心得（可选）:通过这次试验我对皇后问题的知识点有了很大的了解，编写代

12、码和调试代码的能力有所提高。对于回溯法的认知也更深入了在算法设计策略中，回溯法是比贪心法和动态规划法更一般的方法。n皇后问题以检查两皇后是否冲突作为基本运算，该算法的最坏情形复杂性为O(3n×2nn)=O(nn+1)。实验4动态规划法实验目的：1.掌握动态规划算法的基本思想2.掌握多段图的动态规划算法3.选择邻接表或邻接矩阵方式来存储图4.分析算法求解的复杂度实验内容：设G=(V,E)是一个带权有向图，其顶点的集合V被划分成k>2个不相交的子集Vi，1<i<=k，其中V1和Vk分别只有一个顶点s（源）和一个顶点t（汇）。图中所有边的始点和终点都在相邻的两个子集Vi和

13、Vi+1中。求一条s到t的最短路线。参考课本P124图7-1中的多段图，试选择使用向前递推算法或向后递推算法求解多段图问题。主要仪器设备：华硕笔记本、visual stdio2013上机调试修改源程序：#include <stdio.h>#include <stdlib.h>#include <conio.h>#include "iostream"#define MAX 100 #define n 12 #define k 5 using namespace std;int cnn;void init(int cost) int i, j

14、;for (i = 0; i<13; i+)for (j = 0; j<13; j+)cij = MAX;c12 = 9; c13 = 7; c14 = 3; c15 = 2; c26 = 4; c27 = 2; c28 = 1;c36 = 2; c37 = 7; c48 = 11; c57 = 11; c58 = 8; c69 = 6; c610 = 5;c79 = 4; c710 = 3; c810 = 5; c811 = 6; c912 = 4; c1012 = 2; c1112 = 5;void fgraph(int cost, int path, int d) int r

15、, j, temp, min;for (j = 0; j <= n; j+)costj = 0;for (j = n - 1; j >= 1; j-)temp = 0;min = cjtemp + costtemp; for (r = 0; r <= n; r+)if (cjr != MAX)if (cjr + costr)<min) min = cjr + costr;temp = r;costj = cjtemp + costtemp;dj = temp;path1 = 1;pathk = n;for (j = 2; j<k; j+)pathj = dpath

16、j - 1;int main()int cur = -1;int cost13,d12;int pathk;cout <<"多段图问题" << endl;cout << "n"init(cost);fgraph(cost, path, d);cout << "向前递推后的最短路径:n"for (int i = 1; i <= 5; i+)cout << pathi << " "cout << "n"cout << endl &l