BX110937李建辉算法设计实验一

算法分析与设计实验一实验内容分别针对随机生成的三组整数序列(规模为1000个数、10000个数、100000个数)进行排序，排序算法使用以下五种经典的方法，分别是：冒泡排序算法，选择排序算法，插入排序算法，归并排序算法和快速排序算法。

实验目的回顾并熟悉常用的排序算法。

通过实验体会算法设计对问题求解效率所产生的深刻影响。

算法设计的基本思路选择排序在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

直接插入排序在要排序的一组数中，假设前面(n-1)[n=2]个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。

如此反复循环，直到全部排好顺序。

冒泡排序在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。

即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

归并排序算法合并排序(MERGE SORT)是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。

它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个N/2个长度为2或1的有序子序列，再两两合并，如此重复，直到得到一个长度为N的有序数据序列为止，这种排序方法称为2-路合并排序。

快速排序快速排序是对冒泡排序的一种本质改进。

它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。

在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。

快速排序通过一趟扫描，就能确保某个数(以它为基准点吧)的左边各数都比它小，右边各数都比它大。

然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。

lab1_简单算法实验⼀简单算法设计⼀.实验⽬的和要求1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程；2. 掌握简单问题的算法设计与分析，能设计⽐较⾼效的算法；3. 熟悉C/C++语⾔等的集成开发环境，掌握简单程序设计与实现的能⼒；⼆.基本原理算法是有穷指令集合，它为某个特定类型问题提供了解决问题的运算序列。

衡量算法效率⾼低的重要标准是算法的计算复杂性，包括：算法的时间复杂性和空间复杂性。

算法的时间复杂性指算法执⾏过程中所需的时间，通常指算法中元运算的执⾏次数，其为问题规模的函数。

算法的时间复杂性分析⼀般是近似地估算问题规模充分⼤时的时间增长率，⽤O, Ω, Θ估计。

算法的空间复杂性指算法执⾏过程中所需的内存空间。

简单算法设计是培养解决简单的实际应⽤问题的算法设计和分析的实践能⼒，具备基本的程序设计与实现的能⼒。

三.该类算法设计与实现的要点算法时间复杂性通过以下⽅法来估计：（1）计算迭代（循环）次数（2）计算基本运算的频度（3）利⽤递推（递归）关系。

算法最坏情况和平均情况时间复杂性是算法时间复杂性的重要指标。

空间复杂性的分析类似于时间复杂性。

简单算法设计通过分析实际问题，构思⼏种解决问题的算法，分析算法的复杂性，从⽽寻找⽐较⾼效的算法，并实现。

四．实验内容(⼀)相等元素问题1.问题描述元素唯⼀性问题：给出⼀个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。

请设计出⼀个有效算法来解决这个问题，你的算法的时间复杂性是多少？2.代码如下#include#define N 500int main(){int i,j,m,n,t,k=0;int a[N];printf("请输⼊测试的数的个数：\n");scanf("%d",&m);for(t=0;t{printf("请输⼊序列的长度：\n");scanf("%d",&n);printf("请输⼊序列的数字：\n");for(i=0;iscanf("%d",&a[i]);for(i=0;ifor(j=i+1;j{if(a[i]==a[j]){ k=1;printf("yes\n");break;}}if(k!=1) printf("no\n");}return 0;}(⼆) 整数集合分解1.问题描述设计算法把⼀个n个元素的整数集合（n为偶数）分成两个⼦集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最⼤。

《算法设计与分析》课程实验报告实验序号：10实验项目名称：实验十一回溯法（二）一、实验题目1.图的着色问题问题描述：给定无向连通图G和m种不同的颜色。

用这些颜色为图G的各顶点着色，每个顶点着一种颜色。

如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。

图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

2.旅行商问题问题描述：给出一个n个顶点的带权无向图，请寻找一条从顶点1出发，遍历其余顶点一次且仅一次、最后回到顶点1的最小成本的回路——即最短Hamilton回路。

3.拔河比赛问题描述：某公司的野餐会上将举行一次拔河比赛。

他们想把参与者们尽可能分为实力相当的两支队伍。

每个人都必须在其中一只队伍里，两队的人数差距不能超过一人，且两队的队员总体重应该尽量接近。

4.批处理作业调度问题描述：给定n个作业的集合J=(J1,J2, .. Jn)。

每个作业J都有两项任务分别在两台机器上完成。

每个作业必须先由机器1处理，再由机器2处理。

作业i需要机器j的处理时间为tji(i=1,2, ..n; j=1,2)。

