算法实验报告1 全排列和会场安排问题

实验一全排列、快速排序【实验目的】1.掌握全排列的递归算法。

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

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

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

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

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

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

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

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

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

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

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

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

【实验原理】一、动态规划法解最长公共子序列设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>, 则:..i.若xm=yn, 则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列...ii.若xm≠yn且zk≠x., 则Z是Xm-1和Y的最长公共子序列...iii.若xm≠yn且zk≠y.，则Z是X和Yn-1的最长公共子序列.其中Xm-1=<x1, x2, …, xm-1>, Yn-1=<y1, y2, …, yn-1>, Zk-1=<z1, z2, …, zk-1>。

第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。

为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。

二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。

1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。

（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。

- 对每种算法进行时间复杂度和空间复杂度的分析。

- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。

（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。

- 编写三种排序算法的代码。

- 分析代码的时间复杂度和空间复杂度。

- 编写测试程序，生成随机测试数据，测试三种算法的性能。

- 比较三种算法的运行时间和内存占用。

2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。

（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。

- 分析贪心算法的正确性，并证明其最优性。

（3）实验步骤：- 分析活动选择问题的贪心策略。

- 编写贪心算法的代码。

- 分析贪心算法的正确性，并证明其最优性。

- 编写测试程序，验证贪心算法的正确性。

3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。

（2）实验内容：- 实现一个动态规划算法问题，如背包问题。

- 分析动态规划算法的正确性，并证明其最优性。

（3）实验步骤：- 分析背包问题的动态规划策略。

- 编写动态规划算法的代码。

- 分析动态规划算法的正确性，并证明其最优性。

- 编写测试程序，验证动态规划算法的正确性。

三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。

一、实验目的本实验旨在通过递归算法实现全排列，加深对递归思想的理解和应用，并掌握递归算法在解决排列组合问题中的基本方法。

二、实验原理全排列是指将一组数按照一定的顺序进行排列，每个数只能使用一次。

对于n个不同的数，其全排列共有n!种情况。

递归算法是一种常用的算法设计方法，通过将问题分解为更小的子问题，并逐步解决这些子问题，最终得到原问题的解。

三、实验内容1. 算法设计本实验采用递归算法实现全排列。

具体步骤如下：- 定义一个递归函数`permute`，接收当前排列`current`和标记数组`visited`作为参数。

- 如果当前排列`current`的长度等于n，则输出该排列。

- 否则，遍历所有可能的数字，对于每个数字：- 如果该数字未被使用（`visited[i]`为`false`），则：- 将该数字添加到当前排列`current`中。

- 标记该数字为已使用（`visited[i]`设为`true`）。

- 递归调用`permute`函数，传入新的排列`current`和更新后的标记数组`visited`。

- 回溯至上一步，将标记数组`visited`中对应的标记设为`false`，并将当前数字从排列`current`中移除。

2. 实验实现使用Python语言实现全排列递归算法。

代码如下：```pythondef permute(current, n, visited):if len(current) == n:print(current)returnfor i in range(n):if not visited[i]:current.append(i + 1)visited[i] = Truepermute(current, n, visited)current.pop()visited[i] = Falsedef main():n = int(input("请输入数字个数："))current = []visited = [False] npermute(current, n, visited)if __name__ == "__main__":main()```3. 实验结果当输入数字个数n为3时，程序输出以下全排列： ```[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]```当输入数字个数n为4时，程序输出以下全排列： ```[1, 2, 3, 4][1, 2, 4, 3][1, 3, 2, 4][1, 3, 4, 2][1, 4, 2, 3][1, 4, 3, 2][2, 1, 3, 4][2, 1, 4, 3][2, 3, 1, 4][2, 3, 4, 1][2, 4, 1, 3][2, 4, 3, 1]...```（此处省略部分输出结果）四、实验总结本实验通过递归算法实现了全排列，加深了对递归思想的理解和应用。

实验报告课程：班级：学号：姓名：实验日期：指导老师：实验序号：实验一实验题目：随机全排列生成程序及其应用开发实验成绩：实验评语：一．实验内容：编制生成0~n（n≤255）的一个全排列的程序，可选择下列两个方法之一或自行设计另外方法：方法1：从一个随机文件读取n+1 字节数据d0,d1,¡ ,d n。

由预先取定的一个0~n 的全排列P（比如，可为0~n 的自然排列）开始，依次对i=n,n-1,¡ ,1，计算：j=di-1+d i (modi)交换P 的第i 项第j 项（在此注意我们假定P 从第0 项开始）。

方法2：用一个随机函数产生m（m>n）字节数据d1,d2,¡ ,d m。

对d1(mod(n+1)),d2(mod(n+1)) ,d m(mod(n+1))依次考察，把后面出现的与前相同者去掉；在最后剩下的数据中，把没有出现的0~n 依序补写于后面。

二．实验设计：我采用的是另外一种方法，通过构造两个数组，给一个数组赋值，它包含的内容为：a[i]=i, 0≤i＜m, m为我们所需的随机数个数。

