当前位置：文档库 › 算法设计与分析报告大作业

算法设计与分析报告大作业

算法分析与设计大作业

班级：12信科

姓名：郭倩南

学号：1242155105

完成日期：2015-6-4

指导教师：陈平

序号选定题目所用算法设计技术1数字三角形问题动态规划

2集合划分问题分治法

回溯法

求子集问题

评分：

大作业报告

1、数字三角形问题

一、问题描述

对于给定的由n行数字组成的数字三角形，计算从三角形的底至顶的路径经过的数字和的最大值。如：7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

二、实验内容与实验步骤

实验内容:

输入数据的第1 行是数字三角形的行数n，1<=n<=100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间

实验步骤:

1、首先证明该问题满足最优化原理

最优化原理：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。

2、建立动态规划函数

3、填表

三、实验环境

Window7系统，vc++6.0软件

四、问题分析

由观察数字三角形可知，从数字三角形的顶层出发，下一层选择向左还是向右取决于两个4层数字三角形的最大数字和，而对于第四层的决定取决于第三层的最大数字和，依次类推，可知该问题是多阶段决策最优化问题，并且划分出来的子问题是相互重叠的，所以该问题采用动态规划法解决

动态规划：与分治法相似，把问题分解按层次分成子问题，直到可以直接求解的子问题，然后一级一级地向上求解。

与分治法的出别在于：动态规划适用有许多重复子问题出现的问题，它保留已求出问题的解。

3 8 3 8

8 1 0 8 1 1 0

2 7 4 4 2 7 4 7 4 4

4 5 2 6 5 4 5 2 6 5 2 6 5

一个五层数字三角形子问题（1）子问题（2）

五、问题解决

（1）根据对问题的分析，写出解决办法。

1、证明：S,S1,S2,..Sn,t是从S到t的一条数字和最大的路径，从源点S开始，设从S到下一段的顶点S1已经求出，则问题转化为求从S1到t的数字和最大的路径，显然S1，S2，...Sn,t一定构成一条从S1到t的数字和最大值的路径，如若不然，设S1，r1,r2,....rq,t是一条数字和最大的路径，则S,S1，r1,r2,....rq,t 的路径经过数字和的最大值比S,S1，S2，...Sn,t的路径数字和更大，从而导致矛盾，所以数字三角形问题满足最优性原理。

2、动态规划函数：

a[i][j]+=a[i+1][j] 当a[i+1][j]>a[i+1][j+1] 时

a[i][j]+=a[i+1][j+1] 当a[i+1][j]<=a[i+1][j+1] 时

3、填表

（2）你在调试过程中发现了怎样的问题？又做了怎样的改进？

答：（a）在代码编译成功后，显示屏上无任何提示语，让人有点不知所措，感觉设计的不太人性化，于是在代码中又添加了一些提示语句，使其更容易理解和操作

（b）算法设计比较简单，运行结果没有显示路径，所以还有待研究

（3）描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度

答：主要算法：

int func()

{

int i,j;

for(i=n-1;i>=1;i--)

for(j=1;j<=i;j++)

{

if(a[i+1][j]>a[i+1][j+1]) a[i][j]+=a[i+1][j];

else a[i][j]+=a[i+1][j+1];

}

return a[1][1];

}

该段代码是程序的核心部分，可以根据此代码进行填表。

算法复杂度：O(T(n)∈O(n^2))

六、实验结果总结

七、附录及源程序

#include

using namespace std;

const int M=100;

int n;

int a[M][M];

int func()

{

int i,j;

for(i=n-1;i>=1;i--)

for(j=1;j<=i;j++)

{

if(a[i+1][j]>a[i+1][j+1]) a[i][j]+=a[i+1][j];

else a[i][j]+=a[i+1][j+1];

}

return a[1][1];

}

int main()

有限元分析大作业报告