对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间，则所有作业在机器2上完成处理的时间和，称为该作业调度的完成时间和。

批处理作业调度问题要求，对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

二、实验目的（1）通过练习，理解回溯法求解问题的解状态空间树与程序表达的对应关系，熟练掌握排列树、子集树的代码实现。

（2）通过练习，体会减少搜索解空间中节点的方法，体会解的状态空间树的组织及上界函数的选取对搜索的影响。

（3）通过练习，深入理解具体问题中提高回溯算法效率的方法。

（4）（选做题）：在掌握回溯法的基本框架后，重点体会具体问题中解的状态空间搜索时的剪枝问题。

三、实验要求（1）每题都必须实现算法、设计测试数据、记录实验结果，并给出时间复杂度分析。

四、实验过程（算法设计思想、源码）1.图的着色问题(1)算法设计思想用邻接矩阵a[i][j]存储无向图，对于每一个顶点有m种颜色可以涂。

北京理⼯⼤学《数据结构与算法设计》实验报告实验⼀《数据结构与算法设计》实验报告——实验⼀学院：班级：学号：姓名：⼀、实验⽬的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={ |ai∈D,i=1,2,……,n}基本操作：create(&L,n)操作结果：构造⼀个有n个结点的单向环表L。

show(L)初始条件：单向环表L已存在。

操作结果：按顺序在屏幕上输出L的数据元素。

Josephf( L,m,s,n)初始条件：单向环表L已存在， s>0,n>0，s操作结果：返回约瑟夫环的计算结果。

}ADT Joseph（2）、主程序流程主程序⾸先调⽤create(&L,n)函数，创建含有m个节点的单向环表L，然后调⽤show(L)函数，顺序输出链表中的数据，最后调⽤Josephf( L,m,s,n)函数，依次输出报的数。

（3）、函数调⽤关系图2、详细设计(1)、数据类型设计typedef int ElemType; //定义元素类型typedef struct Lnode{ElemType data;struct Lnode *next;}Lnode,*Linklist; //定义节点类型，指针类型（2）、操作算法程序实现：void create(Linklist &L,int m){//⽣成⼀个具有m个结点的单向环表，环表中的结点编号依次为1，2，……，m Linklist h,p;L=(Linklist)malloc(sizeof(Lnode));L->data = 1;h=L;for(int i=2;i<=m;i++){p = (Linklist)malloc(sizeof(Lnode));p->data = i; //⽣成新节点，数据为节点编号h->next = p;h = p; //插⼊链表}h->next = L; //形成循环链表}void show(Linklist L,int m){//从第⼀个节点开始依次输出节点编号printf("The numbers of the list are: \n"); //提⽰⽤户h=L;for(int i=1;i<=m;i++){printf("%d ",h->data);h = h->next;}printf("\n");}void Josephf(Linklist &L,int m,int s,int n){//实现约瑟夫环Linklist h,q;h = L;q = L;while(h->data != s) //定位开始的节点h = h->next;while(q->next!=h) //定位在开始位置的上⼀个节点q = q->next; for(int j=1;j<=m;j++){int i=1;while(i{q=q->next;i++;}printf("%d ",q->next->data); //依次输出报号为n的节点q->next = q->next->next; //删除已输出节点}printf("\n");}（3）、主程序的代码实现：int main(){int s,m,n;printf("请输⼊节点数m：\n"); scanf("%d",&m);create(L,m); //建⽴循环链表show(L,m); //输出链表数据printf("请输⼊起始位置s：\n"); scanf("%d",&s);printf("请输⼊报的数n：\n"); scanf("%d",&n);Josephf(L,m,s,n); //输出所报数字。

第1篇一、实验目的本次实验旨在通过实际操作，加深对算法设计方法、基本思想、基本步骤和基本方法的理解与掌握。

通过具体问题的解决，提高利用课堂所学知识解决实际问题的能力，并培养综合应用所学知识解决复杂问题的能力。

二、实验内容1. 实验一：排序算法分析- 实验内容：分析比较冒泡排序、选择排序、插入排序、快速排序、归并排序等基本排序算法的效率。

- 实验步骤：1. 编写各排序算法的C++实现。

2. 使用随机生成的不同规模的数据集进行测试。

3. 记录并比较各算法的运行时间。

4. 分析不同排序算法的时间复杂度和空间复杂度。

2. 实验二：背包问题- 实验内容：使用贪心算法、回溯法、分支限界法解决0-1背包问题。

- 实验步骤：1. 编写贪心算法、回溯法和分支限界法的C++实现。