另外一个数组中包含的是生成随机数主要程序所生成的m个随机数。

通过将srand( (unsigned)time( NULL ) )和rand()%m相结合来产生随机数。

然后，运用替换的思想，建立swap函数操作这两个数组，避免了输出随机数有重复的情况。

最后输出不重复的随机数m个随机数。

具体代码请见下面实验代码。

三．实验代码：有两种实验代码1：#include "stdio.h"#include "stdlib.h"#include "time.h"swap(int *pm,int *pn){int temp;temp=*pm;*pm=*pn;*pn=temp;}void main(){int i;int a[256];int n=256;int m;start:printf("\n此程序可产生范围在0到255的随机数 \n");printf("\n请输入你所需使用的随机数个数（不大于256）:\n");scanf("%d",&m);if( m>n ){printf("\n 输入数%d 比%d大,请重新输入！\n",m,n);goto start;}srand( (unsigned)time( NULL ) );for(i=0; i<=m-1; i++){a[i]=i;//printf("%d\t",a[i]);}for(i=m-1; i>=0; i--){/* pa=&a[i]; pb=&a[rand()%m+0];*/swap(&a[i], &a[rand()%m+0]); //这表示是样为了使产生的随机数中包含0 }printf("-----\n 以下为产生的不重复的随机数：\n") ;for(i=0; i<=m-1; i++)printf("%d\t",a[i] );}2.#include "stdio.h"#include "stdlib.h"#define N 256char P[N];char d[N];char *full_array(int n){int i,j;char filename[20];FILE *fp;char temp;start:printf("\n请输入随机数据采样文件名：\n");scanf("%s",filename);if((fp=fopen(filename,"rb"))==NULL)printf("没有找到文件：%s\n",filename);goto start;}fread(d,n+1,1,fp);fclose(fp);printf("\n原文件中的字母序列如下:");for(i=0;i<=n;i++){if((i)%8==0)printf("\n");printf("d[%d]=%c ",i,d[i]);}printf("\n\n取定自然排列如下:");for(i=0;i<=n;i++){P[i]=i;if((i)%8==0)printf("\n");printf("p[%d]=%d ",i,i);}for(i=n;i>0;i--){j=(d[i-1]+d[i])%i;temp=P[i];P[i]=P[j];P[j]=temp;}return(P);}void main(){int num,i;printf("输入要进行全排列的字母个数:\n");scanf("%d",&num);full_array(num-1);printf("\n\n随机排列后的新排列为:");for(i=0;i<num;i++){if((i)%8==0)printf("\n");printf("%d(%c) ",i,d[P[i]]);}*/四．实验调试与分析：五．实验总结：。

一、实验目的1. 掌握排序算法的基本原理和实现方法。

2. 熟悉常用排序算法的时间复杂度和空间复杂度。

3. 能够根据实际问题选择合适的排序算法。

4. 提高编程能力和问题解决能力。

二、实验内容1. 实现并比较以下排序算法：冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序。

2. 对不同数据规模和不同数据分布的序列进行排序，分析排序算法的性能。

3. 使用C++编程语言实现排序算法。

三、实验步骤1. 冒泡排序：将相邻元素进行比较，如果顺序错误则交换，直到序列有序。

2. 插入排序：将未排序的元素插入到已排序的序列中，直到序列有序。

3. 选择排序：每次从剩余未排序的元素中选取最小（或最大）的元素，放到已排序序列的末尾。

4. 快速排序：选择一个枢纽元素，将序列分为两部分，一部分比枢纽小，另一部分比枢纽大，递归地对两部分进行排序。

5. 归并排序：将序列分为两半，分别对两半进行排序，然后将两半合并为一个有序序列。

6. 堆排序：将序列构建成一个最大堆，然后依次取出堆顶元素，最后序列有序。

四、实验结果与分析1. 冒泡排序、插入排序和选择排序的时间复杂度均为O(n^2)，空间复杂度为O(1)。

这些算法适用于小规模数据或基本有序的数据。

2. 快速排序的时间复杂度平均为O(nlogn)，最坏情况下为O(n^2)，空间复杂度为O(logn)。

快速排序适用于大规模数据。

3. 归并排序的时间复杂度和空间复杂度均为O(nlogn)，适用于大规模数据。

4. 堆排序的时间复杂度和空间复杂度均为O(nlogn)，适用于大规模数据。

五、实验结论1. 根据不同数据规模和不同数据分布，选择合适的排序算法。

2. 冒泡排序、插入排序和选择排序适用于小规模数据或基本有序的数据。

3. 快速排序、归并排序和堆排序适用于大规模数据。

4. 通过实验，加深了对排序算法的理解，提高了编程能力和问题解决能力。

六、实验总结本次实验通过对排序算法的学习和实现，掌握了常用排序算法的基本原理和实现方法，分析了各种排序算法的性能，提高了编程能力和问题解决能力。

算法实现题4-1★问题描述：假设在足够多的会场里安排一批活动，并希望使用尽可能少的会场。

