算法设计PPT学习教案

1、会计学1算法设计算法设计3 3.3 .3 优化算法的基本技巧优化算法的基本技巧【算法分析算法分析】（1 1）使用）使用ifif语句实现，但需要进行多次条件判断，而且嵌套的语句实现，但需要进行多次条件判断，而且嵌套的ifif语句降低了程序的可读性。语句降低了程序的可读性。（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、2：能被：能被3 3、5 5、7 7中的两个整除中的两个整除 k k为为3 3：能同时被：能同时被3 3、5 5、7 7整除整除第1页/共40页3 3.3 .3 优化算法的基本技巧优化算法的基本技巧（3 3）K%3=0K%5=0K%7=0全部1117其中2个110610150113其中1个1004010200110个0000第2页/共40页3 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(k) switch(k) ca

3、se 7: print(case 7: print(“allall”);break;);break; case 6: print( case 6: print(“3,53,5”);break;);break; case 5: print( case 5: print(“3,73,7”);break;);break; case 4: print case 4: print（”3 3”）；）；break;break; case 3: print( case 3: print(“5,75,7”);break;);break; case 2: print( case 2: print(“5 5”);b

4、reak;);break; case 1: print( case 1: print(“7 7”);break;);break; case 0: print( case 0: print(“NoneNone”);break;);break; 第3页/共40页3 3.4 .4 优化算法的数学模型优化算法的数学模型l选择恰当的数学模型，可以使算法的效率更高、占用空间更合理或使算法更简洁。选择恰当的数学模型，可以使算法的效率更高、占用空间更合理或使算法更简洁。l认识数学模型和数学建模认识数学模型和数学建模w一个关于数学模型的简单实例：已知有一个关于数学模型的简单实例：已知有5 5个数，求前四个数与第

5、五个数分别相乘后的最大数。个数，求前四个数与第五个数分别相乘后的最大数。 p106p106w算法算法1 1：w算法算法2 2：第4页/共40页3 3.4 .4 优化算法的数学模型优化算法的数学模型操作操作算法算法 乘法乘法赋值赋值条件判断条件判断 Max1 4 7 3 Max2 1 4 3第5页/共40页3 3.4 .4 优化算法的数学模型优化算法的数学模型w数学模型：是利用数学语言（符号、式子与图像）模拟现实的模型。数学模型：是利用数学语言（符号、式子与图像）模拟现实的模型。w基本特征：把现实模型抽象、简化为某种数据结构。基本特征：把现实模型抽象、简化为某种数据结构。w作用：作用：w解释特定

6、现象的现实状态解释特定现象的现实状态w预测到对象的未来状况预测到对象的未来状况w提供处理对象的最优决策或控制提供处理对象的最优决策或控制第6页/共40页3 3.4 .4 优化算法的数学模型优化算法的数学模型w数学建模：数学建模就是把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。数学建模：数学建模就是把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。w归纳法：归纳法：w

7、是通用而简单的数学建模方法是通用而简单的数学建模方法。w从分析问题的几种简单的、特殊的情况中，发现一般规律或作出某种猜想，从而找到解决问题的途径。从分析问题的几种简单的、特殊的情况中，发现一般规律或作出某种猜想，从而找到解决问题的途径。w归纳法是从简单到复杂，由个别到一般的一种研究方法。归纳法是从简单到复杂，由个别到一般的一种研究方法。第7页/共40页3 3.4.1 .4.1 杨辉三角形的应用杨辉三角形的应用【例题例题】求求n n次二项式各项的系数。次二项式各项的系数。已知二项式的展开式为：已知二项式的展开式为：分析：若只用的组合数学的知识，直接建模分析：若只用的组合数学的知识，直接建模问题：

8、算法中也要有大量的乘法和除法运算，效率很低。问题：算法中也要有大量的乘法和除法运算，效率很低。第8页/共40页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)(a+b)4 4 1 4 6 4 1 1 4 6 4 1(a+b)(a+b)5 5 数学模型：数学模型：n n次二项式的系数就是次二项式的系数就是

9、n n阶杨辉三角形。阶杨辉三角形。第9页/共40页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) print(ai);第10页/共40页3 3.4.2 .4.2 最大公约数的应用最大公约数的应用

10、【例题例题】数组中有数组中有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】利用一个数组存放原始数据，利用另外一个数组存放结果。利用一个数组存放原始数据，利用另外一个数组存放结果。第11页/共40页3 3.4.2 .4.2 最大公约数的应用最大公约数的应用l若题目限定：不能使用若题目限定：不能使用2 2* *n n以上的

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

12、 如如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）正好将全部数据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次移动就可完成整个移动过程。）正好将全部数据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次移动就可完成整个移动过程。第13页/共40页3 3.4.2 .4.2 最大公约数的应用最大公约数的应用

13、（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）两组移动才能将全部数据操作完毕。）两组移动才能将全部数据操作完毕。 循环移动的组数，与循环移动的组数，与k k、n n的是怎么样的关系呢？的是怎么样的关系呢？ 第14页/共4

14、0页3 3.4.2 .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。共进行二组循环移动，就能将全部数据移动完毕。共进行二组循环移动，就能将全部数据移动完毕。p数学模型：循环移动的组数等于数学模型：循环移动的组数等于N N与与K K的最大公约