有限元分析大作业报告试题1：一、问题描述及数学建模图示无限长刚性地基上的三角形大坝，受齐顶的水压力作用，试用三节点常应变单元和六节点三角形单元对坝体进行有限元分析，并对以下几种计算方案进行比较：（1）分别采用相同单元数目的三节点常应变单元和六节点三角形单元计算；（2）分别采用不同数量的三节点常应变单元计算；（3）当选常应变三角单元时，分别采用不同划分方案计算。该问题属于平面应变问题，大坝所受的载荷为面载荷，分布情况及方向如图所示。二、采用相同单元数目的三节点常应变单元和六节点三角形单元计算 1、有限元建模（1）设置计算类型：两者因几何条件和载荷条件均满足平面应变问题，故均取Preferences 为Structural （2）选择单元类型：三节点常应变单元选择的类型是Solid Quad 4 node182；六节点三角形单元选择的类型是Solid Quad 8 node183。因研究的问题为平面应变问题，故对Element behavior（K3）设置为plane strain。（3）定义材料参数：弹性模量E=2.1e11，泊松比σ=0.3 （4）建几何模型：生成特征点；生成坝体截面（5）网格化分：划分网格时，拾取lineAB和lineBC，设定input NDIV 为15；拾取lineAC，设定input NDIV 为20，选择网格划分方式为Tri+Mapped，最后得到600个单元。

（6)模型施加约束：约束采用的是对底面BC 全约束。大坝所受载荷形式为Pressure ，作用在AB 面上，分析时施加在L AB 上，方向水平向右，载荷大小沿L AB 由小到大均匀分布。以B 为坐标原点，BA 方向为纵轴y ，则沿着y 方向的受力大小可表示为： }{*980098000)10(Y y g gh P -=-==ρρ 2、计算结果及结果分析（1）三节点常应变单元三节点常应变单元的位移分布图三节点常应变单元的应力分布图

中科院陈玉福计算机算法设计与分析期末简答题答案

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类问题。。

《ACM算法与数据结构设计》大作业

《ACM算法与数据结构设计》课程大作业报告题目：五位以内的对称素数学生姓名班级学号学生学院计算机软件学院学生专业计算机科学与技术联系电话电子邮指导教师指导单位计算机学院软件工程系日期2011.5.24

注意事项（1）课程大作业从《ACM算法与数据结构设计》课程实验二（2011年4月19日）或实验三（2011年5月10日）中任选一个课题完成。（2）课程大作业内容包括课题名称、课题内容和要求、课题分析、概要设计、详细设计、测试数据及其结果分析、调试过程中的问题、参考资料列表、课程小结等。（3）课程报告可以打印，也可以手写，但前面两页内容、大作业撰写纲要、课程小结不可遗漏和更换。（4）课程小结给出ACM程序设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考等，需要手写签字。（5）课程大作业提交时间为2011年5月24日（第14周星期二）晚19:00~20:00，地点：计算中心A机房。

一、课题名称：五位以内的对称素数二、课题内容和要求：题目：判断一个数是否为对称且不大于五位数的素数。要求：判断输入的一组数据（正整数）是否是五位以内的对称素数，逐个判断并输出“yes”或“no” 三、课题分析：定义两个函数分别判断数据是否为素数（bool isprime(int n)），是否是对称数（bool issym(int n)）；在main()函数中利用if()语句来判断该数据是否是五位以内的数。只有同时满足三个条件，才能判断一个数据是五位以内的对称素数，输出“yes”；否则输出“no”。输入输出方案：输入: 输入数据含有不多于50个的正整数(0

算法设计与分析实验报告贪心算法

算法设计与分析实验报告贪心算法班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码代码 #include float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree { float weight; intlchild,rchild,parent; }huffman; huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) { inti; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

printf("\n"); for(i=0;i

华科大有限元分析题及大作业题答案——船海专业(DOC)

姓名：学号：班级：

有限元分析及应用作业报告一、问题描述图示无限长刚性地基上的三角形大坝，受齐顶的水压力作用，试用三节点常应变单元和六节点三角形单元对坝体进行有限元分析，并对以下几种计算方案进行比较： 1)分别采用相同单元数目的三节点常应变单元和六节点三角形单元计算； 2)分别采用不同数量的三节点常应变单元计算； 3)当选常应变三角单元时，分别采用不同划分方案计算。

