算法设计与分析实验报告

实验一递归与分治策略一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

二、实验内容1、①设a[0:n-1]是已排好序的数组。

请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。

当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

②写出三分搜索法的程序。

三、实验要求（1）用分治法求解上面两个问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。

如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。

2、将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。

如果x>a[2(n-1)/3]，则只需在数组a的右三分之一部分中继续搜索x。

上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。

五、实验结果分析二分搜索法：三分搜索法：时间复杂性：二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。

（n代表集合中元素的个数）三分搜索法：O（3log3n）空间复杂度：O（1）。

六、实验体会本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。

七、附录：（源代码）二分搜索法：#include<iostream.h>#include<stdio.h>int binarySearch(int a[],int x,int n){int left=0;int right=n-1;int i,j;while(left<=right){int middle=(left+right)/2;if(x==a[middle]){i=j=middle;return 1;}if(x>a[middle])left=middle+1;else right=middle-1;}i=right;j=left;return 0;}int main(){ int a[10]={0,1,2,3,4,5,6,7,8,9};int n=10;int x=9;if(binarySearch(a,x,n))cout<<"找到"<<endl;elsecout<<"找不到"<<endl;return 0;}实验二动态规划——求解最优问题一、实验目的1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。

1、求n个元素的全排。

（30分）2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。

（30分）3、设有n=2k个运动员要进行网球循环赛。

设计一个满足要求的比赛日程表。

（40分）提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include "iostream"using namespace std;#define N 100void Perm(int* list, int k, int m){if (k == m){for (int i=0; i<m; i++)cout << list[i] << " ";cout << endl;return;}else{for (int i=m; i<k; i++){swap(list[m], list[i]);Perm(list, k, m+1);swap(list[m], list[i]);}}}void swap(int a,int b){int temp;temp=a;a=b;b=temp;}int main(){int i,n;int a[N];cout<<"请输入排列数据总个数：";cin>>n;cout<<"请输入数据：";for(i=0;i<n;i++){cin>>a[i];}cout<<"该数据的全排列："<<endl;Perm(a,n,0);return 0;}《算法设计与分析》实验报告实验二递归与分治策略应用提高学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期一、实验目的1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。

算法分析与设计实验报告--回溯法实验目的：通过本次实验，掌握回溯法的基本原理和应用，能够设计出回溯法算法解决实际问题。

实验内容：1.回溯法概述回溯法全称“试探回溯法”，又称“逐步退化法”。

它是一种通过不断试图寻找问题的解，直到找到解或者穷尽所有可能的解空间技术。

回溯法的基本思路是从问题的某一个初始状态开始，搜索可行解步骤，一旦发现不满足求解条件的解就回溯到上一步，重新进行搜索，直到找到解或者所有可能的解空间已经搜索完毕。

2.回溯法的基本应用回溯法可用于求解许多 NP 问题，如 0/1 背包问题、八皇后问题、旅行商问题等。

它通常分为两种类型：一种是通过枚举所有可能的解空间来寻找解；另一种则是通过剪枝操作将搜索空间减少到若干种情况，大大减少了搜索时间。

3.回溯法的解题思路（1）问题分析：首先需要对问题进行分析，确定可行解空间和搜索策略；（2）状态表示：将问题的每一种状况表示成一个状态；（3）搜索策略：确定解空间的搜索顺序；（4）搜索过程：通过逐步试探，不断扩大搜索范围，更新当前状态；（5）终止条件：在搜索过程中，如果找到了满足要求的解，或者所有的可行解空间都已搜索完毕，就结束搜索。

4.八皇后问题八皇后问题是指在一个 8x8 的棋盘上放置八个皇后，使得任意两个皇后都不在同一行、同一列或同一对角线上。

通过回溯法可以求解出所有的可能解。

实验过程：回溯法的实现关键在于搜索空间的剪枝，避免搜索无用的解；因此，对于八皇后问题，需要建立一个二维数组来存放棋盘状态，以及一个一维数组来存放每行放置的皇后位置。

从第一行开始搜索，按照列的顺序依次判断当前的空位是否可以放置皇后，如果可以，则在相应的位置标记皇后，并递归到下一行；如果不能，则回溯到上一行，重新搜索。

当搜索到第八行时，获取一组解并返回。

