算法实验报告二

实验一分治与递归算法的应用一、实验目的1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。

2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。

3．学会利用分治算法解决实际问题。

二 . 实验内容金块问题老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。

假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。

并对自己的程序进行复杂性分析。

三.问题分析:一般思路：假设袋中有n 个金块。

可以用函数M a x（程序1 - 3 1）通过n-1次比较找到最重的金块。

找到最重的金块后，可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。

这样，比较的总次数为2n-3。

分治法：当n很小时，比如说，n≤2，识别出最重和最轻的金块，一次比较就足够了。

当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。

第二步，分别找出在A和B中最重和最轻的金块。

设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。

第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。

在第二步中，若n＞2，则递归地应用分而治之方法程序设计据上述步骤，可以得出程序1 4 - 1的非递归代码。

该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。

当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。

首先处理n≤1的情况。

若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶,数个重量值w [ 1 : n - 1 ]参与f o r循环。

当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。

算法实验报告算法实验报告引言：算法是计算机科学的核心内容之一，它是解决问题的方法和步骤的描述。

算法的设计和分析是计算机科学与工程中的重要研究方向之一。

本实验旨在通过对算法的实际应用和实验验证，深入理解算法的性能和效果。

实验一：排序算法的比较在本实验中，我们将比较三种常见的排序算法：冒泡排序、插入排序和快速排序。

我们将通过对不同规模的随机数组进行排序，并记录每种算法所需的时间和比较次数，以评估它们的性能。

实验结果显示，快速排序是最快的排序算法，其时间复杂度为O(nlogn)，比较次数也相对较少。

插入排序的时间复杂度为O(n^2)，比较次数较多，但对于小规模的数组排序效果较好。

而冒泡排序的时间复杂度也为O(n^2)，但比较次数更多，效率相对较低。

实验二：图的最短路径算法在图的最短路径问题中，我们将比较Dijkstra算法和Floyd-Warshall算法的效率和准确性。

我们将使用一个带权有向图，并计算从一个顶点到其他所有顶点的最短路径。

实验结果表明，Dijkstra算法适用于单源最短路径问题，其时间复杂度为O(V^2)，其中V为顶点数。

而Floyd-Warshall算法适用于多源最短路径问题，其时间复杂度为O(V^3)。

两种算法在准确性上没有明显差异，但在处理大规模图时，Floyd-Warshall算法的效率较低。

实验三：动态规划算法动态规划是一种通过将问题分解成子问题并记录子问题的解来解决复杂问题的方法。

在本实验中，我们将比较两种动态规划算法：0-1背包问题和最长公共子序列问题。

实验结果显示，0-1背包问题的动态规划算法可以有效地找到最优解，其时间复杂度为O(nW)，其中n为物品个数，W为背包容量。

最长公共子序列问题的动态规划算法可以找到两个序列的最长公共子序列，其时间复杂度为O(mn)，其中m和n分别为两个序列的长度。

结论：通过本次实验，我们对不同算法的性能和效果有了更深入的了解。

排序算法中，快速排序是最快且效率最高的；在图的最短路径问题中，Dijkstra算法和Floyd-Warshall算法分别适用于不同的场景；动态规划算法可以解决复杂的问题，并找到最优解。

实验二时间片轮转算法实验报告一、实验目的本次实验的主要目的是了解时间片轮转算法的工作原理，学习如何使用时间片轮转算法进行进程调度，并了解时间片大小对进程调度的影响。

二、实验原理时间片轮转算法是一种公平的进程调度算法，它采用循环队列的形式，将所有需要运行的进程按照到达时间排序，并将它们按照轮转的方式依次执行，每个进程在一个时间片内执行一定的时间（时间片大小），然后被暂停并放在队列的末尾等待下一次调度。

当一个进程的时间片用完后，它会被暂停并放在队列的最后，而在这个时间片内没有执行完的进程会被暂停并放到队列的开头，以便继续下一轮的运行。

这样一直循环下去，直到所有进程都运行完毕。

三、实验步骤1.设定进程数量和时间片大小。

2.定义进程结构体，包括进程ID、到达时间、服务时间、剩余时间等信息。

3.初始化所有进程，并按照到达时间排序。

4.创建一个循环队列，并将所有已到达的进程入队。

5.按照时间片大小循环执行以下步骤：a.从队列中取出一个进程，执行一次时间片大小的时间。

b.更新队列中所有进程的剩余时间。

c.如果剩余时间大于0，将进程放入队尾。

d.如果剩余时间等于0，表示进程执行完毕，将其从队列中移除。

e.输出每个时间片的调度情况。

6.统计平均等待时间和平均周转时间，并输出结果。

四、实验结果本次实验我们设置了4个进程，并且时间片大小为3、以下是每个时间片的调度情况：时间片1：进程1执行，剩余时间为2时间片2：进程2执行，剩余时间为4时间片3：进程3执行，剩余时间为5时间片4：进程1执行，剩余时间为1时间片5：进程2执行，剩余时间为3时间片6：进程3执行，剩余时间为4时间片7：进程4执行，剩余时间为2时间片8：进程1执行，剩余时间为0，进程1执行完毕时间片9：进程2执行，剩余时间为2时间片10：进程3执行，剩余时间为3时间片11：进程4执行，剩余时间为1时间片12：进程2执行，剩余时间为1时间片13：进程3执行，剩余时间为2时间片14：进程4执行，剩余时间为0，进程4执行完毕时间片15：进程2执行，剩余时间为0，进程2执行完毕时间片16：进程3执行，剩余时间为1时间片17：进程3执行，剩余时间为0根据以上调度情况，我们可以计算出平均等待时间和平均周转时间。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- 编写贪心算法的代码。

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

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

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

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

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

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

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

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

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

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