二、几何建模与分析图1-2力学模型由于大坝长度>>横截面尺寸，且横截面沿长度方向保持不变，因此可将大坝看作无限长的实体模型，满足平面应变问题的几何条件；对截面进行受力分析，作用于大坝上的载荷平行于横截面且沿纵向方向均匀分布，两端面不受力，满足平面应变问题的载荷条件。因此该问题属于平面应变问题，大坝所受的载荷为面载荷，分布情况及方向如图1-2所示，建立几何模型，进行求解。假设大坝的材料为钢，则其材料参数：弹性模量E=2.1e11，泊松比σ=0.3 三、第1问的有限元建模本题将分别采用相同单元数目的三节点常应变单元和六节点三角形单元计算。 1）设置计算类型：两者因几何条件和载荷条件均满足平面应变问题，故均取Preferences为Structural 2）选择单元类型：三节点常应变单元选择的类型是PLANE42（Quad 4node42），该单元属于是四节点单元类型，在网格划分时可以对节点数目控制使其蜕化为三节点单元；六节点三角形单元选择的类型是PLANE183（Quad 8node183），该单元属于是八节点单元类型，在网格划分时可以对节点数目控制使其蜕化为六节点单元。因研究的问题为平面应变问题，故对Element behavior（K3）设置为plane strain。 3）定义材料参数 4）生成几何模 a. 生成特征点 b.生成坝体截面 5）网格化分：划分网格时，拾取所有线段设定input NDIV 为10，选择网格划分方式为Tri+Mapped，最后得到200个单元。 6)模型施加约束：约束采用的是对底面BC全约束。大坝所受载荷形式为Pressure，作用在AB面上，分析时施加在L AB上，方向水平向右，载荷大小沿L AB由小到大均匀分布（见图1-2）。以B为坐标原点，BA方向为纵轴y，则沿着y方向的受力大小可表示为： ρ（1） = gh P- =ρ g = - 10 {* } 98000 98000 (Y ) y

算法设计与分析试卷(2010)