15、数。的最大公约数。第15页/共40页3 3.4.2 .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)%nam a(m+k)%n a(m+2

16、k)%n第16页/共40页3 3.4.2 .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) ; 第17页/共40页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) /*共移

17、动m组*/ b0= aj; /*将每组的第一个数保存到b0中*/ tt=j; 3 3.4.2 .4.2 最大公约数的应用最大公约数的应用第18页/共40页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 3.4.2 .4.2 最大公约数的应用最大公约数的应用分析该算法中移动数据时的赋值次数第19页/共40页f=n/m;

18、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 最大公约数的应用最大公约数的应用第20页/共40页【例】编程完成下面给“余”猜数的游戏：你心里先想好一个1100之间的整数x，将它分别除以3、5和7并得到三个余数。你把这三个余数告诉计算机，计算机能马上猜出你心中的这个数。游戏过程如下：Please think of a number between 1 and 100Your number divided by 3 has a remainder of? 1your

19、 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 公倍数的应用公倍数的应用第21页/共40页【问题分析】算法设计的关键：找出余数与求解数之间的关系，建立问题的数学模型。【数学模型】 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 公倍数的应用公倍数的应用

20、第22页/共40页【模型建立】设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：则c3应除以7余1，c1,c2为7的倍数计算后，满足条件的c1=70 c2=21 c3=15 x=70*a+21*b+15*c若求解的d比100大，需要循环减去3，5，7的最小公倍数。第23页/共40页main( ) int a,b,c,d; input(a);/*除3后的余数*/

21、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个除数也由用户给出，请设计算法。第24页/共40页【例例】楼梯上有楼梯上有n n阶台阶，上楼可以一步上阶台阶，上楼可以一步上1 1阶，也可以一步上阶，也可以一步上2 2阶，编写算法计算共有多少种不同的上楼梯方法。阶，编写算法计算共有多少种不同的上楼梯方法。【数学模型数学模型】此问题如

22、果按照习惯，从前向后思考，也就是从第一阶开始，考虑怎么样走到第二阶、第三阶、第四阶此问题如果按照习惯，从前向后思考，也就是从第一阶开始，考虑怎么样走到第二阶、第三阶、第四阶，则很难找出问题的规律；而反过来先思考，则很难找出问题的规律；而反过来先思考“到第到第n n阶有哪几种情况？阶有哪几种情况？”，答案就简单了，只有两种情况：，答案就简单了，只有两种情况： 1 1） 从第从第n-1n-1阶到第阶到第n n阶；阶； 2 2） 从第从第n-2n-2阶到第阶到第n n阶。阶。3 3.4.4 .4.4 斐波那契数列的应用斐波那契数列的应用反向分析法反向分析法第25页/共40页记记n n阶台阶的走法数为

23、阶台阶的走法数为f(n)f(n)，则，则 f(n)= 1 n=1f(n)= 1 n=1 f(n)= 2 f(n)= 2 n=2 n=2 f(n)=f(n-1)+f(n-2) n2 f(n)=f(n-1)+f(n-2) n23 3.4.4 .4.4 斐波那契数列的应用斐波那契数列的应用第26页/共40页（2 2）倒推法：是对某些特殊问题所采用的从后向前推解问题的方法。）倒推法：是对某些特殊问题所采用的从后向前推解问题的方法。【例例3 3】猴子吃桃问题：一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第猴子吃桃问题：一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第1010天时就只有一个桃

24、子了，求原有多少个桃？天时就只有一个桃子了，求原有多少个桃？数学模型：数学模型： 每天的桃子数为：每天的桃子数为：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第27页/共40页【例例2 2】穿越沙漠问题穿越沙漠问题用一辆吉普车穿越用一辆吉普车穿越10001000公里的沙漠。吉普车的总装油量为公里的沙漠。吉普车的总装油量为500500加仑，耗油率为加仑，耗油

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

26、家至少雇几个人才能顺利通过沙漠。 第28页/共40页【例例】核反应堆中有核反应堆中有和和两种粒子，每秒钟内一个两种粒子，每秒钟内一个粒子可以反应产生粒子可以反应产生3 3个个粒子，而一个粒子，而一个粒子可以反应产生粒子可以反应产生1 1个个粒子和粒子和2 2个个粒子。若在粒子。若在t=0t=0时刻的反应堆中只有一个时刻的反应堆中只有一个粒子，求在粒子，求在t t时刻的反应堆中时刻的反应堆中粒子和粒子和粒子数。粒子数。【分析分析】3 3.4.5 .4.5 特征根求解递归方程特征根求解递归方程时刻010103236363*3+2*6i i-13*ai-1+2*bi-1第29页/共40页【数学模型数

27、学模型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（）（） 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+) /

28、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(ntprint(nt，mt); /); /输出结果输出结果 第30页/共40页【数学模型数学模型2 2】设在设在t t时刻的时刻的粒子数为粒子数为f f（t 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）

29、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)=0g(0)=0 g(1)=3 g(1)=33 3.4.5 .4.5 特征根求解递归方程特征根求解递归方程第31页/共40页用特征根求得：用特征根求得： g(t)= g(t)= = =3 3.4.5 .4.5 特征根求解递归方程特征根求解递归方程tt)1(43343第32页/共40页mainmain（）（） int t,i; int t,i; input(t); input(t); n=pow(3,t)

30、; / 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; 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 3.4.5 .4.5 特征根求解递归方程特征根求解递归方程算法分析：在数学模型算法分析：在数学模型2 2中，中，运用数学的方法建立了递归函运用数学的方法建立了递归函数并转化为非递归函数。它的数并转化为非递归函数。它的优点是算法的复杂性与问题的优点是算法的复杂性与问题的规模无关。针对某一具体数据，规模无关。针对某一具体数据，问题的规模对时间的影响微乎问题的规模对时间的影响微