《计算机图形学》实验报告(实验二：图形填充算法)一、实验目的及要求用两种方法做图形的填充算法！二、理论基础1.边填充算法对于每一条扫描线和每条多边形的交点（x1,y1），将该扫描线上的交点右方的所有像素取补。

2.种子填充算法利用栈来实现种子填充算法。

种子像素入栈，当栈非空时重复执行如下步骤：将栈顶像素出栈，将出栈像素置成多边形色，按左，上，右，下顺序检查与出栈像素相邻的四个像素，若其中某个像素不再边界且未置成多边形，则把该像素入栈！三、算法设计与分析1、边填充算法void CEdge_mark_fillView::OnDraw(CDC* pDC){CEdge_mark_fillDoc* pDoc = GetDocument();ASSERT_V ALID(pDoc);int d[500][500]={0};int inside;int x,y;Bresenham(80,101,100,400,d);Bresenham(100,300,290,400,d);Bresenham(292,400,382,50,d);Bresenham(380,50,202,150,d);Bresenham(200,150,82,101,d);for(y=0;y<500;y++){inside=0;for(x=0;x<500;x++){if(d[x][y]==1)if(d[x+1][y]!=1){inside=!(inside);}if(inside!=0)pDC->SetPixel(x,y,12);}}}2、种子填充int x=299,y=51;COLORREF oldcolor;COLORREF newcolor;oldcolor=RGB(256,256,256);newcolor=RGB(123,123,123);pDC->MoveTo (40,40);pDC->LineTo (80,40);pDC->LineTo (70,80);pDC->LineTo (40,40);FloodFill(51,51,RGB(255,255,255),RGB(0,0,255));pDC->LineTo (40,40);void CMyView::FloodFill(int x,int y,COLORREF oldcolor,COLORREF newcolor) {CDC* pDC;pDC=GetDC();if(pDC->GetPixel(x,y)==oldcolor){pDC->SetPixel(x,y,newcolor);FloodFill(x,y-1,oldcolor,newcolor);FloodFill(x,y+1,oldcolor,newcolor);FloodFill(x-1,y,oldcolor,newcolor);FloodFill(x+1,y,oldcolor,newcolor);}四、程序调试及结果的分析1、2、四、实验心得及建议由于很多不会，所以这次没能按时当堂完成，下来花了不少时间才弄出来，第二种尤其比较麻烦，在同学的帮助下才做出来了。

算法设计与分析实验报告实验一全排列、快速排序【实验目的】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的一个最长公共子序列。

《算法设计与分析》课程实验报告实验序号：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．加深对分治法算法设计方法的理解与应用；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篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。

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

二、实验内容本次实验选择了以下常见算法进行设计和实现：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、程序源代码#include<stdio.h>int Research(int a[],int x,int n){int left=0,right=n-1,mid;if(n>0&&x>=a[0]){while(left<right){mid=(left+right+1)/2;if(x<a[mid])right=mid-1;elseleft=mid;}if(x==a[left])return left;}return -1;}void Input(){int a[30],n,i,j,x;printf("输入数组长度n :");scanf("%d",&n);printf("输入有序数组：\n\n");for(i=0;i<n;i++){printf("a[%d]:",i);scanf("%d",&a[i]);}printf("输入要查询的数字:");scanf("%d",&x);j=Research(a,x,n);if(j>=0)printf("%d 在数组中的下标为%d!\n\n",x,j);elseprintf("没找到!\n\n");}main(){Input();}运行结果图一图二实验心得：本次实验让我了解了二分搜索法的基本思想，同时我们应该注意二分搜索法必须是在有序的元素中进行，不能在无序的元素中使用。

快速排序：#include<iostream>using namespace std;#define MAXSIZE 100int Partition(int q[MAXSIZE],int low,int hight);void Qsort(int q[],int low,int hight);int main(){int q[MAXSIZE]; //存储数列的数组q[0]=0;int n=0;cout<<"请输入需要排序的数的个数：";cin>>n;cout<<"\n请输入需要排序的数：\n";for(int i=1;i<=n;i++) //用循环方式输入数列{cin>>q[i];}Qsort(q,1,n); //调用Partition()函数cout<<"\n排序后结果为：\n";for(i=1;i<=n;i++) //循环输出结果{cout<<q[i]<<" ";}cout<<endl;return 0;}int Partition(int q[MAXSIZE],int low,int high) //对数列及数列部分划分成高低两个部分{int pivotkey; //用于标记q[low]这个关键数q[0]=q[low]; //q[0]用于存储q[low]这个数，q[low]空出pivotkey=q[low];while(low<high) //判断长度是否大于1{while(low<high && q[high]>=pivotkey)high--;q[low]=q[high]; //当pivotkey的值大于q[high]，将q[high]放入q[low]中，q[high]空出while(low<high && q[low]<=pivotkey)low++;q[high]=q[low]; //当pivotkey的值小于q[low]，将q[low]放入q[high]中，q[low]空出}q[low]=q[0]; //将q[0]中存储的数放入它合适的位置return low;}void Qsort(int q[MAXSIZE],int low,int high){int pivotkey; //记录关键数上一次排序后的位子if(low<high){pivotkey=Partition(q,low,high);Qsort(q,low,pivotkey-1); //对比关键数小的数（左侧）排序Qsort(q,pivotkey+1,high); //对比关键数大的数（右侧）排序}}运行结果：实验总结：在实验过程中，我只考虑了对数进行排序，没有其他的指针，所以就直接用了int型的数组。