算法设计︰第九讲2013.pptVIP

【例】核反应堆中有α和β两种粒子，每秒钟内一个α粒子可以反应产生3个β粒子，而一个β粒子可以反应产生1个α粒子和2个β粒子。若在t=0时刻的反应堆中只有一个α粒子，求在t时刻的反应堆中α粒子和β粒子数。 【分析】 3.4.5 特征根求解递归方程 …… 3*3+2*6 6 3 3*ai-1+2*bi-1 β i-1 i 6 3 2 3 0 1 0 1 0 β α 时刻 * * 3.3 优化算法的基本技巧 【例题24】有10箱产品每箱有1000件，正品每件100克。其中的几箱是次品，次品每件比正品轻10克，问能否用秤只称一次，就找出哪几箱是次品。 问题分析： （1）若只有一箱是次品： （2）若有几箱是次品： 3.3 优化算法的基本技巧 【例题25】编写算法对输入的一个整数，判断它能否被3，5， 7整除，并输出以下信息之一： （1）? 能同时被3，5，7整除； （2）? 能被其中两数（要指出哪两个）整除； （3）? 能被其中一个数（要指出哪一个）整除； （4）? 不能被3，5，7任一个整除。 3.3 优化算法的基本技巧 【算法分析】 （1）使用if语句实现，但需要进行多次条件判断，而且嵌套的if语句降低了程序的可读性。 （2）使用表达式 k=(x%3==0)+(x%5==0)+(x%7==0) k为0：不能被3，5，7整除 k为1：能被3、5、7中的一个整除，但不能指出是哪一个 k为2：能被3、5、7中的两个整除 k为3：能同时被3、5、7整除 3.3 优化算法的基本技巧 （3） 0 1 0 0 1 1 0 1 K%7==0 1 0 0 0 0 0 0个 2 1 0 4 0 1 其中1个 3 1 0 5 0 1 6 1 1 其中2个 7 1 1 全部 K%5==0 K%3==0 3.3 优化算法的基本技巧 构造表达式 k=(k%3==0)*4+(k%5==0)*2+(k%7==0）*1 switch(k) {case 7: print(“all”);break; case 6: print(“3,5”);break; case 5: print(“3,7”);break; case 4: print（”3”）；break; case 3: print(“5,7”);break; case 2: print(“5”);break; case 1: print(“7”);break; case 0: print(“None”);break; } 3.4 优化算法的数学模型 选择恰当的数学模型，可以使算法的效率更高、占用空间更合理或使算法更简洁。 认识数学模型和数学建模 一个关于数学模型的简单实例：已知有5个数，求前四个数与第五个数分别相乘后的最大数。 p106 算法1： 算法2： 3.4 优化算法的数学模型 3 4 1 Max2 3 7 4 Max1 　条件判断 　　赋值 乘法 　　　　　　　操作 算法 3.4 优化算法的数学模型 数学模型：是利用数学语言（符号、式子与图像）模拟现实的模型。 基本特征：把现实模型抽象、简化为某种数据结构。 作用： 解释特定现象的现实状态 预测到对象的未来状况 提供处理对象的最优决策或控制 3.4 优化算法的数学模型 数学建模：数学建模就是把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。 归纳法： 是通用而简单的数学建模方法。 从分析问题的几种简单的、特殊的情况中，发现一般规律或作出某种猜想，从而找到解决问题的途径。 归纳法是从简单到复杂，由个别到一般的一种研究方法。 3.4.1 杨辉三角形的应用 【例题】求n次二项式各项的系数。 已知二项式的展开式为： 分析：若只用的组合数学的知识，直接建模 问题：算法中也要有大量的乘法和除法运算，效率很低。 3.4.1 杨辉三角形的应用 数学常识：各阶多项式的系数呈杨辉三角形的规律： (a+b)0 1 (a+b)1 1 1 (a+b)2 1 2 　 1 (a+b)3 1 　3 3 1 (a+b)4 1 4 6 4