课程设计报告
课程设计名称: 算法设计与分析
系 : 三系
学生姓名: 吴阳
班级: 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．棋盘覆盖问题
每次都对分割后的四个小方块进行判断, 判断特殊方格是否
在里面。这里的判断的方法是每次先记录下整个大方块的左上角方格的行列坐标, 然后再与特殊方格坐标进行比较, 就能够知道特殊方格是否在该块中。如果特殊方块在里面, 这直接递归下去求即可, 如果不在, 这根据分割的四个方块的不同位置, 把右下角、 左下角、 右上角或者左上角的方格标记为特殊方块, 然后继续递归。在递归函数里, 还要有一个变量s 来记录边的方格数, 每次对方块进行划分时, 边的方格数都会减半, 这个变量是为了方便判断特殊方格的位置。其次还要有一个变nCount 来记录L 型骨牌的数量。
三、 建立数学模型
1．普通背包问题
普通背包问题的数学描述为: 在选择物品i 装入背包时, 能够选择物品i 的一部分, 而不一定要全部装入背包, 1≤i ≤n 。C>0,wi>0,vi>0,1≤i ≤n,要求找出一个n 元0-1向量( x1,x2,x3,·····, xn) ,xi ∈{0,1}, 1≤i ≤n,使得∑=n
i wixi 1≤C,
而且∑=n
xi 1i vi 达到最大。
2．0/1背包问题
0-1背包问题的数学描述为: 不能将物品装入背包多次, 也不能只装入部分的物品i 。 C>0,wi>0,vi>0,1≤i ≤n,要求找出一个n 元0-1向量( x1,x2,x3,·····, xn) ,xi ∈{0,1}, 1≤i ≤n,使得∑=n i wixi 1≤C,而且∑=n
xi 1i vi 达到最大。
3．棋盘覆盖问题
当k>0时, 将2k×2k棋盘分割为4个2^k-1×2^k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中, 其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘, 能够用一个L型骨牌覆盖这3个较小棋盘的会合处, 如 (b)所示, 从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割, 直至棋盘简化为棋盘1×1。
四、算法设计
1．普通背包问题
因为每一个物品都能够分割成单位块, 单位块的利益越大显
然总收益越大, 因此它局部最优满足全局最优, 能够用贪心法解决。
算法设计: 首先计算每种物品单位重量的价值Vi/Wi, 然后按单位重量价值从大到小进行排序, 根据贪心选择策略, 将尽可能多的
单位重量价值最高的物品装入背包。或将这种物品全部装入背包后,
背包内的物品总重量未超过背包容量C, 则选择单位重量价值次高的物品并尽可能多地装入背包, 依此策略一直进行下去, 直到背包装满为止。
2．0/1背包问题
该0-1背包问题采用的是回溯算法, 回溯算法的基本解题步骤是:
( 1) 针对所给问题定义问题的解空间;
( 2) 确定易于搜索的解空间结构;
( 3) 以深度优先方式搜索解空间, 并在搜索过程中用剪枝函数避免无效的搜索。
算法设计:
a.物品有n种, 背包容量为C, 分别用p[i]和w[i]存储第i 种物品的价值和重量, 用
x[i]标记第i种物品是否装入背包, 用bestx[i]存储第i种物品的最优装载方案;
b. 用递归函数Backtrack (i,cp,cw)来实现回溯法搜索子集树( 形式参数i表示递归深
度, n用来控制递归深度, 形式参数cp和cw表示当前总价值和总重量, bestp表示当前
最优总价值) :
①若i >n, 则算法搜索到一个叶结点, 判断当前总价值是否最优:
课程设计报告模板(）
————————————————————————————————作者: ————————————————————————————————日期： ?
课程设计（论文)任务书 软件学院软件+电商专业0９级（2）班 一、课程设计(论文)题目基本模型机设计与实现 二、课程设计（论文）工作自２01１年6月 20 日起至2011年 6月 2４日止。 三、课程设计(论文) 地点：计算机组成原理实验室(５#３0１） 四、课程设计(论文)内容要求： 1.课程设计的目的 通过课程设计的综合训练，在掌握部件单元电路实验的基础上，进一步掌握整机 概念。培养学生实际分析问题、解决问题和动手能力,最终目标是想通过课程设计的形式，帮助学生系统掌握该门课程的主要内容，更好地完成教学任务。 ２.课程设计的任务及要求 １）基本要求? （１）课程设计前必须根据课程设计题目认真查阅资料; (２）实验前准备好实验程序及调试时所需的输入数据； （３)实验独立认真完成; (4)对实验结果认真记录,并进行总结和讨论。 2）课程设计论文编写要求 (1)按照书稿的规格撰写打印课设论文 (2）论文包括目录、绪论、正文、小结、参考文献、附录等 (3）正文中要有问题描述、实验原理、设计思路、实验步骤、调试过程与遇到问题的解决方法、总结和讨论等 （4）课设论文装订按学校的统一要求完成 ３)课设考核 从以下几方面来考查:
（1）出勤情况和课设态度； (2)设计思路； （３）代码实现； （４)动手调试能力； (5)论文的层次性、条理性、格式的规范性。 ４）参考文献 [１］王爱英．计算机组成与结构［M]. 北京：清华大学出版社, 200７. [2] 王爱英. 计算机组成与结构习题详解与实验指导[M]. 北京：清华大学出版社, 2007. 5)课程设计进度安排 内容天数地点 构思及收集资料１图书馆 实验与调试 3 实验室 撰写论文 1 图书馆 6）任务及具体要求 设计实现一个简单的模型机，该模型机包含若干条简单的计算机指令,其中至少包括输入、输出指令，存储器读写指令，寄存器访问指令,运算指令,程序控制指令。学生须根据要求自行设计出这些机器指令对应的微指令代码,并将其存放于控制存储器，并利用机器指令设计一段简单机器指令程序。将实验设备通过串口连接计算机,通过联机软件将机器指令程序和编写的微指令程序存入主存中,并运行此段程序,通过联机软件显示和观察该段程序的运行，验证编写的指令和微指令的执行情况是否符 合设计要求，并对程序运行结果的正、误分析其原因。 学生签名: 亲笔签名 ２０1１年6月20 日 课程设计(论文)评审意见 (1）设计思路:优( ）、良（)、中( )、一般（）、差( ); （2）代码实现：优（）、良（)、中（）、一般（）、差(）;
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 湖南涉外经济学院 课程设计报告 课程名称：网页设计 报告题目：“舌尖上中华人民共和国”网页设计报告 学生姓名： *** 所在学院：信息科学与工程学院 专业班级：电商本**班 学生学号： * * 指引教师： *** 6 月24 日 课程设计任务书 摘要 《舌尖上中华人民共和国》是中华人民共和国央视播出美食类纪录片，重要内容为中华人民共和国各地美食生态。通过中华美食各种侧面，来呈现食物给中华人民共和国人生活带来典礼、伦理等方面文化；见识中华人民共和国特色食材以及构成中华人民共和国美食特有气质一系列元素；理解中华饮食文化精致和源远流长。该片重要主题是“变”，向观众展示老式农耕中华人民共和国，同步也告诉观众诸多中华人民共和国老式正在变化。这不但仅是在拍摄美食，更是在拍摄承载中华人民共和国人精神食物。本网站简介了中华人民共和国各地美食，网页是依照《舌尖上中华人民共和国》这档节目中七个主题来设计。分别为：自然地馈赠、主食故事、转化灵感、时间味道、厨房秘密、五味调和、咱们田野。本站建立使用了Fireworks、Flash和Dreamweaver网页制作工具。采用HTML语言、CSS样式、Javascript脚本语言编写网页，最后使静态页面也有丰富多彩视觉效果；此外又使用了网页特效，赋予了其她页面动态之美，动静结合，主题突出，吸引浏览者目光。 核心词：中华人民共和国；美食；文化 内容涉及：1.为什么要设计该网站？ 2.本网站包括什么内容？采用了什么技术实现 3.建立本网站可以达到什么效果？ 目录 一、作品简介................................................................................ 错误!未定义书签。 二、设计方案................................................................................ 错误!未定义书签。 1. 软硬件环境........................................................................ 错误!未定义书签。 2. 色彩方案............................................................................ 错误!未定义书签。 3. 目录构造图........................................................................ 错误!未定义书签。 三、实现过程................................................................................ 错误!未定义书签。 1. 创立本地站点.................................................................... 错误!未定义书签。 2. 首页.................................................................................... 错误!未定义书签。 3. “自然馈赠”页面............................................................ 错误!未定义书签。 4. “主食故事”页面............................................................ 错误!未定义书签。 5. “**”页面........................................................................... 错误!未定义书签。 6. 申请域名，发布网站........................................................ 错误!未定义书签。 四、结论与心得............................................................................ 错误!未定义书签。 五、参照文献................................................................................ 错误!未定义书签。附录................................................................................................ 错误!未定义书签。 算法设计与分析试卷(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．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否 模拟电子技术课程设计报告设计题目：直流稳压电源设计 专业电子信息科学与技术 班级电信092 学号 200916022230 学生姓名夏惜 指导教师王瑞 设计时间2010-2011学年上学期 教师评分 2010年月日 昆明理工大学津桥学院模拟电子技术课程设计 目录 1.概述 (2) 1.1直流稳压电源设计目的 (2) 1.2课程设计的组成部分 (2) 2.直流稳压电源设计的内容 (4) 2.1变压电路设计 (4) 2.2整流电路设计 (4) 2.3滤波电路设计 (8) 2.4稳压电路设计 (9) 2.5总电路设计 (10) 3.总结 (12) 3.1所遇到的问题，你是怎样解决这些问题的12 3.3体会收获及建议 (12) 3.4参考资料（书、论文、网络资料） (13) 4.教师评语 (13) 5.成绩 (13) 昆明理工大学津桥学院模拟电子技术课程设计 1.概述 电源是各种电子、电器设备工作的动力，是自动化不可或缺的组成部分，直流稳压电源是应用极为广泛的一种电源。直流稳压电源是常用的电子设备，它能保证在电网电压波动或负载发生变化时，输出稳定的电压。一个低纹波、高精度的稳压源在仪器仪表、工业控制及测量领域中有着重要的实际应用价值。 直流稳压电源通常由变压器、整流电路、滤波电路、稳压控制电路所组成，具有体积小，重量轻，性能稳定可等优点，电压从零起连续可调，可串联或关联使用，直流输出纹波小，稳定度高，稳压稳流自动转换、限流式过短路保护和自动恢复功能，是大专院校、工业企业、科研单位及电子维修人员理想的直流稳压电源。适用于电子仪器设备、电器维修、实验室、电解电镀、测试、测量设备、工厂电器设备配套使用。几乎所有的电子设备都需要有稳压的电压供给，才能使其处于良好的工作状态。家用电器中的电视机、音响、电脑尤其是这样。电网电压时高时低，电子设备本身耗供电造成不稳定因家。解决这个不稳定因素的办法是在电子设备的前端进行稳压。 直流稳压电源广泛应用于国防、科研、大专院校、实验室、工矿企业、电解、电镀、充电设备等的直流供电。 1.1直流稳压电源设计目的 （1）、学习直流稳压电源的设计方法； （2）、研究直流稳压电源的设计方案； （3）、掌握直流稳压电源的稳压系数和内阻测试方法。 1.2课程设计的组成部分 1.2.1 设计原理 Guangxi University of Science and Technology 课程设计报告 课程名称：算法与编程综合实习 课题名称： 姓名： 学号： 院系：计算机学院 专业班级：通信121 指导教师： 完成日期：2012年12月15日 目录 第1部分课程设计报告 (3) 第1章课程设计目的 (3) 第2章课程设计内容和要求 (4) 2.1 问题描述 (4) 2.2 设计要求 (4) 第3章课程设计总体方案及分析 (4) 3.1 问题分析 (4) 3.2 概要设计 (7) 3.3 详细设计 (7) 3.4 调试分析 (10) 3.5 测试结果 (10) 3.6 参考文献 (12) 第2部分课程设计总结 (13) 附录(源代码) (14) 第1部分课程设计报告 第1章课程设计目的 仅仅认识到队列是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深入了解队列的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的构造方………………………………………………………………………………………………………………………………………………………………………………………..(省略) 第2章课程设计内容和要求 2.1问题描述： 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。 图A 2.2设计要求： 要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏 幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 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 ）。 《地震勘探课程设计》 报告 院系 班级 学生 学号 指导教师 完成日期2014年3月12日 长江大学工程技术学院 目录 一、课程设计目的 (3) 二、课程设计的容 (3) 三、课程设计原理 (3) 四、工区数据 (4) 五、课程设计步骤 (5) 1、建立工区 (5) 2、资料加载 (8) 3、层位标定和层位追踪 (10) 4、断层解释 (13) 5、构造图绘制 (14) 六、心得体会 (15) 一、课程设计目的 地震勘探解释课程设计是我们勘查技术与工程专业和资源勘查工程专业教学中的一个重要的实践性训练环节，通过上机实际操作，训练我们对地震资料进行常规构造解释的实际能力，最终使我们达到：学会利用地震解释软件来进行地震数据的加载，地震层位的标定，地震层位的追踪对比，在地震资料上分析和解释各种断层，以及地震构造图的编制方法。同时，还要学会综合地震地质资料对构造解释结果进行分析，进而对含油气有利地带进行评价和预测，最终编制成果报告。 二、课程设计的容 本次课程设计是理论联系实际的具体表现，是培养学生分析问题、解决问题能力的一个必不可少的环节，主要分为两部分：一、通过对地震资料解释软件Discovery的使用，追踪解释层位数据；二、通过surfer软件学习成图。使学生对地震常用的解释软件有一个初步的认识，能为毕业后从事地震勘探工作奠定良好的基础。地震解释课程设计是勘查技术与工程专业教学中的一个重要的实践性训练环节。通过实验主要训练学生对地震资料进行常规构造解释的实际能力，具体要使学生达到： 1．了解人机联作的基本知识； 2．初步学会地震解释软件的操作流程（工区建立、资料加载、合成记录制作、层位标定、层位追踪、断层解释、断点组合）； 3. 进一步巩固和掌握地震资料解释的基本功； 4．初步学会地震成果的地质分析； 5．初步学会编写地震资料解释文字报告； 1.正文 (1)引言 ①.程序设计的背景 21世纪的重要特征是数字化、网络化和信息化。自从上个世界90年代以后，以因特网为代表的计算机网络得到了飞速的发展，已从最初的教育科研网络发展成为商业网络，并已成为仅次于全球网的世界第二大网络。很多人认为现在已经是互联网的时代，这是因为互联网正在并继续改变着我们的工作和生活的各个方面，加速了全球信息革命的进程。现在人们的生活、工作、学习和交往都已经离不开因特网，互联网成为全球通信与贸易的重要工具。网上购物系统正在成为人们日益信赖的购物平台，其以优越的方便快捷性、实用性、可获得性等特性获得越来越多人的青睐，网上购物逐渐成为很多人购物的主要途径。另外，随着计算机身份认证技术、数字签名、数据库安全、数字水印、信息隐藏、入侵检测、防火墙等网络安全技术的发展使得网上购物的环境越来越安全，大型的合理构建，政府机构完备的法律制度都极大的保证了网上购物的安全性，提高了顾客的信任度，使得网络购物更加普及。作为当代的大学生，网络更是贯穿于我们的生活，加上年轻人乐于尝试新生事物的心理趋向也让我们对于网上购物有了更多了解并参与其中。基于对网络购物环境的理解，结合自己的网络购物的体会，本小组成员进行了此次课程设计，基本上实现了简单的基于Java平台的JSP电子商务设计（电脑购物B2C模式的电子商务）。 ②.程序设计的需求分析 本电子商务总体基于Java，利用服务器端动态网页开发的JSP技术，辅以客户端动态网页开发的Javascript技术，主要设计实现以下功能： 1.前台销售，包括以下容： 1)用户注册: 显示注册界面，通过Javascript技术判断用户填写的注册信息是否规，用户名是否已经存在、填写的密码是否一致、Email是否为正确格式等等。用户确认所填注册信息并通过验证后，将注册信息添加到数据库中的userInfo表中。 2)用户登录 用户输入用户名和密码后，检验所输入的用户名和密码是否与数据库中的用户名和密码一 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行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比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图： 课程设计报告模版 《城市排水处理》 课程设计报告 系别：城市建设系 专业班级：给水排水0601班 学生姓名： 指导教师：段泽琪 （课程设计时间： 6月15日—— 6月19日） 华中科技大学武昌分校 目录 1．课程设计目的 (1) 2．课程设计题目描述和要求 (1) 3．课程设计报告内容 (3) 3.1污水处理工艺方案比较 (3) 3.2主要污水处理构筑物选型 (6) 3.3污水处理构筑物的主要设计参数 (7) 3.4污水处理辅助构筑物设计 (8) 3.5污水处理厂平面布置设计 (8) 3.6 污水处理厂高程布置设计 (9) 3.7 设计计算……………………………………………………………………… 10 4．总结……………………………………………………………………………页码 参考文献…………………………………………………………………………页码 （要求：目录题头用三号黑体字居中书写，隔行书写目录内容。目录中各级题序及标题用小四号黑体） 1. 课程设计目的 (1) 经过污水处理厂课程设计，巩固学习成果，加深对《水污染控制》课程内容的学习与理解，使学生学习使用规范、手册与文献资料，进一步掌握设计原则、方法等步骤，达到巩固、消化课程的主要内容； (2) 锻炼独立工作能力，对污水处理厂的主体构筑物、辅助设施、计量设备及污水厂总体规划、管道系统做到一般的技术设计深度，培养和提高计算能力、设计和绘图水平； (3) 在教师指导下，基本能独立完成一个中、小型污水处理厂工艺设计，锻炼和提高学生分析及解决工程问题的能力。 2．课程设计题目描述和要求 2.1 设计题目描述 (1) 设计题目 某城市污水处理厂工艺初步设计。 (2) 设计内容 根据任务书所给定的资料，综合运用所学的基础、专业基础和专业知识，设计一个中小型污水处理厂。 ①确定污水处理方法和工艺流程； ②选择各种处理构筑物形式，并进行工艺设计计算（计算书中要附计算草图）； ③估算各辅助构筑物的平面尺寸； ④进行污水厂平面布置和高程布置。 课程设计和调试过程规范化要求 1)需求分析 分析系统功能需求以及用户操作流程。 2)概要设计 在需求分析的基础上，确定系统总体框架(系统功能结构图)。 3)详细设计 定义数据存储结构，并设计实现系统功能的具体算法，画出各算法的工作流程图。 4)代码设计 根据所设计的算法，定义相应函数分别实现系统的各子功能模块，同时由主程序提供友好的用户界面，使用户可通过选择主菜单来调用课程设计中要求完成的各个功能模块，子程序执行完后还可以返回到主菜单，继续选择其他功能执行。源程序要求书写规范，结构清晰。重点函数的重点变量，重点功能部分均要求给出清晰的程序注释。 5)程序调试 程序编译、链接成功后，自己设计实现程序功能的一组或多组测试数据，并严格按照此测试数据进行测试，然后分析测试结果。如果程序不能正常运行或结果不正确，则需对程序进行单步调试，在调试过程中认真查找算法实现中存在的问题，并加以分析和改正。 如果程序能够基本正确地运行，可考虑增加若干基本的容错功能（如避免用户操作错误时程序出现死循环等）；另外尽量对现有算法给出改进方案，并比较不同算法之间的优缺点。 课程设计报告及书写内容要求 课程设计任务完成后，每位同学必须独立书写一份课程设计报告。课程设计报告的内容 应包括以下部分： 1)需求分析。包括设计题目、设计要求以及系统功能需求分析； 2)概要设计。包括系统总体设计框架和系统功能模块图； 3)详细设计。包括主要功能模块的算法设计思路以及对应的工作流程图； 4)主要源程序代码。包括存储结构设计说明，以及完整源程序清单； 5)调试分析过程描述。包括测试数据、测试输出结果，以及对程序调试过程中存在问题的 思考（列出主要问题的出错现象、出错原因、解决方法及效果等）； 6)测试结果。列出所有功能的运行界面，并作文字说明。 7)总结。包括课程设计过程中的学习体会与收获、对C语言和本次课程设计的认识以及 自己的建议等内容。 8）源代码。完整的c语言代码。 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、贪心算法的思想： 单片机系统课程设计报告 专业：自动化 学生姓名： 学号： 指导教师： 完成日期：2011 年 3 月17 日 目录 1 设计任务和性能指标 (3) 1.1设计任务............................................................................ 错误！未定义书签。 2 设计方案 (4) 2.1任务分析 (4) 2.2方案设计 (4) 3 系统硬件设计 (5) 3.1时钟的电路设计 (5) 3.2复位电路设计 (5) 3.3灯控电路设计 (5) 3.4倒计时电路设计 (6) 3.5按键控制电路设计 (7) 4 系统软件设计 (8) 4.11秒定时 (8) 4.2定时程序流程 (8) 4.3交通灯的设计流程图 (9) 4.4定时器0与中断响应 (10) 5 仿真及性能分析 (10) 5.1仿真结果图 (11) 5.2仿真结果与分析 (12) 6 心得体会 (13) 参考文献 (14) 附录1 系统原理图 (15) 附录2 系统PCB图 .................................................................. 错误！未定义书签。附录3 程序清单 (17) 1.1设计任务 利用单片机完成交通信号灯控制器的设计，该交通信号灯控制器由一条主干道和一条支干道汇合成十字路口，在每个入口处设置红、绿、黄三色信号灯，红灯亮禁止通行，绿灯亮允许通行，黄灯亮则给行驶中的车辆有时间停在禁行线外。用红、绿、黄发光二极管作信号灯。如图5.1所示。设东西向为主干道，南北为支干道。 图5.1 交通灯示意图 1. 基本要求 （1） 主干道处于常允许通行的状态，支干道有车来时才允许通行。主干 道亮绿灯时，支干道亮红灯；支干道亮绿灯时，主干道亮红灯。 （2） 主、支干道均有车时，两者交替允许通行，主干道每次放行30秒， 支干道每次放行20秒，设立30秒、20秒计时、显示电路。 （3） 在每次由绿灯亮到红灯亮的转换过程中，要亮5秒黄灯作为过渡。 黄灯亮时，原红灯按1Hz 的频率闪烁。 （4） 要求主支干道通行时间及黄灯亮的时间均可在0～99秒内任意设置。 2. 选做 （1） 可设置紧急按钮，在出现紧急情况时可由交警手动实现全路口车辆 禁行而行人通行状态，即主干道和支干道均为红灯亮。 （2） 实现绿波带。所谓‘绿波带’，是指在一定路段，只要按照规定时速， 就能一路绿灯畅行无阻。“绿波带”将根据道路车辆行驶的速度和路口间的距离，自动设置信号灯的点亮时间差，以保证车辆从遇到第一个绿灯开始，只要按照规定速度行驶，之后遇到的信号灯将全是绿灯。 南 北 东 西 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： 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. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。网课程设计报告例子样本
算法设计与分析试卷(2010)
算法设计与分析课程设计报告样本
课程设计报告【模板】
数据结构课程设计报告范例
计算机算法设计与分析期末考试复习题
课程设计报告(模板)
51CTO下载-电子商务网站课程设计报告范例
算法设计与分析课程设计报告
课程设计报告模版
C语言课程设计报告示例
算法设计与分析期末试题答案解析
算法设计与分析课程报告
单片机课程设计报告模板
算法设计与分析试卷及答案.doc
相关主题
文本预览