《算法设计：第九讲.ppt》由会员分享，可在线阅读，更多相关《算法设计：第九讲.ppt（41页珍藏版）》请在三一办公上搜索。
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语句实现，但需要进行多次条件判断，而且嵌套的if语句降低
2、了程序的可读性。（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）,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;
3、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 优化算法的数学模型,数学模型：是利用数学语言（符号、式子与图像）模拟现实的模型。基本特征：把现实模型抽象、简化为某种数据结构。作用
4、：解释特定现象的现实状态预测到对象的未来状况提供处理对象的最优决策或控制,3.4 优化算法的数学模型,数学建模：数学建模就是把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。归纳法：是通用而简单的数学建模方法。从分析问题的几种简单的、特殊的情况中，发现一般规律或作出某种猜想，从而找到解决问题的途径。归纳法是从简单到复杂，由个别到一般的一种研究方法。,3.4.1 杨辉三角形的应用,【例题】求n次二项式各项的系数。已知二项式的展开式为：分析：若只用的组合数学的知识，直接建模问题：算法中
5、也要有大量的乘法和除法运算，效率很低。,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 1(a+b)5 数学模型：n次二项式的系数就是n阶杨辉三角形。,3.4.1 杨辉三角形的应用,求n阶杨辉三角形的递归算法：,ff(int a,int n)if(n=1)a1=1;a2=1;else ff(a,n-1);/*递归求出n-1阶*/an+1=1;for(i=n;i=2;i-)ai=ai+ai-1;,main()int a100,i,n;input(n);
6、ff(a,n);for(i=1;i=n+1;i=i+1)print(ai);,3.4.2 最大公约数的应用,【例题】数组中有n个数据，要将它们顺序循环向后移k位，即前面的元素向后移k位，后面的元素则循环向前移k位。例：1、2、3、4、5循环移3位后为：3、4、5、1、2。【实现1】利用一个数组存放原始数据，利用另外一个数组存放结果。,3.4.2 最大公约数的应用,若题目限定：不能使用2*n以上的空间来实现此题。【实现2】利用k次循环，每次移动一位。（1）先把an保存到临时单元temp（2）将an-1an，an-2 an-1（3）将temp a0中,3.4.2 最大公约数的应用,【实现3】利用一
7、个临时变量，将每一个数据一次移动到位（1）一组循环移动的情况：通过计算我们可以确定某个元素移动后的具体位置，如n=5,k=3时：0、1、2、3、4循环移3位后为2、3、4、0、1。可通过计算得出03，31，1 4，42，20；一组移动（0-3-1-4-2-0）正好将全部数据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次移动就可完成整个移动过程。,3.4.2 最大公约数的应用,（2）多组循环移动的情况：当n=6，k=3时,1、2、3、4、5、6经移动的结果是4、5、6、1、2、3.并不象上一个例子,一组循环移动（1-4-1）没有将全部数据移动到位。还需要（2-5-2）（3-6-3）两
8、组移动才能将全部数据操作完毕。循环移动的组数，与k、n的是怎么样的关系呢？,3.4.2 最大公约数的应用,我们再看一个例子：当N=6，K=2时,1、2、3、4、5、6经移动的结果是5、6、1、2、3、4.一组移动（1-3-5-1），完成了3个数据的移动；接下来，还有一组2-4-6-2。共进行二组循环移动，就能将全部数据移动完毕。数学模型：循环移动的组数等于N与K的最大公约数。,3.4.2 最大公约数的应用,算法设计：1）编写函数，完成求n,k最大公约数m的功能2）进行m组循环移动。3）每组共n/m个数据：第一组：a1 a(1+k)%n a(1+2k)%n第二组：a2 a(2+k)%n a(2+
9、2k)%n第m组：am a(m+k)%n a(m+2k)%n,3.4.2 最大公约数的应用,/*求a，b的最大公约数*/int ff(int a,int b)t=1;for(i=2；i=a,main()int a100,b0,b1,i,j,n,k,m,tt;input(n,k);for(i=0;in;i=i+1)input(ai);m=ff(n,k);for(j=0;jm;j=j+1)/*共移动m组*/b0=aj;/*将每组的第一个数保存到b0中*/tt=j;,3.4.2 最大公约数的应用,for(i=0;in/m;i=i+1)/*每组中共有n/m个数据*/tt=(tt+k)%n;/*计算移动
10、的目标位置*/b1=att;/*先保存目标位置中的数据*/att=b0;/*将前面的数据b0移入目标位置*/b0=b1;/*将b1作为新的b0*/for(i=0;in;i=i+1)print(ai);,3.4.2 最大公约数的应用,分析该算法中移动数据时的赋值次数,f=n/m;for(j=0;j0;i-)a(j+i*k)%n=a(j+(i-1)*k)%n;/*从后向前移动*/aj=b;/*把该组的最后一个数送到aj处*/,3.4.2 最大公约数的应用,【例】编程完成下面给“余”猜数的游戏：你心里先想好一个1100之间的整数x，将它分别除以3、5和7并得到三个余数。你把这三个余数告诉计算机，计算
11、机能马上猜出你心中的这个数。游戏过程如下：Please think of a number between 1 and 100Your number divided by 3 has a remainder of?1your number divided by 5 has a remainder of?0your number divided by 7 has a remainder of?5your number is 40,3.4.3 公倍数的应用,【问题分析】算法设计的关键：找出余数与求解数之间的关系，建立问题的数学模型。【数学模型】1）不难理解当s=u+3*v+3*w时，s除以3的余数
12、与u除以3的余数是一样的。2）对s=cu+3*v+3*w，当c是除以3余1的数时,s除以3的余数与u除以3的余数也是一样的。,3.4.3 公倍数的应用,【模型建立】设a,b,c分别是该数除以3，5，7后的余数，则该数为：x=c1*a+c2*b+c3*c,3.4.3 公倍数的应用,分析：（1）x除以3余a：则c1应除以3余1，c2,c3为3的倍数（2）x除以5余b：则c2应除以5余1，c1,c3为5的倍数（3）x除以7余c：则c3应除以7余1，c1,c2为7的倍数,计算后，满足条件的c1=70 c2=21 c3=15,x=70*a+21*b+15*c,若求解的d比100大，需要循环减去3，5，7
13、的最小公倍数。,main()int a,b,c,d;input(a);/*除3后的余数*/input(b);/*除5后的余数*/input(c);/*除7后的余数*/d=70*a+21*b+15*c;while(d100)d=d-105;/*105为3,5,7的最小公倍数*/print(“your number is”,d);,3.4.3 公倍数的应用,思考：3个除数也由用户给出，请设计算法。,【例】楼梯上有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编写算法计算共有多少种不同的上楼梯方法。【数学模型】此问题如果按照习惯，从前向后思考，也就是从第一阶开始，考虑怎么样走到第二阶、第三阶、第四
14、阶，则很难找出问题的规律；而反过来先思考“到第n阶有哪几种情况？”，答案就简单了，只有两种情况：1）从第n-1阶到第n阶；2）从第n-2阶到第n阶。,3.4.4 斐波那契数列的应用,反向分析法,记n阶台阶的走法数为f(n)，则 f(n)=1 n=1 f(n)=2 n=2 f(n)=f(n-1)+f(n-2)n2,3.4.4 斐波那契数列的应用,（2）倒推法：是对某些特殊问题所采用的从后向前推解问题的方法。【例3】猴子吃桃问题：一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第10天时就只有一个桃子了，求原有多少个桃？数学模型：每天的桃子数为：a10=1,a9=(1+a10)*2,a8=(1
15、+a9)*2 递推公式为：ai=(1+ai+1)*2 i=9,8,7,61,【例2】穿越沙漠问题用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。【分析】先看一简单问题：有一位探险家用5天的时间徒步横穿A、B两村，两村间是荒无人烟的沙漠，如果一个人只能携带3天的食物和水，那么这个探险家至少雇几个人才能顺利通过沙漠。,【例】核反应堆中有和两种粒子，每秒钟内一个粒子可以反应产生3个粒子，而一个粒子可以反应产生1个粒子和2个粒子。若在t=
16、0时刻的反应堆中只有一个粒子，求在t时刻的反应堆中粒子和粒子数。【分析】,3.4.5 特征根求解递归方程,【数学模型1】本题中共涉及两个变量，i时刻粒子数为ni，粒子数为mi，则有：n0=1,m0=0,ni=mi-1，mi=3ni-1+2mi-1,3.4.5 特征根求解递归方程,main（）int n100,m100,t,i;input(t);n0=1;/初始化操作 m0=0;for(i=1;i=t;i+)/进行t次递推 ni=mi-1;mi=3*ni-1+2*mi-1;print(nt，mt);/输出结果,【数学模型2】设在t时刻的粒子数为f（t），粒子数为g(t)，依题可知：g(t)=3f
17、(t-1)+2g(t-1)（1）f(t)=g(t-1)（2）g(0)=0,f(0)=1 整理得：g(t)=3g(t-2)+2g(t-1)（t2）（4）g(0)=0 g(1)=3,3.4.5 特征根求解递归方程,用特征根求得：g(t)=,3.4.5 特征根求解递归方程,main（）int t,i;input(t);n=pow(3,t);/*n代表a粒子数量*/m=pow(3,t+1);/*m代表B粒子数量*/if(t%2=1)n=n-3;m=m+3;else n=n+3;m=m-3;n=int(n/4);m=int(m/4);print(n,m);,3.4.5 特征根求解递归方程,算法分析：在数
18、学模型2中，运用数学的方法建立了递归函数并转化为非递归函数。它的优点是算法的复杂性与问题的规模无关。针对某一具体数据，问题的规模对时间的影响微乎其微。,【例1】百钱买百鸡【例2】解数字迷：A B C A B A D D D D D D算法设计1：按乘法枚举 枚举范围为：A：39（A=1，2时积不会得到六位数）B：09 C：09 六位数表示为A*10000+B*1000+C*100+A*10+B，共尝试700次。,4.2.1 穷举法,【例2】解数字迷：A B C A B A D D D D D D算法设计2：按除法枚举 将算式变形为除法：DDDDDD/A=ABCAB。此时 A：39 D：19 共
19、尝试7*9=63次。,4.2.1 穷举法,本节将通过蛮力策略，用算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后的算法进行效率上的比较。,4.2.2 其他范例,【例12】某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，那些牢房的锁仍然是打开的？,4.2.2 其他范例,方法一：穷举法for(i=1;i=n;i+)for(j=i;j=n;j=j+i)ai=1-ai;方法二：因数统计法for(i=1;i=n;i+)s=1;for(j=2;j=i;j=j+)if(i%j=0）s=s+1;if（s%2=1）print(i,”is free.”);,4.2.2 其他范例,方法三：完全平方数的因数个数为奇数。for(i=1;i+)if（i*i=n）print(i,”is free.”);else break;,4.2.2 其他范例,
