算法实验一凸包问题
实验一：分治算法
骆吉洲刘显敏
1. 实验目的
1、掌握分治算法的设计思想与方法，
2、熟练使用高级编程语言实现分治算法，
3、通过对比简单算法以及不同的分治求解思想，体验分治算法。
2. 实验学时
4学时，必做实验。
3. 实验问题
求解凸包问题：输入是平面上n个点的集合Q，凸包问题是要输出一个Q的凸包。其中，Q的凸包是一个凸多边形P，Q中的点或者在P上或者在P中。（详情请见课件）
4. 实验步骤
4.1 实现基于枚举方法的凸包求解算法
提示：考虑Q中的任意四个点A、B、C、D，如果A处于BCD构成的三角形内部，那么A一定不属于凸包P的顶点集合。
4.2 实现基于Graham-Scan的凸包求解算法
提示：具体算法思想见课件。
4.3 实现基于分治思想的凸包求解算法
提示：具体算法思想见课件。
4.4 对比三种凸包求解算法
（1）实现随机生成正方形(0,0)-(0,100)-(100,100)-(100,0)内的点集合Q的算法；（2）利用点集合生成算法自动生成大小不同数据集合，如点数大小分别为(1000，2000，3000…)的数据集合；
（3）对每个算法，针对不同大小的数据集合，运行算法并记录算法运行时间；（4）对每个算法，绘制算法性能曲线，对比算法。
5. 帮助
（1）记录算法运行时间方法(要求单位精确到毫秒)：利用各种高级语言提供的记录系统当前时间的函数，在程序中调用算法前记录系统当前时间，在程序中调用算法后记录系统时间，利用两个时间的差作为算法运行时间。
（2）绘制算法性能曲线，可以利用Excel软件的“插入折线图”等类似功能。算法性能曲线应该反映当数据集合从小变大时，具体算法的运行时间。
数值稳定性验证实验报告
实验课程：数值计算方法专业：数学与应用数学班级：08070141 学号：37 姓名：汪鹏飞 中北大学理学院
实验1 赛德尔迭代法 【实验目的】 熟悉用塞德尔迭代法解线性方程组 【实验内容】 1.了解MATLAB 语言的用法 2.用塞德尔迭代法解下列线性方程组 1234123412341234 54 1012581034 x x x x x x x x x x x x x x x x ---=-??-+--=?? --+-=??---+=? 【实验所使用的仪器设备与软件平台】 计算机，MATLAB7.0 【实验方法与步骤】 1.先找出系数矩阵A ，将前面没有算过的x j 分别和矩阵的(,)A i j 相乘,然后将累加的和赋值给sum ，即(),j s u m s u m A i j x =+?.算 出()/(,) i i x b sum A i i =-,依次循环,算出所有的i x 。 2.若i x 前后两次之差的绝对值小于所给的误差限ε，则输出i x .否则重复以上过程，直到满足误差条件为止. 【实验结果】 (A 是系数矩阵，b 是右边向量，x 是迭代初值，ep 是误差限) function y=seidel(A,b,x,ep) n=length(b); er=1; k=0; while er>=ep
k=k+1; for i=[1:1:n] q=x(i); sum=0; for j=[1:1:n] if j~=i sum=sum+A(i,j)*x(j); end end x(i)=(b(i)-sum)/A(i,i); er=abs(q-x(i)); end end fprintf('迭代次数k=%d\n',k) disp(x') 【结果分析与讨论】 >> A=[5 -1 -1 -1;-1 10 -1 -1;-1 -1 5 -1;-1 -1 -1 10]; b=[-4 12 8 34]; seidel(A,b,[0 0 0 0],1e-3) 迭代次数k=6 0.99897849430002 1.99958456867649 2.99953139743435 3.99980944604109
算法设计与分析实验报告贪心算法
算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 实验三：动态规划法 【实验目的】 应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验要求】 应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]， A[1,n]=A[1,k] ×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义： 0 （i=j ） m[i][j]= min{m[i][k]＋m[k+1][j]+n i-1n k n j （i 篇一：大学物理实验1误差分析 云南大学软件学院实验报告 课程：大学物理实验学期： - 学年第一学期任课教师： 专业： 学号： 姓名： 成绩： 实验1 误差分析 一、实验目的 1. 测量数据的误差分析及其处理。 二、实验内容 1．推导出满足测量要求的表达式，即 0? (?)的表达式； 0= (( * )/ (2*θ)) 2．选择初速度A，从[10，80]的角度范围内选定十个不同的发射角，测量对应的射程， 记入下表中： 3．根据上表计算出字母A 对应的发射初速，注意数据结果的误差表示。 将上表数据保存为A. ,利用以下程序计算A对应的发射初速度，结果为100.1 a =9.8 _ =0 =[] _ = ("A. "," ") _ = _ . ad ()[:-1] = _ [:]. ('\ ') _ = _ . ad ()[:-1] = _ [:]. ('\ ') a (0,10): .a d( a . ( a ( [ ])* / a . (2.0* a ( [ ])* a . /180.0))) _ += [ ] 0= _ /10.0 0 4．选择速度B、C、D、重复上述实验。 B C 6．实验小结 (1) 对实验结果进行误差分析。 将B表中的数据保存为B. ,利用以下程序对B组数据进行误差分析，结果为 -2.84217094304 -13 a =9.8 _ =0 1=0 =[] _ = ("B. "," ") _ = _ . ad ()[:-1] = _ [:]. ('\ ') _ = _ . ad ()[:-1] = _ [:]. ('\ ') a (0,10): .a d( a . ( a ( [ ])* / a . (2.0* a ( [ ])* a . /180.0))) _ += [ ] 0= _ /10.0 a (0,10): 1+= [ ]- 0 1/10.0 1 (2) 举例说明“精密度”、“正确度”“精确度”的概念。 1. 精密度 计量精密度指相同条件测量进行反复测量测值间致(符合)程度测量误差角度说精密度所 反映测值随机误差精密度高定确度(见)高说测值随机误差定其系统误差亦。 2. 正确度 计量正确度系指测量测值与其真值接近程度测量误差角度说正确度所反映测值系统误差 正确度高定精密度高说测值系统误差定其随机误差亦。 3. 精确度 计量精确度亦称准确度指测量测值间致程度及与其真值接近程度即精密度确度综合概念 测量误差角度说精确度(准确度)测值随机误差系统误差综合反映。 比如说系统误差就是秤有问题，称一斤的东西少2两。这个一直恒定的存在，谁来都是 这样的。这就是系统的误差。随机的误差就是在使用秤的方法。 篇二：数据处理及误差分析 物理实验课的基本程序 数值分析 实 验 报 告 专业：信息与计算科学 班级： 10***班 学号： 1008060**** 姓名： ****** 实验目的： 用龙贝格积分算法进行积分计算。 算法要求： 龙贝格积分利用外推方法，提高了计算精度，加快了收敛速度。 1--4R R R R 1-j 1-j 1-k 1-j k 1-j k j k ，，，，+= ，k=2，3，… 对每一个k ，j 从2做到k ，一直做到|R R 1-k 1-k k k -，，| 小于给定控制精 度时停止计算。 其中： T R h k 1k =，（复化梯形求积公式），2h 1-k k a -b = 程序代码： #include while(t!=n) { t*=2; ++i; } return i; } float t(int n) { float g,h,q=0; if(1==n) { h = (float)fabs(b-a); q = (f(a)+f(b))*h/2; } else { float x = a; g = 0; h = (float)fabs(b-a)*2/n; x = x+h/2; while(x 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 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={ 实验一简单算法设计 一.实验目的和要求 1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程； 2. 掌握简单问题的算法设计与分析，能设计比较高效的算法； 3. 熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力； 二．实验内容 (一)相等元素问题 1.问题描述先排序函数，再查找函数。 #define size 100 Typedef strat { Int Array[size] Int listlength }List List a; Main() { 1、输入 2、排序 3、查找 4、输出 } 元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？ 2. 测试数据 输入： 9 71 25 64 38 52 5 31 19 45 26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91 输出：No Yes No 3. 设计与实现的提示 算法最坏情况和平均情况的时间复杂性是衡量算法优劣的重要指标，算法设计要求尽可能设计比较高效的算法。 (二) 整数集合分解（选做） 1.问题描述 设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。 2. 测试数据 输入： 68 25 34 16 2 37 3 95 76 57 21 13 4 78 29 6 17 39 51 20 43 12 28 3 48 59 14 32 47 51 42 61 9 24 52 78 65 2 37 78 51 73 29 7 26 95 37 2 输出： 2 3 4 6 12 13 16 17 20 21 25 29 34 37 39 43 51 57 68 76 78 95 2 2 3 7 9 1 4 24 26 28 29 32 37 37 42 47 48 51 51 52 59 61 62 65 73 78 95 3. 设计与实现的提示 本题可以有多种方法。算法时间复杂性是选取算法的重要依据。输出的两个新整数集合要求按照从小到大排序后输出。该排序步骤对算法时间复杂性的影响在此不计。 实验一 误差分析 实验（病态问题） 实验目的：算法有“优”与“劣”之分，问题也有“好”与“坏”之别。对数值方法的研究而言，所谓坏问题就是问题本身对扰动敏感者，反之属于好问题。通过本实验可获得一个初步体会。 数值分析的大部分研究课题中，如线性代数方程组、矩阵特征值问题、非线性方程及方程组等都存在病态的问题。病态问题要通过研究和构造特殊的算法来解决，当然一般要付出一些代价（如耗用更多的机器时间、占用更多的存储空间等）。 问题提出：考虑一个高次的代数多项式 )1.1() ()20()2)(1()(20 1∏=-=---=k k x x x x x p 显然该多项式的全部根为1,2,…,20共计20个，且每个根都是单重的。现考虑该多项式的一个扰动 )2.1(0 )(19=+x x p ε 其中ε是一个非常小的数。这相当于是对（）中19x 的系数作一个小的扰动。我们希望比较（）和（）根的差别，从而分析方程（）的解对扰动的敏感性。 实验内容：为了实现方便，我们先介绍两个Matlab 函数：“roots ”和“poly ”。 roots(a)u = 其中若变量a 存储n+1维的向量，则该函数的输出u 为一个n 维的向量。设a 的元素依次为121,,,+n a a a ，则输出u 的各分量是多项式方程 01121=+++++-n n n n a x a x a x a 的全部根；而函数 poly(v)b = 的输出b 是一个n+1维变量，它是以n 维变量v 的各分量为根的多项式的系数。可见“roots ”和“poly ”是两个互逆的运算函数。 ;000000001.0=ess );21,1(zeros ve = ;)2(ess ve = ))20:1((ve poly roots + 上述简单的Matlab 程序便得到（）的全部根，程序中的“ess ”即是（）中的ε。 实验要求： （1）选择充分小的ess ，反复进行上述实验，记录结果的变化并分析它们。 如果扰动项的系数ε很小，我们自然感觉（）和（）的解应当相差很小。计算中你有什么出乎意料的发现表明有些解关于如此的扰动敏感性如何 （2）将方程（）中的扰动项改成18x ε或其它形式，实验中又有怎样的现象 出现 （3）（选作部分）请从理论上分析产生这一问题的根源。注意我们可以将 方程（）写成展开的形式， ) 3.1(0 ),(1920=+-= x x x p αα 同时将方程的解x 看成是系数α的函数，考察方程的某个解关于α的扰动是否敏感，与研究它关于α的导数的大小有何关系为什么你发现了什么现象，哪些根关于α的变化更敏感 思考题一：（上述实验的改进） 在上述实验中我们会发现用roots 函数求解多项式方程的精度不高，为此你可以考虑用符号函数solve 来提高解的精确度，这需要用到将多项式转换为符号多项式的函数poly2sym,函数的具体使用方法可参考Matlab 的帮助。 算法设计与分析实验报告 学院：信息学院 专业：物联网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．M1040A型无心磨床一台； 2．分辨率为0.001mm的电感测微仪一台； 3．块规一付（尺寸大小根据试件尺寸而定）； 4．千分尺一只； 5．试件一批约120件， 6．计算机和数据采集系统一套。 三、实验容 在无心磨床上连续磨削一批试件（120件），按加工顺序在比较仪上测量尺寸，并记录之，然后画尺寸点图和X---R图。并从点图上取尺寸比较稳定（即尽量排除掉变值系统性误差的影响）的一段时间连续加工的零件120件，由此计算出X、σ，并做出尺寸分布图，分析加工过程中产生误差的性质，工序所能达到的加工精度；工艺过程的稳定性和工艺能力；提出消除或降低加工误差的措施。 四、实验步骤 1. 按被磨削工件的基本尺寸选用块规，并用气油擦洗干净后推粘在一起； 2. 用块规调整比较仪，使比较仪的指针指示到零，调整时按大调---微调---水平调整步骤进行（注意大调和水平调整一般都予先调好），调整好后将个锁紧旋钮旋紧，将块规放入盒中。 3. 修正无心磨床的砂轮，注意应事先把金刚头退后离开砂轮。将冷却液喷向砂轮，然后在按操作规程进刀，修整好砂轮后退刀，将冷却液喷头转向工件位置。 4. 检查磨床的挡片，支片位置是否合理（如果调整不好，将会引起较大的形变误差）。对于挡片可通过在机床不运转情况下，用手将工件沿着支片紧贴挡片前后推动，同时调整前后螺钉，直至工件能顺利、光滑推过为宜。 5. 按给定尺寸（Φd-0.02）调整机床，试磨五件工件，使得平均尺寸应保证在公差带中心稍偏下为宜，然后用贯穿法连续磨削一批零件，同时用比较仪，按磨削顺序测量零件尺寸并记录之。 6. 清理机床，收拾所用量具、工具等。 7. 整理实验数据，打印做实验报告。 五、实验结果及数据处理 该实验选用M1040A型无心磨床和块规一付 （1）实验原始数据 实验三 龙贝格方法 【实验类型】 验证性 【实验学时】 2学时 【实验内容】 1.理解龙贝格方法的基本思路 2.用龙贝格方法设计算法，编程求解一个数值积分的问题。 【实验前的预备知识】 1．计算机基础知识2．熟悉编程基本思想3．熟悉常见数学函数； 【实验方法或步骤】 龙贝格方法的基本思路龙贝格方法是在积分区间逐次二分的过程中，通过 对梯形之值进行加速处理，从而获得高精度的积分值。 1． 龙贝格方法的算法 步骤1 准备初值()f a 和()f b ，用梯形计算公式计算出积分近似值 ()()12b a T f a f b -=+??? ? 步骤2 按区间逐次分半计算梯形公式的积分近似值令 2i b a h -=，0,1,2,...i =计算12102122n n n i i h T T f x -+=??=+ ??? ∑，2i n = 步骤3 按下面的公式积分梯形公式：()223n n n n T T S T -=+ 辛普生公式：()2215n n n n S S C S -=+ 龙贝格公式：()2263n n n n C C R C -=+ 步骤4 精度控制 当2n n R R ε-<，（ε为精度）时，终止计算，并取2n R 为近似值否则将步长折 半，转步骤2。 [实验程序] #include 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。 实验报告一 课程C++ 实验名称简单算法设计第 1 页专业_数学与应用数学_ __ 班级__ 双师一班学号105012011056 姓名陈萌 实验日期：2013 年 3 月9 日报告退发(订正、重做) 一、实验目的 1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程； 2. 掌握简单问题的算法设计与分析，能设计比较高效的算法； 3. 熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力。 二、实验内容 (一)相等元素问题 1.问题描述 元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？ 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1767题 输入：输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n<=500)，表示整数序列的长度，第二行给出整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出一行，若该组测试例中存在两个相等的元素则输出”Yes”，否则，输出”No”。每个测试例的输出数据用一行表示。 3. 测试数据 输入：3 10 9 71 25 64 38 52 5 31 19 45 16 26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33 20 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91 输出：No Yes No (二) 整数集合分解 1.问题描述 设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1768题 输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n为偶数，且n<=500)，表示原整数集合的长度，第二行给出这n个整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出两行，分别表示新生成的整数集合。其中，第一行是元素和比较小的整数集合，第二行是元素和比较大的整数集合，整数之间用一个空格隔开。两个测 一元线性回归在公司加班制度中的应用 院（系）： 专业班级： 学号姓名： 指导老师： 成绩： 完成时间： 一元线性回归在公司加班制度中的应用 一、实验目的 掌握一元线性回归分析的基本思想和操作，可以读懂分析结果，并写出回归方程，对回归方程进行方差分析、显著性检验等的各种统计检验 二、实验环境 SPSS21.0 windows10.0 三、实验题目 一家保险公司十分关心其总公司营业部加班的程度，决定认真调查一下现状。经10周时间，收集了每周加班数据和签发的新保单数目，x 为每周签发的新保单数目，y 为每周加班时间（小时），数据如表所示 y 3.5 1.0 4.0 2.0 1.0 3.0 4.5 1.5 3.0 5.0 2. x 与y 之间大致呈线性关系？ 3. 用最小二乘法估计求出回归方程。 4. 求出回归标准误差σ∧ 。 5. 给出0 β∧与1 β∧ 的置信度95%的区间估计。 6. 计算x 与y 的决定系数。 7. 对回归方程作方差分析。 8. 作回归系数1 β∧ 的显著性检验。 9. 作回归系数的显著性检验。 10.对回归方程做残差图并作相应的分析。 11.该公司预测下一周签发新保单01000 x=张，需要的加班时间是多少？ 12.给出0y的置信度为95%的精确预测区间。 13.给出 () E y的置信度为95%的区间估计。 四、实验过程及分析 1.画散点图 如图是以每周加班时间为纵坐标，每周签发的新保单为横坐标绘制的散点图，从图中可以看出，数据均匀分布在对角线的两侧，说明x和y之间线性关系良好。 2.最小二乘估计求回归方程 用SPSS 求得回归方程的系数01,ββ分别为0.118,0.004，故我们可以写出其回归方程如下： 0.1180.004y x =+ 3.求回归标准误差σ∧ 由方差分析表可以得到回归标准误差：SSE=1.843 故回归标准误差： 2= 2SSE n σ∧-，2σ∧=0.48。 4.给出回归系数的置信度为95%的置信区间估计。 由回归系数显著性检验表可以看出，当置信度为95%时： Romberg龙贝格算法实验报告 2017-08-09 课程实验报告 课程名称： 专业班级： CS1306班学号： U201314967 姓名：段沛云指导教师：报 告日期： 计算机科学与技术学院 目录 1 实验目的 (1) 2 实验原理 (1) 3 算法设计与流程框图 (2) 4 源程序 (4) 5 程序运行 (7) 6 结果分析 (7) 7 实验体会 (7) 1 实验目的 掌握Romberg公式的用法，适用范围及精度，熟悉Romberg算法的流程，并能够设计算法计算积分 31 得到结果并输出。 1x 2 实验原理 2.1 取k=0,h=b-a,求T0= 数)。 2.2 求梯形值T0( b-a ),即按递推公式（4.1）计算T0。 k 2 h [f(a)+f(b)]，令1→k,(k记区间[a，b]的二分次2 2.3 求加速值，按公式(4.12)逐个求出T表的第k行其余各元素Tj(k-j) (j=1,2,….k)。 2.4 若|Tk+1-Tk| n-1 11T2n=[Tn+hn∑f(xi+)] 22i=0 1 Sn=T2n+(T2n-Tn) 31 Cn=S2n+(S2n-Sn) 151 Rn=C2n+(C2n-Cn) 63 3 算法设计与流程框图 算法设计：(先假定所求积分二分最大次数次数为20) 3.1 先求T[k][0] 3.2 再由公式T (k)m 4m(k+1)1)=mTm-1-mTm(k-1(k=1,2,) 求T[i][j] 4-14-1 3.3 在求出的同时比较T[k][k]与T[k-1][k-1]的大小，如果二者之差的绝对 值小于1e-5，就停止求T[k][k]；此时的k就是所求的二分次数，而此时的T[k][k]就是最终的结果 3.4 打印出所有的T[i][j]；程序流程图 实验报告 （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]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 误差分析及实验心得 误差分析 1 系统误差：使用台秤、量筒、量取药品时产生误差； 2 随机误差：反应未进行完全，有副反应发生；结晶、纯化及过滤时，有部分产品损失。 1、实验感想： 在实验的准备阶段，我就和搭档通过校园图书馆和电子阅览室查阅到了很多的有关本实验的资料，了解了很多关于阿司匹林的知识，无论是其发展历史、药理、分子结构还是物理化学性质。而从此实验，我们学习并掌握了实验室制备阿司匹林的各个过程细节，但毕竟是我们第一次独立的做实验，导致实验产率较低，误差较大。 在几个实验方案中，我们选取了一个较简单，容易操作的进行实验。我与同学共做了3次实验，第一次由于加错药品而导致实验失败，第二次实验由于抽滤的时候加入酒精的量过多，导致实验产率过低。因此，我们进行了第三次实验，在抽滤时对酒精的用量减少，虽然结果依然不理想，但是我们仍有许多的收获： （1）、培养了严谨求实的精神和顽强的毅力。通过此次的开放性实验，使我们了解到“理论结合实践”的重要性，使我们的动手能力和思考能力得到了锻炼和提高，明白了在实践中我们仍需要克服很多的困难。（2）、增进同学之间的友谊，增强了团队合作精神。这次的开放性实验要求两个或者两个以上的同学一起完成，而且不像以前实验时有已知的实验步骤，这就要求我们自己通力合作，独立思考，查阅资料了解实验并制定方案，再进行实验得到要求中的产物。我们彼此查找资料，积极的发表个人意见，增强了团队之间的协作精神，培养了独立思考问题的能力，同时培养了我们科学严谨的求知精神，敢于追求真理，不怕失败的顽强毅力。当然我们也在实验中得到了很大的乐趣。 九、实验讨论及心得体会 本次实验练习了乙酰水杨酸的制备操作，我制得的乙酰水杨酸的产量为理论上应该是约1.5g。所得产量与理论值存在一定偏差通过分析得到以下可能原因： a、减压过滤操作中有产物损失。 b、将产物转移至表面皿上时有产物残留。 c、结晶时没有结晶完全。 通过以上分析我觉得有些操作导致的损失可以避免所以我在以后的实验中保持严谨的态度。我通过本次实验我学到了乙酸酐和水杨酸在酸催化下制备乙酰水杨酸的操作方法初步了解有机合成中乙酰化反应原理巩固和进一步熟悉了减压过滤、重结晶基本操作的原理和方法了解到乙酰水杨酸中杂质的来源及其鉴别方法通过误差分析可能原因进一步更深理解实验的原理和操作养成严谨的态度。 算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明 实验内容 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 数值分析实验报告总结 随着电子计算机的普及与发展，科学计算已成为现代科 学的重要组成部分，因而数值计算方法的内容也愈来愈广泛和丰富。通过本学期的学习，主要掌握了一些数值方法的基本原理、具体算法，并通过编程在计算机上来实现这些算法。 算法算法是指由基本算术运算及运算顺序的规定构成的完 整的解题步骤。算法可以使用框图、算法语言、数学语言、自然语言来进行描述。具有的特征：正确性、有穷性、适用范围广、运算工作量少、使用资源少、逻辑结构简单、便于实现、计算结果可靠。 误差 计算机的计算结果通常是近似的，因此算法必有误差， 并且应能估计误差。误差是指近似值与真正值之差。绝对误差是指近似值与真正值之差或差的绝对值；相对误差：是指近似值与真正值之比或比的绝对值。误差来源见表 第三章泛函分析泛函分析概要 泛函分析是研究“函数的函数”、函数空间和它们之间 变换的一门较新的数学分支，隶属分析数学。它以各种学科 如果 a 是相容范数，且任何满足 为具体背景，在集合的基础上，把客观世界中的研究对象抽 范数 范数，是具有“长度”概念的函数。在线性代数、泛函 分析及相关的数学领域，泛函是一个函数，其为矢量空间内 的所有矢量赋予非零的正长度或大小。这里以 Cn 空间为例， Rn 空间类似。最常用的范数就是 P-范数。那么 当P 取1, 2 ,s 的时候分别是以下几种最简单的情形: 其中2-范数就是通常意义下的距离。 对于这些范数有以下不等式: 1 < n1/2 另外，若p 和q 是赫德尔共轭指标，即 1/p+1/q=1 么有赫德尔不等式: II = ||xH*y| 当p=q=2时就是柯西-许瓦兹不等式 般来讲矩阵范数除了正定性，齐次性和三角不等式之 矩阵范数通常也称为相容范数。 象为元素和空间。女口：距离空间，赋范线性空间， 内积空间。 1-范数: 1= x1 + x2 +?+ xn 2-范数: x 2=1/2 8 -范数: 8 =max oo ，那 外，还规定其必须满足相容性: 所以算法设计实验3
大学物理实验报告数据处理及误差分析
数值分析—龙贝格算法
北京理工大学《数据结构与算法设计》实验报告实验一
实验一 简单算法设计
数值分析实验报告1
算法设计与实验报告讲解
机械加工误差分析实验报告
数值分析龙贝格实验报告
银行家算法设计实验报告
算法设计实验报告一(简单算法设计)
一元线性回归分析实验报告
Romberg龙贝格算法实验报告.
南京邮电大学算法设计实验报告——动态规划法
误差分析及实验心得
算法与设计实验报告
数值分析实验报告总结