算法设计与分析试验报告

学生学号0121010680524 实验课成绩武汉理工大学学生实验报告书实验课程名称《算法设计与分析》开课学院计算机科学与技术学院指导老师姓名何九周学生姓名王鹏学生专业班级软件 10042012 —2013 学年第1 学期实验课程名称：算法设计与分析实验项目名称分治法应用及设计实验成绩实验者王鹏专业班级软件1004 组别同组者实验日期年月日第一部分：实验分析与设计（可加页）一、实验内容描述（问题域描述）实验描述：利用分治法，解决检索和排序中的两个问题，在计算机上实现，同时进行时间复杂性分析。

本实验是综合型、设计型实验，在实验中需要综合运用《数据结构》中的递归方法和树的知识；《程序设计》中的数组、条件控制、循环控制和《算法设计与分析》中的分治法、计算时间的渐进表示和算法的时间复杂性分析等等方面的知识。

实验内容：1）利用分治法，写一个二分检索的递归算法，并利用任何一种语言，在计算机上实现，同时进行时间复杂性分析。

2）用分治法，实现对n个元素进行排序的算法，并进行时间复杂性分析。

实验要求：首先要对实验内容进行描述，用伪代码设计算法，并对算法在最好，最差和平均情况下的时间复杂性进行分析，然后C/C++或JA VA语言编写程序对算法实现，同时用具用代表性的数据进行测试，实验后，进行实验总结，描述设计过程步骤及各步骤含义。

其中实验内容1要求用递归方法实现，实验内容2要求用非递归方式实现。

二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）实验一代码：#include <stdio.h> //比较x和yint compare(int x,int y){if( x < y ) return -1;else if ( x == y) return 0;else return 1;}//二分查找(折半查找)的递归(迭代)算法，返回查找到的值在数组中的位置下标int BinSearch(int list[],int searchnum,int Left,int Right){int middle;if(Left <= Right){middle = (Left + Right)/2;printf("middle = %d\n",middle);switch(compare(list[middle],searchnum)){case -1:return BinSearch(list,searchnum,middle + 1,Right); case 0:return middle;case 1:return BinSearch(list,searchnum,Left,middle - 1); }}}void main(){int list[10] = {1,2,3,4,5,6,7,8,9,10};int searchnum = 5;int Left = 0;int Right = 9;int num = BinSearch(list,searchnum,Left,Right);printf("返回%d\n",num);}实验二代码：#include <iostream>#include <cstdlib>using namespace std;int merge(int c[],int d[],int l,int m,int r){int i=l,j=m+1,k=l,q;while(i<=m&&j<=r){if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];}if(i>m)for(q=j;q<=r;q++)d[k++]=c[q];if(j>r)for(q=i;q<=m;q++)d[k++]=c[q];return 0;}int mergePass(int x[],int y[],int s,int n){int i=0,j;while(i<=n-2*s){//合并大小为S的相邻子段merge(x,y,i,i+s-1,i+2*s-1);i+=2*s;}//剩下的元素个数少于2sif(i+s<n)merge(x,y,i,i+s-1,n-1);elsefor(j=i;j<=n-1;j++)y[j]=x[j];return 0;}//合并数组int mergeSort(int a[],int n){int s=1;int *b=new int[n];//int *b=(int *)malloc(n*sizeof(int));//动态的给b分配n 个int类型空间while(s<n){mergePass(a,b,s,n);//合并到数组bs+=s;mergePass(b,a,s,n);s+=s;}return 0;}int main(){int i,n;cout<<"请输入数组元素的个数："; cin>>n;int *a=new int[n];cout<<"请输入数组a的元素:";for(i=0;i<n;i++)cin>>a[i];mergeSort(a,n);cout<<endl;for(i=0;i<n;i++)cout<<a[i]<<" ";return 0;}三、主要仪器设备及耗材个人计算机, Visual studio 2012第二部分：实验调试与结果分析（可加页）一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等）实验一：调试方法：直接在函数体内定义测试，负责初始化查找的有序表。

没有设定好中值点，忘记在两个端点的差值上增加左边端点的内容。

递归调用时，错误使用了边界条件，导致结果不正确。

实验二：调试方法：直接在函数体内定义测试，负责初始化分治法排序的列表。

对于算法没有理解透彻，没有用好边界条件。

