深圳大学实验报告
课程名称：算法设计与分析
实验项目名称：排序算法性能分析
学院：
专业、班级：
指导教师：杨烜
报告人：学号：
实验报告提交时间： 2015.4.3
教务处制
一、实验目的与实验环境
实验目的：
1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理
2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。
实验环境：VC++ 6.0
二、实验原理与算法描述
算法（1）选择排序 SelectSort(A[0...n-1],n)
//利用选择排序对给定的数组排序
//输入：一个可排序数组A[0...n-1]
//输出：非降序排列的数组A[0...n-1]
for i<-0 to n-2 do
min<-i
for j<-i+1 to n-1 do
if A[j] min<-j swap A[i] and A[min] 理论效率：C(n) ∈θ(n^2),不稳定算法 算法（2）快速排序 QuickSort(A[0...n-1],n) //利用快速排序对给定的数组排序 //输入：一个可排序数组A[0...n-1] //输出：非降序排列的数组A[0...n-1] if l s<-Partition(A[l...r]) //s是分裂位置 Quicksort(A[l...s-1]) Quicksort(A[s+1...r]) Partition(A[l...r]) //以第一个数为中轴，对子数组进行分区 //输入：数组A[0...n-1]中的子数组A[l...r]，由左右下标l和r定义 //输出：数组A[l...r]的一个分区，分裂点的未知作为函数的返回值p<-A[l] i<-l;j<-r+1 repeat repeat i<-i+1 until A[i]>=P repeat j<-j-1 until A[j]<=P swap(A[i],A[j]) until i>=j swap (A[i],A[j]) //当i>=j撤销最后一次交换 swap (A[l],A[j]) return j 理论效率：C(n) ∈θ(nlnn)，不稳定算法 算法（3）合并排序 MergeSort(A[0...n-1]) //利用合并排序对给定的数组排序 //输入：一个可排序数组A[0...n-1] //输出：非降序排列的数组A[0...n-1] if n>1 copy A[0...?n/2?-1] to B[0...?n/2?-1] copy A[?n/2?...n-1] to C[0...?n/2?-1] Mergesort(B[0...?n/2?-1]) Mergesort(C[0...?n/2?-1]) Merge(B,C,A) Merge(B[0...p-1],C[0...q-1],A[0...p+q-1]) //将两个有序数组合并为一个有序数组 //输入：两个有序数组B[0...p-1],C[0...q-1] //输出：A[0...p+q-1]中已经有序存放了B和C中的元素 i<-0;j<-0;k<-0 while i if B[i]<=C[j] A[k]<-B[i];i<-i+1 else A[k]<-C[j];j<-j+1 k<-k+1 if i=p copy C[j...q-1] to A[k...p+q-1] else copy B[i...p-1] to A[k...p+q-1] 理论效率：C(n)∈θ(nlogn)，稳定算法 算法（4）冒泡排序 BubbleSort(A[0...n-1]) //利用冒泡排序对给定的数组排序 //输入：一个可排序数组A[0...n-1] //输出：非降序排列的数组A[0...n-1] for i<-0 to n-2 do for j<-0 to n-2-i do if A[j+1] swap A[j] and A[j+1] 理论效率：C(n)∈θ(n^2)，稳定算法 算法（5）插入排序 InsertSort(A[0...n-1],n) //利用插入排序对给定的数组排序 //输入：一个可排序数组A[0...n-1] //输出：非降序排列的数组A[0...n-1] for k<-2 to n do A[0]<-A[k] j<-k-1 while (j!=0 and A[j]>A[0]) do A[j+1]<-A[j] j<-j-1 A[j+1]<-A[0] 理论效率：C(n)∈θ(n^2)，稳定算法 三、实验代码与运行截图 实验关键代码： 1.选择排序 2.快速排序 3.合并排序 4.冒泡排序 5.插入排序 四、实验数据整理与分析 表一选择排序输入规模n与运行时间统计图 n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0020 0.1795 17.8550 表二快速排序输入规模n与运行时间统计图 n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0010 0.0020 0.0435 表三合并排序输入规模n与运行时间统计图 n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0005 0.0025 0.0260 表四冒泡排序输入规模n与运行时间统计图 n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0025 0.3550 39.8810 表五插入排序输入规模n与运行时间统计图 n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0005 0.0900 8.9120 图1. 选择排序时间效率与输入规模n的关系图 图2. 快速排序时间效率与输入规模n的关系图 图3. 合并排序时间效率与输入规模n的关系图 图4. 冒泡排序时间效率与输入规模n的关系图 图5. 插入排序时间效率与输入规模n的关系图 图6. 5种不同排序算法时间效率对比图 实验分析： 1.从实验结果可以看出，可以验证，当规模n趋向无穷大的时候，排序算法的效率关系为合并排序<快速排序<插入排序<选择排序<冒泡排序。 2.从实验结果可以看出，当输入规模为100000时，合并排序所需时间仅为0.026sec，而冒泡排序则大概需要40sec,合并排序的效率大概是冒泡排序的1500倍，从理论分析来看，合并排序的时间复杂度为θ(nlogn)，而冒泡排序的时间复杂度为θ(n^2),当n取100000时，两者比值大约为1500，因此可以看出，理论效率与实际效率比值基本一致。其余几种排序算法的效率比较也和此相同。同时，这也正是合并排序和快速排序比冒泡排序和选择排序效率高这么多的原因。 3.从算法实现的角度来看，选择排序和插入排序，都必须执行n-1趟；当冒泡排序处于最坏情况下时同样需要进行n-1趟，同时冒泡排序进行第i趟排序需要做n-i次关键字的比较和交换；而选择排序每趟执行同样要n-i-1次关键字的比较；插入排序每执行一趟排序最多比较i次；因此，这三种排序算法效率相比快速排序和合并排序较慢也是意料之中的。 4.实验测试结果与理论结果存在着差距，可能是因为测试组数较少，实验所得数据较少，因此造成数据统计以及作图不准确，造成一定的误差。 5.不同计算机的硬件系统不同，不同计算机的性能不同，因此造成不同时间测试数据的微弱差距。 五、实验结论与实验总结 实验结论：5种不同的算法都能实现排序，但效率不尽相同。从比较可以看出，当输入规模n比较小是，各个算法的优劣体现的并不明显，当规模n达到一定程度时，不同算法之间的不同效率就明显的体现出来了。实际效率与理论效率相比，基本一致。可以看出，其中合并排序以及快速排序的时间效率最高。因此，选择正确的效率高的算法，能给我们的工作带来便捷。 指导教师批阅意见： 成绩评定： 指导教师签字： 年月日备注： 注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。 2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。 1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号： 05 学生姓名：俞梦真 指导教师：郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 实验题目 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.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。 3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢（2）递归与非递归之间如何实现程序的转换？ （3）分析二分查找和快速排序中使用的分治思想。 答： 1．一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。 2．复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。 （4）分析二次取中法和锦标赛算法中的分治思想。 二次取中法：使用快速排序法中所采用的分划方法，以主元为基准，将一个表划分为左右两个子表，左子表中的元素均小于主元，右子表中的元素均大于主元。主元的选择是将表划分为r 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1．普通背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2．0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3．棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析 1．普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量Ｗ, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Ｗi－Ｗ的物品j 中可装入容量为C－Ｗ的背包且具有最大价值的物品。 2．0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 深圳大学-大学物理实验c-杨氏模量的测量 ————————————————————————————————作者: ————————————————————————————————日期： 得分教师签名批改日期深圳大学实验报告 课程名称: 大学物理实验（一) 实验名称： 学院: 指导教师: 报告人:组号： 学号实验地点 实验时间: 年月日 提交时间： 一、实验目的 １． 掌握用拉伸法测定金属丝的杨氏模量； 2. 学会用光杠杆测量长度的微小变化 3． 学会用逐差法处理数据。 二、实验原理 １. 胡克定律和杨氏弹性模量 当固体受外力作用时,它的体积和形状将要发生变化，这种变化,称为形变。物体的形变可分为弹性形变和塑性形变。固体材料的弹性形变又可分为纵向、切变、扭转、弯曲。当外力不太大时,物体的形变与外力成正比，且外力停止作用物体立即恢复原来的形状和体积，这种形变称弹性形变。当外力较大时,物体的形变与外力不成比例,且当外力停止作用后，物体形变不能完全消失，这种形变称为范性形变。范性形变的产生,是由于物体形变而产生的内应力（大小等于单位面积上的作用力）超过了物体的弹性限度(屈服极限）的缘故。如果再继续增大外力,当物体内产生的内应力超过物体的强度极限时,物体便被破坏了。胡克定律:在物体的弹性限度内，胁强于胁变成正比,其比例系数称为杨氏模量（记为Ｅ）。在数值上等于产生单位胁变时的胁强。它的单位是与胁强的单位相同。其中:单位面积上所受到的力称为协强，协变是指在外力作用下的相对形变,它反映了物体形变的大小。杨氏模量来描述材料抵抗纵向弹性形变的能力。 胡克定律指出，在弹性限度内,弹性体的应力和应变成正比。设有一根长为L ，横截面积为S 的钢丝,在外力F 作用下伸长了L ?，则 L L E S F ?= （5-1) 式中的比例系数E 称为杨氏模量，单位为Ｎ·m -２。设实验中所用钢丝直径为d ，则24 1d s π=, 将此公式代入上式整理以后得 L d FL E ?=2 4π （5-２） 上式表明,对于长度Ｌ,直径d 和所加外力Ｆ相同的情况下，杨氏模量Ｅ大的金属丝的伸长量L ?小。因而,杨氏模量是表征固体材料性质的一个重要的物理量,是工程设计上选用材料时常需涉及的重要参数之一,一般只与材料的性质和温度有关,与外力及物体的几何形状无关。对一定材料而言，E 是一个常数，它仅与材料的结构、化学成分及其加工制造的方法有关。杨氏模量的大小标志了材料的刚性。 为能测出金属丝的杨氏模量 E ，必须准确测出上式中右边各量。其中 Ｌ、d 、F 都可用一般方法测得，唯有 ΔL 是一个微小的变化量，用一般量具难以测准，为了测量细钢丝的微小长度变化,实验中使用了光杠杆放大法间接测量。利用光杠杆不仅可以测量微小长度变化，也可测量微小角度变化和形状变化。由于光杠杆放大法具有稳定性好、简单便宜、受环境干扰小等特点，在许多生产和科研领域得到广泛应用。 2、光杠杆和镜尺系统是测量微小长度变化的装置 光杠杆结构如图５－１(ａ) 所示,它实际上是附有三个尖足的平面镜。三个尖足的边线为一等腰三角形。前两足刀口与平面镜在同一平面内(平面镜俯仰方位可调)，后足在前两足刀口的中垂线上。镜尺系统由一把竖立的毫米刻度尺和在尺旁的一个望远镜组成。镜尺系统和光杠杆组成如图５-2(b) 所示的测量系统。 学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日 实验一：递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2018年10月10日16:00。 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： 【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 深圳大学实验报告 课程名称：连续式与分页式主存管理的模拟实现 实验项目名称：进程的控制 学院：信息工程学院（软件学院） 专业：软件工程 指导教师：白鉴聪 报告人：罗城龙学号：20XX151095班级：软件1班 实验时间：20XX/6/20 实验报告提交时间：20XX/6/20 教务处制 实验目的与要求： 模拟在连续分配与分页管理两种方式下，主存空间的分配与回收，帮助学生加深了解存储器管理的工作过程。 方法、步骤： 1、根据例程，尝试采用首次适应算法、循环首次适应算法、最佳适应算法其中的一种 或多种算法实现3.2.1的动态分区分配。算法思想请参考课本P108-109的分区分配算法。 2、根据例程，尝试实现3.2.1的分区回收功能。 3、根据例程，尝试实现3.2.2的分页系统功能 4、至少完成上述三项实验内容中的一个。 5、自行设定内存总空间，大小单位为KB，分页管理需要设定每个页的大小。 6、随机设置当前内存分配状态。 7、自行设计作业队列，队列中至少要有5个作业，设定各个作业空间大小，大小要适 中。 8、输出结果要尽量详细清晰，如果输出内容比较多，可以考虑把输出结果保存到文件 中，通过文件来查看。 9、程序代码要尽量加入注释，提高程序的清晰度与可读性。 10、在实验报告中，一方面可以对实验结果进行分析，一方面可以对两种分配方式 进行比较，分析它们的优劣。 实验过程及内容： 循环首次适应算法： 关键源代码： 1．MEM * temp=NULL;//声明一个MEM的指针，用于保留循环的开始位置2．void init() //在初始化函数init()最后加一个语句，用于 { //指针temp的初始化，因为它开始也要指向空 ……… //链的起始 temp = empty; } 3．实现关键函数 void mem_alloc_loop(MEM *pjob) { MEM * pr; //循环首次适应算法 pr = temp; while (pr != NULL) { if (pr->length > pjob->length) { pjob->head = pr->head; //直接把作业数据块插入已分配队列 alloc_insert(pjob);//插入作业数据块到已分配队列 //产生碎片,需要修改被分配空闲区的参数 //产生小碎片，pr指向它 pr->head = pr->head + pjob->length; pr->length = pr->length - pjob->length; temp=pr->link;//指向分配后的下一个指针 printf("!!!!!%s分配成功!!!!!\n", pjob->name); break; } if (pr->length == pjob->length) //刚好满足 { pjob->head = pr->head; //直接把作业数据块插入已分配队列 temp=pr->link;//指向分配后的下一个指针 alloc_insert(pjob); empty_remove(pr); //从空闲队列中删除该空闲区 printf("!!!!!%s分配成功!!!!!\n", pjob->name); break; } //空闲块太小，则指向下一个空闲块。 if (pr->length < pjob->length) { pr = pr->link; } } if(pr==NULL) { pr=empty; 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图： 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入： 一个算法有 0 个或多个输入， 法 本身定除了初始条件; ④ 输出： 一个算法有一个或多个输出， 是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章 算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响） 般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 以刻画运算对象的初始情况， 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法 位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解） 分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想： 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 深圳大学实验报告课程名称：计算机导论实验 实验项目名称：互联网与网络安全 学院：计算机与软件学院 专业： 指导教师： 报告人：学号：班级： 实验时间：2016. 10.20 实验报告提交时间：2016.12.9 教务处制 实验步骤： 一、浏览器使用，网页下载和保存、搜索引擎使用和信息检索方法。 (一)浏览器使用 浏览器是指可以显示网页服务器或者文件系统的HTML文件（标准通用标记语言的一个应用）内容，并让用户与这些文件交互的一种软件。 它用来显示在万维网或局域网等内的文字、图像及其他信息。这些文字或图像，可以是连接其他网址的超链接，用户可迅速及轻易地浏览各种信息。大部分网页为HTML格式。 一个网页中可以包括多个文档，每个文档都是分别从服务器获取的。大部分的浏览器本身支持除了HTML之外的广泛的格式，例如JPEG、PNG、GIF等图像格式，并且能够扩展支持众多的插件（plug-ins）。另外，许多浏览器还支持其他的URL类型及其相应的协议，如、HTTPS（HTTP协议的加密版本）。HTTP内容类型和URL协议规范允许网页设计者在网页中嵌入图像、动画、视频、声音、流媒体等。 游览器使用: 1.单击【开始】菜单，在弹出的开始菜单中选择【Internet】命令，打开IE浏览器窗口。 2.也可以通过桌面双击IE浏览器的图标来打开IE浏览器、 3.新打开的IE浏览器窗口中不会显示任何内容。需要您指定网站地址才能够访问并显示内 容。 4.打开健康频道页面 在人民网首页的导航栏中单击【健康】超链接文本，打开健康频道页面。 5.打开详细页面 在高血压专题页面中单击某个文章标题，即可查看该标题下的内容。 6.在【健康】频道页面顶部的导航栏中单击【高血压】超链接文本，可以打开高血压专题页 面。 7.在详细页面中可以阅读打开的新闻内容。 实验报告 （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) 掌握收发电子邮件的方法。 3) 掌握在网上查找并下载软件的方法。 4) 掌握网络即时通讯软件和BBS的使用方法。 二、实验说明和实验环境 1) 硬件环境：微型计算机，并已连接到Internet。 2) 软件环境：Windows XP中文版、Internet Explorer(简称IE)浏览器程序、Outlook Express 电子邮件管理程序、FTP客户端软件Leapftp、网络即时通信软件Tencent QQ。 三、实验分析设计 （实验原理和设计） 四、主要实验过程（或核心代码说明） (1) 浏览器的基本使用 浏览器的基本使用步骤如下。 1）启动浏览器。在Windows桌面或快速启动栏中，单击图标，启动应用程序IE 6.0。 2) 输入网页地址(URL)。在IE窗口的地址栏输入要浏览页面的统一资源定位器(Uniform Resource Locator，URL)，按下Enter键，观察IE窗口右上角的IE标志，等待出现浏览页面的内容。例如，在地址栏输入深圳大学主页的URL（https://www.doczj.com/doc/0613749907.html,/），IE浏览器将打开深圳大学的主页，如图9-1所示。 图9-1 用IE6.0打开浏览页面 3) 网页浏览。在IE打开的页面中，包含有指向其他页面的超链接。当将鼠标光标移动到具有超链接的文本或图像上时，鼠标指针会变为“”形，单击鼠标左键，将打开该超链接所指向的网页。根据网页的超链接，即可进行网页的浏览。 图9-2 IE浏览器的菜单和工具栏 4) 断开当前连接。IE浏览器的菜单和工具栏如图9-2所示。单击工具栏中的“停止”按钮，中断当前网页的传输。 5) 重新建立连接。在执行步骤4之后，单击工具栏中的“刷新”按钮，将重新开始 被中断的网页的传输。 6) 保存当前网页信息。使用“文件”菜单的“另存为”命令，将当前网页保存到本地计算机。 7) 保存图像或动画。在当前网页中选择一幅图像或动画，单击鼠标右键，从弹出的快捷菜单中选择“图片另存为”，将该图像或动画保存到本地计算机。 8) 将当前网页地址保存到收藏夹。使用“收藏”菜单的“添加到收藏夹”命令，并在“添加到收藏夹”窗口中选中“允许脱机使用”复选框，如图9-3所示，将当前网页放入收藏夹。 若单击“自定义”按钮，即可激活“脱机收藏夹向导”，利用该向导，可设置脱机浏览内容的数量、如何使脱机网页与网络上的最新网页保持同步、以及是否需要用户名和密码等。 图9-3 添加到收藏夹对话框 9) 在已经浏览过的网页之间跳转。通常的方法是单击工具栏中的“后退”按钮 与“前进”按钮，返回到前一页，或回到后一页。也可以单击工具栏中“后退”与“前进”右侧的“ ”形按钮，从弹出的下拉列表中直接选择某个浏览过的网页。 10) 浏览历史记录 单击工具栏中的“历史”按钮，会在IE窗口的左边打开“历史记录”窗口，该窗口列出了最近一段时间以来所有浏览过的页面。可以按日期、访问站点、访问次数查看历史记录，也可以根据指定的关键词对历史记录进行搜索。 11) 主页设置 使用“工具”菜单中的“Internet选项”命令，打开“Internet选项”对话框。单击“常规”属性页，在“主页”的地址栏中，输入一个URL地址（如https://www.doczj.com/doc/0613749907.html,），单击“确定”按钮，即可以将输入的URL设置为IE的主页，如图9-4所示。 也可以通过单击“使用当前页”按钮，将IE浏览器当前打开的页面作为主页；单击“使 实验总体要求 为避免重复与抄袭，算法分析与设计的实验只规定算法策略，具体的算法题目由学生依据现实当中的问题自行拟定，选题的难易会影响实验得分。 实验可以分组进行，组内与组间可选不同策略的不同题目（问题）、相同策略里面的不同题目、相同题目的不同解法等，尽量避免重复。完全相同的实验报告得0分，不同的重复率扣不同的分数。分组的意义在于研究与实践不同策略的不同题目的差异、不同策略里不同题目异同、相同题目不解法之间的异同与算法效率等。 所有实验都需要包含八个组成部分： （1）实验题目 要求：一句简要的话概括或抽象出所做的实验内容 （2）个人所承担的工作 要求：独立完成报告所有内容者仅填写独立完成即可，此种情况若发现报告有雷同者得0分。协作完成的，重点写自己完成的部分，其他部分可略写，为了锻炼同学们的设计与分析能力，原则上不允许算法模型、算法描述与分析、算法实现上相同。 （3）选题背景与意义 要求：描述选题的背景、针对该问题求解的算法有多少种，发展历史及研究价值等。 （4）问题描述 要求：可以实际问题的描述，也可以某类问题的抽像描述。如果是某类问题的抽象描述，需要指出它的应用场景。 （5）算法策略选择 要求：简要说出选择该策略的理由 （6）计算模型 要求：最接近程序实现中问题求解的数学模型。指明定义域和值的范围或解空间。可以有数据结构及推导或计算公式。递归模型至少有递推公式、递归的出口。如果有的话，给出必要的证明。 （7）算法描述与分析 要求：以标准的描述方式，如流程图、伪码、语言文字。对算法进行时间和空间复杂度分析。时间复杂度要求有必要的推导步骤。 （8）算法实现 要求：给出编程语言、开发环境。给出可执行的算法代码，提供必要的注释。 （9）调试分析记录 要求：软件开发调试过程中遇到的问题及解决过程；核心算法的运行时间和所需内存空间的中科院陈玉福计算机算法设计与分析期末简答题答案
算法设计与分析实验报告贪心算法
算法设计与分析实验报告
算法设计与分析试卷(2010)
算法设计与分析课程设计报告样本
计算机算法设计与分析期末考试复习题
深圳大学大学物理实验c杨氏模量的测量
《算法设计与分析》实验一
深圳大学实验报告
算法设计与分析课程设计报告
算法设计与分析期末试题答案解析
算法设计与分析课程报告
算法设计与分析试卷及答案.doc
深圳大学计算机导论互联网与网络安全实验报告
南京邮电大学算法设计实验报告——动态规划法
深圳大学计导实验报告 网络基本操作
算法设计与分析报告 正文
相关主题
文本预览