算法设计与分析试卷(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 ）。

《程序设计与算法综合实践》期末大作业题目及评分标准

2017级《程序设计与算法综合实践》期末大作业题目及评分标准有如下情况之一者，为不及格。（1）未能完成所选题目评分标准的最低要求。（2）抄袭他人成果。（3）大作业检查时不带电脑，或电脑没有C语言开发环境。（4）出勤次数、课堂表现等不符合学校相关教学文件规定等其他情况。备选题目目录 1.图书购买系统...............................................................................................................- 2 - 2.物流信息管理系统 ....................................................................................................- 3 - 3.PM2.5实时信息管理系统 ............................................................ - 5 - 4.电影评论系统 ............................................................................... - 6 - 5.游戏角色属性分析........................................................................ - 8 - 6.KTV点歌系统 ................................................................................ - 9 - 7.英语词斩系统 ............................................................................. - 11 - 8.校运动会成绩管理系统.............................................................. - 14 - 9.通讯录管理系统 ......................................................................... - 15 - 10.机票购买系统 ............................................................................. - 16 - 11.车辆销售管理系统...................................................................... - 17 - 12.饮品自动贩卖机系统.................................................................. - 18 -

完整word版有限元分析大作业报告要点

船海1004 黄山 U201012278 有限元分析大作业报告试题1：一、问题描述及数学建模图示无限长刚性地基上的三角形大坝，受齐顶的水压力作用，试用三节点常应变单元和六节点三角形单元对坝体进行有限元分析，并对以下几种计算方案进行比较：（1）分别采用相同单元数目的三节点常应变单元和六节点三角形单元计算；（2）分别采用不同数量的三节点常应变单元计算；（3）当选常应变三角单元时，分别采用不同划分方案计算。该问题属于平面应变问题，大坝所受的载荷为面载荷，分布情况及方向如图所示。

二、采用相同单元数目的三节点常应变单元和六节点三角形单元计算 1、有限元建模（1）设置计算类型：两者因几何条件和载荷条件均满足平面应变问题，故均取Preferences为Structural （2）选择单元类型：三节点常应变单元选择的类型是Solid Quad 4 node182；六节点三角形单元选择的类型是Solid Quad 8 node183。因研究的问题为平面应变问题，故对Element behavior（K3）设置为plane strain。（3）定义材料参数：弹性模量E=2.1e11，泊松比σ=0.3 （4）建几何模型：生成特征点；生成坝体截面（5）网格化分：划分网格时，拾取lineAB和lineBC，设定input NDIV 为15；拾取lineAC，设定input NDIV 为20，选择网格划分方式为Tri+Mapped，最后得到600个单元。

1 船海1004 黄山 U201012278 （6)模型施加约束：约束采用的是对底面BC全约束。大坝所受载荷形式为Pressure，作用在AB面上，分析时施加在L上，方向水平向右，载荷大小沿L 由小到大均匀分布。以ABAB B为坐标原点，BA方向为纵轴y，则沿着y方向的受力大小可表示为： P?gh?gyY}*{?)??98000?9800(10? 2、计算结果及结果分析（1）三节点常应变单元三节点常应变单元的位移分布图

软件系统分析与设计大作业

《软件系统分析与设计》期末大作业选题名称：游戏平台管理系统设计人：徐文豪刘青海赖超宇甘智宏班级：软工143班南昌大学软件学院 2016.6.1

目录一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················

一、整体描述随着移动通讯的发展，手机应用也越来越多，其中，游戏应用占据了很大的比重，游戏平台管理系统是整合了大量游戏应用，以及玩家线上交流的平台。主要受众群：拥有移动端或电脑端的人群。应用前景：移动互联的发展为游戏平台的发展提供了很大的生存空间，应用前景十分广阔盈利方式：向平台中游戏的开发商收取一定的费用，游戏玩家向游戏中注入资金时，收取一定比例的游戏收入。面临的困难：游戏平台前期的推广，提高游戏平台本身对开发商和游戏玩家的吸引力，游戏平台能否适应大部分游戏玩家的要求。玩家首先要注册账号，然后就可以在上面下载游戏应用，上传自己的游戏资源。同时，根据玩家的活跃程度获取相应积分，用积分可以兑换游戏礼包，也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验，提出意见和建议，以便游戏及时更新，弥补相应不足。玩家也可以建立游戏工会，不同游戏的玩家都可以加入，分享自己的游戏心得或者转赠游戏装备或积分。

二、需求分析时间when：游戏厂商：随时；注册用户：随时；管理人员：正常工作时间。地点Where：游戏厂商，管理人员：工作地点；注册用户：随地人员who：游戏厂商，管理人员，注册用户， What：游戏厂商：推广游戏，管理人员：扩大服务，盈利；注册人员：玩游戏。 Why：游戏厂商：推广力度不大，效果不好，管理人员：方便管理，注册用户：良好的游戏环境。性能Performance：系统提供服务的效率，响应时间快，由于是手机端的APP吞吐量不需要太大。成本Cost：实现系统需要付出的代价，耗费****元时间Time：2016年6月3日可靠性Reliability: 需要系统长时间正确运行的能力安全性Security: 由于该平台会涉及资金的流动，所以需要对信息安全的保护能力。合规性Compliance: 需要符合各种行业的标准，法律法规，规范。技术性Technology:要求基于安卓平台开发。兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。

算法设计与分析课程设计报告

压缩软件课程设计书一、问题描述：建立一个文本文件，统计该文件中各字符频率，对各字符进行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.以小组为单位完成有限元分析计算，并将计算结果上交； 2.以小组为单位撰写计算分析报告； 3.按下列模板格式完成分析报告； 4.计算结果要求提交电子版，一个算例对应一个文件夹，报告要求提交电子版和纸质版。有限元分析》大作业小组成员：储成峰李凡张晓东朱臻极高彬月 Job name ：banshou 完成日期： 2016-11-22 一、问题描述（要求：应结合图对问题进行详细描述，同时应清楚阐述所研究问题的受力状况和约束情况。图应清楚、明晰，且有必要的尺寸数据。）如图所示，为一内六角螺栓扳手，其轴线形状和尺寸如图，横截面为一外接圆半径为0.01m的正六边形，拧紧力F为600N，计算扳手拧紧时的应力分布图1 扳手的几何结构数学模型

要求：针对问题描述给出相应的数学模型，应包含示意图，示意图中应有必要的尺寸数据；

图 2 数学模型如图二所示，扳手结构简单，直接按其结构进行有限元分析。三、有限元建模 3.1 单元选择要求：给出单元类型，并结合图对单元类型进行必要阐述，包括节点、自由度、实常数等。）图 3 单元类型如进行了简化等处理，此处还应给出文字说

扳手截面为六边形，采用4 节点182单元，182 单元可用来对固体结构进行

二维建模。182单元可以当作一个平面单元，或者一个轴对称单元。它由4 个结点组成，每个结点有2 个自由度，分别在x,y 方向。扳手为规则三维实体，选择8 节点185单元，它由8 个节点组成，每个节点有3 个自由度，分别在x，y，z 方向。 3.2 实常数（要求：给出实常数的具体数值，如无需定义实常数，需明确指出对于本问题选择的单元类型，无需定义实常数。）因为该单元类型无实常数，所以无需定义实常数 3.3材料模型（要求：指出选择的材料模型，包括必要的参数数据。）对于三维结构静力学，应力主要满足广义虎克定律，因此对应ANSYS中的线性，弹性，各项同性，弹性模量EX：2e11 Pa, 泊松比PRXY=0.3 3.4几何建模由于扳手结构比较简单，所以可以直接在ANSYS软件上直接建模，在ANSYS建立正六边形，再创立直线，面沿线挤出体，得到扳手几何模型图4 几何建模

算法设计与分析期末试题答案解析

1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；

健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一

算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.

算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题目录 1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结

1.动态规划解决乘法表问题 1.1问题描述定义于字母表∑{a,b,c)上的乘法表如表所示：依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种，字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种, 字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。则原问题的解是：result[i][n][a] 。设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ：result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a]; result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b]; result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c];