2. 使用标准测试数据集进行测试。

3. 对比分析三种算法的执行时间和求解质量。

3. 实验三：矩阵链乘问题- 实验内容：使用动态规划算法解决矩阵链乘问题。

- 实验步骤：1. 编写动态规划算法的C++实现。

2. 使用不同规模的矩阵链乘实例进行测试。

3. 分析算法的时间复杂度和空间复杂度。

4. 实验四：旅行商问题- 实验内容：使用遗传算法解决旅行商问题。

- 实验步骤：1. 设计遗传算法的参数，如种群大小、交叉率、变异率等。

2. 编写遗传算法的C++实现。

3. 使用标准测试数据集进行测试。

4. 分析算法的收敛速度和求解质量。

三、实验结果与分析1. 排序算法分析- 通过实验，我们验证了快速排序在平均情况下具有最佳的性能，其时间复杂度为O(nlogn)，优于其他排序算法。

- 冒泡排序、选择排序和插入排序在数据规模较大时效率较低，不适合实际应用。

2. 背包问题- 贪心算法虽然简单，但在某些情况下无法得到最优解。

- 回溯法能够找到最优解，但计算量较大，时间复杂度较高。

- 分支限界法结合了贪心算法和回溯法的特点，能够在保证解质量的同时，降低计算量。

3. 矩阵链乘问题- 动态规划算法能够有效解决矩阵链乘问题，时间复杂度为O(n^3)，空间复杂度为O(n^2)。

算法分析与设计实验指导书《算法分析与设计》实验指导书本书是为配合《算法分析与设计实验教学⼤纲》⽽编写的上机指导，其⽬的是使学⽣消化理论知识，加深对讲授容的理解，尤其是⼀些算法的实现及其应⽤，培养学⽣独⽴编程和调试程序的能⼒，使学⽣对算法的分析与设计有更深刻的认识。

上机实验⼀般应包括以下⼏个步骤：（1）、准备好上机所需的程序。

⼿编程序应书写整齐，并经⼈⼯检查⽆误后才能上机。

（2）、上机输⼊和调试⾃⼰所编的程序。

⼀⼈⼀组，独⽴上机调试，上机时出现的问题，最好独⽴解决。

（3）、上机结束后，整理出实验报告。

实验报告应包括：1）问题分析2）算法描述3）运⾏结果、4）算法性能分析。

实验⼀实验名称：贪⼼算法应⽤及设计实验学时：6学时实验类型：验证实验⽬的：1.理解贪⼼算法的基本思想2.掌握利⽤贪⼼算法求解问题的求解步骤实验容1.活动选择问题（2学时）问题描述：设有11个会议等待安排，⽤贪⼼法找出满⾜⽬标要求的会议集合，这些会议按结束时间的⾮减序排列如下表。

实验实现提⽰：１)数据结构设计：将会议开始时间存储在数组B中，结束时间存储在数组E中，数组下标为会议的代码。

结果存储在数组A中，其元素A[i]==true，表⽰会议i被选中。

２）算法：void GreedySelect(int n, struct time B[], struct time E[], bool A[]){int i,j;A[1]=true;j=1; i=2;while( i<=n)if (B[i]>=E[j]){ A[i]=true; j=i;}elseA[i]=false;}思考题：证明所得的解是最优解？2.单源点最短路径问题。

（2学时）问题描述如图所⽰的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。

并对算法进⾏性能分析。

实现提⽰1）数据结构设计：将图存储在邻接矩阵C中，结点个数为n，源点编号为u, 源点u到其余顶点的最短路径长度存储在dist[],最短路径存储在p[]。

《算法设计与分析》实验报告目录一、实验内容描述和功能分析.二、算法过程设计.三、程序调试及结果（附截图）.四、源代码（附源代码）.一、实验内容描述和功能分析.1.彼岸内容描述：突破蝙蝠的包围，yifenfei来到一处悬崖面前，悬崖彼岸就是前进的方向，好在现在的yifenfei已经学过御剑术，可御剑轻松飞过悬崖。

现在的问题是：悬崖中间飞着很多红，黄，蓝三种颜色的珠子，假设我们把悬崖看成一条长度为n的线段，线段上的每一单位长度空间都可能飞过红，黄，蓝三种珠子，而yifenfei 必定会在该空间上碰到一种颜色的珠子。

如果在连续3段单位空间碰到的珠子颜色都不一样，则yifenfei就会坠落。

