算法设计与分析课程设计
实验指导书
一、运动员比赛日程表
设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表：
●每个选手必须与其它n-1个选手各赛一次
●每个选手一天只能赛一次
●循环赛一共进行n-1天
1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机
通过。
输入：运动员人数n（假定n恰好为2的i次方）
输出：比赛日程表A[1..n,1..n]
1. for i←1 to n //设置运动员编号
2. A[i,1]←i
3. end for
4. Calendar(0,n) //位移为0，运动员人数为n。
过程Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。
1. if k=2 then //运动员人数为2个
2. A[v+2,2]←A[v+1,1] //处理右下角
3. A[v+1,2]←A[v+2,1]//处理右上角
4. else
5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表
6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表
7. comment：将2个k/2人组的解，组合成1个k人组的解。
8. for i←1 to k/2
9. for j←1 to k/2
10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角
11. end for
12. end for
13. for i←k/2+1 to k
14. for j←1 to k/2
15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角
16. end for
17. end for
18. end if
2、编制该问题的非递归算法，上机通过。
将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。
二、最长公共子序列
运用动态规划法最长公共子序列问题，给出最优值并输出最优解。
提示：最长公共子序列的结构
最长公共子序列的结构有如下表示：
设序列X=
若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
其中Xm-1= zk-1>。 子问题的递归结构 由最长公共子序列问题的最优子结构性质可知，要找出X= 由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。 用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi= 计算最优值 直接利用上节节末的递归式，我们将很容易就能写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X= 【实验要求】 将如上文件保存在命名为“学号+姓名+实验二”的文件夹中并上传到指定的服务器。 三、桥本分数式 把1，2，…，9这9个数字填入下式的9个方格中，要求： 1、各数字不得重复 2、数字“0”不得填在各分数的分子或分母的首位。 3、式中各分数为最简真分数，即分子分母没有大于1的公因数 这一分数等式填数共有多少种解答，试用回溯法求出所有解答。 提示： ?设置a数组，式中每一□位置用一个数组元素表示： ?为避免解重复，设a(1) ?m1=a(2)a(3)=a(2)*10+a(3) ?m2=a(5)a(6)=a(5)*10+a(6) ?m3=a(8)a(9)=a(8)*10+a(9) ?所求分数等式等价于整数等式 a(1)*m2*m3+a(4)*m1*m3=a(7)*m1*?m2成立。 ?设置中间变量g：先赋值g=1；若出现某两数字相同(即a(i)=a(k))或 a(1)>a(4)，则赋值g=0(重复标记)。 ?首先从a(1)=1开始，逐步给a(i)(1≤i≤9)赋值，每一个a(i)赋值从1开 始递增至9。直至a(9)赋值，判断： ?若i=9,g=1,a(1)*m2*m3+a(4)*m1*m3=a(7)*m1*m2?同时满足，为一组 解，用n统计解的个数后，格式输出这组解。 ?若i<9且g=1，表明还不到9个数字，则下一个a(i)从1开始赋值继续。若a(9)=9，则返回前一个数组元素a(8)增1赋值(此时，a(9)又从1开始)再试。若a(8)=9，则返回前一个数组元素a(7)增1赋值再试。依此类推，直到a(1)=9时，已无法返回，意味着已全部试毕，求解结束。 【实验要求】 将如上文件保存在命名为“学号+姓名+实验三”的文件夹中并上传到指定的服务器。 四、删数字问题 在给定的n个数字的数字串中，删除其中k(k 例如在整数762191754639820463中删除6个数字后，所得最大整数为多大？ 提示： ?操作对象是一个可以超过有效数字位数的n位高精度数，存储在数组a 中。 ?在整数的位数固定的前提下，让高位的数字尽量大，整数的值就大。这 就是所要选取的贪心策略。 ?每次删除一个数字，选择一个使剩下的数最大的数字作为删除对象。选 择这样“贪心”操作，是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。 ?当k=1时，在n位整数中删除哪一个数字能达到最大？从左到右每相邻 的两个数字比较：若出现增，即左边数字小于右边数字，则删除左边的小数字。若不出现增，即所有数字全部降序或相等，则删除最右边的小数字。 ?例如，在18位整数762191754639820463中，删除1个数字，使剩下的 17位数最大，如何删？ ?要使删除1个数字后的17位数最大，须首位数字最大。首先，首位数 字“7”大于第2位数字“6”比较，首位数字“7”不能删！ ?往后推，“6”与“2”比较，因6>2，为减，“6”不能删； ?再往后推，“2”与“1”比较，因2>1,为减，“2”不能删； ?继续往后推，“1”与“9”比较，因1<9，出现增，则删除左边的小数字 “1”。 ?当k>1（当然小于n），按上述操作,每一次操作从串首开始，每相邻的两 个数字比较，出现“增”时，删除左边的小数字。每次操作删除一个数字后，后面的数字向前移位。 ?因此，只要从左至右每两相邻数字比较，出现“增”，即删除首数字。 直到不出现“增”时，此时如果还不到删除指定的k位，打印剩下串的左边n?k个数字即可（相当于删除了余下的最右边若干个小数字）。 将如上文件保存在命名为“学号+姓名+实验四”的文件夹中并上传到指定的服务器。 五***马步遍历问题 在给定棋盘中，马从棋盘的某个起点出发，按“马走日”的行走规则经过棋盘中的每一个方格恰好一次。该问题称为马步遍历问题，经过棋盘的每一个方格恰好一次的线路称为马步遍历路径。 例如下表所示即为4行5列棋盘中，马从起点(1,1)出发的一条马步遍历路径。 求解在n行×m列广义棋盘中，马从棋盘的某个指定起点出发的马步遍历路径。 1. 回溯设计 （1）位置表示 ?设置数组x(i),y(i)记录遍历中第i步的行列位置，设置二维数组d(u,v)记录 棋盘中位置(u,v)即第u行第v列所在格的整数值，该整数值即为遍历路径上的步数。 ?例如上表所示遍历，第8步走在(3,2），x(8)=3,y(3)=2；d(3,2)=8。 ?若d(i,j)=0，表示(i,j)为空，可走位。 ?注意到马走“日”形，对于有些马位，马最多可走8个方向。如图3所 示，当马处在(x,y)时可选的8个方向： （2）．控制马步规则 ?设置控制马步规则的数组a(k)、b(k)，若马当前位置为（x,y），马步可跳 的8个位置分别为（x+a(k),y+b(k)）,其中 ?a(k)={ 2, 1,-1,-2,-2,-1, 1, 2 } ?b(k)={ 1, 2, 2, 1,-1,-2,-2,-1 }（k=1,2, (8) 在回溯过程中，需知第i步到第i+1步原已选取到了哪一个方向，设置t(i)记录第i步到第i+1步原已选取的方向数，回溯时只要从t(i)+1——8选取方向即可。（3）回溯实施 ?设遍历起点为(u,v)，即位置(u,v)点为1。显然 x(1)=u,v(1)=v,d(u,v)=1。 ?回溯从i=1开始进入条件循环，条件循环的条件为i>0。即当i>0时还未 回溯完成，继续试探走马。 ?设置k（t(i)+1——8）循环依次选取方向，当t(i)=0时，即从1——8选 取方向，并求出此方向的走马位置：u=x(i)+a(k), v=y(i)+b(k)。 ?判断：若1≤u≤n, 1≤v≤m, d(u,v)=0，即所选位置在棋盘中且该位为空， 可走马步d(u,v)=i+1；同时记录此时的方向t(i)=k，q=1标志此步走马成功，退出选方向循环。 ?走马成功后，检测若i=m*n-1，标志已完成遍历，以二维形式输出此遍 历解。 （4）继续求出所有解 ?若需继续求解，方向t(i)与最后两步马位清“0”后，经i=i-1回溯继续， 可求出所有遍历解。 ?走马成功后，检测若i 索。 ?若保持q=0，即i 时的8 个方向均不能走马，在此卡住，不能再向前了， 于是方向t(i)与此马位清“0”后，经i=i-1回溯到前一步，继续探索。 ?当回溯到i=0时，所有结点搜索完成，结束。输出共有遍历解的个数。**你还能用递归和贪心法求解吗? 附录实验报告封面 算法设计与分析课程设计 实习报告 学院：计算机与信息 专业： 班级： 学号： 姓名： 【实验报告】 实验报告X 一、上机实验的问题和要求： 见指导书 二、源程序及注释： 三、运行输出结果： 四、调试和运行程序过程中产生的问题及采取的措施： 《工艺综合课程设计》简明指导书 1.设计目的 《机械制造工艺与机床夹具》是一门实践性很强的课程，只有通过实践性教学环节才能使学生对该课程的基础理论有更深刻的理解，也只有通过实践才能培养学生理论联系实际的能力和独立工作能力。该设计的目的就在于： （1）在结束了《机械制造工艺与机床夹具》及有关课程的学习后，通过本次设计使学生所学到的知识得到巩固和加深，并培养学生学会全面综合地应用所学知识，去分析和解决机械制造中的问题的能力。 （2）通过设计提高学生的自学能力，使学生熟悉机械制造中的有关手册、图表和技术资料，并学会结合生产实际正确使用这些资料。 （3）通过设计使学生树立正确的设计思想，懂得合理的设计应该是技术上先进的，经济上合理的并且在生产实践中是可行的。 （4）通过编写设计说明书，提高学生对技术文件的整理、写作及组织编排能力，为学生将来撰写技术及科研论文打下基础。 2．设计内容 （1）编制规定零件的机械制造工艺规程一份； （2）填写规定零件的《机械加工工艺过程卡》一份； （3）填写规定零件某机械加工工序的《机械加工工序卡片》一份； （4）设计规定零件的某机械加工工序的专用夹具一套并绘制其总装图一张； （5）编写设计说明书一份。 3．设计步骤及要求 （1）根据给定的生产纲领，确定生产类型。 （2）分析和审查零件图：读懂零件图；审查该零件的结构工艺性；了解其主要技术要求；区分哪些表面是加工表面，哪些表面是不加工表面；查清各表面的尺寸公差、形位公差、表面粗糙度和特殊要求，区分各表面的精密与粗糙、主要与次要、重要与不重要等相对地位。在此基础上初步确定各加工表面的加工方法。 （3）根据给定的零件材料，确定毛坯种类。并确定加工表面的总加工余量。 （4）拟定零件的机械加工工艺规程：选择粗基准和精基准；确定各表面的加工方法；确定加工顺序；安排热处理工序及必要的辅助工序。 （5）确定各工序的加工设备，刀具及夹具。 （6）对工艺规程中的某道工序使用的夹具进行设计：一般画一张A1图，要求手工绘图。 a. 以有利于反映该工序加工的位置，选取投影视图。用双点划线画出零件轮廓。 b. 在零件定位表面处，画出定位元件或机构。 c. 在夹紧位置处画夹紧机构。 d. 在对刀位置画出对刀元件或刀具导引装置。 e. 画出与机床连接的元件及其它元件。 f. 绘图时要遵守国家标准的规定画法，能用标准件的尽量采用标准件。 g. 为表达清楚夹具结构，应有足够的视图、剖面图、局部视图等。 h. 夹具图上应标注夹具的总体轮廓尺寸，对刀尺寸，配合尺寸及配合公差要求，并标明夹具制造，验收和使用的技术要求。 i. 在夹具图右下角绘制国家标准规定的标题栏和明细表，表中详细列出零件的名称，代号，数量，材料，热处理及其它要求。 （7）确定所设计夹具的工序的工序余量，计算工序尺寸及公差。 （8）确定所设计工序的切削用量及工时定额。 （9）填写工艺文件——工艺过程卡和工序卡各一份。 实验三分治算法（2） 一、实验目的与要求 1、熟悉合并排序算法（掌握分治算法） 二、实验题 1、问题陈述: 对所给元素存储于数组中和存储于链表中两中情况，写出自然合并排序算法. 2、解题思路: 将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序. 三、实验步骤 程序代码: #include int target[N],head[N],tail[N]; int i=0,n,m; for(; i 算法设计与分析实验报告 贪心算法 班级：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 无机非金属材料专业 《无机材料工艺课程设计》 指导书 无机非金属材料研究所编 2010年5月 目录 课程设计要求与说明 (1) 第一章窑炉制图规格 (2) 第二章窑体图 (9) 第三章尺寸标注 (13) 第四章窑炉课程设计说明书撰写规范 (19) 第五章设计说明书的编写 (22) 图1 隧道窑窑体主图 (26) 图2 隧道窑预热带典型断面图 (30) 图3 辊道窑窑体主图 (31) 图4 辊道窑窑体断面图 (33) 课程设计要求与说明 一、课程设计目的 课程设计是课堂教学的实践延伸，目的是对学生学习《陶瓷工艺学》课程的最后总结，是教学重要的一环。要求学生通过课程设计能综合运用和巩固所学的理论知识，并学会如何将理论与实践结合，研究解决实际中的工程技术问题。 主要任务是培养学生设计与绘图的基本技能，掌握窑炉设备的设计程序、过程与内容。学生根据老师给定的设计任务，在规定的时间里，应围绕自己的题目内容，结合所学知识，认真查阅资料，体验工程设计的过程，同时锻炼学生分析和解决实际问题的能力。 二、课程设计要求 通过本课程设计，要求学生进一步了解窑炉设备的基本结构；掌握窑炉设备的工作原理、工程制图方法和编制设计说明书的方法，同时要求学生融会贯通所学的理论知识，与实践结合，理解窑炉设备的设计思想和设计方法。学生对课程设计题目应视作真正的任务，要求学生认真负责地进行设计，每一个计算数据和结构设计应尽可能与生产实际相结合，课程设计应作为学生的创造性成果，不能抄袭历届学生的设计，也不允许简单照搬现成的资料，要求学生能表达自己的设计思想。 三、课程设计题目、内容 1、设计题目：隧道窑设计 辊道窑设计 2、设计内容 （1）图纸：主体结构图及主要断面图。要求尺寸标注齐全，线条、文字、图例规范； （2）说明书：确定主要尺寸和工作系统，进行燃烧计算和热平衡计算，要求计算正确，编写完整，格式规范。 课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 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．通过实际产品的焊接工艺设计，使学生了解焊接结构的生产工艺过程； 2．掌握焊接工艺的设计方法及工艺文件的制定； 3．培养学生运用专业理论知识解决实际焊接生产问题的能力，锻炼查阅文献资料及工具书籍的基本技能。 二、设计内容 在规定时间内，完成由教师指定的某一个结构件的焊接工艺设计任务，主要内容包括： 1. 焊接结构件的设计简图与技术要求； 2. 产品的制造工艺性能分析； 3. 主要接头的焊接方法选择与说明，坡口型式及尺寸的设计与说明； 4. 主要部件（筒节、封头等）的加工工艺过程卡； 5. 产品的装焊工艺过程卡； 6. 壳体的焊接工艺卡。 三、设计要求 1．手绘产品的结构设计简图，标注出产品的主要结构尺寸；主要零件的名称、材质与规格；设计技术要求（包括制造技术要求与检验要求）等。 2．产品的制造工艺性能分析主要包括容器主体材料的焊接性分析与结构的装焊工艺性能分析。容器主体材料的焊接性能主要分析材质的焊接裂纹倾向及产生其它焊接缺陷的倾向，说明为保证焊接质量应采取的工艺措施，如合理选用焊接方法、焊接材料、焊前预热、焊后热处理、层间温度等；结构的装焊工艺性能分析主要针对特殊、复杂容器结构，分析需要采用的装焊顺序与方法。 2. 接头焊接方法的选择和坡口型式的设计应包括纵焊缝、环焊缝、封头拼缝、 人孔接管与筒体的焊缝等，绘制接头的局部放大图。选择与设计的依据主要从容器结构尺寸、接头位置、材质及厚度、施焊条件与可操作性、焊接变形与应力、装焊顺序等方面考虑。 3. 主要部件（筒节、封头等）的加工过程卡要求制定部件从原材料备料至组 装焊接之前的全部加工工艺过程，包括各加工工序的名称、加工内容、所用的工装设备与检验要求等，必要时绘制出加工工艺简图； 4. 壳体的装焊工艺设计包括装焊工艺顺序、工序名称与内容、各工序所涉及 学号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。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 冲压工艺及模具设计》课程设计指导书 2.1 课程设计目的 本课程设计是在学生学完“冲压工艺与冷冲模具设计”理论课并进行了上机练习之后 进行的一个重要教学环节。是学生运用所学理论，联系实际，提高工程技术能力和培养严 谨细致作风的一次重要机会。通过本次设计要达到以下目的： 1、巩固与扩充“冲压工艺与冷冲模具设计”以及有关技术基础课程所学的内容，掌握 制订冲压工艺规程和设计冲压模具的方法。 2、培养综合运用本专业所学课程的知识， 解决生产中实际问题的工程技术能力 设计、计 算、绘图、技术分析与决策、文献检索以及撰写技术论文的能力)。 3、养成严肃、认真、细致地从事技术工作的优良作风。 2.2 课程设计步骤 1. 设计准备 1) 阅读产品零件图 (1) 设计前应预先准备好设计资料、手册、图册、绘图用具、图纸、说明书用纸。 (2) 认真研究任务书及指导书，分析设计题目的原始图样、零件的工作条件，明确设 计要求 及内容。 (3) 熟悉各种可采用的模具结构形式及其优缺点。 2) 冲件图样分析 产品零件图是分析编制冲压方案、设计模具的重要依据，对零件图的分析 主要是从冲 压工艺的角度出发，对冲压件的形状、尺寸 ( 最小孔边距、孔径、材料厚度、最大 外形 精度、表面粗糙度、材料性能等逐项分析，确定冲压工序图。若有与冲压工艺要求相悖者， 应采 取相应的解决措施或与指导教师协商更改。 (1) 工艺分析。 合理的冲压工艺，既能保证冲件的质量，使冲压工艺顺利进行，提高模具寿命，降低 成本，提高经济效益，同时给模具的设计、制造与修理带来方便。所以必须对指定的冲压 件图样进行充分的工艺分析，在此基础上，拟订各种可能的不同工艺方案。 工艺分析主要是分析冲件的形状、尺寸及使用要求，分析冲件的工艺性；根据成形规 律，确定所用冲压工艺方法；根据生产批量、冲压设备、模具加工的工艺条件等多方面因 素，进行全面的分析、研究，确定冲件的工艺性质、工序数量、工序的组合和先后顺序。 在几种可能的冲压工艺方案中，选择一种经济、合理的工艺方案，并填写冲压工艺卡。 (2) 制订冲压工艺。 制订冲压工艺方案时，应做如下工作： ① 备料。确定板料、条料的规格、要求，并计算出材料利用率。 ② 确定工序性质、数目、先后顺序、工序的组合形式。 包括： )、 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行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.了解焊接工程技术人员的主要任务,工作内容和方式方法. 二、设计内容与计划 （一）设计内容 1. 5～50T通用桥式起重机主梁箱型结构设计。 2. 5～50T通用桥式起重机主梁生产工艺指定。 3．5～50T通用桥式起重机主梁结构生产图纸绘制。 （二）设计计划 1．接受设计任务、查阅资料和制定设计方案。（2天） 2．主梁结构设计计算；（7天） 3．主梁结构生产图纸绘制；（1天） 4．主梁结构生产工艺分析；（2天） 5．主梁生产工艺规程制定。（2天） 6．总结和考核。（1天） （三）任务完成 课程设计完成后，学生应交付以下材料： 1 主梁结构设计计算说明书； 2 主梁结构生产工艺分析报告； 3 主梁结构生产用施工图纸; 4 主梁生产工艺规程. 通用桥式起重机主梁结构及生产工艺设计 §1 通用桥式起重机简介 通用桥式起重机是指用吊钩或抓斗（有的也有用电磁盘）吊取货物的一般用途的桥式起重机，它桥架（大车）和起重小车两大部分组成，桥架横跨于厂房或露天货物上空，沿吊车梁上的起重机轨道纵向运行。通用桥式起重机有大车运行机构（装在桥架上），起升机构和小车运行机构（装在小车上）等三种工作性机构，皆为电动。通用桥式起重机的起重量可达500吨，跨度50～60米。 1.1 通用桥式起重机的基本组成 1.2 通用桥式起重机的基本参数 1额定起重量Q（tf） 2 跨度L（m） 3大车运行速度（m/min） 4 小车运行速度（m/min） 5 起升高度（m） 6 起升速度（m/min） 7 接电持续率JC JC = 100t i /T % t i —在起重机的一个工作循环中该机的总运转时间。 T --起重机一个工作循环所需的时间。 T = 360/N h （s） 通用桥式起重机 大车 小车桥架 大车运行机构 主梁 端梁小车架 小车运行机构 起升机构 图 1 通用桥式起重机组成 算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序代码如下： #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入： 一个算法有 0 个或多个输入， 法 本身定除了初始条件; ④ 输出： 一个算法有一个或多个输出， 是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章 算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响） 般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 以刻画运算对象的初始情况， 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法 位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解） 分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想： 焊接结构课程设计指导书 机电工程系 洛阳理工学院 目录 前言 (2) 一．课程设计的性质和目的 (3) 二．课程设计的基本任务 (3) 三．课程设计的基本要求 (3) 四．课程设计的基本步骤 (4) 五．课程设计说明书要求 (4) 六．课程设计内容简介 (4) 七．附录 (6) 前言 课程设计是焊接结构生产课程教学的最后一个环节，是对学生进行全面系统的训练。课程设计可以让学生将学过的零碎知识系统化，真正地把学过的知识落到实处，进一步激发学生学习的热情，因此课程设计是必不少的，是非常必要的。 但是，在教学实践中，一方面，我们感到学生掌握的理论知识和实践知识有限；另一方面课程设计的时间有限。要想学生在规定时间内，运用自己有限的知识去独立完成某一焊接结构的全部设计是不现实的。因此，在两周的课程设计时间内，除了让每个学生清楚地了解焊接结构的整个设计、装配过程外，更应该注重焊接结构设计的某一细节，完全弄懂、弄透，能够达到举一反三的目的，从而培养学生设计焊接结构的初步能力。 基于以上认识，作者编写了《焊接结构课程设计指导书》。 编者 一、课程设计的性质、目的 焊接作为先进制造技术的重要组成部分，在国民经济的发展和国家建设中发挥了重要的作用。焊接技术在航空航天、核能、船舶、电力、海洋钻探、高层建筑等领域得到了广泛的应用。焊接结构是焊接技术应用于工程实际产品的主要形式，也是在许多部门中应用最为广泛的金属结构。焊接结构学作为焊接专业基础课，对学生的专业知识和技能的培养具有重要的作用。《焊接结构》课程设计是在完成焊接结构理论教学课程后，进行的综合运用所学基本知识和技能的一个非常重要的教学环节。本周开展了焊接结构学的课程设计，主要目的：进一步加深学生对焊接结构学理论知识的回顾和焊接结构在实际生产中的应用； 通过本次课程设计，使学生将理论知识与实际的焊接构件设计相结合，培养学生的理论联系实际的能力； 本次课程设计可以采用计算机绘图和手工试图，使学生加深绘图要点和培养计算机绘图技能； 通过本次课程设计培养学生的查阅技术资料、团队协作和独立创新能力。 二、课程设计的主要内容和基本任务 了解焊接结构、工况环境、制造过程的特点，掌握焊接结构的整体设计、焊接工艺规程、焊接工艺卡的编制要领。最终能根据实际需要独立研究设计相应的焊接结构，制定相关的焊接工艺。设计主体可以是梁柱桁架类和压力容器结构，对选择构件进行结构的设计，焊接接头（对接、搭接、T形和角接头）合理性分析，对相关接头的强度进行简单的计算，对易产生的应力应变特征进行分析，绘制部分结构的草图，最后绘制一张A1焊接结构图纸，并编写课程设计说明书一份。 三、课程设计的基本要求 熟悉焊接结构（梁柱桁架类和压力容器结构）的结构特点，了解焊接结构（梁柱桁架类和压力容器）各部分的受力及运行状态、结构特点以及影响制造工艺的因素并能按实际情况具体制定相应的工艺流程卡和工艺卡（具体要求见附录）。 具体要求： 1) 要充分认识课程设计对培养自己的重要性，认真做好设计前的各项准备工作； 2) 既要虚心接受老师的指导，又要充分发挥主观能动性。结合课题，独立思考,努力钻研，勤 于实践，勇于创新； 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 实验报告 （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]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。工艺综合课程设计指导书
算法设计与分析实验三
算法设计与分析实验报告贪心算法
算法设计与分析实验报告
无机材料工艺课程设计指导书
算法设计与分析课程设计报告样本
焊接工艺课程设计指导书
《算法设计与分析》实验一
冲压工艺与模具设计课程设计指导与任务书
《算法设计与分析》递归算法典型例题
算法设计与分析课程设计报告
焊接结构课程设计指导书
《算法设计与分析》实验报告
算法设计与分析课程报告
《焊接结构》课程设计指导书.
算法设计与分析实验报告 统计数字问题
南京邮电大学算法设计实验报告——动态规划法
相关主题
文本预览