算法设计：第九讲2019ppt课件

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

2、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其中1个

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

5、7”);break; case 4: 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: print(“None”);break; case 0: print(“None”);break; 3.4 3.4 优化算法的数学模型优化算法

6、的数学模型l选择恰当的数学模型，可以使算法的效率更高、占用空间更选择恰当的数学模型，可以使算法的效率更高、占用空间更合理或使算法更简洁。合理或使算法更简洁。l认识数学模型和数学建模认识数学模型和数学建模l一个关于数学模型的简单实例：已知有一个关于数学模型的简单实例：已知有5 5个数，求前四个数与个数，求前四个数与第五个数分别相乘后的最大数。第五个数分别相乘后的最大数。 p106 p106l算法算法1 1：l算法算法2 2：3.4 3.4 优化算法的数学模型优化算法的数学模型操作操作算法算法 乘法乘法赋值赋值条件判断条件判断 Max1 4 7 3 Max2 1 4 33.4 3.4 优化算法的数

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

8、抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。数学知识的这一应用过程称为数学建模。w归纳法：归纳法：w是通用而简单的数学建模方法。是通用而简单的数学建模方法。w从分析问题的几种简单的、特殊的情况中，发现一般规律从分析问题的几种简单的、特殊的情况中，发现一般规律或作出某种猜想，从而找到解决问题的途径。或作出某种猜想，从而找到解决问题的途径。w归纳法是从简单到复杂，由个别到一般的一种研究方法。归纳法是从简单到复杂，由个别到一般的一种研究方法。3.4.1 3.4.1

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

10、b)3 1 (a+b)3 1 3 3 13 3 1(a+b)4 1 4 6 4 1(a+b)4 1 4 6 4 1(a+b)5 (a+b)5 数学模型：数学模型：n n次二项式的系数就是次二项式的系数就是n n阶杨辉三角形。阶杨辉三角形。3.4.1 3.4.1 杨辉三角形的应用杨辉三角形的应用求求n n阶杨辉三角形的递归算法：阶杨辉三角形的递归算法：ff(inta,intn)if(n=1)a1=1;a2=1;elseff(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

11、 ); ff(a,n); for(i=1;i=n+1;i=i+1) print(ai);3.4.2 3.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】利用一个数组存放原始数据，利用另外一个数组存】利用一个数组存放原始数据，利用另外一个数组存放结果

12、。放结果。3.4.2 3.4.2 最大公约数的应用最大公约数的应用l若题目限定：不能使用若题目限定：不能使用2 2* *n n以上的空间来实现此题。以上的空间来实现此题。 l【实现【实现2 2】利用】利用k k次循环，每次移动一位。次循环，每次移动一位。l （1 1先把先把anan保存到临时单元保存到临时单元temptempl （2 2将将an-1anan-1an，an-2 an-1an-2 an-1l （3 3将将temp a0temp a0中中3.4.2 3.4.2 最大公约数的应用最大公约数的应用【实现【实现3 3】利用一个临时变量，将每一个数据一次移动到位】利用一个临时变量，将每一个数

13、据一次移动到位（1 1一组循环移动的情况：一组循环移动的情况： 通过计算我们可以确定某个元素移动后的具体位置，通过计算我们可以确定某个元素移动后的具体位置， 如如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。 可通过计算得出可通过计算得出0303，3131，1 41 4，4242，2020； 一组移动一组移动0-3-1-4-2-00-3-1-4-2-0正好将全部数据按要求进行了正好将全部数据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次移动就可移动。这样只需要一个辅助变量，每个数

14、据只需一次移动就可完成整个移动过程。完成整个移动过程。3.4.2 3.4.2 最大公约数的应用最大公约数的应用（2 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两组移动才能将全部两组移动才能将全部数据操作完毕。数据操作完毕。 循环移动的组数，

15、与循环移动的组数，与k k、n n的是怎么样的关系呢？的是怎么样的关系呢？ 3.4.2 3.4.2 最大公约数的应用最大公约数的应用我们再看一个例子：我们再看一个例子：当当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。共进行二组循环移动，就能将全部数据移动完。共进行二组循环移动，就能将全部数据移动完毕。毕。数学模型：循环

16、移动的组数等于数学模型：循环移动的组数等于N N与与K K的最大公约数。的最大公约数。3.4.2 3.4.2 最大公约数的应用最大公约数的应用算法设计：算法设计：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组：组： am a(m+k)%n a(m+2k)%