比如经过长度为3的悬崖，碰到的珠子先后为“红黄蓝”，或者“蓝红黄”等类似情况就会坠落，而如果是“红黄红”或者“红黄黄”等情况则可以安全到达。

现在请问：yifenfei安然抵达彼岸的方法有多少种？输入：输入数据首先给出一个整数C，表示测试组数。

然后是C组数据，每组包含一个正整数n (n<40)。

输出：对应每组输入数据，请输出一个整数，表示yifenfei安然抵达彼岸的方法数。

每组输出占一行。

例如：输入：2 输出：92 2132.统计问题内容描述：在一无限大的二维平面中，我们做如下假设：1、每次只能移动一格；2、不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；3、走过的格子立即塌陷无法再走第二次；求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。

输入：首先给出一个正整数C，表示有C组测试数据接下来的C行，每行包含一个整数n (n<=20)，表示要走n步。

输出：请编程输出走n步的不同方案总数；每组的输出占一行。

例如：输入：2 输出：31 723.Message Decowing内容描述：The cows are thrilled because they've just learned about encrypting messages. Theythink they will be able to use secret messages to plot meetings with cows on other farms.Cows are not known for their intelligence. Their encryption method is nothing like DES or BlowFish or any of those really good secret coding methods. No, they are using a simple substitution cipher.The cows have a decryption key and a secret message. Help them decode it. The key looks like this:yrwhsoujgcxqbativndfezmlpkWhich means that an 'a' in the secret message really means 'y'; a 'b' in the secret message really means 'r'; a 'c' decrypts to 'w'; and so on. Blanks are not encrypted; they are simply kept in place. Input text is in upper or lower case, both decrypt using the same decryption key, keeping the appropriate case, of course.输入：* Line 1: 26 lower case characters representing the decryption key* Line 2: As many as 80 characters that are the message to be decoded输出：* Line 1: A single line that is the decoded message. It should have the same length as the second line of input.例如：输入：eydbkmiqugjxlvtzpnwohracsfKifq oua zarxa suar bti yaagrj fa xtfgrj输出：Jump the fence when you seeing me coming二、算法过程设计.第一题是一个典型的递归问题，通过对开始的几项附初始值，通过循环利用通项公式依次递归调用公式便可以得到第n项的值。

一、实验目的本次实验旨在帮助学生掌握算法的基本概念、设计方法和分析方法，通过实际操作加深对算法原理的理解，提高编程能力和问题解决能力。

二、实验内容1. 实验一：排序算法（1）实验目的：掌握常见的排序算法，如冒泡排序、选择排序、插入排序、快速排序等，并分析其时间复杂度和空间复杂度。

（2）实验内容：① 冒泡排序：通过相邻元素的比较和交换，将待排序序列变为有序序列。

② 选择排序：每次从待排序序列中选出最小（或最大）的元素，将其放到序列的起始位置。

③ 插入排序：将无序序列的元素逐个插入到已排序序列的合适位置。

④ 快速排序：通过一趟排序将待排序序列分为独立的两部分，其中一部分的所有元素均比另一部分的所有元素小。

（3）实验步骤：① 编写每个排序算法的代码；② 编写测试代码，验证排序算法的正确性；③ 分析每个排序算法的时间复杂度和空间复杂度。

2. 实验二：查找算法（1）实验目的：掌握常见的查找算法，如顺序查找、二分查找等，并分析其时间复杂度和空间复杂度。

（2）实验内容：① 顺序查找：从序列的起始位置逐个比较，找到待查找元素。

② 二分查找：对于有序序列，每次将待查找元素与序列中间的元素比较，缩小查找范围。

（3）实验步骤：① 编写每个查找算法的代码；② 编写测试代码，验证查找算法的正确性；③ 分析每个查找算法的时间复杂度和空间复杂度。

3. 实验三：图算法（1）实验目的：掌握常见的图算法，如深度优先搜索（DFS）、广度优先搜索（BFS）等，并分析其时间复杂度和空间复杂度。

（2）实验内容：① 深度优先搜索：从给定顶点开始，探索所有相邻顶点，直至所有可达顶点都被访问。

② 广度优先搜索：从给定顶点开始，按照顶点之间的距离顺序访问相邻顶点。

（3）实验步骤：① 编写每个图算法的代码；② 编写测试代码，验证图算法的正确性；③ 分析每个图算法的时间复杂度和空间复杂度。

三、实验结果与分析1. 实验一：排序算法（1）冒泡排序、选择排序、插入排序的时间复杂度均为O(n^2)，空间复杂度均为O(1)。