设计一个有效的贪心算法进行安排。

★算法设计：对于给定的k个待安排的活动，计算使用最少会场的时间表。

★数据输入：由文件给出输入数据。

第1行有一个正整数k，表示有k个待安排的活动。

接下来的k行中，每行有两个正整数，分别表示k个待安排的活动的开始时间和结束时间。

时间以0点开始的分钟计。

结果输出：将计算的最少会场数输出到文件。

输入文件示例输出文件示例5 31 2312 2825 3527 8036 50★算法描述：?Stept1：输入各个活动的开始时间（s）和结束时间（e），初始化各活动的会场号。

Step2：按活动的开始时间和活动时间排序，s最早（第一优先级）和持续时间最短（第二优先级）的活动排在最前。

Step3：执行贪婪算法，即s最早和持续时间最短的优先安排会场，并记录会场号，其余活动的s大于或等于已安排活动的e的安排在同一会场，若某活动的s 小于安排活动的e，则安排在另一会场，记录会场号，依次循环，直到所有活动均被安排。

Step4：统计会场号数，输出。

★程序代码：#include<iostream>using namespace std;#define M 50 >>a[i].e;a[i].no=0;}>a[j].s)swap(a[i],a[j]);if(a[i].s==a[j].s){if(a[i].e>a[j].e)swap(a[i],a[j]);}}}int sum=1;o=sum;for(i=2;i<=k;i++){for(n=1;n<i;n++){if(a[n].no!=0&&a[n].e<=a[i].s){a[i].no=a[n].no;a[n].no=0;o=sum;}}cout<<"输出最少会场数:\n"<<sum<<endl;system("pause");}★运行结果：。

第1篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。

通过实际编程，加深对算法的理解，提高编程能力，并学会运用算法解决实际问题。

二、实验内容本次实验选择了以下常见算法进行设计和实现：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

2. 查找算法：顺序查找、二分查找。

3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）。

4. 动态规划算法：0-1背包问题。

三、实验原理1. 排序算法：排序算法的主要目的是将一组数据按照一定的顺序排列。

常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。

2. 查找算法：查找算法用于在数据集中查找特定的元素。

常见的查找算法包括顺序查找和二分查找。

3. 图算法：图算法用于处理图结构的数据。

常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）等。

4. 动态规划算法：动态规划算法是一种将复杂问题分解为子问题，通过求解子问题来求解原问题的算法。

常见的动态规划算法包括0-1背包问题。

四、实验过程1. 排序算法（1）冒泡排序：通过比较相邻元素，如果顺序错误则交换，重复此过程，直到没有需要交换的元素。

（2）选择排序：每次从剩余元素中选取最小（或最大）的元素，放到已排序序列的末尾。

（3）插入排序：将未排序的数据插入到已排序序列中适当的位置。

（4）快速排序：选择一个枢纽元素，将序列分为两部分，使左侧不大于枢纽，右侧不小于枢纽，然后递归地对两部分进行快速排序。

（5）归并排序：将序列分为两半，分别对两半进行归并排序，然后将排序好的两半合并。

（6）堆排序：将序列构建成最大堆，然后重复取出堆顶元素，并调整剩余元素，使剩余元素仍满足最大堆的性质。

2. 查找算法（1）顺序查找：从序列的第一个元素开始，依次比较，直到找到目标元素或遍历完整个序列。

第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. 实验方法本次实验设计了四种排序算法，分别为冒泡排序、插入排序、选择排序和快速排序。

实验采用Python语言进行实现，并通过编写测试函数对算法进行验证。

测试函数会生成一定数量的随机数，并对这些随机数进行排序，统计算法的执行时间和比较次数，最后将结果进行记录和分析。

3. 测试结果及分析3.1 冒泡排序冒泡排序是一种简单且常用的排序算法，其基本思想是从待排序的数据中依次比较相邻的两个元素，如果它们的顺序不符合要求，则交换它们的位置。

经过多轮的比较和交换，最小值会逐渐冒泡到前面。

测试结果显示，冒泡排序在排序1000个随机数时，平均执行时间为0.981秒，比较次数为499500次。

从执行时间和比较次数来看，冒泡排序的性能较差，对于大规模数据的排序不适用。

3.2 插入排序插入排序是一种简单但有效的排序算法，其基本思想是将一个待排序的元素插入到已排序的子数组中的正确位置。

通过不断将元素插入到正确的位置，最终得到排序好的数组。

测试结果显示，插入排序在排序1000个随机数时，平均执行时间为0.892秒，比较次数为249500次。

插入排序的性能较好，因为其内层循环的比较次数与待排序数组的有序程度相关，对于近乎有序的数组排序效果更好。

3.3 选择排序选择排序是一种简单但低效的排序算法，其基本思想是在待排序的数组中选择最小的元素，将其放到已排序数组的末尾。

通过多次选择和交换操作，最终得到排序好的数组。

测试结果显示，选择排序在排序1000个随机数时，平均执行时间为4.512秒，比较次数为499500次。