算法分析与设计
实验报告
实验名称：输油管道问题
实验日期： 2011/03/１３
学生姓名：
学生学号：
一、实验目的
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标（东西向）和y坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。
给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。二、实验环境
Windows7 + Visual Studio 2010
三、实验内容
1.设计思路
因为输油管道是东西走向，每口油井到管道的最短路径都是垂直于管道的。所以，该问题实际是求得所有油井的Ｙ坐标的中位数。利用线性时间选择算法找到坐标中位数。再求出最小长度总和。
2.相关模块
#include
#include
#include
#include
#include
usingnamespace std;
void write(char* filename,int length);
int RandomizedSelect(int *a,int p,int r,int k);
int RandomizedPartition(int *a,int p,int r);
int Partition(int *a,int p,int r);
void swap(int&,int&);
int Random(int p,int r);
int lengthOfPipeline(int *a,int size,int length);
int main()
{
int size=0;
char* inFileName = "H:\\C++\\Algorithms\\in.txt";
char* outFileName = "H:\\C++\\Algorithms\\out.txt";
ifstream input(inFileName,ios::in);
//从文件读取数据
input>> size;
int *a = newint[size];
int readcount=1,i=0;
while(readcount<=(size*2))
{
int temp = 0;
input>> temp;
if(readcount%2==0)
a[i++]=temp;
readcount++;
}
input.close();
//获取数据中位数y，即为通道Y坐标
int length = RandomizedSelect(a,0,size-1,(size+1)/2);
//将总的管道长度写入out.txt文件中
write(outFileName,lengthOfPipeline(a,size,length));
system("pause");
return 0;
}
//将最后结果写入文件中
void write(char* filename,int length)
{
ofstream output;
output.open(filename,ofstream::out);
output< output.close(); } //随机获取p到r中的数 int Random(int p,int r) { return p + rand()%(r - p + 1); } //划分 int Partition(int *a,int p,int r) { int i = p, j = r + 1; int x = a[p]; //将 //将>x的元素交换到左边区域 while(true) { while(a[++i] while(a[--j]>x); if(i>=j)break; swap(a[i],a[j]); } a[p]=a[j]; a[j]=x; return j; } //产生随机划分优化算法 int RandomizedPartition(int *a,int p,int r) { int i= Random(p,r); swap(a[i],a[p]); return Partition(a,p,r); } //利用随机划分来找到中位数 int RandomizedSelect(int *a,int p,int r,int k) { if(p>=r)return a[p]; int i = RandomizedPartition(a,p,r), j = i-p+1; if (k == j) return a[i]; if(k elsereturn RandomizedSelect(a,i+1,r,k-j); } //交换两个数据 void swap(int&n,int&m) { int temp = n; n = m; m = temp; } //计算输油管道最小长度总和 int lengthOfPipeline(int *a,int size,int length) { int distance = 0; for(int i=0; i distance += abs(a[i] - length); return distance; } 四、实验结果分析及结论 算法RandomizedSelect 可以在O（n）平均时间内找出n个坐标中的中位数。 华东师范大学计算机科学技术系上机实践报告 一、 内容与设计思想 1．对于以下5 个矩阵： M 1: 2?3, M 2: 3?6, M 3: 6?4, M 4: 4?2, M 5: 2?7 , (a) 找出这5个矩阵相乘需要的最小数量乘法的次数。 (b) 请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。 输入： 第一行为正整数N,表示有N 组测试数据； 每组测试数据的第一行为n,表示有n 个矩阵,2<=n<=50； 接下去的n 行,每行有两个整数x 和y,表示第ni 个矩阵是x*y 的。 输出： 对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积。 我们保证输出的结果在2^64之内。 基本思想： 对于n 个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下： 2．定义0/1/2背包问题为：}x p max{n 1i i i ∑=。限制条件为：c x w n 1i i i ≤∑=，且 n i 1},2,1,0{x i ≤≤∈。设f(i , y)表示剩余容量为y ，剩余物品为：i ，i+1，…，n 时的最优解的值。 1．）给出f(i , y)的递推表达式； 2．）请设计求解f(i , y)的算法，并实现你的算法； 3．）设W=[10,20,15,30]，P=[6,10,15,18],c=48，请用你的算法求解。 输入： 第一行为一个正整数N ，表示有几组测试数据。 每组测试数据的第一行为两个整数n 和M ，0 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 实验二动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述： 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 三、算法设计 void main() { 申明一个5*5的二维数组； for(int i=0;i<5;i++) { for(int j=0;j<=i;j++) { 输入数组元素p[i][j]; } } for(int k=0;k<5;k++) { for(int w=0;w<=k;w++) { 输出数组元素p[k][w]; } } for(int a=4;a>0;a--) { for(int s=0;s<=a;s++) { if(p[a][s]大于p[a][s+1]) p[a-1][s]等于p[a-1][s]加p[a][s]; else p[a-1][s] 等于p[a-1][s] 加p[a][s+1]; } } 输出p[0][0] } 四.程序调试及运行结果分析 五.实验总结 虽然这个实验比较简单，但是通过这次实验使我更加了解的动态规划法的好处和、，在解决问题时要尝试使用动态规划，这样就有可能得到一种即简单复杂性有不高的算法。 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 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={ 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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．代码设计： 一、实验目的 (2) 二、实验内容 (2) 三、实验步骤 (3) 四.程序调试及运行结果分析 (5) 附录：程序清单（程序过长，可附主要部分） (7) 实验四动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述： 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 题目二：最长单调递增子序列问题(课本184页例28) 设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j) 若存在i1 题目三 0-1背包问题 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c，。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，，物品的个数n。接下来的n 行表示n个物品的重量和价值。输出为最大的总价值。 输入样例： 20 3 11 9 9 10 7 5 输出样例 19 2.数据输入：个人设定，由键盘输入。 3.要求： 1）上述题目任选一做。上机前，完成程序代码的编写 2）独立完成实验及实验报告 三、实验步骤 1.理解算法思想和问题要求； 2.编程实现题目要求； 3.上机输入和调试自己所编的程序； 4.验证分析实验结果； 5.整理出实验报告。 算法设计与分析实验报告 学院：信息学院 专业：物联网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、递推关系： 1、蒙特卡罗定位 足球机器人中自定位方法是由Fox提出的蒙特卡罗定位。这是一种概率方法，把足球机器人当前位置看成许多粒子的密度模型。每个粒子可以看成机器人在此位置定位的假设。在多数应用中，蒙特卡罗定位用在带有距离传感器的机器人设备上，如激光扫描声纳传感器。只有一些方法，视觉用于自定位。在足球机器人自定位有些不同，因为机器人占的面积相对比较小，但是机器人所在位置的面积必须相当准确的确定，以便允许同组不同机器人交流有关场地物体信息和遵守比赛规则。这种定位方法分为如下步骤，首先所有粒子按照一起那机器人的活动的运动模型移动。概率pi取决于在感知模型的基础上所有粒子在当前传感器上的读数。基于这些概率，就提出了所谓的重采样，将更多粒子移向很高概率的采样位置。概率平均分布的确定用来表示当前机器人的位置的最优估计。最后返回开始。 2、蒙塔卡罗 基本思想 当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。 工作过程 蒙特卡罗方法的解题过程可以归结为三个主要步骤：构造或描述概率过程；实现从已知概率分布抽样；建立各种估计量。 蒙特卡罗方法解题过程的三个主要步骤： （1）构造或描述概率过程 对于本身就具有随机性质的问题，如粒子输运问题，主要是正确描述和模拟这个概率过程，对于本来不是随机性质的确定性问题，比如计算定积分，就必须事先构造一个人为的概率过程，它的某些参量正好是所要求问题的解。即要将不具有随机性质的问题转化为随机性质的问题。 2）实现从已知概率分布抽样 构造了概率模型以后，由于各种概率模型都可以看作是由各种各样的概率分布构成的，因此产生已知概率分布的随机变量（或随机向量），就成为实现蒙特卡罗方法模拟实验的基本手段，这也是蒙特卡罗方法被称为随机抽样的原因。最简单、最基本、最重要的一个概率分布是（0，1）上的均匀分布（或称矩形分布）。随机数就是具有这种均匀分布的随机变量。随机数序列就是具有这种分布的总体的一个简单子样，也就是一个具有这种分布的相互独立的随机变数序列。产生随机数的问题，就是从这个分布的抽样问题。在计算机上，可以用物理方法产生随机数，但价格昂贵，不能重复，使用不便。另一种方法是用数学递推公式产生。这样产生的序列，与真正的随机数序列不同，所以称为伪随机数，或伪随机数序列。不过，经过多种统计检验表明，它与真正的随机数，或随机数序列具有相近的性质，因此可把它作为真正的随机数来使用。由已知分布随机抽样有各种方法，与从(0,1)上均匀分布抽样不同，这些方法都是借助于随机序列来实现的，也就是说，都是以产生随机数为前提的。由此可见，随机数是我们实现蒙特卡罗模拟的基本工具。 （3）建立各种估计量 四、实验结果显示 五、实验总结 通过理解最优子结构的性质和子问题重叠性质，在VC++6.0环境下实现动态规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优，最后构造一个最优解。经过反复的调试操作，程序运行才得出结果。 六、附录 A #include 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。 图1-1 蒙特卡罗方法学习总结 核工程与核技术2014级3班张振华20144530317 一、蒙特卡罗方法概述 1.1蒙特卡罗方法的基本思想 1.1.1基本思想 蒙特卡罗方的基本思想就是，当所求问题的解是某个事件的概率，或者是某个随机变量的数学期望，或者是与概率、数学期望有关的量时，通过某种试验方法，得出该事件发生的频率，或者该随机变量若干个具体观察值的算术平均值，通过它得到问题的解。 1.1.2计算机模拟打靶游戏 为了能更为深刻地理解蒙特卡罗方法的基本思想，我们学习了蒲丰氏问题和打靶游戏两大经典例子。下面主要对打靶游戏进行剖析、计算机模拟（MATLAB 程序）。 设某射击运动员的弹着点分布如表1-1 所示， 首先用一维数轴刻画出已知该运动员的弹 着点的分布如图1-1所示。研究打靶游戏，我 们不用考察子弹的运动轨迹，只需研究每次“扣动扳机”后的子弹弹着点。每一环数对应唯一确定的概率，且注意到概率分布函数有单调不减和归一化的性质。首先我们产生一个在(0,1)上均匀分布的随机数（模拟扣动扳机），然后将该随机数代表的点投到P 轴上（模拟子弹射向靶上的一个确定点），得到对应的环数（即子弹的弹着点），模拟打靶完成。反复进行N 次试验，统计出试验结果的样本均值。样本均值应当等于数学期望值，但允许存在一定的偏差，即理论计算值应该约等于模拟试验结果。 clear all;clc; N=100000;s=0; for n=1:N %step 4.重复N 次打靶游戏试验 x=rand(); %step 1.产生在(0,1)上均匀分布的随机数if(x<=0.1) %step 2.若随机数落在(0.0,0.1)上，则代表弹着点在7环g=7; s=s+g; %step 3.统计总环数elseif(x<=0.2) %step 2.若随机数落在(0.1,0.2)上，则代表弹着点在8环g=8;s=s+g; elseif(x<=0.5) %step 2.若随机数落在(0.2,0.5)上，则代表弹着点在9环g=9;s=s+g; else %step 2.若随机数落在(0.5,1.0)上，则代表弹着点在10环 g=10;s=s+g; end end gn_th=7*0.1+8*0.1+9*0.3+10*0.5; %step 5.计算、输出理论值fprintf('理论值：%f\n',gn_th); gn=s/N; %step 6.计算、输出试验结果 fprintf('试验结果：%f\n',gn);1.2蒙特卡罗方法的收敛性与误差 1.2.1收敛性 由大数定律可知，应用蒙特卡罗方法求近似解，当随机变量Z 的简单子样数N 趋向于无穷大（N 充分大）时，其均值依概率收敛于它的数学期望。 1.2.2误差 由中心极限定理可知，近似值与真值的误差为N Z E Z N αλ<-)(?。式中的αλ的值可以根据给出的置信水平，查阅标准正态分布表来确定。 1.2.3收敛性与误差的关系 在一般情况下，求具有有限r 阶原点矩()∞ 实验报告 （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]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 计算机算法与分析 设计报告 班级：信管一班信管二班 姓名（学号）：赵立贺(060340219) 赵艳（060340114）刘辉（060340125）王勇（060340116）万玉琪（060340213）刘旺（060340205）指导教师：赵晓峰姚天祥 设计地点：信息系统实验室 信息管理系 2008年12月13日 一、实验名称： 用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。 二、实验目的： 课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节。通过实践教学，要达到以下目的： （1）使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法； （2）使学生掌握以抽象数据类型为模块的面向对象程序设计方法； （3）使学生提高对实际问题的分析、设计和实现能力； （4）为学生后续课程的学习及课程设计打下坚实的实践基础。 三、使用的策略： 贪心算法、回溯算法等。 四、实验内容： （一）问题描述 一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。 给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。 （二）问题分析（前提行驶前车里加满油） 对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n 1.始点到终点的距离小于Ｎ，则加油次数k=0； 2.始点到终点的距离大于N， A 加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n； B 加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点； C 加油站间的距离相等，即ａ[i]=a[j]=L 算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明 实验内容 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 蒙特卡罗方法的解题过程可以归结为三个主要步骤：构造或描述概率过程；实现从已知概率分布抽样；建立各种估计量。 蒙特卡罗方法解题过程的三个主要步骤： （1）构造或描述概率过程 对于本身就具有随机性质的问题，如粒子输运问题，主要是正确描述和模拟这个概率过程，对于本来不是随机性质的确定性问题，比如计算定积分，就必须事先构造一个人为的概率过程，它的某些参量正好是所要求问题的解。即要将不具有随机性质的问题转化为随机性质的问题。 （2）实现从已知概率分布抽样 构造了概率模型以后，由于各种概率模型都可以看作是由各种各样的概率分布构成的，因此产生已知概率分布的随机变量（或随机向量），就成为实现蒙特卡罗方法模拟实验的基本手段，这也是蒙特卡罗方法被称为随机抽样的原因。最简单、最基本、最重要的一个概率分布是（0，1）上的均匀分布（或称矩形分布）。随机数就是具有这种均匀分布的随机变量。随机数序列就是具有这种分布的总体的一个简单子样，也就是一个具有这种分布的相互独立的随机变数序列。产生随机数的问题，就是从这个分布的抽样问题。在计算机上，可以用物理方法产生随机数，但价格昂贵，不能重复，使用不便。另一种方法是用数学递推公式产生。这样产生的序列，与真正的随机数序列不同，所以称为伪随机数，或伪随机数序列。不过，经过多种统计检验表明，它与真正的随机数，或随机数序列具有相近的性质，因此可把它作为真正的随机数来使用。由已知分布随机抽样有各种方法，与从(0,1)上均匀分布抽样不同，这些方法都是借助于随机序列来实现的，也就是说，都是以产生随机数为前提的。由此可见，随机数是我们实现蒙特卡罗模拟的基本工具。 （3）建立各种估计量 一般说来，构造了概率模型并能从中抽样后，即实现模拟实验后，我们就要确定一个随机变量，作为所要求的问题的解，我们称它为无偏估计。建立各种估计量，相当于对模拟实验的结果进行考察和登记，从中得到问题的解。 蒙特卡洛法模拟蒲丰（Buffon）投针实验-使用Matlab 2010年03月31日星期三8:47 蒲丰投针实验是一个著名的概率实验，其原理请参见此页： https://www.doczj.com/doc/6515934339.html,/reese/buffon/buffon.html 现在我们利用Matlab来做模拟，顺便说一下，这种随机模拟方法便是传说中的“蒙特- 《算法设计》课程报告 课序号： 01 学号： 2012141461134 姓名：刘佳玉 任课教师：陈瑜 评阅成绩： 评阅意见： 提交报告时间：2014年 6 月 16 日 贪心算法 1、问题描述 （这是我在soj上找的一道题，以前没做出来，现在用贪心的思想做出来了） 约翰要去钓鱼。他有h小时可用（1≤h≤16），在这个地区有n个湖泊（2≤n≤25），所有的湖泊沿着一条单行道可到达。约翰从湖泊1开始，他可以在任何湖泊结束。他只能从一个湖，到下一个，但他没有必要停在任何湖除非他想停。对于每个i = 1，……，n-1，ti 表示从湖i到湖i+1的5分钟的时间间隔（0 < ti < = 192）。例如，t3 = 4意味着它从湖3湖4需要20分钟的时间。 为了帮助他们规划自己的钓鱼旅行，约翰已经收集了一些关于湖泊信息。对于每个湖泊的i，能钓到的鱼在最初的5分钟的数量，用fi表示（fi > = 0），是已知的。每钓5分钟的鱼，能钓到的鱼在接下来的5分钟的间隔降低一个恒定的数di（di＞＝0）。如果能钓到的鱼在一个时间区的数量小于或等于di，将不会有更多的鱼留在湖里在下一个时间间隔。为了简化规划，约翰认为没有人会在影响他期待钓到的鱼的数量的湖里钓鱼。 写一个程序来帮助约翰计划他的最大化期望钓到的鱼的数量的钓鱼之旅。在每个湖花费的时间数必须是5的倍数。 这个问题包含多个测试案例！ 一个多输入的第一行是一个整数N，然后一个空白行后的N个输入块。每个输入块由问题描述中的格式表示的。每个输入块之间有一个空行。 输出格式包含N个输出块。输出块之间要有一个空白行。 输入 在输入中，会给你一个案例输入的数量。每一种情况下，以n开始，其次是h，接下来有一行n个整数指定fi（1 < =i< = n），然后有一行n个整数di（1≤i＜＝n），最后，有一行n - 1的整数ti（1≤i＜＝n-1）。输入在n=0的情况下终止。 输出 算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序代码如下： #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验3 贪心算法 哈夫曼编码 班级：软件102班 学号：11003215 姓名：鹿迅 实验3 贪心算法 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 struct huffman { double weight; //用来存放各个结点的权值 int lchild,rchild,parent; //指向双亲、孩子结点的指针 }; 核心源代码 #include int min=11000; int min1; for(int k=0;k 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i动态规划实验报告
算法设计与分析实验报告贪心算法
动态规划算法的应用实验报告
北京理工大学《数据结构与算法设计》实验报告实验一
算法设计与分析实验报告
动态规划算法实验
算法设计与实验报告讲解
蒙特卡罗 算法
动态规划算法分析实验报告
银行家算法设计实验报告
蒙特卡罗方法学习总结
南京邮电大学算法设计实验报告——动态规划法
贪心算法解汽车加油问题实验报告
算法与设计实验报告
蒙特卡罗方法的解题过程可以归结为三个主要步骤
算法设计实验报告(川大陈瑜)
《算法设计与分析》实验报告
哈夫曼编码_贪心算法
算法设计与分析实验报告 统计数字问题
相关主题
文本预览