对于算法的交换应该是首先保存旧值，在第一次也就是从右侧开始时把右侧的值传至左侧，把左侧的值保存，用来给从左侧开始进行的查找。

二、实验结果及分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等）（1）查找均为正确结果。

时间复杂度：O(nlogn)空间复杂度：无需大量增加空间，仍为O(n)（2）时间复杂度：最好：O(n)平均：O(n log2n)最差：O(n2)空间复杂度：O(n)三．实验小结、建议及体会初次涉及这方面的编程，由开始的无所适从，到慢慢有了头绪，直到完成。

每到遇到难题，心中不免烦闷，每获成功，又不由有些自豪。

编程的乐趣莫过于此。

实验课程名称：算法设计与分析实验项目名称动态规划算法应用及设计实验成绩实验者王鹏专业班级软件1004 组别同组者实验日期年月日第一部分：实验分析与设计（可加页）一、实验内容描述（问题域描述）实验描述：将动态规划算法应用于货郎担问题和工程中的资金分配问题的求解，设计出高效的算法。

本实验是综合型、设计型实验，在实验中需要综合运用《离散数学》中的数理逻辑、图；《数据结构》中的集合、队列、树；《程序设计》中的数组、条件控制、循环控制、指针、结构体和《算法设计与分析》中的动态规划算法、多段图、以及计算时间的渐进表示和算法的时间复杂性分析等等方面的知识。

实验内容：1）利用动态规划思想，求货郎担问题，并利用任何一种语言，在计算机上实现，同时进行时间复杂性分析。

2）已知资金总数为a（万元）,工程数n，以及利润值g(i,j)(表示对工程i 投资j万元所获得的利润，其中a≤1，且j只取整数)，试用动≤0,i≤jn≤态规划方法求出如何分配资金才能使获得的利润最大（资金的分配以万元为单位）。

实验要求首先要对实验内容进行描述，用SPARK语言设计算法，然后C/C++或JAVA语编写程序对算法实现，同时用具用代表性的数据(给3组典型输入数据)进行测试，实验后，进行实验总结，描述设计过程步骤及各步骤含义。

其中实验内容1）还要求对算法的时间复杂性进行分析，实验内容2）还要求写出动态规划递推关系式。

二、实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述）实验一：算法分析，比较次数的递推关系式：C(n) = 1 n=2C(n) = 2C(n/2) + 2 n>2求解关系式：C(n) = 3n/2 – 2当且仅当n是2的幂时的最优解。

否则，C(n)取其递推式向上取整数。

代码：#include <iostream>#include <math.h>#define NUM 4using namespace std;int num = (int)pow(2, NUM - 1);class subset{public:bool contains[NUM - 1]; //除了开始结点外，包含哪个城市就把相应的contains设置为1；bool is_in(int i){i--;if (contains[i]) return true;else return false;}//判断第i个城市是否在子集中，如果在返回true，否则false；};//所有节点城市的子集。

void set_ct(subset * s, int begin, int end, int process){if (NUM - 2 == process){s[begin].contains[process] = false;s[end].contains[process] = true;}else{int middle = (end + begin) / 2;int i;for (i = begin; i <= middle; i++)s[i].contains[process] = false;set_ct(s, begin, middle, process + 1);for (i = middle + 1; i <= end; i++)s[i].contains[process] = true;set_ct(s, middle + 1, end, process + 1);}}//用递归的方法初始化子集结点；int combian(int a, int b){if (b >= 0 && a >= b){if (0 == b || a == b) return 1;else{if (a - b < b) b = a - b; //组合数的性质；int i, result = 1;for (i = a - b + 1; i <= a; i++)result *= i;for (i = 2; i <= b; i++)result /= i;return result;}}else return -1;}//组合数（a选b）的计算,数据合法返回正确的值，否则返回-1，int get_h(bool *c, int n){int i, result = 0;for (i = 0; i < NUM - 1; i++){if (i != n && c[i]) result += (int)pow(2, NUM - 2 - i);}return result;}//计算table_d表的横坐标horizontal，int main(){int **cities = new int *[NUM]; //存储个城市之间的代价矩阵int **table_d = new int *[NUM]; //存储动态距离表int **table_p = new int *[NUM]; //存储动态结点选在表subset *sbst = new subset[num]; //所有城市节点的子集。