17、n am a(m+k)%n a(m+2k)%n3.4.2 3.4.2 最大公约数的应用最大公约数的应用/*求求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)

18、/*共移动m组*/ b0= aj; /*将每组的第一个数保存到b0中*/ tt=j; 3.4.2 3.4.2 最大公约数的应用最大公约数的应用for(i=0;in/m;i=i+1) /*每组中共有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.4.2 3.4.2 最大公约数的应用最大公约数的应用分析该算法中移动数据时的赋值次数f=n/m;for(j=0;j0;i-) a

19、(j+i*k)%n=a(j+(i-1)*k)%n;/*从后向前移动*/ aj=b; /*把该组的最后一个数送到aj处*/ 3.4.2 3.4.2 最大公约数的应用最大公约数的应用【例】编程完成下面给“余猜数的游戏：你心里先想好一个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

20、remainder of? 0your number divided by 7 has a remainder of? 5your number is 403.4.3 3.4.3 公倍数的应用公倍数的应用【问题分析】算法设计的关键：找出余数与求解数之间的关系，建立问题的数学模型。【数学模型】 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.4.3 3.4.3 公倍数的应用公倍数的应用【模型建立】设a,b,c分别是该数除以3，5，7后的余数，则该数为： x=c1*

21、a+c2*b+c3*c3.4.3 3.4.3 公倍数的应用公倍数的应用分析：（1x除以3余a：则c1应除以3余1，c2,c3为3的倍数（2x除以5余b：则c2应除以5余1，c1,c3为5的倍数（3x除以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的最小公倍数。main( ) int a,b,c,d; input(a);/*除3后的余数*/ input(b);/*除5后的余数*/ input(c);/*除7后的余数*/ d=70*a+21*b+15*c; whil

22、e (d100) d=d-105;/*105为3,5,7的最小公倍数*/ print( “your number is ”, d); 3.4.3 3.4.3 公倍数的应用公倍数的应用思索：3个除数也由用户给出，请设计算法。【例】楼梯上有【例】楼梯上有n n阶台阶，上楼可以一步上阶台阶，上楼可以一步上1 1阶，也可以一步阶，也可以一步上上2 2阶，编写算法计算共有多少种不同的上楼梯方法。阶，编写算法计算共有多少种不同的上楼梯方法。【数学模型】此问题如果按照习惯，从前向后思考，也就是【数学模型】此问题如果按照习惯，从前向后思考，也就是从第一阶开始，考虑怎么样走到第二阶、第三阶、第四阶从第一阶开始，

23、考虑怎么样走到第二阶、第三阶、第四阶，则很难找出问题的规律；而反过来先思考，则很难找出问题的规律；而反过来先思考“到第到第n n阶有阶有哪几种情况？哪几种情况？”，答案就简单了，只有两种情况：，答案就简单了，只有两种情况： 1 1） 从第从第n-1n-1阶到第阶到第n n阶；阶； 2 2） 从第从第n-2n-2阶到第阶到第n n阶。阶。3.4.4 3.4.4 斐波那契数列的应用斐波那契数列的应用反向分析法反向分析法记记n n阶台阶的走法数为阶台阶的走法数为f(n)f(n)，那么，那么 f(n)= 1 n=1 f(n)= 1 n=1 f(n)= 2 f(n)= 2 n=2 n=2 f(n)=f(

24、n-1)+f(n-2) n2 f(n)=f(n-1)+f(n-2) n23.4.4 3.4.4 斐波那契数列的应用斐波那契数列的应用（2 2倒推法：是对某些特殊问题所采用的从后向前推解问题倒推法：是对某些特殊问题所采用的从后向前推解问题的方法。的方法。【例【例3 3】猴子吃桃问题：一只小猴子摘了若干桃子，每天吃现】猴子吃桃问题：一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第有桃的一半多一个，到第1010天时就只有一个桃子了，求原有多天时就只有一个桃子了，求原有多少个桃？少个桃？数学模型：数学模型： 每天的桃子数为：每天的桃子数为：a10=1, a9=(1+a10)a10=1, a9=(

25、1+a10)* *2, a8=(1+a9)2, a8=(1+a9)* *2 2 递推公式为：递推公式为：ai=(1+ai+1)ai=(1+ai+1)* *2 i = 9,8,7,612 i = 9,8,7,61【例【例2 2】穿越沙漠问题】穿越沙漠问题用一辆吉普车穿越用一辆吉普车穿越10001000公里的沙漠。吉普车的总装油量为公里的沙漠。吉普车的总装油量为500500加仑，耗油率为加仑，耗油率为1 1加仑加仑/ /公里。由于沙漠中没有油库，必须先用公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠

