《算法设计与分析》习题 第一章算法引论 1、算法的定义 答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。 2、算法的特征 答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性 3、算法的描述方法有几种 答：自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面 答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。 5、时间复杂度、空间复杂度定义 答：指的是算法在运行过程中所需要的资源（时间、空间）多少。 6、时间复杂度计算： {i=1； while（i<=n） i=i*2； } 答：语句①执行次数1次， 语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ； 7.递归算法的特点 答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件） ②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式） 8、算法设计中常用的算法设计策略 答：①蛮力法；②倒推法；③循环与递归；④分治法； ⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法 9、设计算法： 递归法：汉诺塔问题兔子序列（上楼梯问题） 整数划分问题 蛮力法：百鸡百钱问题 倒推法：穿越沙漠问题
答：算法如下： （1） 递归法 汉诺塔问题 void hanoi(int n, int a, int b, int c) {if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 兔子序列（fibonaci 数列 ） 递归实现： Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+… 将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 递归算法： Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n
实验设计方法㈠ 统计学设计方法按因素分为： 单因素：完全随机，配对设计，序贯设计。 两因素：配伍组设计（随机区组设计），均衡不完全配伍组设计 配对设计，两层次分组设计。 三因素：拉丁方设计，尧敦方设计，裂区设计。 多因素：析因设计，正交设计，均匀设计。 嵌套设计，重复测量设计，调查设计，诊断试验。 一、完全随机设计(Complete random design) （一）概念 ?完全随机设计：又称简单随机分组设计，将受试的对象 随机地分配到各处理组（水平）进行试验，或从不同总 体中随机抽样进行观察。 ?是最简单、最易于掌握的设计方法。 ?可设置两个组，也可设置多个组，可设置2个以上的水平。 ?设计中未考虑非处理因素的影响。 （二）应用条件 １.应用条件： ①计数、计量、等级分组资料； ②适合于样本内个体变异较小的情况； ③注意各组的均衡和可比性。 ④各组样本含量可以不等，但最好是n1 = n2 2.缺点： 只能分析单因素。因工作量大，统计效率低。 （三）实验设计方法 ?单因素多水平完全随机设计：将符合实验要求的观察对象随机分配到n个水平组中。 ?单因素g水平组内完全随机设计：研究某药物治疗某疾病，比较该药物对不同年龄段病人的作用，可采用随机抽样，分别从该疾病的老中青三个总体中随机抽取所需要的样本，比较观察。完全随机设计多组试验 二、配对设计(matched-pairs design) 配对设计：是将条件相同或相近的受试对象按某些特征或条件配成对子，然后把每对中两个受试对象随机分配到不同研究组，这种设计称配对设计。可分为四种： (一)前后配对设计 (二)左右配对设计 (三)异体配对设计 (四) 配对设计与完全随机设计比较 (五)交叉配对设计 （一）前后配对设计 指同一批实验对象，施加一种受试因素后，观察某一实验指标在实验前后的变化。同一批标本接受两种不同测定方法的检查也这属类配对。 １.应用范围：主要应用于急性病与短期实验，但不是绝对不能用于慢性病（病情稳定的慢性
常用算法设计方法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，常用的算法设计方法主要有迭代法、穷举搜索法、递推法、递归法、贪婪法、回溯法、分治法、动态规划法等。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：（1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还大于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)； /*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)； prin tf(“方程的近似根是%f\n”，x0)； } 具体使用迭代法求根时应注意以下两种可能发生的情况： （1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制； （2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。 【举例】求方程X2-X-1=0的正根，误差<0.05 解：（1）建立迭代公式 由于X=X2-1
第8 章排序(算法设计)习题练习答案 13. 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。 解：重写的算法如下： void InsertSort(SeqList R) {//对顺序表中记录R[0..n-1]按递增序进行插入排序 int i,j; for(i=n-2;i>=0;i--) //在有序区中依次插入R[n-2]..R[0] 课后答案网https://www.doczj.com/doc/387874516.html, if(R[i].key>R[i+1].key) //若不是这样则R[i]原位不动 { R[n]=R[i];j=i+1; //R[n]是哨兵 do{ //从左向右在有序区中查找插入位置 R[j-1]=R[j]; //将关键字小于R[i].key 的记录向右移 j++; }while(R[j].key KeyType key; //关键字域 OtherInfoType info; //其它信息域， struct node * next; //链表中指针域 }RecNode; //记录结点类型 typedef RecNode * LinkList ; //单链表用LinkList 表示 void InsertSort(LinkList head) {//链式存储结构的直接插入排序算法,head 是带头结点的单链表RecNode *p,*q,*s; if ((head->next)&&(head->next->next))//当表中含有结点数大于1 { p=head->next->next;//p 指向第二个节点 head->next=NULL; q=head;//指向插入位置的前驱节点 while(p)&&(q->next)&&(p->key 《算法设计与分析实用教程》参考解答 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 VB 程序设计的常用算法 算法( Algorithm )：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据(输入什么数据、输出什么结果)、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。 一、计数、求和、求阶乘等简单算法 此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。 例：用随机函数产生100 个［0，99］范围内的随机整数，统计个位上的数字分别为1，2，3，4，5，6，7，8，9，0 的数的个数并打印出来。 本题使用数组来处理，用数组a(1 to 100)存放产生的确100个随机整数，数组x(1 to 10)来存放个位上的数字分别为1，2，3，4，5，6，7，8，9，0 的数的个数。即个位是1 的个数存放在x(1) 中，个位是2 的个数存放在x(2)中，...................... 个位是0的个数存放在x(10)。 将程序编写在一个GetTJput过程中，代码如下： Public Sub GetTJput() Dim a(1 To 100) As Integer Dim x(1 To 10) As Integer Dim i As Integer, p As Integer '产生100 个［0，99］范围内的随机整数，每行 1 0个打印出来 For i = 1 To 100 a(i) = Int(Rnd * 100) If a(i) < 10 Then Form1.Print Space(2); a(i); 分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间） 分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ） 常用算法设计方法C语言 常用算法设计方法 (1) 一、迭代法 (1) 二、穷举搜索法 (2) 三、递推法 (6) 四、递归 (7) 五、回溯法 (15) 六、贪婪法 (28) 七、分治法 (33) 八、动态规划法 (39) 常用算法设计方法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递 推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： 选一个方程的近似根，赋给变量x0； 将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； 当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为：【算法】迭代法求方程的根 { x0=初始近似根； d o { x1=x0； 教师教案( 2005 —2006 学年第 1 学期 ) 课程名称：试验设计方法 授课学时：32 授课班级：23034010-11 任课教师：何为 教师职称：教授 教师所在学院：微电子与固体电子学院电子科技大学 绪论 1学时 教学内容及要求 试验设计方法在科学研究中的作用 1. 科学研究的基本过程 2. 科学研究的基本方法 3. 试验设计方法的主要内容 ●试验设计方法在科学技术发展中的地位和作用。 ●试验设计方法的起源。 ●我国试验设计方法的发展和现状。 ●使用试验设计方法的目的、内容和应用。 ●试验设计方法是当代科技和工程技术人员必须掌握的技术方法。 ●教学内容：正交试验法、优选法基础、回归分析法、均匀设计法、单 纯形优化法 参考资料 ?项可风.试验设计与数据分析.上海科技出版社.1991年 ?陈宝林.最优化理论及算法.清华大学出版社.1990年 ?邓正龙.化工中的优化方法.化学工业出版社.1991年 ?陈魁.试验设计与分析.清华大学出版社.1996年 ? (日)田口玄一.实验设计法.魏锡,王世芳译.机械工业出版社.1987 ? Phadke, M.S. "Quality Engineering Using Robust Design" Prentice Hall, Englewood Cliff, NJ. November 1989 ? Taguchi, Genichi. "System of Experimental Design" Edited by Don Clausing. New York: UNIPUB/Krass International Publications, Volume 1 & 2, 1987 ? Montgomery, D. C.. Design and analysis of experiment. New York: Wiley.1997 ?杨德.试验设计与分析.中国农业出版社.2002 第一章正交试验基本方法 5学时 授课时数： 一、教学内容及要求 ●多因素试验问题、正交试验、正交表符号的意义。 ●因素、水平、自由度、试验指标、交互作用。均衡分散性、整齐可比 浅论五个常用算法 软件工程 姓名：余智昆 专业班级：软件102班 日期：2012.2.18 【摘要】随着信息工业的发展，计算机已然成为人们日常生活中不可或缺的工具。目前， 各行业、各领域都广泛采用了计算机信息技术，并由此产生出开发各种应用软件的需求。为了以最少的成本、最快的速度、最好的质量开发出适应各种应用需求的软件，必须遵循软件工程的原则。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学领域数据结构与算法设计所研究的主要内容。通过对计算机算法系统的学习与研究，掌握算法设计的主要方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定了坚实的理论基础。 在计算机语言中，算法的概念是至关重要的，一个优秀的软件，设计出有效的算法将起决定性的作用。本篇论文将对五种常用算法概括总结，希望能够对算法有更深入的理解。 【关键词】递归与分治策略、动态规划、贪心算法、回溯法、分之界限法 【正文】 一、递归与分治策略 A．1.递归：一个直接或间接调用自身的算法称为递归算法。在计算机算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。有些数据结构如二叉树等，由于其本身固有的递归特性，特别适合用递归形式来描述。还有一些问题，虽然本身并没有明显的递归结构，但是用递归技术来求解设计出的算法简洁易懂且易于分析。 2.递归算法要求：递归算法所体现的“重复”一般有三个要求 一是每次调用在规模上都有所缩小(通常是减半)； 二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)； 三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。 3.递归过程实质： 算法的嵌套调用，只是 调用算法和被调用算法 是同一个算法。和每次 调用相关的一个重要概 念是递归算法的调用层 次。若调用一个递归算 法的主算法为第0层算 法，则主算法调用递归 算法为进入第一层调 用；从第i层递归调用 本算法为进入第i+1层 调用。反之，退出第i 层调用，则返回第i-1 层递归调用。为了保证 递归调用正确执行，系 统要建立一个递归调用 工作栈，为各层次的调 用数据存储区。 4.递归算法的优缺点：结构清晰、可读性强，且容易用数学归纳法证明算法的正确性， 因此它为设计算法、调试程序带来很大的方便。然而，递归算法的运行效率较低，无论是耗费的计算时间还是占用的空间都要比非递归算法要多。因此，我们使用递归算法，必须权衡运行时间与内存这两者的消耗。 B.1.分治策略：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 它的一般算法设计模式： Divid-and-Conquer(p) VB程序设计的常用算法 算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。 一、计数、求和、求阶乘等简单算法 此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。 例：用随机函数产生100个[0，99]范围内的随机整数，统计个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数并打印出来。 本题使用数组来处理，用数组a(1 to 100)存放产生的确100个随机整数，数组x(1 to 10)来存放个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数。即个位是1的个数存放在x(1)中，个位是2的个数存放在x(2)中，……个位是0的个数存放在x(10)。 将程序编写在一个GetTJput过程中，代码如下： Public Sub GetTJput() Dim a(1 To 100) As Integer Dim x(1 To 10) As Integer Dim i As Integer, p As Integer '产生100个[0，99]范围内的随机整数，每行10个打印出来 For i = 1 To 100 a(i) = Int(Rnd * 100) If a(i) < 10 Then Form1.Print Space(2); a(i); Else Form1.Print Space(1); a(i); End If If i Mod 10 = 0 Then Form1.Print Next i '统计个位上的数字分别为1，2，3，4，5，6，7，8， 1.数字三角形 这道题目可以用递归的方法解决。基本思路是： 以D( r, j)表示第r行第j 个数字(r，j都从1开始算)，以MaxSum(r, j) 代表从第r 行的第j 个数字到底边的最佳路径的数字之和，则本题是要求MaxSum(1, 1) 。 从某个D(r, j)出发，显然下一步只能走D(r+1, j)或者D(r+1, j+1)。 i.如果走D(r+1, j)，那么得到的MaxSum(r, j)就是MaxSum(r+1, j) + D(r, j)； ii.如果走D(r+1, j+1)，那么得到的MaxSum(r, j)就是MaxSum(r+1, j+1) + D(r, j)。 所以，选择往哪里走，就看MaxSum(r+1, j)和MaxSum(r+1, j+1)哪个更大了。程序如下：#include 《计算机常用算法与程序设计案例教程》 习题解答提要 习题1 1-1 分数分解算法描述 把真分数a/b 分解为若干个分母为整数分子为“1”的埃及分数之和： （1） 寻找并输出小于a/b 的最大埃及分数1/c ； （2） 若c>900000000，则退出； （3） 若c ≤900000000，把差a/b-1/c 整理为分数a/b ，若a/b 为埃及分数，则输出后结束。 （4） 若a/b 不为埃及分数，则继续（1）、（2）、（3）。 试描述以上算法。 解：设)(int a b d = (这里int(x)表示取正数x 的整数)，注意到1+< if(c>900000000) return; else { print(1/c+); a=a*c-b; b=b*c; // a,b迭代，为选择下一个分母作准备 if(a==1) { print(1/b);return;} } } 1-2 求出以下程序段所代表算法的时间复杂度 （1）m=0; for(k=1;k<=n;k++) for(j=k;j>=1;j--) m=m+j; 解：因s=1+2+…+n=n(n+1)/2 时间复杂度为O(n2)。 （2）m=0; for(k=1;k<=n;k++) for(j=1;j<=k/2;j++) m=m+j; 解：设n=2u+1，语句m=m+1的执行频数为 s=1+1+2+2+3+3+…+u+u=u(u+1)=(n?1)(n+1)/4 设n=2u，语句m=m+1的执行频数为 s=1+1+2+2+3+3+…+u=u2=n2/4 时间复杂度为O(n2)。 （3）t=1;m=0; for(k=1;k<=n;k++) {t=t*k; for(j=1;j<=k*t;j++) m=m+j; } 解：因s=1+2×2!+ 3×3!+…+ n×n!=(n+1)!?1 时间复杂度为O((n+1)!). （4）for(a=1;a<=n;a++) 常用实验设计方法（三） 六.析因设计（f a c t o r i a l d e s i g n） ◆析因设计是一种多因素试验设计。 ◆可将两个或多个因素的各个水平进行排列组合，交叉分组进行全面实验。 ◆总的实验方案(组合)是各因素水平的乘积。 例如： 2×2析因设计（两个因素，每个因素均为2个水平，常可写成22析因设计） A因素（A1、A2）和B因素（B1、B2）共4种实验方案或组合（A1B1、A1B2、A2B1、A2B2） 3×3析因设计（两个因素，每个因素均为3个水平，常可写成23析因设计） A因素（A1、A2、A3）和B因素（B1、B2、B3）共9种组合 （A1B1、A1B2、A1B3、A2B1、A2B2A2B3、A3B1、A3B2A3B3）2×3×3析因设计（三个因素，一个因素为2个水平，余均为3个水平）共18种组合 1.特点 ①研究的因素个数m≥2，各因素的水平数≥2； ②各因素在实验中同时实施且所处的地位基本平等。 ③每个因素水平相互组合的实验方案，至少进行2次及以上独立重复实验。 ④因素间存在交互效应。例如，一级（两个因素间）或二级交互（三个因素间）效应。 ⑤统计学分析时，各因素及交互项所用误差项是相同的。 ◆优点： ?可分析各因素的主效应(m a i n e f f e c t s)（某因素各水平间的平均效应差异） ?因素间的交互效应(i n t e r a c t i o n)(一个因素的水平改变会影响另一个因素的效应) ?寻找最优方案或最佳组合 ?可允许数据缺失（完全随机分配情况下） ◆缺点： ?当因素较多或水平数较多时，所需实验次数过多。 ?一般来说，因素数最好不要多于6个，水平数亦不要过多，一般为2或3个。 【推荐】实验设计方案四篇 实验设计方案篇1 发展节水型水产养殖、种植模式，进化水质节约用水，清除鱼池中有机质带来的污染，绿化池塘有效提高池塘利用率，把池塘效益最大化除了优化水产品的品种结构外，还可以开发利用水面及水面以上的空间。这是未来池塘养殖的发展趋势。利用池塘养殖空间，水下养鱼，水面种菜，是发展水池养殖与种植相结合的方向之一。鱼的生存生长产生的废物，恰好是水生蔬菜所必须的营养。精养鱼池的肥水实际上是无土栽培的营养液。在池塘蔬菜种植和水产养殖的结合中，要根据重庆地区池塘养殖的模式和特点，结合当地的气候季节变化，如何因事利导，趋利避害，因地制宜，选择合适的品种搭配采取相适应的种养技术，是我们鱼菜共生实验成功的关键。根据上述思路制定设计方案如下： 一、设计目标 我场位于璧山县城与狮子镇之间，养殖水源已严重污染，河水无法使用。其净化池水水质减少循环已成头等大事。 1。鱼菜共生池全年不因养鱼投饲料污染水质而换水（确因天旱池水枯竭，只能适当补给）。利用蔬菜汲取池中氨、氮、磷等多余元素净化水质达到不换水的目的。 2。鱼产量1000公斤/亩、蔬每亩500公斤。 3。对比池鱼产量1000公斤/亩。 二、设计方案 由于该实验在重庆地区属初试，在全国也没有完全成熟的经验可以借鉴，所以在种植蔬菜的浮床用材方面，既要考虑浮力，又要与就地取材、低成本原则相结合考虑：1。浮床： ①用竹子做浮筐，在浮筐上用聚乙烯网布作浮床的面和底。使其面、底中空高度在10cm左右、面部开孔植菜，底部透水供菜营养、并防鱼吃菜根。 ②用塑料管做浮筐，其他同①。 ③用板房填充泡沫作浮床开孔植菜，但下部分需网布防鱼吃菜根。 ④利用竹块定型，同样用网布上下隔两层，然后在四角用竹棍定植在池中，靠四角竹棍支撑重量，成本最低。 2。植菜的品种：适应水生的品种。 ①空心菜：生长期4—10月，时间长、产菜期长。 ②水芹菜：生长期10—来年3月，有效利用冬季延续空心菜的产量。 ③丝瓜：需大水大肥、可搭架立体利用水面以上的空间。 3。池鱼放养模式：结合当地养殖习惯，不回避草鱼。 4。种植面积不超过养鱼水面的20%、不低于15%。 三、实验场地 准实验研究设计方法 从研究设计的思想和要求来推论，可以认为准实验设计是一种降低了控制标准的类似真实验的研究方法，因此准实验研究设计的方法在许多方面与真实验有相同之处，常用的准实验设计方法有不相等实验组控制组前后测准实验设计、不相等区组后测准实验设计、单组前测后测时间系列准实验设计、多组前测后测时间系列准实验设计、修补法准实验设计等五种。 （一）不相等实验组控制组前后测准实验设计 这种准实验设计方法通常应用的情况是：需要安排两组被试作为实验组和控制组进行研究，但又不能按照随机化原则重新选择被试样本和分配被试。这是一种典型的准实验设计方法，用于针对不同被试组在一开始就不相等时，进行实验组和控制组后测结果的比较，实验程序安排如表7-6所示： 表7-6 不相等实验组控制组前测后测准实验设计程序 不相等实验组控制组前后测准实验设计在进行过程中要注意两个问题。 ⑴进行前测是用于检验在实验要考证的问题上实验组和控制组原有的近似程度，而不考虑其它因素。只有当两个组在考证问题上原有水平相接近时，才能进行该种准实验研究。 ⑵对结果进行分析时，要对R3和R4之间的差异进行统计检验，而非简单比较平均分、方差等，通过检验确定进行实验后两个组之间是否存在差异，差异程度如何。 [例6-1] 某一课题要研究利用多媒体计算机辅助物理教学后学生的学习效果，应用准实验方法进行研究，设计方案如下： 第一步：选取实验对象。 为保证正常教学的进行，在某个年级中选择两个现成的整班参加实验。 为了保证参加研究的两个班物理学习的原始水平相似，对该年级所有的班进行前测以检测起始水平，从中选出两个水平接近的整班参加研究，保证选出的两个班在物理学习上总体水平相同或相近。然后从中随机确定一个班作为实验组，接受多媒体计算机辅助物理教学；同时另一个班作为控制组按照原有教学计划和教学方式进行学习。 第二步：经过同一进度的教学活动后，同时对两个班级的物理课学习成绩进行考核，考核的结果进行后测。 第三步：将两个班的后测成绩分别减去各自的前测成绩，并用独立样本的t检验对这两个差值的差别显著性进行统计检验，最后判断实验组和控制组在进行实验前后是否有明显的差异，从而得出结论。 在这种准实验设计方法中，实验的情况通常可用图7-4表示： 经典算法设计方法 一、什么是算法 算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。时间复杂度用“O（数量级）” n）对数阶；来表示，称为“阶”。常见的时间复杂度有： O（1）常数阶；O（log 2 O（n）线性阶；O（n2）平方阶。 算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。 二、算法设计的方法 1.递推法 递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。 【问题】阶乘计算 问题描述：编写程序，对给定的n（n≦100），计算并输出k的阶乘k！（k=1，2，…，n）的全部有效数字。 由于要求的整数可能大大超出一般整数的位数，程序用一维数组存储长整数，存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组 a[ ]存储： N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100 并用a[0]存储长整数N的位数m，即a[0]=m。按上述约定，数组的每个元素存储k的阶乘k！的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素……。例如，5！=120，在数组中的存储形式为： 3 0 2 1 …… 首元素3表示长整数是一个3位数，接着是低位到高位依次是0、2、1，表示成整数120。 计算阶乘k！可采用对已求得的阶乘(k-1)！连续累加k-1次后求得。例如，已知4！=24，计算5！，可对原来的24累加4次24后得到120。细节见以下程序。# include 四种排序方法： 一、选择排序： 1.初始化一个长度为r[]的数组； 1.1数组下标从1开始； 2.for（i=1;i<=n-1:i++） 2.1 for(j=i+1;j<=n:j++) 2.2 在无序区中找最小记录； 2.3 若最小记录不在最终位置则交换； 二、起泡排序： 1.初始化一个长度为r[]的数组； 1.1数组下标从1开始； 2.for(i=1;i<=n-1;i++) 2.1 for(j=1;j<=n-i;j++) 2.2如果反序，则交换元素； 三、归并排序： 1.初始化一个长度为r[]的数组； 2.若s==t则r1[s]=r[s]; 2.1 m=(s+t)/2; 2.2 归并排序前半子序列； 2.3 归并排序后半子序列； 2.4 合并两个已排序的子序列； 四、快速排序： 1.初始化一个长度为r[]的数组； 2.若开始小于结尾 2.1问题分解，pivot是轴值在序列序列中的位置； 2.2递归地对左侧子序列进行快速排序； 2.3递归地对右侧子序列进行快速排序； #include 对试验设计方法的一些探究 试验设计概述： 试验研究可分为试验设计、试验的实施、收集整理和分析试验数据等步骤。而实验设计是影响研究成功与否最关键的一个环节，是提高试验质量的重要基础。试验设计是在试验开始之前，根据某项研究的目的和要求，制定试验研究进程计划和具体的试验实施方案。其主要内容是研究如何安排试验、取得数据，然后进行综合的科学分析，从而达到尽快获得最优方案的目的。如果试验安排得合理，就能用较少的试验次数，在较短的时间内达到预期的试验目的；反之，试验次数既多，其结果还往往不能令人满意。试验次数过多，不仅浪费大量的人力和物力，有时还会由于时间拖得太长，使试验条件发生变化而导致试验失败。因此，如何合理安排试验方案是值得研究的一个重要课题。 目前，已建立起许多试验设计方法。如我们大家比较熟悉的，常用单因素实验设计方法的有黄金分割法、分数法、交替法、等比法、对分法和随机法等，这些方法为多因素试验水平范围的选取提供了重要的依据，并在生产中取得了显著成效。而多因素试验设计方法有正交试验设计、均匀实验设计、稳健试验设计、完全随机化设计、随机区组试验设计、回归正交试验设计、回归正交旋转试验设计等。下面通过以下几种方法进行探究。 一、单因素试验设计 在其他因素相对一致的条件下，只研究某一个因素效应的试验，就叫单因素试验。常用的单因素试验设计方法有黄金分割法、分数法、交替法、等比法、对分法和随机法等。单因素试验不仅简单易行，而且能对被试验因 素作深入研究，是研究某个因素具体规律时常用而有效的手段。同时还可结合生产中出现的问题随时布置试验，求得迅速解决。单因素试验由于没有考虑各因素之间的相互关系，试验结果往往具有一定的局限性。 单因素试验只研究一个因素的效应，制定试验方案时，根据研究的目的要求及试验条件，把要研究的因素分成若干水平，每个水平就是一个处理，再加上对照（有时就是该因素的零水平）就可以了。 例如硫酸铵加量对微生物生长的影响试验，硫酸铵的用量分 p、1p、2p、 p四个水平。 3 在设计单因素试验方案时，应注意数量水平的级差不能过细。过细，试验因素不同水平的效应差异不明显，甚至会被试验误差所掩盖，试验结果不能说明问题。但单因素试验设计方法为多因素试验设计水平范围的选取提供了重要的依据，并在生产中取得了显著的成效。下面通过几种方法来看一下。 1.分数法 由菲波那契(Fibonacci)数列： 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, … 得出分数数列： 1/2 , 2/3, 3/5, 5/8, 8/13, 13/21, 21/34, 34/55, 55/89, …用分数数列来安排试验点的优选法称为分数法。 分数法适用场合：试验点只能取整数的情况；受条件限制只能做几次试验的情况。《算法设计与分析实用教程》习题参考解答
VB程序设计的常用算法
算法设计与分析复习题目及答案 (3)
常用算法设计方法C语言
《实验设计方法》教案
计算机算法设计与分析 五种常用算法
VB程序设计的常用算法
算法设计与分析常见题
《计算机常用算法及程序设计案例教程》习题解答
常用实验设计方法-析因设计
【推荐】实验设计方案四篇
准实验研究设计方法
经典算法设计方法
算法设计常用的四种排序
试验设计方法
相关主题
文本预览