华南农业大学期末考试试卷（A卷） 2004学年第二学期(2005.6)考试科目：算法设计与分析考试类型：（开卷）考试时间：120分钟 学号姓名年级专业 一、选择题（30分，每题2分） 1、一个算法应该包含如下几条性质，除了 A 。 （A）二义性（B）有限性（C）正确性（D）可终止性 2、解决一个问题通常有多种方法。若说一个算法“有效”是指 D 。 （A）这个算法能在一定的时间和空间资源限制内将问题解决 （B）这个算法能在人的反应时间内将问题解决 （C）这个算法比其他已知算法都更快地将问题解决 （D）A和C 3、当输入规模为n时，算法增长率最小的是 B 。 （A）5n （B）20log2n（C）2n2（D）3nlog3n 4、渐进算法分析是指 B 。 （A）算法在最佳情况、最差情况和平均情况下的代价 （B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间 （D）在最小输入规模下算法的资源代价 5、当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价？C （A）大O表示法（B）大Ω表示法 （C）Θ表示法（D）小o表示法 6、采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序搜索法分析正确的是 B 。
（A）最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同 （B）最佳情况的渐进代价要好于最差情况和平均情况的渐进代价 （C）最佳情况和平均情况的渐进代价要好于最差情况的渐进代价 （D）最佳情况的渐进代价要好于平均情况的渐进代价，而平均情况的渐进代价要好于最差情况的渐进代价 7、递归通常用 C 来实现。 （A）有序的线性表（B）队列（C）栈（D）数组 8、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。C （A）问题规模相同，问题性质相同 （B）问题规模相同，问题性质不同 （C）问题规模不同，问题性质相同 （D）问题规模不同，问题性质不同 9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n 个元素进行划分，如何选择划分基准？下面 D 答案解释最合理。 （A）随机选择一个元素作为划分基准 （B）取子序列的第一个元素作为划分基准 （C）用中位数的中位数方法寻找划分基准 （D）以上皆可行。但不同方法，算法复杂度上界可能不同 10、对于0－1背包问题和背包问题的解法，下面 C 答案解释正确。 （A）0－1背包问题和背包问题都可用贪心算法求解 （B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解 （C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解 （D）因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解 11、关于回溯搜索法的介绍，下面D是不正确描述。 （A）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解（B）回溯法是一种既带系统性又带有跳跃性的搜索算法 （C）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯 （D）回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径 改：树结构 回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结
学习必备欢迎下载 第一课初识算法与程序设计 一、教学目标 1、知识与技能 （1）理解算法的概念，培养学生自我探索信息，高效获取信息的能力； （2）能初步利用算法解决简单的问题，培养学生的理论联系实际能力和动 手操作能力。 2、情感、态度、价值观 学生在学习过程中，通过亲身经历体验获得对此算法的感性认识，培养学 生自我获取信息、分析评价信息、、表达呈现信息的能力，进一步提高其信息素养。 二、教学重点难点 重点：算法概念的理解 难点：如何科学合理的选择和设计算法。 三、教学策略与手段 以趣味性问题设置情境，激发学生探索解决问题的兴趣，与学生进行互动 探讨，通过 Flash 演示材料，比较直观地把抽象的问题简单化，使学生的思考 逐步深入，从而总结出算法的概念，学会如何设计和选择算法，培养学生自主 探究学习的能力。 四、教学过程（ 1 课时） （一）我们来共同寻找下面一些生活中比较现实的问题的解决方法。 【问题一】天下真的有“不要钱的午餐”吗？ 某一餐馆门口海报上写着“不要钱的午餐”，规则如下：在三个月内，来
的顺序都坐一遍，以后来吃饭就可永远免费” 。于是有人想，这太容易了，每人每次坐不同的位置，吃五次不就行了？于是他就叫上自己的朋友参加这项活动，可是，吃了十次之后，还没有吃上免费午餐，这是怎么回事呢？ 学生们感觉非常有意思，很快以小组为单位进行热烈的讨论并得出了破解问题 的步骤：①第一个座位５个人都有坐的机会②第二个座位只有４个人中的任一 个有坐的机会（一个人不能同时坐两个座位）③第三个座位只有３个人中的任 一个有坐的机会④第四个座位只有２个人中的任一个有坐的机会⑤第五个座位 只有１个人有坐的机会⑥计算：５×４×３×２×１＝１２０⑦得出结论：需 要吃１２０次才有可能吃上免费午餐。 【问题二】有三个和尚和三个妖怪过河，只有一条能装下两个人的船，在河的 任何一方或者船上，如果妖怪的人数大于和尚的人数，那么和尚就会有被吃掉 的危险。你能不能找出一种安全的渡河方法呢？请写一写你的渡河方案。学 生：学生讨论回答。 〖展示步骤〗 ①两个妖怪先过河，一个妖怪回来； ②再两个妖怪过河，一个妖怪回来； ③两个和尚过河，一个妖怪和一个和尚回来； ④两个和尚过河，一个妖怪回来； ⑤两个妖怪过河，一个妖怪回来； ⑥两个妖怪过河。 【F lash 动画展示】通过讨论和动画展示，我们可以知道，计算机解决问题和 人解决问题一样需要有清晰的解题步骤。算法就是解决问题的程序或步骤。（二）【课件展示】算法的概念：
Y J K软件的优化设计Prepared on 21 November 2021
一、当前软件(PKPM)主要问题 1、计算模型落后甚至不正确的若干方面 2、采用的算法不完全满足规范要求的若干方面 3、采用的过于简化的计算模型的若干方面 4、设计观念已经落后的若干方面 5、计算模型粗放忽略了结构有利要素的若干方面 6、涉及优化的关键环节缺失的若干方面 7、不开放接口的封闭观念 1、计算模型落后甚至不正确的若干方面 （1）基础筏板、桩筏或桩承台有限元计算常给出配筋异常大的结果（2）楼板按照单房间的导致支座钢筋偏大； （3）基础冲切计算流程错误导致筏板承台厚度过大； （4）承台独基与地基梁的重复计算造成重复布置 2、采用的算法不完全满足规范要求的若干方面 （1）剪力墙边缘构件配筋的单肢配筋方式配筋过大或不够； （2）柱剪跨比按简化计算方法常导致短柱过多超限过多； （3）型钢混凝土柱的配筋按不同规程才可优化 3、采用的过于简化的计算模型的若干方面 （1）对弹性时程分析结果只能作全楼统一的地震作用放大； （2）对活荷载的折减系数、重力荷载代表值系数只能设置全楼统一的数值； （3）施工模拟计算不能胜任目前多种工程需要； （4）转换梁按照梁杆件计算模型导致易发生抗剪抗弯超限； （5）地下室外墙的计算模型不合理导致地下室外墙过大的配 筋设计； （6）基础考虑上部楼层刚度的计算不全面； 4、设计观念已经落后的若干方面 认为梁设计时考虑楼板的壳元计算减少梁的配筋偏于不安全 5、计算模型粗放忽略了结构有利要素的若干方面 （1）地下1层以下地下室的不需按抗震设计； （2）梁配筋计算没有考虑支承梁的柱的宽度影响； （3）应正确区分框架梁与非框架梁； 6、涉及优化的关键环节缺失的若干方面 （1）基础承载力验算；
优化设计方法的发展与应用情况 贾瑞芬张翔 （福建农林大学 机电工程学院， 福建 福州 ３５０００２） 摘 要：本文概要地介绍了优化设计方法在国内近年的应用和发展情况，包括传统优化方法、现代优化方法，以及优化软件的应用和发展情况。 关键词：优化 遗传算法 神经网络 ＭＡＴＬＡＢ 优化方法是２０世纪６０年代随着计算机的应用而迅速发展起来的，较早应用于机械工程等领域的设计。８０年代以来，随着国内有关介绍优化设计方法的专著（如《机械优化设计》［１］）的出版和计算机应用的普及，优化设计方法在国内的工程界得到了迅速的推广。本文按传统优化方法、现代优化方法、优化软件应用等三个方面，概要地介绍优化设计方法近年来在国内工程界的应用和发展情况。 １． 传统优化方法的应用与改进情况 １．１传统优化方法的应用 从近10年发表的工程优化设计的论文可以看出，罚函数法、复合形法、约束变尺度法、随机方向法、简约梯度法、可行方向法等，都有较为广泛的应用。对重庆维普信息数据库中的工程技术类刊物做检索，1993年至2003年，这6种约束优化方法应用的文献检出率的比例，依次约为12：10：3：1.5：1.5。 以机械设计为例，传统优化方法主要应用于机构和机械零部件的优化设计，主要对零件或机构的性能、形状和结构进行优化。在结构方面，如对升降天线杆的结构优化设计[2]，采用内点罚函数法优化，在保证天线杆具有足够的刚度和压弯组合强度的前提下所设计出的结构尺寸比按一般的常规设计方法所计算的尺寸要小，自重更轻。在形状方面，赵新海等［３］对一典型的轴对称Ｈ型锻件的毛坯形状进行了优化设计，取得了明显的效果。在性能方面，《凸轮一连杆组合机构的优化设计》［４］一文以最大压力角为最小做为优化目标、并采用坐标轮换法和黄金分割法等优化方法对书本打包机中的推书机构（凸纶—连杆组合机构）进行优化设计，从而使得机构确保运动的平衡性的前提下具有良好的传力性能，使设计结果更加合理。《弹性连杆机构结构和噪声控制一体化设计》［３７］一文，利用改进的约束变尺度法，求解基于噪声控制的弹性连杆机构结构控制同步优化问题，同步优化后机构的声辐射性能指标具有明显改善。由以上的例子可以看出，因此，传统优化方法仍然具有不可忽视的作用。 将优化技术与可靠性理论相结合，形成了可靠性优化设计法。按照可靠性优化设计法设计的产品，既能定量地回答产品在运行中的可靠性，又能使产品的功能参数获得优化解，两种方法相辅相成，是一种非常具有工程实用价值的设计方法。如采用惩罚函数内点法求解齿轮传动的可靠性优化设计的数学模型[5]，以及运用二阶矩法和约束随机方向法对钢板弹簧进行可靠性优化设计[6]。 １．２传统优化方法的一些改进 目前，随着工程问题的日益扩大，优化要面对的问题的规模和复杂程度在逐渐增大，传统的优化方法解决这些问题时，就显露出了其局限性与缺陷。于是就出现了在分析现有算法的基础上，针对方法的不足或应用问题而作出的改进。 1．2．1对传统优化方法应用于离散变量优化的改进 工程设计问题中，经常遇到设计变量必须符合本行业的设计规范和标谁，只能取为限定的离散值或整数值的情况。若应用连续变量优化方法．得到最优解后再作简单的圆整处理，可能造成设计上的不可行解，或得到一个非最优解。为此适用于变量取离散值的优化方法发展起来。朱浩鹏等[7]提出了改进的动态圆整法、拉格朗日松弛法。 惩罚函数优化方法是一种常用的求解约束非线性问题的方法，但它仅限于求解连续变量的优化问题。
分类号：密级： 专业学位研究生学位论文 论文题目（中文） 进化程序设计模式研究和生命进化现象的程序模拟 论文题目（外文）The study on "Evolutionary Programming Model" and the programming simulation on the phenomenon of the life evolution 研究生姓名范玫 学位类别工程硕士 专业学位领域计算机应用 学位级别硕士 校内导师姓名、职称马义忠教授 校外导师单位、姓名甘肃省冶金设计院郎宪录高工论文工作起止年月2011 年1月至2012年3月 论文提交日期2012年 3月 论文答辩日期2012年 5月 学位授予日期2012年 5月 校址：甘肃省兰州市
原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：日期： 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学。 本学位论文研究内容： □可以公开 □不易公开，已在学位办公室办理保密申请，解密后适用本授权书。 （请在以上选项内选择其中一项打“√”） 论文作者签名：导师签名： 日期：日期：
《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）； 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题； 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率， ρ为电阻率。可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述： ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)
机械优化设计 摘要 机械优化设计是最优化技术在机械设计领域的移植和应用,其基本思想是根据机械设计的理论,方法和标准规范等建立一反映工程设计问题和符合数学规划要求的数学模型,然后采用数学规划方法和计算机计算技术自动找出设计问题的最优方案。作为一门新兴学科，它建立在数学规划理论和计算机程序设计基础上，通过计算机的数值计算,能从众多的设计方案中寻到尽可能完善的或最适宜的设计方案，使期望的经济指标达到最优，它可以成功地解决解析等其它方法难以解决的复杂问题。优化设计为工程设计提供了一种重要的科学设计方法。因而采用这种设计方法能大大提高设计效率和设计质量。本文论述了优化设计方法的发展背景、流程，并对无约束优化及约束优化不同优化设计方法的发展情况、原理、具体方法、特点及应用范围进行了叙述。另外，选择合适的优化设计方法是解决某个具体优化设计问题的前提，而对优化设计方法进行分析、比较和评判是其关键，本文分析了优化方法的选取原则。之后对并对近年来出现的随机方向法、遗传算法、蚁群算法和模拟退火算法等新兴优化方法分别进行了介绍。本文以交通领域中建立最优交通网路为例说明了优化设计方法的应用特点。 关键词：机械优化设计；约束；特点；选取原则
目录 第一章引言 (1) 1.1优化设计的背景 (1) 1.2机械优化设计的特点 (2) 1.3优化设计的模型 (3) 1.4优化设计的流程 (4) 第二章优化设计方法的分类 (6) 2.1无约束优化设计方法 (7) 2.1.1梯度法 (7) 2.1.2牛顿型方法 (7) 2.1.3共轭梯度法 (8) 2.1.4变尺度法 (8) 2.2约束优化设计方法 (9) 2.2.1直接解法 (9) 2.2.2间接解法 (11) 2.3多目标优化方法 (13) 2.3.1主要目标法 (14) 2.3.2加权和法 (14) 第三章各类优化设计方法的特点 (15) 3.1无约束优化设计方法 (15) 3.2约束优化设计方法 (16) 3.3基因遗传算法（Genetic Algorithem,简称GA） (16) 3.4模糊优化设计方案 (17) 第四章优化方法的选择 (18) 4.1优化设计方法的评判指标 (18) 4.2优化方法的选取原则 (19) 第五章机械优化设计发展趋势 (21) 第六章 UG/PRO-E建模 (23) 参考文献 (27)
差分进化算法-入门
基本差分进化算法 1基本差分进化算法的基本思想 DE 算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如： 1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2、在遗传算法中通过两个父代个体的交叉产生两个子个体，而在差分进化算法中通过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。 变异是DE 算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。 差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2 差分进化算法的基本操作 设当前进化代数为t ，群体规模为NP ，空间维数为D ，当前种群为 {}1 2 (),,,t t t NP X t x x x =L ，() 1 2 ,,,T t t t t i i i iD x x x x =L 为种群中的第i 个个体。在进化过程 中，对于每个个体t i x 依次进行下面三种操作。 2.1 变异操作 对于每个个体t i x 按下式产生变异个体12(,,,)t t t t T i i i iD v v v v =L ，则 123() 1,2,,D t t t t ij r j r j r j v x F x x j =+-=L (1) 其中111112(,,,)t t t t T r r r r D x x x x =L ，222212(,,,)t t t t T r r r r D x x x x =L 和333312(,,,)t t t t T r r r r D x x x x =L 是群体中随机选择的三个个体，并且123r r r i ≠≠≠；1t r j x ，2t r j x 和3t r j x 分别为个体1r ，2r 和3r 的第j 维分量；F 为变异因子，一般取值于[0,2]。这样就得到了变异个体t i v 。
算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中
for(i=0;i
算法与程序设计思想 【基本信息】 【课标要求】 （一）利用计算机解决问题的基本过程 （1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。 （2）经历用自然语言、流程图或伪代码等方法描述算法的过程。 （4）了解程序设计语言、编辑程序、编译程序、连接程序以及程序开发环境等基本知识。 【学情分析】 高一年级的学生已具备了一定的观察、思考、分析和解决问题能力，也已有了顺序结构、分支结构、循环结构等知识的储备。因此，对于如何将解决问题的思路画成流程图已有一定的基础，但可能还不很熟练，尤其对刚学过的循环结构，教师在课堂上要注意引导。 『此处说“已有了顺序结构、分支结构、循环结构等知识的储备”，应该是指在必修部分对“计算机解决实际问题的基本过程”已有所体验与了解，或是指已学习过数学中相关模块的知识，这是本案例教学得以实施的必不可少的前提条件。』 【教学目标】 1.知识与技能： 建立求一批数据中最大值的算法设计思想，并将算法的设计思想用流程图表示出来。 2.过程与方法： 利用现实生活中比较身高的活动，以及对武术比赛中“打擂台”流程的逐步梳理，让学生学会从此类生活实际中提炼出求最大值的思想方法，即算法思想。 培养学生分析问题、解决问题的能力，让学生学会在面对问题时能梳理出解决问题的清晰思路，进而设计出解决某个特定问题的有限步骤，从而理解计算机是如何解决、处理某种问题的。 『在过程上，通过现实生活中的实例来引导学生总结“求最大值”的算法思想。过程的实现关键在于实例引用是否贴切，是否有利于学生向抽象结论的构建。本案例的实例选择是符合这一要求的。在方法上，注重培养学生分析、解决问题的一般能力，再次体验与理解应用计算机解决问题的基本过程，为后面更一步的学习打下基础，积累信心。』 3.情感态度与价值观：
HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日
一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。
解析法 一、基本说明 1、教学内容所属模块：信息技术选修1《算法与程序设计》 2、年级：高一年级 3、所用教材出版单位：上海科技教育出版社 4、所属的章节：第三章第一节 5、学时数：45分钟 二、教学设计 1、教学目标： （1）了解解析算法的基本概念。通过实例的学习，掌握用解析算法设计程序的基本思路。 （2）学会根据问题寻找恰当算法和解决问题的方法，并进一步理解分析问题、设计算法、编写程序、调试程序这一用计算机解决问题的过程和方法。 （3）学会合作、交流，培养勇于实践、勤于思考和善于总结的精神和态度。 2、内容分析： 本节内容为用解析法设计程序，解析法是一种最基本的常用算法，在之前三种基本结构程序设计的例题分析中也曾使用过，该算法的分析也为今后的各种算法学习做好了准备。本课教学重点是“理解解析算法的思想，能写出求解问题的解析式并用程序实现”，本课的教学难点是“如何学会分析问题，合理设计算法，建立求解问题的解析式”。 3、学情分析： 学生已经具备了可视化编程的能力及程序设计的基本技能，这样就可以将教学的重点放在算法的分析上，培养学生解决实际问题的能力。 4、设计思路： 本课采用一个测量树高的例子进行引入，用简单的例子分析解析算法，然后采用教材上的活动“求解铁丝问题”让学生掌握解析算法的实现过程，用“求岛屿面积”的实践环节巩固学生的学习。课堂教学中主要采用任务驱动、分析归纳、小组合作、自主探究相结合的学习方法。
题 2’ 从A、B两点仰角的角度与两点之 间的距离可计算出MN的高度。 引出课题：解析法 探究学习 8’[学习任务一] 问题：MN是竖直于地面的物体， 其底部N不可到达。为了测量MN 的高度，在地面上选取一条与MN 在同一平面的水平线线段AB为 基线，测得AB的长为a=20米， 在A点向M点张望的仰角α =38.4°，在B点向M点张望的仰 角β=22.8°。试设计程序计算高 度MN。 要求：完成“学习任务一”（填 写电子文档） 1、问题分析：怎样写出计算表达 式。（请学生回答） 2、设计求解表达式MN=a/(1/tan β- 1/tanα)的算法。 (以下部分小组合作完成) 3、实现应用程序：老师提供程序 的可视化界面及不完整的程序， 要求学生程序填空，完善程序。 4、将程序输入到程序窗体的按钮 中并调试计算本题结果。附带计 算学校中一棵桂花树和一棵龙柏 的高度。 1、由α、β与a 推导出计算表达 式。 2、根据计算表达 式，分析解题算 法。 3、小组合作，填 空完成程序，交流 填空结果。 4、复制程序，调 试并得出运算结 果。 让学生在 老师的带 领下了解 解析法解 题的一般 过程。 学习小结2’老师提问：请同学说说求解任务 一的步骤是怎样的？ 老师用流程图表示这个步 骤，提出解析法的概念。 了解解析算法的 概念。 让学生初 步了解解 析算法的 概念。 [学习任务二]求解“铁丝问题” “智力大比拼”活动： （1）一根长为6米，可制作一个 2平方米的矩形框，问该矩形长 和宽各为多少？ （2）上面同样的问题，制作的面 积为2.1平方米，那么长、宽各 参与“智力大比 拼”活动。 产生计算机程序 解决问题与简单 人脑思维运算的 比较。 让学生参 与“智力大 比拼”活 动，产生冲 突，激发学 生学习的 兴趣。
一、当前软件(PKPM)主要问题 ? 1、计算模型落后甚至不正确的若干方面 ? 2、采用的算法不完全满足规范要求的若干方面 ? 3、采用的过于简化的计算模型的若干方面 ? 4、设计观念已经落后的若干方面 ? 5、计算模型粗放忽略了结构有利要素的若干方面 ? 6、涉及优化的关键环节缺失的若干方面 ? 7、不开放接口的封闭观念 1、计算模型落后甚至不正确的若干方面 ?（1）基础筏板、桩筏或桩承台有限元计算常给出配筋异常大的结果?（2）楼板按照单房间的导致支座钢筋偏大； ?（3）基础冲切计算流程错误导致筏板承台厚度过大； ?（4）承台独基与地基梁的重复计算造成重复布置 2、采用的算法不完全满足规范要求的若干方面 ?（ 1）剪力墙边缘构件配筋的单肢配筋方式配筋过大或不够； ? （ 2）柱剪跨比按简化计算方法常导致短柱过多超限过多； ? （ 3）型钢混凝土柱的配筋按不同规程才可优化 3、采用的过于简化的计算模型的若干方面 ? （ 1）对弹性时程分析结果只能作全楼统一的地震作用放大； ? （ 2）对活荷载的折减系数、重力荷载代表值系数只能设置全楼统一的数值； ? （ 3）施工模拟计算不能胜任目前多种工程需要； ? （ 4）转换梁按照梁杆件计算模型导致易发生抗剪抗弯超限； ? （ 5）地下室外墙的计算模型不合理导致地下室外墙过大的配 筋设计； ? （ 6）基础考虑上部楼层刚度的计算不全面； 4、设计观念已经落后的若干方面 ? 认为梁设计时考虑楼板的壳元计算减少梁的配筋偏于不安全 5、计算模型粗放忽略了结构有利要素的若干方面 ? （ 1）地下1层以下地下室的不需按抗震设计； ? （ 2）梁配筋计算没有考虑支承梁的柱的宽度影响； ? （ 3）应正确区分框架梁与非框架梁； 6、涉及优化的关键环节缺失的若干方面 ? （ 1）基础承载力验算；
《算法设计与分析实用教程》参考解答 1-1 加减得1的数学游戏 西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。 例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。 （1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2）算法描述 // 两数若干次加减结果为1的数学游戏 #include
压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行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、引言 ANSYS程序最常见的优化算法有零阶方法，一阶方法，随机搜索法，等步长搜索法，乘子计算法和最优梯度法。 本篇仅作简单描述，更多的细节参见ANSYS Theory Reference chapter 20。要想深刻的了解这些算法，需要具 有一定数学知识，并有一定的兴趣爱好才能精下心了好好的理解和学习这一部分的理论性内容，但这也是快速提 升自己水平的好途径。 2、优化算法简介 2.1 零介方法 零阶方法之所以称为零阶方法是由于它只用到因变量而不用到它的偏导数。在零阶方法中有两个重要的概念： 1）目标函数和状态变量的逼近方法； 2）由约束的优化问题转换为非约束的优化问题。 逼近方法是指程序用曲线拟合来建立目标函数和设计变量之间的关系。这是通过用几个设计变量序列计算目标函 数然后求得各数据点间最小平方实现的。该结果曲线（或平面）叫做逼近。每次优化循环生成一个新的数据点， 目标函数就完成一次更新。实际上是逼近被求解最小值而并非目标函数。状态变量也是同样处理的。每个状态变 量都生成一个逼近并在每次循环后更新。用户可以控制优化近似的逼近曲线。可以指定线性拟合，平方拟合或平 方差拟合。缺省情况下，用平方差拟合目标函数，用平方拟合状态变量。用下列方法实现该控制功能： Command: OPEQN GUI: Main Menu>Design Opt>Method/Tool 转换为非约束问题的原因是状态变量和设计变量的数值范围约束了设计，优化问题就成为约束的优化问题。 ANSYS程序将其转化为非约束问题，因为后者的最小化方法比前者更有效率。转换的实现方法是通过对目标函数 逼近加罚函数的方法计入所加约束的。 收敛检查：前面的或最佳设计是合理的而且满足下列条件之一时，问题就是收敛的：1）目标函数值由最佳合理设计到当前设计的变化应小于目标函数允差。 2）最后两个设计之间的差值应小于目标函数允差。 3）从当前设计到最佳合理设计所有设计变量的变化值应小于各自的允差。 4）最后两个设计所有设计变量的变化值应小于各自的允差。 但收敛并不代表实际的最小值已经得到了，只说明以上四个准则之一满足了。因此，用户必须确定当前设计优化 的结果是否足够。如果不足的话，就要另外做附加的优化分析。 对于零阶方法，优化处理器开始通过随机搜索建立状态变量和目标函数的逼近。由于是随机搜索，收敛的速度可 能很慢。用户有时可以通过给出多个合理的起始设计来加速收敛。只简单的运行一系列的随机搜索并删除所有不 合理的设计。也可以运行多次单独的循环，并在每次运行前指定新的设计变量序列来生成起
Ex.1(p20)若将y ← uniform(0, 1) 改为y ← x, 则上述的算法估计的值是什么？解：若将y ← uniform(0, 1) 改为y ← x，此时有，则k++，即，此时k++，由于此时x ← uniform(0, 1)，所以k/n=，则此时4k/n=2。所以上述算法估计的值为2。Ex.2(p23) 在机器上用估计π值，给出不同的n值及精度。解：由ppt上p21可知，的大小，其中k为落入圆内的数目，n为总数，且π=，即需要计算4k/n。我们先令x ← un iform(0, 1)，y ← uniform(0, 1)。计算 的值，如果小于等于1，那么此时k++。最后计算4k/n的值即可估计此时的π值。代码的主要部分为： 执行结果为：
结果分析：随着N的取值不断地增加，得到的π值也就越来越精确。 Ex.3(p23) 设a, b, c和d是实数，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一个连续函数，写一概率算法计算积分： 注意，函数的参数是a, b, c, d, n和f, 其中f用函数指针实现，请选一连续函数做实验，并给出实验结果。 解：的值为y=，y=0，x=a，x=b围成的面积。根据之前的例子我们可以知道 = k(b-a)d/n。其中k是落在函数y=，x=a，x=b以及y=0所包围区间内的个数。代码的主要部分为： 运行结果为：
结果分析： 随着N的取值不断地增加，得到的积分值越来越精确。 Ex4(p24). 设ε,δ是(0,1)之间的常数，证明：若I是的正确值，h是由HitorMiss算法返回的值，则当n ≥ I(1-I)/ε2δ时有： Prob[|h-I| < ε] ≥ 1 –δ 上述的意义告诉我们：Prob[|h-I| ≥ ε] ≤δ, 即：当n ≥ I(1-I)/ ε2δ时，算法的计算结果的绝对误差超过ε的概率不超过δ，因此我们根据给定ε和δ可以确定算法迭代的次数 () 解此问题时可用切比雪夫不等式，将I看作是数学期望。 证明：由切比雪夫不等式可知： P( | X - E(X) | < ε ) ≥ 1 - D(X) / ε2 由题目知，E(X)=I。且根据题意，我们可知，在HotorMiss算法中，若随机选取n个点，其中k个点在积分范围内，则。且k的分布为二项分布B(n，I)（在积分范围内或者不在 积分范围内），则。又因为k=x*n，所以D(X)=I(1-I)/n。再将E(X)和D(X)带入切比雪夫不等式中即可得到 Ex5(p36). 用上述算法，估计整数子集1~n的大小，并分析n对估计值的影响。解：由题知，集合的大小，通过计算新生成的集合中元素的个数来估计原集合的大小，代码的主体部分如下：