算法设计与分析实验报告.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：2.46M 资料格式：pdf 举报版权申诉

第1页 / 共73页

qq_40263477-10820396-算法设计与分析实验报告.pdf-第2页.png

第2页 / 共73页

qq_40263477-10820396-算法设计与分析实验报告.pdf-第3页.png

第3页 / 共73页

qq_40263477-10820396-算法设计与分析实验报告.pdf-第4页.png

第4页 / 共73页

qq_40263477-10820396-算法设计与分析实验报告.pdf-第5页.png

第5页 / 共73页

qq_40263477-10820396-算法设计与分析实验报告.pdf-第6页.png

第6页 / 共73页

qq_40263477-10820396-算法设计与分析实验报告.pdf-第7页.png

第7页 / 共73页

qq_40263477-10820396-算法设计与分析实验报告.pdf-第8页.png

第8页 / 共73页

文本预览

算法设计与分析实验报告二零一八年十一月

目录分治策略算法设计实验 ..................................... 1 单峰序列问题 .......................................... 1 问题描述与要求 ..................................... 1 算法设计及时间复杂度分析： ......................... 1 输入数据的格式 ..................................... 2 编程实现源代码(cpp) ................................ 3 程序调试与测试记录 ................................. 5 寻找第 K 小元素问题 .................................... 6 问题描述与要求 ..................................... 6 算法设计及时间复杂度分析 ........................... 6 输入数据的格式 ..................................... 8 编程实现源代码(cpp) ................................ 9 程序调试与测试记录 ................................ 20 Matlab 编程绘制算法效率图 .......................... 23 动态规划算法设计实验 .................................... 26 数字三角形问题 ....................................... 26 问题描述与要求 .................................... 26 算法设计及时间复杂度分析： ........................ 26 输入数据的格式 .................................... 26 编程实现源代码(cpp) ............................... 27 程序调试与测试记录 ................................ 31 0-1 背包问题 ......................................... 32 问题描述与要求 .................................... 32 算法设计及时间复杂度分析： ........................ 32 编程实现源代码(cpp) ............................... 33 程序调试与测试记录 ................................ 38

字符串相似性 ......................................... 40 问题描述与要求 .................................... 40 算法设计及时间复杂度分析： ........................ 40 编程实现源代码(cpp) ............................... 41 程序调试与测试记录 ................................ 44 回溯策略算法设计实验 .................................... 46 八皇后循环实现问题 ................................... 46 问题描述与要求 .................................... 46 算法设计及时间复杂度分析： ........................ 48 输入数据的格式 .................................... 48 编程实现源代码(cpp) ............................... 49 程序调试与测试记录 ................................ 55 生成集合全排序问题 ................................... 56 问题描述与要求 .................................... 56 算法设计及时间复杂度分析： ........................ 56 编程实现源代码(cpp) ............................... 57 程序调试与测试记录 ................................ 59 生成集合 r 组合问题 ................................... 60 问题描述与要求 .................................... 60 算法设计及时间复杂度分析： ........................ 60 编程实现源代码(cpp) ............................... 60 程序调试与测试记录 ................................ 63 子集和问题 ........................................... 64 问题描述与要求 .................................... 64 算法设计及时间复杂度分析 .......................... 64 编程实现源代码(cpp) ............................... 65 程序调试与测试记录 ................................ 69

单峰序列问题分治策略算法设计实验单峰序列问题问题描述与要求给定含有 n 个不同元素的数组 L ，如果 L 中存在 xi 使得，则成 L 是单峰序列，称是 L 的峰顶。完成下面的任务： a）设计一个分治算法找到 L 的峰顶，编程调试正确。 b）从理论上分析算法的时间复杂度。算法设计及时间复杂度分析：输入任意一个序列，要判定其是否为单峰序列，可根据峰顶元素本身的性质进行算法设计，一个序列要成为单峰序列，那么其只能有一个峰顶，并且峰顶元素的特点就是 L[k-1]L[k+1],那么递归寻找这样的可能成为峰顶的元素，并返回其下标。利用二分查找算法，中间元素和其相邻的两个元素之间的关系只有 4 种可能性： 1) num[mid-1]>num[mid]&&num[mid]num[mid+1] 3) num[mid-1]>num[mid]&&num[mid]>num[mid+1] 4) num[mid-1]

单峰序列问题将找出来的元素，利用单峰序列本身的特点就是峰顶元素左边是递增的，右边是递减的来进一步判定是否是单峰序列。类似于二分查找算法，原规模问题被分解成两个子问题，则时间复杂度递推式为： T(N)=T(N/2)+C1 T(1)=C2，其中 C 表示某个常数可以使用迭代法或者主定理，求解出时间复杂度 T(N)=O(logn)。输入数据的格式 Maxn=6; 1 2 3 4 5 6 1 2 6 5 4 3 1 2 3 4 6 5 2

单峰序列问题 1 2 3 6 5 4 6 5 4 3 2 1 6 5 3 2 4 1 编程实现源代码(cpp) #include using namespace std; int num[100]; //递归找到峰顶元素的下标 int findtopindex(int num[],int start,int end) { if(end-start==2) return start+1; if(end-start<2) return -1; int mid=(start+end)/2; //中点元素就是峰顶元素 if(num[mid-1]num[mid+1]) return mid; if(num[mid-1]>num[mid]&&num[mid]num[mid]&&num[mid]>num[mid+1]) return findtopindex(num,start,mid); //在中点元素右边寻找 if(num[mid-1]

单峰序列问题 if(a[i]a[i+1]) continue; else break; if(i==j) return true; return false; void putnumtop(int num[],int maxn) { } int index=findtopindex(num,0,maxn-1); if(index!=-1&&isup(num,0,index)&&isdown(num,index,maxn-1)) { } cout<<"The sequence is a unimodal sequence"<

单峰序列问题 cout<<"Input the number of sequence:"; cin>>x; cout<<"Input the element of sequence:"; for(int i=0;i>num[i]; putnumtop(num,x); return 0; } 程序调试与测试记录在各种数据测试下面，峰顶元素在不同的位置，利用所设计的算法都可达到正确的结果，可以初步推断出该算法具有较好解决单峰序列的问题。 5

分享到：

赞收藏

资料库

算法设计与分析实验报告.pdf

相关推荐

课程资源

热门标签

最新资料