算法设计第九讲PPT课件

《算法设计第九讲PPT课件》由会员分享，可在线阅读，更多相关《算法设计第九讲PPT课件（41页珍藏版）》请在装配图网上搜索。

1、3 3.3 .3 优化算法的基本技巧优化算法的基本技巧【例题例题2424】有有1010箱产品每箱有箱产品每箱有10001000件，正品每件件，正品每件100100克。其中克。其中的几箱是次品，次品每件比正品轻的几箱是次品，次品每件比正品轻1010克，问能否用秤只称一次克，问能否用秤只称一次，就找出哪几箱是次品。，就找出哪几箱是次品。问题分析：问题分析：（1 1）若只有一箱是次品：）若只有一箱是次品：（2 2）若有几箱是次品：）若有几箱是次品：3 3.3 .3 优化算法的基本技巧优化算法的基本技巧【例题例题2525】编写算法对输入的一个整数，判断它能否被编写算法对输入的一个整数，判断它能否被3

2、3，5 5，7 7整除，并输出以下信息之一：整除，并输出以下信息之一：（1 1）能同时被能同时被3 3，5 5，7 7整除；整除；（2 2）能被其中两数（要指出哪两个）整除；能被其中两数（要指出哪两个）整除；（3 3）能被其中一个数（要指出哪一个）整除；能被其中一个数（要指出哪一个）整除；（4 4）不能被不能被3 3，5 5，7 7任一个整除。任一个整除。3 3.3 .3 优化算法的基本技巧优化算法的基本技巧【算法分析算法分析】（1 1）使用）使用ifif语句实现，但需要进行多次条件判断，而且嵌套语句实现，但需要进行多次条件判断，而且嵌套的的ifif语句降低了程序的可读性。语句降低了程序的可读

3、性。（2 2）使用表达式）使用表达式 k=(x%3=0)+(x%5=0)+(x%7=0)k=(x%3=0)+(x%5=0)+(x%7=0)k k为为0 0：不能被：不能被3 3，5 5，7 7整除整除 k k为为1 1：能被：能被3 3、5 5、7 7中的一个整除，但不能指出是哪一个中的一个整除，但不能指出是哪一个 k k为为2 2：能被：能被3 3、5 5、7 7中的两个整除中的两个整除 k k为为3 3：能同时被：能同时被3 3、5 5、7 7整除整除3 3.3 .3 优化算法的基本技巧优化算法的基本技巧（3 3）K%3=0K%5=0K%7=0全部1117其中2个110610150113其