26、，应在什么地方建油库，以及各处的贮油量。沙漠，应在什么地方建油库，以及各处的贮油量。【分析】先看一简单问题：【分析】先看一简单问题： 有一位探险家用有一位探险家用5 5天的时间徒步横穿天的时间徒步横穿A A、B B两村，两村间是两村，两村间是荒无人烟的沙漠，如果一个人只能携带荒无人烟的沙漠，如果一个人只能携带3 3天的食物和水，那么天的食物和水，那么这个探险家至少雇几个人才能顺利通过沙漠。这个探险家至少雇几个人才能顺利通过沙漠。 【例】核反应堆中有【例】核反应堆中有和和两种粒子，每秒钟内一个两种粒子，每秒钟内一个粒子粒子可以反应产生可以反应产生3 3个个粒子，而一个粒子，而一个粒子可以反应产生

27、粒子可以反应产生1 1个个粒子和粒子和2 2个个粒子。若在粒子。若在t=0t=0时刻的反应堆中只有一个时刻的反应堆中只有一个粒子粒子，求在，求在t t时刻的反应堆中时刻的反应堆中粒子和粒子和粒子数。粒子数。【分析】【分析】3.4.5 3.4.5 特征根求解递归方程特征根求解递归方程时刻010103236363*3+2*6i i-13*ai-1+2*bi-1【数学模型【数学模型1 1】本题中共涉及两个变量，】本题中共涉及两个变量，i i时刻时刻粒子数为粒子数为nini，粒子数为粒子数为mimi，则有：，则有：n0=1,m0=0,ni=mi-1n0=1,m0=0,ni=mi-1，mi=3ni-mi

28、=3ni-1+2mi-11+2mi-13.4.5 3.4.5 特征根求解递归方程特征根求解递归方程mainmain（）（） int n100,m100,t,i; int n100,m100,t,i; input(t); input(t); n0=1; / n0=1; /初始化操作初始化操作 m0=0; m0=0; for (i=1;i=t;i+) / for (i=1;i=t;i+) /进行进行t t次递推次递推 ni=mi-1; ni=mi-1; mi=3 mi=3 * * ni-1 + 2 ni-1 + 2 * * mi-1; mi-1; print(nt print(nt，mt); /m

29、t); /输出结果输出结果 【数学模型【数学模型2 2】设在】设在t t时刻的时刻的粒子数为粒子数为f ft t），），粒子数为粒子数为g(t)g(t)，依题可知：，依题可知： g(t)=3f(t -1)+2g(t -1) g(t)=3f(t -1)+2g(t -1) （1 1） f(t)=g(t -1) f(t)=g(t -1) （2 2） g(0)=0, g(0)=0, f(0)=1 f(0)=1 整理得：整理得： g(t)=3g(t-2)+2g(t-1) g(t)=3g(t-2)+2g(t-1) （t2t2） （4 4） g(0)=0 g(0)=0 g(1)=3 g(1)=33.4.5

30、3.4.5 特征根求解递归方程特征根求解递归方程用特征根求得：用特征根求得： g(t)= g(t)= = =3.4.5 3.4.5 特征根求解递归方程特征根求解递归方程tt)1(43343mainmain（）（） int t,i; int t,i; input(t); input(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代表代表B B粒子数量粒子数量* */ / if(t%2=1) if(t%2=1) n=n-3; m=m+3; n=n-3;

31、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,m); print(n,m); 3.4.5 3.4.5 特征根求解递归方程特征根求解递归方程算法分析：在数学模型算法分析：在数学模型2 2中，中，运用数学的方法建立了递归函运用数学的方法建立了递归函数并转化为非递归函数。它的数并转化为非递归函数。它的优点是算法的复杂性与问题的优点是算法的复杂性与问题的规模无关。针对某一具体数据，规模无关。针对某一具体数据，问题的规模对时间的影响微乎问题的规模对时间的影响微乎其微。其微。【例【例1 1】百钱买百鸡】百钱买百鸡【例【例2 2】解数字迷：】解数字迷： A B C