算法设计与分析课程报告

算法设计与分析课程报告第一章算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入：一个算法有 0 个或多个输入，法本身定除了初始条件; ④ 输出：一个算法有一个或多个输出，是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系：区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。第二章算法分析基础 1、算法复杂性分析：算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。算法复杂性度量：期望反映算法本身性能，与环境无关。理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单以刻画运算对象的初始情况，所谓 0 个输入是指算以反映对输入数据加工后的结果。没有输出的算法

位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。第五章分治法 1、递归算法：直接或间接地调用自身的算法。用函数自身给出定义的函数称为递归函数。注：边界条件与递归方程是递归函数的二个要素。实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解）分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。第六章贪心法 1、贪心算法的思想：

有限元分析大作业试题

有限元分析习题及大作业试题要求：1）个人按上机指南步骤至少选择习题中3个习题独立完成，并将计算结果上交； 2）以小组为单位完成有限元分析计算； 3）以小组为单位编写计算分析报告； 4）计算分析报告应包括以下部分： A、问题描述及数学建模； B、有限元建模（单元选择、结点布置及规模、网格划分方案、载荷及边界条件处理、求解控制） C、计算结果及结果分析（位移分析、应力分析、正确性分析评判） D、多方案计算比较（结点规模增减对精度的影响分析、单元改变对精度的影响分析、不同网格划分方案对结果的影响分析等） E、建议与体会 4）11月1日前必须完成，并递交计算分析报告（报告要求打印）。