4、中1个1004010200110个00003 3.3 .3 优化算法的基本技巧优化算法的基本技巧 构造表达式构造表达式 k=(k%3=0)k=(k%3=0)*4 4+(k%5=0)+(k%5=0)*2 2+(k%7=0+(k%7=0）*1 1 switch(kswitch(k)case 7:case 7:print(“all”);breakprint(“all”);break;case 6:print(“3,5”);break;case 6:print(“3,5”);break;case 5:print(“3,7”);break;case 5:print(“3,7”);break;case 4

5、:print case 4:print（”3”3”）；）；break;break;case 3:print(“5,7”);break;case 3:print(“5,7”);break;case 2:print(“5”);break;case 2:print(“5”);break;case 1:print(“7”);break;case 1:print(“7”);break;case 0:case 0:print(“None”);breakprint(“None”);break;3 3.4 .4 优化算法的数学模型优化算法的数学模型l选择恰当的数学模型，可以使算法的效率更高、占用空间更选择恰当

6、的数学模型，可以使算法的效率更高、占用空间更合理或使算法更简洁。合理或使算法更简洁。l认识数学模型和数学建模认识数学模型和数学建模w一个关于数学模型的简单实例：已知有一个关于数学模型的简单实例：已知有5 5个数，求前四个个数，求前四个数与第五个数分别相乘后的最大数。数与第五个数分别相乘后的最大数。p106p106w算法算法1 1：w算法算法2 2：3 3.4 .4 优化算法的数学模型优化算法的数学模型操作操作算法算法 乘法乘法赋值赋值条件判断条件判断 Max1 4 7 3 Max2 1 4 33 3.4 .4 优化算法的数学模型优化算法的数学模型w数学模型：是利用数学语言（符号、式子与图像）模

7、拟现数学模型：是利用数学语言（符号、式子与图像）模拟现实的模型。实的模型。w基本特征：把现实模型抽象、简化为某种数据结构。基本特征：把现实模型抽象、简化为某种数据结构。w作用：作用：w解释特定现象的现实状态解释特定现象的现实状态w预测到对象的未来状况预测到对象的未来状况w提供处理对象的最优决策或控制提供处理对象的最优决策或控制3 3.4 .4 优化算法的数学模型优化算法的数学模型w数学建模：数学建模就是把现实世界中的实际问题加以提数学建模：数学建模就是把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型

8、所提供的解答来解释现实问题，我们把，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。数学知识的这一应用过程称为数学建模。w归纳法：归纳法：w是通用而简单的数学建模方法是通用而简单的数学建模方法。w从分析问题的几种简单的、特殊的情况中，发现一般从分析问题的几种简单的、特殊的情况中，发现一般规律或作出某种猜想，从而找到解决问题的途径。规律或作出某种猜想，从而找到解决问题的途径。w归纳法是从简单到复杂，由个别到一般的一种研究方归纳法是从简单到复杂，由个别到一般的一种研究方法。法。3 3.4.1 .4.1 杨辉三角形的应用杨辉三角形的应用【例题例题】求求n n次二项

9、式各项的系数。次二项式各项的系数。已知二项式的展开式为：已知二项式的展开式为：分析：若只用的组合数学的知识，直接建模分析：若只用的组合数学的知识，直接建模问题：算法中也要有大量的乘法和除法运算，效率很低。问题：算法中也要有大量的乘法和除法运算，效率很低。3 3.4.1 .4.1 杨辉三角形的应用杨辉三角形的应用数学常识：各阶多项式的系数呈杨辉三角形的规律：数学常识：各阶多项式的系数呈杨辉三角形的规律：(a+b)(a+b)0 0 1 1 (a+b)(a+b)1 1 1 1 1 1(a+b)(a+b)2 2 1 2 1 2 1 1(a+b)(a+b)3 3 1 1 3 3 13 3 1(a+b)(

10、a+b)4 4 1 4 6 4 1 1 4 6 4 1(a+b)(a+b)5 5 数学模型：数学模型：n n次二项式的系数就是次二项式的系数就是n n阶杨辉三角形。阶杨辉三角形。3 3.4.1 .4.1 杨辉三角形的应用杨辉三角形的应用求求n 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);ff(a,n);for(i=1;i=n+1;i=i+1)prin

11、t(ai);3 3.4.2 .4.2 最大公约数的应用最大公约数的应用【例题例题】数组中有数组中有n n个数据，要将它们顺序循环向后移个数据，要将它们顺序循环向后移k k位，即位，即前面的元素向后移前面的元素向后移k k位，后面的元素则循环向前移位，后面的元素则循环向前移k k位。位。例：例：1 1、2 2、3 3、4 4、5 5循环移循环移3 3位后为：位后为：3 3、4 4、5 5、1 1、2 2。【实现实现1 1】利用一个数组存放原始数据，利用另外一个数组存利用一个数组存放原始数据，利用另外一个数组存放结果。放结果。3 3.4.2 .4.2 最大公约数的应用最大公约数的应用l若题目限定：

12、不能使用若题目限定：不能使用2 2*n n以上的空间来实现此题。以上的空间来实现此题。【实现实现2 2】利用利用k k次循环，每次移动一位。次循环，每次移动一位。（1 1）先把）先把anan 保存到临时单元保存到临时单元temptemp （2 2）将将an-1an-1an，an-2 an-1 （3）将）将temp a0中3 3.4.2 .4.2 最大公约数的应用最大公约数的应用【实现实现3 3】利用一个临时变量，将每一个数据一次移动到位利用一个临时变量，将每一个数据一次移动到位（1 1）一组循环移动的情况：）一组循环移动的情况：通过计算我们可以确定某个元素移动后的具体位置，通过计算我们可以确定

13、某个元素移动后的具体位置，如如n=5,k=3n=5,k=3时：时：0 0、1 1、2 2、3 3、4 4循环移循环移3 3位后为位后为2 2、3 3、4 4、0 0、1 1。可通过计算得出可通过计算得出0 03 3，3 31 1，1 1 4 4，4 42 2，2 20 0；一组移动（一组移动（0-3-1-4-2-00-3-1-4-2-0）正好将全部数据按要求进行了）正好将全部数据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次移动就可移动。这样只需要一个辅助变量，每个数据只需一次移动就可完成整个移动过程。完成整个移动过程。3 3.4.2 .4.2 最大公约数的应用最大公约数的应用（2

14、 2）多组循环移动的情况：）多组循环移动的情况：当当n=6n=6，k=3k=3时时,1 1、2 2、3 3、4 4、5 5、6 6经移动的结果是经移动的结果是4 4、5 5、6 6、1 1、2 2、3.3.并不象上一个例子并不象上一个例子,一组循环移动（一组循环移动（1-4-11-4-1）没有将全部数）没有将全部数据移动到位。还需要（据移动到位。还需要（2-5-22-5-2）（）（3-6-33-6-3）两组移动才能将全部）两组移动才能将全部数据操作完毕。数据操作完毕。循环移动的组数，与循环移动的组数，与k k、n n的是怎么样的关系呢？的是怎么样的关系呢？3 3.4.2 .4.2 最大公约数的

15、应用最大公约数的应用我们再看一个例子：我们再看一个例子：当当N=6N=6，K=2K=2时时,1 1、2 2、3 3、4 4、5 5、6 6经移动的结果是经移动的结果是5 5、6 6、1 1、2 2、3 3、4.4.一组移动一组移动（1-3-5-11-3-5-1），完成了），完成了3 3个数据的移动；接下来，还有个数据的移动；接下来，还有一组一组2-4-6-22-4-6-2。共进行二组循环移动，就能将全部数据移动完。共进行二组循环移动，就能将全部数据移动完毕。毕。p数学模型：循环移动的组数等于数学模型：循环移动的组数等于N N与与K K的最大公约数。的最大公约数。3 3.4.2 .4.2 最大公

16、约数的应用最大公约数的应用算法设计：算法设计：1 1）编写函数，完成求）编写函数，完成求n,kn,k最大公约数最大公约数m m的功能的功能2 2）进行）进行m m组循环移动。组循环移动。3 3）每组共）每组共n/mn/m个数据：个数据：第一组：第一组：a1 a(1+k)%n a(1+2k)%na1 a(1+k)%n a(1+2k)%n第二组：第二组：a2 a(2+k)%n a(2+2k)%na2 a(2+k)%n a(2+2k)%n第第m m组：组：amam a(m+k)%na(m+k)%n a(m+2k)%n a(m+2k)%n3 3.4.2 .4.2 最大公约数的应用最大公约数的应用/*求

17、求a，b的最大公约数的最大公约数*/int ff(int a,int b)t=1;for(i=2；i=a&i=b；i+)while (a%i=0 and b%i=0)t=t*i;a=a/i;b=b/i;return(t);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 3.4.2 .4.2 最大公约数的应用最大公约数的应用for(i=0;in/m;i=i+1)/*每组

18、中共有n/m个数据*/tt=(tt+k)%n;/*计算移动的目标位置*/b1=att;/*先保存目标位置中的数据*/att=b0;/*将前面的数据b0移入目标位置*/b0=b1;/*将b1作为新的b0*/for(i=0;in;i=i+1)print(ai);3 3.4.2 .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 3.4.2 .4.2 最大公约数的应用最大公约数的应用【例】编程完成下面给“余”猜数的游戏

19、：你心里先想好一个1100之间的整数x，将它分别除以3、5和7并得到三个余数。你把这三个余数告诉计算机，计算机能马上猜出你心中的这个数。游戏过程如下：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 403 3.4.3 .4.3 公倍数的应用公倍数的应用【问题分析】

20、算法设计的关键：找出余数与求解数之间的关系，建立问题的数学模型。【数学模型】1）不难理解当s=u+3*v+3*w时，s除以3的余数与u除以3的余数是一样的。2）对s=cu+3*v+3*w，当c是除以3余1的数时,s除以3的余数与u除以3的余数也是一样的。3 3.4.3 .4.3 公倍数的应用公倍数的应用【模型建立】设a,b,c分别是该数除以3，5，7后的余数，则该数为：x=c1*a+c2*b+c3*c3 3.4.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：

21、则c3应除以7余1，c1,c2为7的倍数计算后，满足条件的c1=70 c2=21 c3=15 x=70*a+21*b+15*c若求解的d比100大，需要循环减去3，5，7的最小公倍数。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 3.4.3 .4.3 公倍数的应用公倍数的应用思考：3个除数也由用户给出，请设计算法。【例例】楼梯

22、上有楼梯上有n n阶台阶，上楼可以一步上阶台阶，上楼可以一步上1 1阶，也可以一步阶，也可以一步上上2 2阶，编写算法计算共有多少种不同的上楼梯方法。阶，编写算法计算共有多少种不同的上楼梯方法。【数学模型数学模型】此问题如果按照习惯，从前向后思考，也就是此问题如果按照习惯，从前向后思考，也就是从第一阶开始，考虑怎么样走到第二阶、第三阶、第四阶从第一阶开始，考虑怎么样走到第二阶、第三阶、第四阶，则很难找出问题的规律；而反过来先思考，则很难找出问题的规律；而反过来先思考“到第到第n n阶有阶有哪几种情况？哪几种情况？”，答案就简单了，只有两种情况：，答案就简单了，只有两种情况：1 1）从第从第n-

23、1n-1阶到第阶到第n n阶；阶；2 2）从第从第n-2n-2阶到第阶到第n n阶。阶。3 3.4.4 .4.4 斐波那契数列的应用斐波那契数列的应用反向分析法反向分析法记记n n阶台阶的走法数为阶台阶的走法数为f(nf(n)，则，则 f(nf(n)=1 n=1)=1 n=1 f(nf(n)=2 n=2)=2 n=2 f(nf(n)=f(n-1)+f(n-2)n2)=f(n-1)+f(n-2)n23 3.4.4 .4.4 斐波那契数列的应用斐波那契数列的应用（2 2）倒推法：是对某些特殊问题所采用的从后向前推解问题）倒推法：是对某些特殊问题所采用的从后向前推解问题的方法。的方法。【例例3 3】

24、猴子吃桃问题：一只小猴子摘了若干桃子，每天吃现猴子吃桃问题：一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第有桃的一半多一个，到第1010天时就只有一个桃子了，求原有多天时就只有一个桃子了，求原有多少个桃？少个桃？数学模型：数学模型：每天的桃子数为：每天的桃子数为：a a1010=1,a=1,a9 9=(1+a=(1+a1010)*2,a2,a8 8=(1+a=(1+a9 9)*2 2 递推公式为：递推公式为：a ai i=(1+a=(1+ai+1i+1)*2 i=9,8,7,62 i=9,8,7,61 1【例例2 2】穿越沙漠问题穿越沙漠问题用一辆吉普车穿越用一辆吉普车穿越100010

25、00公里的沙漠。吉普车的总装油量为公里的沙漠。吉普车的总装油量为500500加仑，耗油率为加仑，耗油率为1 1加仑加仑/公里。由于沙漠中没有油库，必须先用公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。沙漠，应在什么地方建油库，以及各处的贮油量。【分析分析】先看一简单问题：先看一简单问题：有一位探险家用有一位探险家用5 5天的时间徒步横穿天的时间徒步横穿A A、B B两村，两村间是两村，两村间是荒无人烟的沙漠，如果一个人只能携带荒无人烟的沙漠，如果一个人只能

26、携带3 3天的食物和水，那么天的食物和水，那么这个探险家至少雇几个人才能顺利通过沙漠。这个探险家至少雇几个人才能顺利通过沙漠。【例例】核反应堆中有核反应堆中有和和两种粒子，每秒钟内一个两种粒子，每秒钟内一个粒子粒子可以反应产生可以反应产生3 3个个粒子，而一个粒子，而一个粒子可以反应产生粒子可以反应产生1 1个个粒子和粒子和2 2个个粒子。若在粒子。若在t=0t=0时刻的反应堆中只有一个时刻的反应堆中只有一个粒子粒子，求在，求在t t时刻的反应堆中时刻的反应堆中粒子和粒子和粒子数。粒子数。【分析分析】3 3.4.5 .4.5 特征根求解递归方程特征根求解递归方程时刻010103236363*3

27、+2*6i i-13*ai-1+2*bi-1【数学模型数学模型1 1】本题中共涉及两个变量，本题中共涉及两个变量，i i时刻时刻粒子数为粒子数为n ni i，粒子数为粒子数为m mi i，则有：，则有：n n0 0=1,m=1,m0 0=0,n=0,ni i=m=mi-1i-1，m mi i=3n=3ni-1i-1+2m+2mi-1i-13 3.4.5 .4.5 特征根求解递归方程特征根求解递归方程mainmain（）（）intint n100,m100,t,i;n100,m100,t,i;input(tinput(t););n0=1;/n0=1;/初始化操作初始化操作 m0=0;m0=0;f

28、or(i=1;i=for(i=1;i=t;it;i+)/+)/进行进行t t次递推次递推 nini=mi-1;=mi-1;mimi=3=3*ni-1+2 ni-1+2*mi-1;mi-1;print(ntprint(nt，mt);/);/输出结果输出结果【数学模型数学模型2 2】设在设在t t时刻的时刻的粒子数为粒子数为f f（t t），），粒子数为粒子数为g(tg(t)，依题可知：，依题可知：g(tg(t)=3f(t-1)+2g(t-1)=3f(t-1)+2g(t-1)（1 1）f(tf(t)=)=g(tg(t-1)-1)（2 2）g(0)=0,g(0)=0,f(0)=1 f(0)=1 整理

29、得：整理得：g(tg(t)=3g(t-2)+2g(t-1)=3g(t-2)+2g(t-1)（t2t2）（4 4）g(0)=0g(0)=0 g(1)=3 g(1)=33 3.4.5 .4.5 特征根求解递归方程特征根求解递归方程用特征根求得：用特征根求得：g(tg(t)=)=3 3.4.5 .4.5 特征根求解递归方程特征根求解递归方程tt)1(43343mainmain（）（）intint t,it,i;input(tinput(t););n=pow(3,t);/n=pow(3,t);/*n n代表代表a a粒子数量粒子数量*/m=pow(3,t+1);/m=pow(3,t+1);/*m m代

30、表代表B B粒子数量粒子数量*/if(t%2=1)if(t%2=1)n=n-3;m=m+3;n=n-3;m=m+3;else else n=n+3;m=m-3;n=n+3;m=m-3;n=int(n/4);n=int(n/4);m=int(m/4);m=int(m/4);print(n,mprint(n,m););3 3.4.5 .4.5 特征根求解递归方程特征根求解递归方程算法分析：在数学模型算法分析：在数学模型2 2中，中，运用数学的方法建立了递归函运用数学的方法建立了递归函数并转化为非递归函数。它的数并转化为非递归函数。它的优点是算法的复杂性与问题的优点是算法的复杂性与问题的规模无关。针

31、对某一具体数据，规模无关。针对某一具体数据，问题的规模对时间的影响微乎问题的规模对时间的影响微乎其微。其微。【例例1 1】百钱买百鸡百钱买百鸡【例例2 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 4.2.1 穷举法穷举法【例例2 2】解数字迷：解数字迷：A B C A B A D D D D D D算法设计

32、算法设计2：按除法枚举：按除法枚举 将算式变形为除法：将算式变形为除法：DDDDDD/A=ABCAB。此时。此时 A：39 D：19 共尝试共尝试7*9=63次。次。4.2.1 4.2.1 穷举法穷举法l本节将通过蛮力策略，用算法模拟问题中所描述的全部过程和全部状态，来找出问题的解，并与经过数学建模后的算法进行效率上的比较。4.2.2 4.2.2 其他范例其他范例【例12】某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的

33、规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，那些牢房的锁仍然是打开的？4.2.2 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 4.2.2 其他范例其他范例方法三：完全平方数的因数个数为奇数。for(i=1;i+)if（i*i=n）print(i,”is free.”);else break;4.2.2 4.2.2 其他范例其他范例