下载文档原格式
《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：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篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。
为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。
二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。
1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。
（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。
- 对每种算法进行时间复杂度和空间复杂度的分析。
- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。
（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。
- 编写三种排序算法的代码。
- 分析代码的时间复杂度和空间复杂度。
- 编写测试程序，生成随机测试数据，测试三种算法的性能。
- 比较三种算法的运行时间和内存占用。
2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。
（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。
- 分析贪心算法的正确性，并证明其最优性。
（3）实验步骤：- 分析活动选择问题的贪心策略。
- 编写贪心算法的代码。
- 分析贪心算法的正确性，并证明其最优性。
- 编写测试程序，验证贪心算法的正确性。
3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。
（2）实验内容：- 实现一个动态规划算法问题，如背包问题。
- 分析动态规划算法的正确性，并证明其最优性。
（3）实验步骤：- 分析背包问题的动态规划策略。
- 编写动态规划算法的代码。
- 分析动态规划算法的正确性，并证明其最优性。
- 编写测试程序，验证动态规划算法的正确性。
三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(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的一个最长公共子序列。
《算法设计与分析》课程实验报告实验序号：07实验项目名称：实验8 贪心算法（一）一、实验题目1.删数问题问题描述：键盘输入一个高精度的正整数N（不超过250 位），去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的非负整数。
编程对给定的N 和k，寻找一种方案使得剩下的数字组成的新数最小。
若输出前有0则舍去2.区间覆盖问题问题描述：设x1,x2,...xn是实轴上的n个点。
用固定长度为k的闭区间覆盖n个点，至少需要多少个这样的固定长度的闭区间？请你设计一个有效的算法解决此问题。
3.会场安排问题问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。
设计一个有效的贪心算法进行安排。
（这个问题实际上是著名的图着色问题。
若将每一个活动作为图的一个顶点，不相容活动间用边相连。
使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。
）4.导弹拦截问题问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
给定导弹依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
二、实验目的（1）通过实现算法，进一步体会具体问题中的贪心选择性质，从而加强对贪心算法找最优解步骤的理解。
（2）掌握通过迭代求最优的程序实现技巧。
（3）体会将具体问题的原始数据预处理后（特别是以某种次序排序后），常能用贪心求最优解的解决问题方法。
三、实验要求（1）写出题1的最优子结构性质、贪心选择性质及相应的子问题。
（2）给出题1的贪心选择性质的证明。
（3）（选做题）：写出你的算法的贪心选择性质及相应的子问题，并描述算法思想。
实验一找最大和最小元素与归并分类算法实现（用分治法）一、实验目的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篇一、实验目的1. 理解快速排序算法的基本原理和实现方法。
2. 掌握快速排序算法的时间复杂度和空间复杂度分析。
3. 通过实验验证快速排序算法的效率。
4. 提高编程能力和算法设计能力。
二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验原理快速排序算法是一种分而治之的排序算法，其基本思想是：选取一个基准元素，将待排序序列分为两个子序列，其中一个子序列的所有元素均小于基准元素，另一个子序列的所有元素均大于基准元素，然后递归地对这两个子序列进行快速排序。
快速排序算法的时间复杂度主要取决于基准元素的选取和划分过程。
在平均情况下，快速排序的时间复杂度为O(nlogn)，但在最坏情况下，时间复杂度会退化到O(n^2)。
四、实验内容1. 快速排序算法的代码实现2. 快速排序算法的时间复杂度分析3. 快速排序算法的效率验证五、实验步骤1. 设计快速排序算法的C++代码实现，包括以下功能：- 选取基准元素- 划分序列- 递归排序2. 编写主函数，用于生成随机数组和测试快速排序算法。
3. 分析快速排序算法的时间复杂度。
4. 对不同规模的数据集进行测试，验证快速排序算法的效率。
六、实验结果与分析1. 快速排序算法的代码实现```cppinclude <iostream>include <vector>include <cstdlib>include <ctime>using namespace std;// 生成随机数组void generateRandomArray(vector<int>& arr, int n) {srand((unsigned)time(0));for (int i = 0; i < n; ++i) {arr.push_back(rand() % 1000);}}// 快速排序void quickSort(vector<int>& arr, int left, int right) { if (left >= right) {return;}int i = left;int j = right;int pivot = arr[(left + right) / 2]; // 选取中间元素作为基准 while (i <= j) {while (arr[i] < pivot) {i++;}while (arr[j] > pivot) {j--;}if (i <= j) {swap(arr[i], arr[j]);i++;j--;}}quickSort(arr, left, j);quickSort(arr, i, right);}int main() {int n = 10000; // 测试数据规模vector<int> arr;generateRandomArray(arr, n);clock_t start = clock();quickSort(arr, 0, n - 1);clock_t end = clock();cout << "排序用时：" << double(end - start) / CLOCKS_PER_SEC << "秒" << endl;return 0;}```2. 快速排序算法的时间复杂度分析根据实验结果，快速排序算法在平均情况下的时间复杂度为O(nlogn)，在最坏情况下的时间复杂度为O(n^2)。
本科实验报告课程名称: 算法设计与分析实验项目: 递归与分治算法实验地点: 计算机系实验楼１１0专业班级: 物联网１601 学号: 201６00２１05 学生姓名: 俞梦真指导教师: 郝晓丽2018年05月04 日实验一递归与分治算法１.1 实验目的与要求１.进一步熟悉C/C+＋语言的集成开发环境;2.通过本实验加深对递归与分治策略的理解与运用。
1.２实验课时2学时1、3 实验原理分治(Dｉvide－and-Ｃonquer)的思想:一个规模为ｎ的复杂问题的求解,可以划分成若干个规模小于n的子问题,再将子问题的解合并成原问题的解。
需要注意的就是,分治法使用递归的思想。
划分后的每一个子问题与原问题的性质相同,可用相同的求解方法。
最后,当子问题规模足够小时,可以直接求解,然后逆求原问题的解。
1、4 实验题目1、上机题目:格雷码构造问题Gｒaｙ码就是一个长度为2n的序列。
序列无相同元素,每个元素都就是长度为n的串,相邻元素恰好只有一位不同。
试设计一个算法对任意n构造相应的Grａy码(分治、减治、变治皆可)。
对于给定的正整数n,格雷码为满足如下条件的一个编码序列。
(1)序列由2ｎ个编码组成,每个编码都就是长度为n的二进制位串。
(2)序列中无相同的编码。
(3)序列中位置相邻的两个编码恰有一位不同。
2、设计思想:根据格雷码的性质,找到她的规律,可发现,1位就是0 1。
两位就是00 ０1１1 10。
三位就是00０001 011 ０１０１１0 1１1 101 100。
n位就是前ｎ-1位的2倍个。
Ｎ-1个位前面加0,Ｎ-2为倒转再前面再加1。
3.代码设计:Ｍy＿gｒaｄ、clear();}ｒｅturn 0;}运行结果:1、5 思考题(1)递归的关键问题在哪里?答:1、递归式,就就是如何将原问题划分成子问题。
2.递归出口,递归终止的条件,即最小子问题的求解,可以允许多个出口。
3.界函数,问题规模变化的函数,它保证递归的规模向出口条件靠拢(2)递归与非递归之间如何实现程序的转换?(３)分析二分查找与快速排序中使用的分治思想。
答:1、一般根据就是否需要回朔可以把递归分成简单递归与复杂递归,简单递归一般就就是根据递归式来找出递推公式(这也就引申出分治思想与动态规划)。
２.复杂递归一般就就是模拟系统处理递归的机制,使用栈或队列等数据结构保存回朔点来求解。
(４)分析二次取中法与锦标赛算法中的分治思想。
二次取中法:使用快速排序法中所采用的分划方法,以主元为基准,将一个表划分为左右两个子表,左子表中的元素均小于主元,右子表中的元素均大于主元。
主元的选择就是将表划分为r部分,对找出r个中的中间值,并求r组的中间值中的中间值。
锦标赛算法:两两分组比较,大者进入下一轮,知道剩下1个元素max为止。
在每次比较中淘汰较小元素,将被淘汰元素记录在淘汰它的元素的链表上。
检查maｘ的链表,从中知道最大元素,即secondﻬ本科实验报告课程名称: 算法设计与分析实验项目: 贪心算法实验地点: 计算机系实验楼110专业班级: 物联网160１学号: 2016002１05学生姓名: 俞梦真指导教师: 郝晓丽20１8年05月04日实验二贪心算法2.１实验目的与要求1.理解贪心算法的基本思想;2.运用贪心算法解决实际问题,加深对贪心算法的理解与运用。
2.2 实验课时4学时(课内2学时+课外2学时)2.3 实验原理贪心算法的思想:(1)贪心算法(Greedy Ａpｐroach)能得到问题的最优解,要证明我们所做的第一步选择一定包含着一个最优解,即存在一个最优解的第一步就是从我们的贪心选择开始。
(２)在做出第一步贪心选择后,剩下的子问题应该就是与原问题类似的规模较小的子问题,为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。
2、４实验题目１、上机题目:最小延迟调度问题给定等待服务的客户集合A=｛1,2,…,n},预计对客户ｉ的服务时长为tｉ>０,T=(t1,t2,…,t n),客户ｉ希望的服务完成时刻为dｉ>0,Ｄ＝(d1,d2,…,d n);一个调度f:Ａ→Ｎ,f(i)为客户i的开始时刻。
如果对客户i的服务在d i之前结束,那么对客户i的服务没有延迟,即如果在ｄi之后结束,那么这个服务就被延迟了,延迟的时间等于该服务的实际完成时刻f(i)+t i减去预期结束时刻d i。
一个调度f的最大延迟就是所有客户延迟时长的最大值max i∈A{ｆ(i)+tｉ d i｝。
附图２所示就是不同调度下的最大延迟。
使用贪心策略找出一个调度使得最大延迟达到最小。
2、设计思想:贪心思想,按照她们的截止时间从小到大排序,如果截止时间相同按照花费时间从小到大排序。
然后按照f_ｍｉn(所有客户延迟时长的最大值)=max(woｒks［i］、cosｔ+ｔime-ｗｏrks［i]、ｄｅadline,f_miｎ);寻找最所有客户延迟时长的最大值。
3、代码设计:5 ８４10 31012 １5 1１２０*/运行结果:２、5 思考题(１)哈夫曼编码问题的编程如何实现？答:哈夫曼树,又名最优树,给定ｎ个权值作为n的叶子结点,构造一颗二叉树,若带权路径长度达到最小,成这样的二叉树为最优二叉树,也称哈夫曼树。
实现步骤:1、初始化: 根据给定的n个权值{ｗ1,w2,…、、wn、、}构成ｎ棵二叉树的集合F={T １,T2….Ｔｎ},其中每棵二叉树中只有一个带权Wi的根结点,左右子树均空。
2、找最小树:在F 中选择两棵根结点权值最小的树作为左右子树构造一-棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树,上根结点的权值之与。
3、删除与加入: 在Ｆ中删除这两棵树,并将新的二叉树加入F中。
4、判断:重复前两步(2与３),直到F中只含有一棵树为止。
该树即为哈夫曼树。
(２)使用贪心策略求解背包问题。
答:首先计算每种物品单位重量的价值vi/wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。
若将这种物品全部装入背包后,背包内的物品总重量未达到w,则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直地进行下去直到背包满重为止。
算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。
因此,算法的计算时间上界为O(nｌogn)。
(３)分析普里姆算法与克鲁斯卡尔算法中的贪心策略。
答:１、普里姆算法贪心策略:要记录到S中的下一条边(u,v)就是一条不在S中,且使得SＵ｛ｕ,v}的权值之与也就是最小的边时间复杂度:O(n^2) 空间复杂度:O(n^２)2、克鲁斯卡尔算法中的贪心策略:选取属于不同联通分量且构成权值最小且不形成回路的两个顶点组成的边、ﻬ本科实验报告课程名称: 算法设计与分析实验项目: 动态规划实验地点: 计算机系实验楼1１0专业班级: 物联网160１学号: 20160０２105学生姓名: 俞梦真指导教师: 郝晓丽2018年05月０7日实验三动态规划算法3、１实验目的与要求1、理解动态规划算法的基本思想;2、运用动态规划算法解决实际问题,加深对贪心算法的理解与运用。
３、2 实验课时４学时(课内2学时+课外2学时)3.３实验原理动态规划(Dyｎaｍic Progrａmmiｎｇ)算法思想:把待求解问题分解成若干个子问题,先求解子问题,然后由这些子问题的解得到原问题的解。
动态规划求解过的子问题的结果会被保留下来,不像递归那样每个子问题的求解都要从头开始反复求解。
动态规划求解问题的关键在于获得各个阶段子问题的递推关系式:(1)分析原问题的最优解性质,刻画其结构特征;(2)递归定义最优值;(3)自底向上(由后向前)的方式计算最优值;(4)根据计算最优值时得到的信息,构造一个最优解。
3、４实验题目１、上机题目:最大子段与问题给定n个整数(可以为负数)组成的序列(a１,a2,…,aｎ),使用动态规划思想求该序列的子段与的最大值。
注:当所有整数均为负整数时,其最大子段与为0。
例如,对于六元组(-2,1１, -４,13, -5, -2),其最大字段与为:a2+a3＋a４=20。
除了动态规划,该问题可以使用顺序求与+比较(蛮力法)与分治法求解,思考其求解过程。
2、设计思想动态规划思想:ｄp［i］,表示到当前i的最大字段与为多少,而她的字段与时要不就就是前面的最大字段与加上本身的数值要不就就是自身的数值。
状态转移方程:dｐ[ｉ]=mａx(dｐ[ｉ],ｄp[i-１]+ａ[i]);3.代码设计3、５思考题(1)深刻理解动态规划与递归求解问题的区别就是什么？、答:动态规划其实与分治策略就是类似的,也就是将一个原问题分解为若干个规模较小的子问题,递归的求解这些子问题,然后合并子问题的解得到原问题的解。
区别在于这些子问题会有重叠,一个子问题在求解后,可能会再次求解,于就是我们想到将这些子问题的解存储起来,当下次再次求解这个子问题时,直接拿过来就就是。
(2)动态规划思想解题的步骤就是什么？答:第一步:确定子问题。
在这一步重点就是分析那些变量就是随着问题规模的变小而变小的, 那些变量与问题的规模无关。
第二步:确定状态:根据上面找到的子问题来给您分割的子问题限定状态第三步:推到出状态转移方程:这里要注意您的状态转移方程就是不就是满足所有的条件, 注意不要遗漏。
第四步:确定边界条件:先根据题目的限制条件来确定题目中给出的边界条件就是否能直接推导出, 如果不行也可以尝试从边界条件反推(举个例子:a(n)→ａ(2)有递推关系, 但就是ａ(2)→ａ(1)不符合上述递推关系, 我们就可以考虑用ａ(1)来倒推出a(2), 然后将递推的终点设置为a(2));第五步:确定实现方式:这个依照个人习惯就像就是0１背包的两层for循环的顺序第六步:确定优化方法:很多时候您会发现走到这里步的时候您需要返回第１步重来。
首先考虑降维问题(优化内存),优先队列、四边形不等式(优化时间)等等。
(3)动态规划思想与贪心算法在求解问题时的区别就是什么？答:共同点: 求解的问题都具有最优子结构性质区别点:动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每做一次贪心选择就将所求问题简化为规模更小的子问题。
(４)使用动态规划算法求解最长公共子序列(ＬCS)问题。
答:LCS问题的最优子结构性质,得其状态转移方程或者说递归式: dp［i][j]表示记录ａ[ｉ] b[j］的LSＣ的长度时间复杂度: O(m+n);a[ｉ]=＝b[ｊ] dp[i-１][ｊ-1]+1;a[i]!=ｂ［j］mａｘ(dp［i-1][j],dｐ[i][j－1]);(５)使用动态规划算法求解最长最大字段与问题。
答:动态规划思想:dp[ｉ],表示到当前i的最大字段与为多少,而她的字段与时要不就就是前面的最大字段与加上本身的数值要不就就是自身的数值。