代码实现：```pythondef is_valid(board, row, col):for i in range(row):if board[i] == col or abs(board[i] - col) == abs(i - row):return Falsereturn True实验结果：当 n=4 时，求得的所有可行解如下：```[[1, 3, 0, 2],[2, 0, 3, 1]]```本次实验通过实现回溯法求解八皇后问题，掌握了回溯法的基本原理和应用，并对回溯法的核心思想进行了深入理解。

算法实验报告范文《算法设计与分析》实验报告班级姓名学号年月日目录实验一二分查找程序实现…………………………………………………………………03页实验二棋盘覆盖问题（分治法）.…………………………………………………………08页实验三0-1背包问题的动态规划算法设计……………………………………………….11页实验四背包问题的贪心算法………………………………………………………………14页实验五最小重量机器设计问题（回溯法）………………………………………………17页实验六最小重量机器设计问题（分支限界法）…………………………………………20页指导教师对实验报告的评语成绩：指导教师签字：年月日2实验一：二分查找程序实现一、实验时间：2022年10月8日，星期二，第一、二节地点：J13#328二、实验目的及要求目的：1、用c/c++语言实现二分搜索算法。

2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。

三、实验环境平台：Win732位操作系统开发工具：Codeblock10.05四、实验内容对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素某。

五、算法描述及实验步骤算法描述：折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。

它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的某作比较，如果某=a[n/2]则找到某，算法终止。

如果某a[n/2]，则我们只要在数组a的右半部继续搜索某。

二分搜索法的应用极其广泛，而且它的思想易于理解。

确定算法复杂度基本步骤：1、首先设定问题规模n；2、随即产生递增数列；3、在n个有序数中随机取一个作为待查找量，搜索之；4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次；5、改变问题规模n重复上述步骤2~4，n取100、200……1000；6、依实验数据作图，并与理论图作比较；7、二分搜索算法平均查找次数：问题规模为n时，平均查找次数为：A(n)=Int(logn)+1/2//Int()函数为向下取整3即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。

算法分析与设计实验报告：合并排序与快速排序一、引言算法是计算机科学中非常重要的一部分，它涉及到解决问题的方法和步骤。

合并排序和快速排序是两种经典而常用的排序算法。

本文将对这两种排序算法进行分析和设计实验，通过对比它们的性能和效率，以期得出最优算法。

二、合并排序合并排序是一种分治算法，它将原始数组不断分解为更小的数组，直到最后细分为单个元素。

然后，再将这些单个元素两两合并，形成一个有序数组。

合并排序的核心操作是合并两个有序的数组。

1. 算法步骤（1）将原始数组分解为更小的子数组，直到每个子数组只有一个元素；（2）两两合并相邻的子数组，同时进行排序，生成新的有序数组；（3）重复步骤（2），直到生成最终的有序数组。

2. 算法性能合并排序的最优时间复杂度为O(nlogn)，其中n为待排序数组的长度。

无论最好情况还是最坏情况，合并排序的复杂度都相同。

合并排序需要额外的存储空间来存储临时数组，所以空间复杂度为O(n)。

三、快速排序快速排序也是一种分治算法，它将原始数组根据一个主元（pivot）分成两个子数组，一个子数组的元素都小于主元，另一个子数组的元素都大于主元。

然后，递归地对这两个子数组进行排序，最后得到有序数组。

快速排序的核心操作是划分。

1. 算法步骤（1）选择一个主元（pivot），可以是随机选择或者固定选择第一个元素；（2）将原始数组根据主元划分为两个子数组，一个子数组的元素都小于主元，另一个子数组的元素都大于主元；（3）递归地对这两个子数组进行快速排序；（4）重复步骤（2）和（3），直到每个子数组只有一个元素，即得到最终的有序数组。

2. 算法性能快速排序的平均时间复杂度为O(nlogn)，其中n为待排序数组的长度。

最坏情况下，当每次选择的主元都是最小或最大元素时，时间复杂度为O(n^2)。

快速排序是原地排序，不需要额外的存储空间，所以空间复杂度为O(1)。

四、实验设计为了验证合并排序和快速排序的性能和效率，我们设计以下实验：1. 实验目的：比较合并排序和快速排序的时间复杂度和空间复杂度。

算法分析与设计实验报告算法分析与设计实验报告一、引言算法是计算机科学的核心，它们是解决问题的有效工具。

算法分析与设计是计算机科学中的重要课题，通过对算法的分析与设计，我们可以优化计算机程序的效率，提高计算机系统的性能。

本实验报告旨在介绍算法分析与设计的基本概念和方法，并通过实验验证这些方法的有效性。

二、算法分析算法分析是评估算法性能的过程。

在实际应用中，我们常常需要比较不同算法的效率和资源消耗，以选择最适合的算法。

常用的算法分析方法包括时间复杂度和空间复杂度。

1. 时间复杂度时间复杂度衡量了算法执行所需的时间。

通常用大O表示法表示时间复杂度，表示算法的最坏情况下的运行时间。

常见的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)和O(n^2)等。

其中，O(1)表示常数时间复杂度，O(log n)表示对数时间复杂度，O(n)表示线性时间复杂度，O(n log n)表示线性对数时间复杂度，O(n^2)表示平方时间复杂度。

2. 空间复杂度空间复杂度衡量了算法执行所需的存储空间。

通常用大O表示法表示空间复杂度，表示算法所需的额外存储空间。

常见的空间复杂度有O(1)、O(n)和O(n^2)等。

其中，O(1)表示常数空间复杂度，O(n)表示线性空间复杂度，O(n^2)表示平方空间复杂度。

三、算法设计算法设计是构思和实现算法的过程。

好的算法设计能够提高算法的效率和可靠性。

常用的算法设计方法包括贪心算法、动态规划、分治法和回溯法等。

1. 贪心算法贪心算法是一种简单而高效的算法设计方法。

它通过每一步选择局部最优解，最终得到全局最优解。

贪心算法的时间复杂度通常较低，但不能保证得到最优解。

2. 动态规划动态规划是一种将问题分解为子问题并以自底向上的方式求解的算法设计方法。

它通过保存子问题的解，避免重复计算，提高算法的效率。

动态规划适用于具有重叠子问题和最优子结构的问题。

3. 分治法分治法是一种将问题分解为更小规模的子问题并以递归的方式求解的算法设计方法。

院系：计算机科学学院专业：年级：课程名称：算法设计与分析基础班号：组号：指导教师：年月日实验结果及分析1.求最大数2.递归法与迭代法性能比较递归迭代3.改进算法1.利用公式法对第n项Fibonacci数求解时可能会得出错误结果。

主要原因是由于double类型的精度还不够，所以程序算出来的结果会有误差，要把公式展开计算。

2.由于递归调用栈是一个费时的过程，通过递归法和迭代法的比较表明，虽然递归算法的代码更精简更有可读性，但是执行速度无法满足大数问题的求解。

3.在当前计算机的空间较大的情况下，在一些速度较慢的问题中，空间换时间是一个比较周全的策略。

实验原理（算法基本思想）定义：若A=(a ij), B=(b ij)是n×n的方阵，则对i,j=1,2,…n，定义乘积C=A⋅B 中的元素c ij为：1.分块解法通常的做法是将矩阵进行分块相乘，如下图所示：二．Strassen解法分治法思想将问题实例划分为同一问题的几个较小的实例。

对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一种算法。

如果有必要，合并这些问题的解，以得到原始问题的解。

求解矩阵相乘的DAC算法，使用了strassen算法。

DAC（A[]，B[]，n）{If n=2 使用7次乘法的方法求得解ElseDivide（A）//把A分成4块Divide（B）//把B分成4块调用7次strassen算法求得解的4块合并这4块得到解并返回}伪代码Serial_StrassenMultiply(A, B, C) {T1 = A0 + A3;T2 = B0 + B3;StrassenMultiply(T1, T2, M1);T1 = A2 + A3;StrassenMultiply(T1, B0, M2);T1 = (B1 - B3);StrassenMultiply (A0, T1, M3);T1 = B2 - B0;StrassenMultiply(A3, T1, M4);T1 = A0 + A1;StrassenMultiply(T1, B3, M5);T1 = A2 – A0;T2 = B0 + B1;StrassenMultiply(T1, T2, M6);T1 = A1 – A3;T2 = B2 + B3;StrassenMultiply(T1, T2, M7);C0 = M1 + M4 - M5 + M7C1 = M3 + M5C2 = M2 + M4C3 = M1 - M2 + M3 + M6}实验结果及分析时间复杂度1.分块相乘总共用了8次乘法，因而需要Θ(n log28)即Θ(n3)的时间复杂度。

算法设计与分析实验报告实验一全排列、快速排序【实验目的】1. 掌握全排列的递归算法。

2. 了解快速排序的分治算法思想。

【实验原理】一、全排列全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。

任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n 个数字的排列为例说明排列的生成法。

n个字符的全体排列之间存在一个确定的线性顺序关系。

所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。

每个排列的后继都可以从它的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。

二、快速排序快速排序（Quicksort）是对冒泡排序的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

【实验内容】１.全排列递归算法的实现。

２.快速排序分治算法的实现。

【实验结果】１. 全排列：２. 快速排序：实验二最长公共子序列、活动安排问题【实验目的】１. 了解动态规划算法设计思想，运用动态规划算法实现最长公共子序列问题。

２. 了解贪心算法思想，运用贪心算法设计思想实现活动安排问题。

【实验原理】一、动态规划法解最长公共子序列设序列X=和Y=的一个最长公共子序列Z=，则：i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；ii. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；iii. 若xm≠yn且z k≠yn ，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=，Yn-1=，Zk-1=。

最长公共子序列问题具有最优子结构性质。

由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。

题目: 输油管道问题学号0091313000913133学生姓名张一楠朱玉婷专业（班级）09计本1班设计题目输油管道问题设计技术参数系统平台：windows 7开发工具：Microsoft Visual C++ 6.0设计要求1.掌握问题分析的方法与步骤，选择合适的方法解决问题。

2.选择合适的算法编写程序。

工作计划1：熟悉题目并理解，及找寻相关资料。

2：根据题目设计并分析算法。

3：使用Visual C++实现。

4：完成设计报告参考资料吕国英.《算法设计与分析》.北京:清华大学出版社,2009摘要本实验，我们通过综合应用算法解决了实际生活中的输油管道问题，通过比较各种算法的时间复杂度以及解决效率，采用了算法中以分治法为基础的随机划分来解决问题，利用随机选择方法找到各个油井的中位数，通过讨论论证了中位数即最优管道位置。

信息奥赛中一个问题有多个算法解决，通过比较不同算法解决问题的效率，选择最高效的一个。

在输油管道问题这个实验中得到运用。

关键词：算法设计，分治法，随机划分，随机选择，中位数目录1 需求分析.............................................................................. 错误！未定义书签。

1.1 实验内容.................................................................... 错误！未定义书签。

1.2 系统的基本逻辑模型 ....................................................... 错误！未定义书签。

1.3 确定目标系统的功能 (5)2 总体设计............................................................................. 错误！未定义书签。

实验一找最大和最小元素与归并分类算法实现（用分治法）一、实验目的1．掌握能用分治法求解的问题应满足的条件；2．加深对分治法算法设计方法的理解与应用；3．锻炼学生对程序跟踪调试能力；4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

二、实验内容1、找最大和最小元素输入n 个数，找出最大和最小数的问题。

2、归并分类将一个含有n个元素的集合，按非降的次序分类（排序）。

三、实验要求（1）用分治法求解问题（2）上机实现所设计的算法；四、实验过程设计（算法设计过程）1、找最大和最小元素采用分治法，将数组不断划分，进行递归。

递归结束的条件为划分到最后若为一个元素则max和min都是这个元素，若为两个取大值赋给max，小值给min。

否则就继续进行划分，找到两个子问题的最大和最小值后，比较这两个最大值和最小值找到解。

2、归并分类使用分治的策略来将一个待排序的数组分成两个子数组，然后递归地对子数组进行排序，最后将排序好的子数组合并成一个有序的数组。

在合并过程中，比较两个子数组的首个元素，将较小的元素放入辅助数组，并指针向后移动，直到将所有元素都合并到辅助数组中。

五、源代码1、找最大和最小元素#include<iostream>using namespace std;void MAXMIN(int num[], int left, int right, int& fmax, int& fmin); int main() {int n;int left=0, right;int fmax, fmin;int num[100];cout<<"请输入数字个数：";cin >> n;right = n-1;cout << "输入数字:";for (int i = 0; i < n; i++) {cin >> num[i];}MAXMIN(num, left, right, fmax, fmin);cout << "最大值为：";cout << fmax << endl;cout << "最小值为：";cout << fmin << endl;return 0;}void MAXMIN(int num[], int left, int right, int& fmax, int& fmin) { int mid;int lmax, lmin;int rmax, rmin;if (left == right) {fmax = num[left];fmin = num[left];}else if (right - left == 1) {if (num[right] > num[left]) {fmax = num[right];fmin = num[left];}else {fmax = num[left];fmin = num[right];}}else {mid = left + (right - left) / 2;MAXMIN(num, left, mid, lmax, lmin);MAXMIN(num, mid+1, right, rmax, rmin);fmax = max(lmax, rmax);fmin = min(lmin, rmin);}}2、归并分类#include<iostream>using namespace std;int num[100];int n;void merge(int left, int mid, int right) { int a[100];int i, j,k,m;i = left;j = mid+1;k = left;while (i <= mid && j <= right) {if (num[i] < num[j]) {a[k] = num[i++];}else {a[k] = num[j++];}k++;}if (i <= mid) {for (m = i; m <= mid; m++) {a[k++] = num[i++];}}else {for (m = j; m <= right; m++) {a[k++] = num[j++];}}for (i = left; i <= right; i++) { num[i] = a[i];}}void mergesort(int left, int right) { int mid;if (left < right) {mid = left + (right - left) / 2;mergesort(left, mid);mergesort(mid + 1, right);merge(left, mid, right);}}int main() {int left=0,right;int i;cout << "请输入数字个数：";cin >> n;right = n - 1;cout << "输入数字:";for (i = 0; i < n; i++) {cin >> num[i];}mergesort(left,right);for (i = 0; i < n; i++) {cout<< num[i];}return 0;}六、运行结果和算法复杂度分析1、找最大和最小元素图1-1 找最大和最小元素结果算法复杂度为O(logn）2、归并分类图1-2 归并分类结果算法复杂度为O(nlogn）实验二背包问题和最小生成树算法实现（用贪心法）一、实验目的1．掌握能用贪心法求解的问题应满足的条件；2．加深对贪心法算法设计方法的理解与应用；3．锻炼学生对程序跟踪调试能力；4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

算法设计与分析实验报告教师：学号：姓名：实验一：串匹配问题实验目的：(1) 深刻理解并掌握蛮力法的设计思想;(2) 提高应用蛮力法设计算法的技能;(3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。

三、实验要求：( 1) 实现BF 算法;(2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法;(3 ) 对上述3 个算法进行时间复杂性分析, 并设计实验程序验证分析结果。

#include "stdio.h"#include "conio.h"#include <iostream>//BF算法int BF(char s[],char t[]){ int i; int a; int b; int m,n; m=strlen(s); //主串长度n=strlen(t); //子串长度printf("\n*****BF*****算法\n");for(i=0;i<m;i++){ b=0; a=i; while(s[a]==t[b]&&b!=n){a++; b++; }if(b==n){ printf("查找成功!!\n\n"); return 0;}}printf("找不到%s\n\n",t); return 0; }//前缀函数值,用于KMP算法int GETNEXT(char t[],int b){ int NEXT[10]; NEXT[0]=-1;int j,k; j=0; k=-1; while(j<strlen(t)){if ((k==-1)||(t[j]==t[k])){j++;k++;NEXT[j]=k; }else k=NEXT[k];}b=NEXT[b];return b;}//KMP算法int KMP(char s[],char t[]){int a=0; int b=0;int m,n; m=strlen(s); //主串长度n=strlen(t); //子串长度printf("\n*****KMP算法*****\n");while(a<=m-n){while(s[a]==t[b]&&b!=n){a++;b++; }if(b==n){printf("查找成功!!\n\n");return 0;}b=GETNEXT(t,b);a=a-b;if(b==-1) b++;}printf("找不到%s\n\n",t);return 0; } //滑动距离函数,用于BM算法int DIST(char t[],char c){ int i=0,x=1;int n; n=strlen(t);while(x&&i!=n-1){if(t[i]==c)x=0;else i++;}if(i!=n-1)n=n-1-i;return n; } //BM算法结果分析与体会：glibc里的strstr函数用的是brute-force(naive)算法，它与其它算法的区别是strstr不对pattern(needle)进行预处理，所以用起来很方便。

《算法设计与分析》实验报告实验三回溯法3.迷宫问题一天Luna在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，. 和#，前者表示可以通行后者表示不能通行。

同时当Luna处在某个格点时，她只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Luna想要从点A走到点B（不能走出迷宫）。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

[输入]第1行是测试数据的组数k，后面跟着k组输入。

每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n 的。

接下来是一个n * n的矩阵，矩阵中的元素为. 或者#。

再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb 行, 第lb列。

注意到ha, la, hb, lb全部是从0开始计数的。

1.八皇后问题1.1解题思路八皇后问题的解法，很简单的解法。

通过回溯实现枚举。

对于当前行，尝试是否可在当前列放置皇后，然后进入下一行的尝试，同时尝试完毕以后，要将当前行回复（回溯），来进行下一次尝试。

到达最后一行的时候，即递归结束条件，打印结果即可。

1.2程序运行情况1.3所有的皇后解见附录。

（毕竟92个解...）1.4程序源码（含注释）2. 24点问题2.1 解题思路这题虽然使用dfs很简单，但是有一点思维在里面。

我很惭愧，自己没有想出来怎么如意的独立AC此题。

遇到的最大的问题——如何插入括号？枚举插入、和运算符一同排列都不靠谱。

解决方法是：用同等的办法转化。

每一次从待组合的是数字中，任取两个数，随机用运算符计算完毕后，再放回去。

下一次计算，再次重复这个过程，可以等价为有括号的运算方式了。

遇到第二个问题——如何实现这种“任取两个数”的选择方式。

这里就直接体现出了我个人能力的不足。

居然没想到。

尝试使用STL的set，但是没成功。

算法设计与分析报告学生姓名学号专业班级指导教师完成时间目录一、课程内容 (3)二、算法分析 (3)1、分治法 (3)（1)分治法核心思想 (3)（2）MaxMin算法分析 (3)2、动态规划 (4)（1）动态规划核心思想 (4)（2）矩阵连乘算法分析 (5)3、贪心法 (5)(1）贪心法核心思想 (5)（2）背包问题算法分析 (6)（3）装载问题算法分析 (7)4、回溯法 (7)（1）回溯法核心思想 (7)（2)N皇后问题非递归算法分析 (7)(3）N皇后问题递归算法分析 (8)三、例子说明 (9)1、MaxMin问题 (9)2、矩阵连乘 (10)3、背包问题 (10)4、最优装载 (10)5、N皇后问题(非递归） (11)6、N皇后问题(递归) (11)四、心得体会 (12)五、算法对应的例子代码 (12)1、求最大值最小值 (12)2、矩阵连乘问题 (13)3、背包问题 (15)4、装载问题 (17)5、N皇后问题(非递归） (19)6、N皇后问题(递归） (20)一、课程内容1、分治法,求最大值最小值，maxmin算法；2、动态规划，矩阵连乘，求最少连乘次数；3、贪心法，1）背包问题，2）装载问题；4、回溯法，N皇后问题的循环结构算法和递归结构算法。

二、算法分析1、分治法（1）分治法核心思想当要求解一个输入规模为n,且n的取值相当大的问题时，直接求解往往是非常困难的。

如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n, 而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。

那末，这类问题可以用分治法求解。

分治法的核心技术1)子问题的划分技术.2）递归技术。

反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。

3)合并技术.（2）MaxMin算法分析问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。

《算法分析与设计》课程实验实验报告专业：计算机科学与技术班级：姓名：学号：完成时间：2009年6月15日实验一算法实现一一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对分治法、贪心算法的理解。

二、实验内容:掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。

三、实验题1. 【伪造硬币问题】给你一个装有n个硬币的袋子。

n个硬币中有一个是伪造的。

你的任务是找出这个伪造的硬币。

为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。

试用分治法的思想写出解决问题的算法，并计算其时间复杂度。

2.【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。

售货员希望用数目最少的硬币找给小孩。

假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。

给出一种找零钱的贪心算法。

四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。

五、实验程序1.伪造硬币问题源程序：//c语言实现#include<stdio.h>#include<stdlib.h>#include<math.h>#define N 100#define N1 12//只能判断是否相等的天平void solve(int coin[],int count,int first,int last) {if (count==2) {printf("无法判断\n");return;}if (first==last) {//只有一个硬币时候printf("假币的序号为%d, 假币的重量为%d\n", first, coin[first]);}else if(last-first==1){ //如果只剩下两个硬币（此时count不为）if (first > 0) { //不是最开始的硬币if (coin[first] == coin[0]) //如果第first和第个相等，说明first 位置不是伪币solve(coin,count,first+1,last);else//否则，说明first位置是伪币solve(coin,count,first,last-1);}else if(last<count-1){ //不是最后的硬币if (coin[first]==coin[count-1]) //如果第first和最后一个相等，说明last位置不是伪币solve(coin,count,first+1,last);else//否则，说明first位置是伪币solve(coin,count,first,last-1);}}else if (first<last){int temp=(last-first+1)/3; //将硬币分为三组int sum1=0, sum2=0;for(int i=0;i<temp;i++){sum1+=coin[first+i];sum2+=coin[last-i];}if (sum1==sum2){ //两边的总重相等,在中间，递归solve(coin,count,first+temp,last-temp);}else {//在两边,不在中间if (sum1==coin[first+temp]*temp){ //左边的和中间的相等,在右边，递归solve(coin,count,last-temp+1,last);}else {solve(coin,count,first,first+temp-1); //右边的和中间的相等,在左边，递归}}}}void main() {int i;int coin[N]; //定义数组coin用来存放硬币重量for(i=0;i<N;i++) //初始化数组coin[i]=0; //所用硬币初始值为coin[N1]=1; //第N1个设置为，即伪币int cnt = N;printf("硬币个数：%d\n",cnt);solve(coin,cnt,0,cnt-1);}2找零钱问题（1）零钱个数无限制的时候:源程序：//c语言实现#include<stdio.h>main(){int T[]={25,10,5,1};int a[5];int money,i,j;printf("输入钱数:\n");scanf("%d",&money);for(i=0;i<4;i++){a[i]=money/T[i];money=money%T[i];}printf("找钱结果:\n硬币:\t");for(i=0;i<=3;i++){printf("%d\t|\t",T[i]);}printf("\n个数:\t");for(i=0;i<=3;i++){printf("%d\t|\t",a[i]);}printf("\n");return(0);}（2）当零钱个数有个数限制的时候：源程序：//c语言实现#include<stdio.h>main(){int T[]={25,10,5,1}; //硬币的面值int a[5]; //用来记录找钱的个数int count[]={1,2,10,1000}; //各个面值硬币的个数int money,i;printf("输入钱数:\n");scanf("%d",&money);for(i=0;i<4;i++){if(money>T[i]*count[i]){ //当剩余钱数大于当前硬币总值a[i]=count[i]; //当前硬币个数取现有的最大值money=money-T[i]*count[i];}else{a[i]=money/T[i];money=money%T[i];}}printf("找钱结果:\n硬币:\t");for(i=0;i<=3;i++){printf("%d\t|\t",T[i]);}printf("\n\n个数:\t");for(i=0;i<=3;i++){printf("%d\t|\t",a[i]);}printf("\n");return(0);}六、实验结果1伪造硬币问题运行结果：硬币个数：100假币的序号为12, 假币的重量为1截图：2找零钱问题（1、硬币个数无限制）运行结果：输入钱数:67找钱结果:硬币: 25 | 10 | 5 | 1 |个数: 2 | 1 | 1 | 2 |截图：3找零钱问题（2、硬币个数有限制，其中硬币个数限制分别为1,2,10和1000。

算法分析与设计实验报告算法分析与设计实验报告⼀．实验⽬的1掌握回溯法解题的基本思想以及算法设计⽅法;2.掌握动态规则法和分⽀限界法的基本思想和算法设计⽅法；3掌握深度优先遍历法的基本思想及运⽤；4．进⼀步的对N皇后问题，⼦集和数问题，0-1背包问题做深⼊的了解。

⼆．实验内容1.实现求n 皇后问题和⼦集和数问题的回溯算法。

2.⽤动态规划的⽅法实现0/1背包问题。

3.⽤分⽀限界法实现0/1背包问题。

4.⽤深度优化的⽅法遍历⼀个图，并判断图中是否有回路存在，如果有，请输出回路。

三．实验设计1． N 皇后问题：我是采取了尊循 top-down design 的顺序来设计整个算法和程序。

采⽤ OOP 的思想，先假设存在⼀个 · 表⽰棋盘格局的类 queens ，则定义回溯函数 solve_from(queens configuration)，configuration 表⽰当前棋盘格局，算法不断扩展棋盘的当前格局（找到下⼀个⾮冲突位置），当找到⼀个解决⽅案时打印该⽅案。

该递归函数采⽤回溯法求出所有解。

main 函数调⽤ solve_from 时传递的实参是⼀个空棋盘。

对于模拟棋盘的 queens 类，我们可以定义三个数据成员： 1.size ：棋盘的边长，即⼤⼩ .2. count ：已放置的互不冲突的皇后数 3.array[][]：布尔矩阵，true 表⽰当前格有皇后这⾥需要稍加思考以便稍后可以简化程序：因为每⾏只能放⼀个皇后，从上到下，从左到右放，那么 count 个皇后占⽤的⾏为 0——count －1。

所以count 还表⽰下⼀个皇后应该添加在哪⼀⾏。

这样，和 remove 操作的⼊⼝参数就只需要提供列号就⾏了， add 降低了耦合度：）下⾯是程序运⾏结果：2．⼦集和数问题：本设计利⽤⼤⼩固定的元组来研究回溯算法，在此情况下，解向量的元素X （i ）取1或0值，它表⽰是否包含了权数W （i ）.⽣成图中任⼀结点的⼉⼦是很容易的。

算法设计及实验报告实验报告1 递归算法一、实验目的掌握递归算法的基本思想；掌握该算法的时间复杂度分析；二、实验环境电脑一台，Turbo C 运行环境三、实验内容、步骤和结果分析以下是四个递归算法的应用例子：用C语言实现1.阶乘：main(){int i,k;scanf("%d\n",&i);k= factorial(i);printf("%d\n",k);}int factorial(int n){ int s;if(n==0) s=1;else s=n*factorial(n-1); //执行n-1次return s;}阶乘的递归式很快，是个线性时间，因此在最坏情况下时间复杂度为O(n)。

2.Fibonacci 数列：main(){int i,m;scanf("%d\n",&i);m=fb(i);printf("%d",m);}int fb(int n){int s;if(n<=1)return 1;else s=fb(n-1)+fb(n-2);return s;}Fibonacci数列则是T(n)=T(n-1)+T(n-2)+O(1)的操作，也就是T(n)=2T(n)+O(1),由递归方程式可以知道他的时间复杂度T(n)是O(2n)，该数列的规律就是不停的赋值，使用的内存空间也随着函数调用栈的增长而增长。

3.二分查找（分治法）#include<stdio.h>#define const 8main(){int a[]={0,1,2,3,4,5,6,7,8,9};int n=sizeof(a);int s;s=BinSearch(a,const,n);printf("suo cha de shu shi di %d ge",s);}BinSearch(int a[],int x,int n){int left,right,middle=0;left=0;right=n-1;whlie(left<=right){middle=(left+right)/2;if(x==a[middle]) return middle;if(x>a[middle]) left=middle+1;else right=middle-1;}return -1;}二分搜索算法利用了元素间的次序关系，采用分治策略，由上程序可知，每执行一次while循环，数组大小减少一半，因此在最坏情况下，while循环被执行了O（logn）次。

本科实验报告课程名称：算法设计与分析实验项目：递归与分治算法实验地点：计算机系实验楼110专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真指导教师：郝晓丽2018年05月04 日实验一递归与分治算法1.1 实验目的与要求1．进一步熟悉C/C++语言的集成开发环境；2．通过本实验加深对递归与分治策略的理解和运用。

1.2 实验课时2学时1.3 实验原理分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。

需要注意的是，分治法使用递归的思想。

划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。

最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。

1.4 实验题目1．上机题目：格雷码构造问题Gray码是一个长度为2n的序列。

序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。

试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。

对于给定的正整数n，格雷码为满足如下条件的一个编码序列。

（1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。

（2）序列中无相同的编码。

（3）序列中位置相邻的两个编码恰有一位不同。

2．设计思想：根据格雷码的性质，找到他的规律，可发现，1位是0 1。

两位是00 01 11 10。

三位是000 001 011010 110 111 101 100。

n位是前n-1位的2倍个。

N-1个位前面加0，N-2为倒转再前面再加1。

3．代码设计：}}}int main(){int n;while(cin>>n){get_grad(n);for(int i=0;i<My_grad.size();i++)cout<<My_grad[i]<<endl;My_grad.clear();}return 0;}运行结果：1.5 思考题（1）递归的关键问题在哪里？答：1.递归式，就是如何将原问题划分成子问题。

《算法设计与分析》课程实验报告实验序号：04实验项目名称：实验4 分治法（三）一、实验题目1.邮局选址问题问题描述：在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。

用x 坐标表示东西向，用y坐标表示南北向。

各居民点的位置可以由坐标(x,y)表示。

街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值∣x1−x2∣+∣y1−y2∣度量。

居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。

编程任务：给定n 个居民点的位置,编程计算邮局的最佳位置。

2.最大子数组问题问题描述：对给定数组A，寻找A的和最大的非空连续子数组。

3.寻找近似中值问题描述：设A是n个数的序列，如果A中的元素x满足以下条件：小于x的数的个数≥n/4,且大于x的数的个数≥n/4 ，则称x为A的近似中值。

设计算法求出A的一个近似中值。

如果A中不存在近似中值，输出false，否则输出找到的一个近似中值4.循环赛日程表问题描述：设有n=2^k个运动员要进行网球循环赛。

现要设计一个满足以下要求的比赛日程表：每个选手必须与其他n-1个选手各赛一次，每个选手一天只能赛一次，循环赛一共进行n-1天。

二、实验目的（1）进一步理解分治法解决问题的思想及步骤（2）体会分治法解决问题时递归及迭代两种不同程序实现的应用情况之差异（3）熟练掌握分治法的自底向上填表实现（4）将分治法灵活于具体实际问题的解决过程中，重点体会大问题如何分解为子问题及每一个大问题涉及哪些子问题及子问题的表示。

三、实验要求（1）写清算法的设计思想。

（2）用递归或者迭代方法实现你的算法，并分析两种实现的优缺点。

（3）根据你的数据结构设计测试数据，并记录实验结果。

（4）请给出你所设计算法的时间复杂度的分析，如果是递归算法，请写清楚算法执行时间的递推式。

四、实验过程（算法设计思想、源码）1.邮局选址问题(1)算法设计思想根据题目要求，街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值∣x1−x2∣+∣y1−y2∣度量。