《算法设计：第九讲》PPT课件

《《算法设计：第九讲》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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语句实现，但需要进

2、行多次条件判断，而且嵌套的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）K%3==0K%5==0K%7==0全部1117其中2个110610150113其中1个1004010200110个00003.3优化算法的基本技巧构造表达式k=(k%3==0)*4+(k%5==0)*2+(k%7==0）*1switch(k)

3、{case7:print(“all”);break;case6:print(“3,5”);break;case5:print(“3,7”);break;case4:print（”3”）；break;case3:print(“5,7”);break;case2:print(“5”);break;case1:print(“7”);break;case0:print(“None”);break;}3.4优化算法的数学模型选择恰当的数学模型，可以使算法的效率更高、占用空间更合理或使算法更简洁。认识数学模型和数学建模一个关于数学模型的简单实例：已知有

4、5个数，求前四个数与第五个数分别相乘后的最大数。p106算法1：算法2：3.4优化算法的数学模型操作算法乘法赋值条件判断Max1473Max21433.4优化算法的数学模型数学模型：是利用数学语言（符号、式子与图像）模拟现实的模型。基本特征：把现实模型抽象、简化为某种数据结构。作用：解释特定现象的现实状态预测到对象的未来状况提供处理对象的最优决策或控制3.4优化算法的数学模型数学建模：数学建模就是把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用

5、过程称为数学建模。归纳法：是通用而简单的数学建模方法。从分析问题的几种简单的、特殊的情况中，发现一般规律或作出某种猜想，从而找到解决问题的途径。归纳法是从简单到复杂，由个别到一般的一种研究方法。3.4.1杨辉三角形的应用【例题】求n次二项式各项的系数。已知二项式的展开式为：分析：若只用的组合数学的知识，直接建模问题：算法中也要有大量的乘法和除法运算，效率很低。3.4.1杨辉三角形的应用数学常识：各阶多项式的系数呈杨辉三角形的规律：(a+b)01(a+b)111(a+b)2121(a+b)31331(a+b)414641(a+b)5……数学模

6、型：n次二项式的系数就是n阶杨辉三角形。3.4.1杨辉三角形的应用求n阶杨辉三角形的递归算法：ff(inta[],intn){if(n==1){a[1]=1;a[2]=1;}else{ff(a,n-1);/*递归求出n-1阶*/a[n+1]=1;for(i=n;i>=2;i--)a[i]=a[i]+a[i-1];}}main(){inta[100],i,n;input(n);ff(a,n);for(i=1;i<=n+1;i=i+1)print(a[i]);}3.4.2最大公约数的应用【例题】数组中有n个数据，要将它们顺序循环向后移k位，即前

7、面的元素向后移k位，后面的元素则循环向前移k位。例：1、2、3、4、5循环移3位后为：3、4、5、1、2。【实现1】利用一个数组存放原始数据，利用另外一个数组存放结果。3.4.2最大公约数的应用若题目限定：不能使用2*n以上的空间来实现此题。【实现2】利用k次循环，每次移动一位。（1）先把a[n]保存到临时单元temp（2）将a[n-1]→a[n]，a[n-2]→a[n-1]……（3）将temp→a[0]中3.4.2最大公约数的应用【实现3】利用一个临时变量，将每一个数据一次移动到位（1）一组循环移动的情况：通过计算我们可以确定某个元素移动

8、后的具体位置，如n=5,k=3时：0、1、2、3、4循环移3位后为2、3、4、0、1。可通过计算得出0→3，3→1，1→4，4→2，2→0；一组移动（0-3-1-4-2-0）正好