习题及上机指南：（试题见上机指南）例题1 坝体的有限元建模与受力分析例题2 平板的有限元建模与变形分析例题1：平板的有限元建模与变形分析计算分析模型如图1-1 所示, 习题文件名: plane 0.5 m 0.5 m 0.5 m 0.5 m 板承受均布载荷：1.0e 5 P a 图1－1 受均布载荷作用的平板计算分析模型 1.1 进入ANSYS 程序 →ANSYSED 6.1 →Interactive →change the working directory into yours →input Initial jobname: plane →Run 1.2设置计算类型 ANSYS Main Menu : Preferences →select Structural → OK 1.3选择单元类型 ANSYS Main Menu : Preprocessor →Element T ype →Add/Edit/Delete →Add →select Solid Quad 4node 42 →OK (back to Element T ypes window) → Options… →select K3: Plane stress w/thk →OK →Close (the Element T ype window) 1.4定义材料参数 ANSYS Main Menu : Preprocessor →Material Props →Material Models →Structural →Linear →Elastic →Isotropic →input EX:2.1e11, PRXY :0.3 → OK 1.5定义实常数 ANSYS Main Menu: Preprocessor →Real Constant s… →Add … →select T ype 1→ OK →input THK:1 →OK →Close (the Real Constants Window)

算法设计与分析试卷及答案.doc

湖南科技学院二○ 年学期期末考试信息与计算科学专业年级《算法设计与分析》试题考试类型：开卷试卷类型： 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. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。

对并行算法的介绍和展望——学期大作业

《计算机系统结构》大作业对并行算法的介绍和展望专业计算机科学与技术班级 111 学号 111425020133 姓名完颜杨威日期 2014年4月17日河南科技大学国际教育学院

对并行算法的介绍和展望我们知道，算法是求解问题的方法和步骤。而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法的研究涉及到理论、设计、实现、应用等多个方面，要保持并行算法研究的持续性和完整性，需要建立一套完整的“理论－设计－实现－应用”的学科体系，也就是所谓的并行算法研究的生态环境。其中，并行算法理论是并行算法研究的理论基础，包含并行计算模型和并行计算复杂性等；并行算法的设计与分析是并行算法研究的核心内容；并行算法的实现是并行算法研究的应用基础，包含并行算法实现的硬件平台和软件支撑技术等；并行应用是并行算法研究的发展动力，除了包含传统的科学工程计算应用外，还有新兴的与社会相关的社会服务型计算应用等。并行算法主要分为数值计算问题的并行算法和非数值计算问题的并行算法。而并行算法的研究主要分为并行计算理论、并行算法的设计与分析、和并行算法的实现三个层次。现在，并行算法之所以受到极大的重视，是为了提高计算速度、提高计算精度，以及满足实时计算需要等。然而，相对于串行计算，并行计算又可以划分成时间并行和空间并行。时间并行即流水线技术，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。随着高性价比可扩展集群并行系统的逐步成熟和应用，大规模电力系统潮流并行计算和分布式仿真成为可能。目前，并行算法在地震数据处理中应用已较为成熟，近年来向更实用的基于PC机群的并行技术发展.然而，在非地震方法中，并行算法应用较少见文献报道，研究尚处于初级研究阶段。在大地电磁的二维和三维正、反演问题上，并行计算技术逐渐得到越来越多关注和重视.随着资源和能源需求的增长，地球物理勘探向深度和广度快速发展，大幅增长的数据量使得高性能并行计算机和高效的并行算法在勘探地球物理学中的发展和应用将占据愈来愈重要的地位。计算机技术在生物医学领域已经广泛应用，实践证明，并行算法在生物医学工程的各个领域中具有广泛的应用价值，能有效提高作业效率。随着电子科学技术的发展，电磁问题变得越来越复杂，为了在有限的计算机资源条件下求解大规模复杂电磁问题，许电磁学家已