浙江大学城市学院实验报告
课程名称 数据结构基础 实验项目名称 实验三 算法和算法分析 学生姓名 专业班级 学号
实验成绩 指导老师（签名 ） 日期
一. 实验目的和要求
1. 通过对算法的分析，了解提高算法的运算速度和降低算法的存储空间之间的矛盾。
2. 通过对算法复杂度的分析，掌握计算时间复杂度和空间复杂度的基本方法。
3. 初步掌握测试算法运行时间的基本方法。
二. 实验内容
1、 根据算法编写程序
已知输入x ，y ，z 三个不相等的整数，试根据如下算法（N-S 图）编写一个C 语言函数，实现三个数从小到大顺序的输出。
x 中已存放最小数）
y 中已存放次小数）
三个数排序算法的N-S 图
要求：把该程序存放在文件test1_3_1.cpp 中，编译并调试程序，直到正确运行。
并请分析：该算法要进行___3___次比较，在最好的情况下需要交换数据元素____0__次，在最坏的情况下需要交换数据元素__3____次。
2、测试算法的运行时间
在此，我们通过一个比较两个算法执行效率的程序例子，掌握测试算法运行时间的基本方法。这里涉及到C语言中标准的函数库sys/timeb。sys/timeb函数库中提供了处理与时间相关的函数。其中函数ftime的功能是获取当前的系统时间。
步骤1：输入两个C语言主程序test1_3_2.cpp和test1_3_3.cpp。
主文件(test1_3_2.cpp) ：
# include
# include
void main()
{
1 timeb t1, t2;
2 long t;
3 double x, sum=1, sum1;
4 int i, j, n;
5 printf("请输入x，n：") ;
6 scanf("%lf,%d", &x, &n) ;
7 ftime(&t1) ; // 求得当前时间
8 for(i=1; i<=n; i++)
9 {
10 sum1=1;
11 for(j=1; j<=i; j++)
12 sum1=sum1*(-1.0/x) ;
13 sum+=sum1;
14 }
15 ftime(&t2) ; // 求得当前时间
16 t=(t2.time-t1.time)*1000+(https://www.doczj.com/doc/6c18123539.html,litm) ; //计算时间差，转换成毫秒
17 printf("sum=%lf 用时%ld 毫秒\n", sum, t) ;
}
该算法的N-S 图如下所示。为了便于说明程序段与N-S 图之间的对应关系，我们将函数体中的语句加上了标号，并与图中相应的处理框、循环框或判断框相对应。
…5, 6---7…15…16, 17…外循环8,9,10,14…内外循环11,12,13
主文件 (test1_3_3.cpp) ：
# include
# include
void main()
{
timeb t1, t2;
long t;
double x, sum1=1, sum=1;
int i, n;
printf("请输入x，n: ") ;
scanf("%lf,%d", &x, &n) ;
ftime(&t1) ; // 求得当前时间
for(i=1;i<=n;i++)
{
sum1*=-1.0/x;
sum+=sum1;
}
ftime(&t2) ; // 求得当前时间
t=(t2.time-t1.time)*1000+(https://www.doczj.com/doc/6c18123539.html,litm) ; // 计算时间差，转换成毫秒printf("sum=%lf 用时%ld毫秒\n", sum, t) ;
}
步骤2：请读懂这两个算法，并分析：
这两个算法的功能是：
计算 1!/2 + 2!/3 +...+ i!/(i+1) +...+ n!/(n+1)的值，并计算运算所需的时间
这两个算法在程序结构上的区别是：
_____________使用的算法不同，程序的简洁性，易读性，快捷性也不同。___
_____________________________________________________________________
它们的时间复杂度分别是：test1_3_2.cpp为o（n^3），
test1_3_3.cpp为o(n) 。
你的判断是：算法___test1_3_3.cpp____优于算法_test1_3_2.cpp______。
步骤3：调试这两个测试程序，并写出运行结果 (其中用时与计算机的配置有关) 。
test1_3_2.cpp的运行结果为：
输入x, n：__________10,1000______________________；
输出为：_____sum=0.909091___用时16毫秒_______。
test1_3_3.cpp的运行结果为：
输入x, n：____10,1000 _____________________________；
输出为：_______ sum=0.909091___用时0毫秒_________________。
3、编写程序并分析时间复杂度
编写高效率的程序计算1!/2 + 2!/3 +...+ i!/(i+1) +...+ n!/(n+1)的值，把该程序存放在文件test1_3_4.cpp中，并分析：
该算法的时间复杂度为o（n^3）
该算法的时间效率是否已经最优否
4、填写实验报告内容，实验报告文件取名为report3.doc。
5、上传实验报告文件report3.doc、源程序文件test1_3_1.cpp、test1_3_2.cpp、test1_3_3.cpp及test1_3_4.cpp到Ftp服务器上自己的文件夹下。
三. 实验结果与分析
（包括运行结果截图、结果分析等）
程序
1
第四题
程序3：
四. 心得体会
（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）
【附录----源程序】
第一题：
#include
int main(void){
int x,y,z,t;
scanf("%d%d%d",&x,&y,&z);
if(x>y)
{ x=x;
}
else
{
t=x;
x=y;
y=t;
}
if(x>z)
{
x=x;
}
else
{
t=x;
x=z;
z=t;
}
if(y>z)
{
z=z;
}
else
{
t=y;
y=z;
z=t;
}
printf("x=%d,y=%d,z=%d\n",x,y,z);
return 0;
}
第三题：
# include
# include
void main()
{
timeb t1, t2;
long t;
double sum1, sum=0;
int i,j, n;
printf("请输入n: ") ;
scanf("%d", &n) ;
ftime(&t1) ;
for(i=1;i<=n;i++)
{
sum1=1;
for(j=1;j<=i;j++){
sum1=sum1*j;
}
sum1=sum1/(i+1);
sum=sum+sum1;
}
ftime(&t2) ;
t=(t2.time-t1.time)*1000+(https://www.doczj.com/doc/6c18123539.html,litm) ;
printf("sum=%lf 用时%ld毫秒\n", sum, t) ; }
《数据结构》必须掌握的知识点与算法 第一章绪论 1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系： （1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 （3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算） 第二章线性表 1、线性表的特点： （1）存在唯一的第一个元素；（这一点决定了图不是线性表） （2）存在唯一的最后一个元素； （3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表） （4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法： （1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节） （2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为： A a[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、线性表的归并排序： 设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4 9、顺序线性表的删除元素过程，可见算法2.5 10、顺序线性表的归并算法，可见算法2.7 11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11 16、链表的归并算法，可见算法2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解
算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 算法分析实验报告 实验一分治策略排序 实验目的 1）以排序问题为例，掌握分治法的基本设计策略； 2）熟练掌握合并排序算法的实现； 3）熟练掌握快速排序算法的实现； 4) 理解常见的算法经验分析方法。 实验环境 计算机、C语言程序设计环境、VC++6.0 实验步骤 算法的基本描述： 1、合并排序的基本思想描述：首先将序列分为两部分，分到每组只有两个元 素，然后对每一部分进行循环递归地合并排序，然后逐个将结果进行合并。 2、快速排序的基本思想描述：将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最后达到排序效果。 要求：编写一个函数data-generate，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为本算法实验的输入数据。 程序流程图： 合并排序原理图 快速排序流程图1.生成2000个随机整数的程序：#include { FILE *fpt; fpt = fopen("D://data.txt","w"); srand(time(0)); for(int i=0;i<2000;i++) fprintf(fpt,"%3d\t",rand()%10000+1); return 0; fclose(fpt); } 并生成data.txt文件。 2.读取data.txt文件，并排序。实现合并排序算法输入：待排数据文件data.txt； 输出：有序数据文件resultsMS.txt 合并排序算法： #include 专题1：算法初步知识点及典型例题（原卷版） 【知识梳理】 知识点一、算法 1．算法的概念 （1）古代定义：指的是用阿拉伯数字进行算术运算的过程。 （2）现代定义：算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。 （3）应用：算法通常可以编成计算机程序，让计算机执行并解决问题。 2．算法的特征： ①指向性：能解决某一个或某一类问题； ②精确性：每一步操作的内容和顺序必须是明确的；算法的每一步都应当做到准确无误，从开始的“第一步”直到“最后一步”之间做到环环相扣，分工明确.“前一步”是“后一步”的前提，“后一步”是“前一步”的继续. ③有限性：必须在有限步内结束并返回一个结果；算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能无限制的持续进行. ④构造性：一个问题可以构造多个算法，算法有优劣之分。 3．算法的表示方法： （1) 用自然语言表示算法: 优点是使用日常用语, 通俗易懂；缺点是文字冗长, 容易出现歧义； （2) 用程序框图表示算法：用图框表示各种操作，优点是直观形象, 易于理解。 注：泛泛地谈算法是没有意义的，算法一定以问题为载体。 例1．下面给出一个问题的算法: S1输入x; S2若x≤2,则执行S3;否则,执行S4; S3输出-2x-1; S4输出x2-6x+3. 问题: (1)这个算法解决的是什么问题? (2)当输入的x值为多大时,输出的数值最小? 知识点二：流程图 1. 流程图的概念： 流程图，是由一些图框和流程线组成的，其中图框表示各种操作的类型，图框中的文字和符合表示操作的内容，流程线表示操作的先后次序。 2. 图形符号名称含义 开始/结束框 用于表示算法的开始与结束 输入/输出框 用于表示数据的输入或结果的输出 处理框描述基本的操作功能，如“赋值”操作、数学 运算等 判断框判断某一条件是否成立，成立时在出口处标明 “是”或“Y”；不成立时标明“否”或“N” 流程线 表示流程的路径和方向 连接点 用于连接另一页或另一部分的框图 注释框 框中内容是对某部分流程图做的解释说明 3. (1)使用标准的框图的符号； (2)框图一般按从上到下、从左到右的方向画； (3)除判断框图外，大多数框图符号只有一个进入点和一个退出点。判断框是具有超过一个退出点的唯一符号； (4)一种判断框是“是”与“不是”两分支的判断，而且有且仅有两个结果；另一种是多分支判断，有几种不同的结果； (5)在图形符号内描述的语言要非常简练清楚。 4.算法的三种基本逻辑结构： （1)顺序结构：由若干个按从上到下的顺序依次进行的处理步骤（语句或框）组成。这是任何一个算法都离不开的基本结构。 （2)条件结构：算法流程中通过对一些条件的判断，根据条件是否成立而取不同的分支流向的结构。它是依据指定条件选择执行不同指令的控制结构。 （3)循环结构：根据指定条件，决定是否重复执行一条或多条指令的控制结构称为循环结构。 知识点三：基本算法语句 程序设计语言由一些有特定含义的程序语句构成，与算法程序框图的三种基本结构相对应，任何程序设计语言都包含输入输出语句、赋值语句、条件语句和循环语句。以下均为BASIC 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 1.通过实验实践、巩固线性表的相关操作； 2.熟悉VC环境，加强编程、调试的练习； 3.用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作； 4.理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的 结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到 第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点 的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出 了这个环表的全部结点为止。 三、程序设计 1、概要设计 为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。 （1）、单向环表的抽象数据类型定义为： ADT Joseph{ 数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={ 兰州交通大学 《算法设计与分析》 实验报告3 题目03-动态规划 专业计算机科学与技术 班级计算机科学与技术2016-02班学号201610333 姓名石博洋 第3章动态规划 1. 实验题目与环境 1.1实验题目及要求 (1) 用代码实现矩阵连乘问题。 给定n个矩阵{A1,A2,…,A n}，其中A i与A i+1是可乘的，i=1,2,…,n-1。考察这n 个矩阵的连乘积A1A2…A n。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，则可以依此次序反复调用2个矩阵相乘的标准算法（有改进的方法，这里不考虑）计算出矩阵连乘积。 确定一个计算顺序，使得需要的乘的次数最少。 (2) 用代码实现最长公共子序列问题。 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>，使得对于所有j=1,2,…,k有Xij=Zj 。例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。 (3) 0-1背包问题。 现有n种物品，对1<=i<=n，已知第i种物品的重量为正整数W i，价值为正整数V i，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分） 使用动态规划使得装入背包的物品价值之和最大。 1.2实验环境： CPU：Intel(R) Core(TM) i3-2120 3.3GHZ 内存：12GB 操作系统：Windows 7.1 X64 编译环境：Mircosoft Visual C++ 6 2. 问题分析 (1) 分析。 《算法设计与分析》知识点总结 1．算法的渐进时间复杂度分析，能够对给定的代码段（伪代码段）进行时间复杂度分析，能够对用关于问题规模n的函数表示的时间复杂度计算其渐进阶。 2．概念： 算法：通俗来讲，算法是指解决问题的方法或者过程，包括输入，输出，确定性，有限性。 1）子问题：结构性质与原问题相似的具有规模更小的问题。 2）可行解：满足某线性规划所有的约束条件（指全部前约束条件和后约束条件）的任意一组决策变量的取值，都称为该线性规划的一个可行解。 3）解空间：若齐次线性方程组有非零解,则其解有无穷多个,而齐次线性方程组所有解的集合构成一个向量空间,这个向量空间就称为解空间. 4）目标函数：指所关心的目标(某一变量)与相关的因素(某些变量)的函数关系。 5）最优解：使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解，都称为该线性规划的一个最优解。 6）最优化问题：一般是指按照给定的标准在某些约束条件下选取最优的解集，即使系统的某些性质能指标达到最大或最小。 7）递归算法：直接或者间接地调用自身的算法称为递归算法。 8）分治法：将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。递归地求出子问题的解，就可得到原问题的解。 9）动态规划：将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解，与分治法不同的，分解的子问题往往不是互相独立的。（为了避免指数时间，不管子问题的解会不会用到，都会填入到一个表中） 10）最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。（动态规划和贪心都有） 11）重叠子问题性质：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要此子问题时，只是简单地用常数时间查看一下结果。 12）备忘录算法：动态规划方法的变形。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的。（其控制结构与递归方法是一样的，只是备忘录方法为每一个解过的子问题建立备忘录，以便需要时查看，避免相同子问题的重复求解） 13）贪心法：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。 14）贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。 15）回溯法：是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这 算法设计与分析实验报告 学院：信息学院 专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月 目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4) 3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6) 作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理： 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系： 《算法设计与分析》实验报告 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 学生实验报告书 实验课程名称算法设计与分析开课学院计算机科学与技术学院 指导教师姓名李晓红 学生姓名 学生专业班级软件工程zy1302班2015-- 2016学年第一学期 实验课程名称：算法设计与分析 同组者实验日期2015年10月20日第一部分：实验分析与设计 一．实验内容描述（问题域描述） 1、利用分治法，写一个快速排序的递归算法，并利用任何一种语言，在计算机上实现，同时 进行时间复杂性分析； 2、要求用递归的方法实现。 二.实验基本原理与设计（包括实验方案设计，实验手段的确定，试验步骤等，用硬件逻辑或者算法描述） 本次的解法使用的是“三向切分的快速排序”，它是快速排序的一种优化版本。不仅利用了分治法和递归实现，而且对于存在大量重复元素的数组，它的效率比快速排序基本版高得多。 它从左到右遍历数组一次，维护一个指针lt使得a[lo..lt-1]中的元素都小于v，一个指针gt 使得a[gt+1..hi]中的元素都大于v，一个指针i使得a[lt..i-1]中的元素都等于v，a[i..gt]中的元素都还未确定，如下图所示： public class Quick3way { public static void sort(Comparable[] a, int lo, int hi) { if (lo >= hi) return; int lt = lo, i = lo + 1, gt = hi; Comparable pivot = a[lo]; 第二部分：实验调试与结果分析 一、调试过程（包括调试方法描述、实验数据记录，实验现象记录，实验过程发现的问题等） 1、调试方法描述： 对程序入口进行断点，随着程序的运行，一步一步的调试，得到运行轨迹； 2、实验数据： "R", "B", "W", "W", "R", "W", "B", "R", "R", "W", "B", "R"； 3、实验现象： 4、实验过程中发现的问题： （1）边界问题： 在设计快速排序的代码时要非常小心，因为其中包含非常关键的边界问题，例如： 什么时候跳出while循环，递归什么时候结束，是对指针的左半部分还是右半部分 排序等等； （2）程序的调试跳转： 在调试过程中要时刻记住程序是对那一部分进行排序，当完成了这部分的排序后， 会跳到哪里又去对另外的那一部分进行排序，这些都是要了然于心的，这样才能准 确的定位程序。 二、实验结果分析（包括结果描述、实验现象分析、影响因素讨论、综合分析和结论等） 1、实验结果： 一、基本题： 算法： 1、程序是算法用某种程序设计语言的具体实现。 2、算法就是一组有穷的序列(规则) ，它们规定了解决某一特定类型问题的一系 列运算。 3、算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。 4、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。 5、算法满足的性质：输入、输出、确定性、有限性。 6、衡量一个算法好坏的标准是时间复杂度低。 7、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂性和 空间复杂性。 8、任何可用计算机求解的问题所需的时间都与其规模有关。 递归与分治： 9、递归与分治算法应满足条件：最优子结构性质与子问题独立。 10、分治法的基本思想是首先将待求解问题分解成若干子问题。 11、边界条件与递归方程是递归函数的两个要素。 12、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。 13、将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击 破。这属于分治法的解决方法。 14、Strassen矩阵乘法是利用分治策略实现的算法。 15、大整数乘积算法是用分治法来设计的。 16、二分搜索算法是利用分治策略实现的算法。 动态规划： 17、动态规划算法的两个基本要素是最优子结构性质和重叠子问题性质。 18、下列算法中通常以自底向上的方式求解最优解的是动态规划法。 19、备忘录方法是动态规划算法的变形。 20、最优子结构性质是贪心算法与动态规划算法的共同点。 21、解决0/1背包问题可以使用动态规划、回溯法，其中不需要排序的是动态规 划，需要排序的是回溯法。 贪心算法： 22、贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体 最优考虑，它所做出的选择只是在某种意义上的局部最优解。 23、最优子结构性质是贪心算法与动态规划算法的共同点。 24、背包问题的贪心算法所需的计算时间为 O(nlogn) 。 回溯法： 25、回溯法中的解空间树结构通常有两种，分别是子集树和排列树。（3） 26、回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。 27、解决0/1背包问题可以使用动态规划、回溯法，其中不需要排序的是动态规 划，需要排序的是回溯法。 28、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数 的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包，只使用约束条件进行裁剪的是 N 皇后问题。 29 用搜索算法解旅行售货员问题时的解空间树是排列树。 30 回溯法搜索状态空间树是按照深度优先遍历的顺序。 31、回溯法算法是以深度优先策略进行搜索的。 32、0-1背包问题的回溯算法所需的计算时间为 O（n2n） 分支限界法： 33、以广度优先搜索或以最小耗费（最大效益）优先的方式搜索问题解的算法称 为分支限界法。 34、分支限界法主要有队列式（FIFO）分支限界法和优先队列式分支限界法。 35、分支限界法解旅行售货员问题时，活结点表的组织形式是最小堆。 其他： 36、10000*n^2+10*n+1的时间复杂度是______。 37、f(n)=n^2+10*n+1000000的时间复杂度是______。 38、算法分析中,记号O表示渐进上界。 39、f(n)= 6×2n+n2，f(n)的渐进上界是 O(2^n)。 40、f(n)= 6×2n+n2，f(n)的渐进上界是 O(n^2)。 41、f(n)= 100×3n+10000×n2，f(n)的渐进上界是_____________。 42、f(n)= 6×4n+n2，f(n)的渐进上界是 O(2^n) 。 43、按照渐近阶从低到高的顺序排列下列表达式：4n2，logn，3n， n2/3，n!，2n。 Logn< n2/3<4n2<2n<3n 算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明 实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 一：实验目的 1：掌握动态规划算法的基本思想，学会用其解决实际问题。 2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。 二：实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 实验一：杨辉三角 问题分析： ①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码： public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1; System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果：n=10 实验二：0-1背包问题 问题分析：：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 实验五动态规划实验 一、实验目的 1.掌握动态规划算法的基本思想。 二、实验内容 1、参考教材描述，使用动态规划算法求解多段图的最短路径问题。#include int *cost=new int[n]; int min_cost; for(i=0;i 第一章概述 算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 算法的特征： 可终止性：算法必须在有限时间内终止； 正确性：算法必须正确描述问题的求解过程； 可行性：算法必须是可实施的； 算法可以有0个或0个以上的输入； 算法必须有1个或1个以上的输出。 算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束； 程序可以没有输出,而算法则必须有输出； 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现； 程序可以不满足算法的有限性性质。 算法描述方式：自然语言，流程图，伪代码，高级语言。 算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。 一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。 算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。 第二章递归与分治 分治法的基本思想： 求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。 分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。 分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。 使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。） 递归的概念：算法分析——实验一
专题1：算法初步知识点及典型例题(原卷版)
北京理工大学《数据结构与算法设计》实验报告实验一
算法分析_实验报告3
算法知识点总结
算法设计与实验报告讲解
算法分析实验报告--分治策略
银行家算法设计实验报告
南京邮电大学算法设计实验报告——动态规划法
武汉理工大学算法分析实验报告
算法设计与分析复习题整理 (1)
算法与设计实验报告
算法设计与分析实验报告
算法分析与设计实验六
算法分析与设计知识点总结
相关主题
文本预览