《算法基本工具(Part3).ppt》由会员分享，可在线阅读，更多相关《算法基本工具(Part3).ppt（20页珍藏版）》请在三一办公上搜索。
1、1,算法基本工具,主要内容,2.1 循环与递归2.2 算法与数据结构2.3 优化算法的数学模型,2,3,2.3优化算法的数学模型,说到数学建模，有好多人感到不知所云，下面我们看一个很简单的例子：已知有五个数，求前四个数与第五个数分别相乘后的最大当数。给出两个算法分别如下：,max1(int a,b,c,d,e)max2(int a,b,c,d,e)int x;int x a=a*e;if(ab)b=b*e;x=a;c=c*e;else d=d*e;x=b;if(ab)if(cx)x=a;x=c;else if(dx)x=b;x=d;if(cx)x=x*e;x=c;print(x);if(dx)
2、x=d;print(x);,以上两个算法基于的数学模型是不同的，一个算法先积再求最大值，另一个算法先求最大值再求积，求从上表可以看出，后一个算法的效率明显要高于前一个算法。,数学建模就是把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。,2数学建模的基本方法从分析问题的几种简单的、特殊的情况中，发现一般规律或作出某种猜想，从而找到解决问题的途径。这种研究问题方法叫做归纳法。即归纳法是从简单到复杂，由个别到一般的一种研究方法。,2.3.1 杨辉三角形的应用,【例】求n次二项式各项的系
3、数：已知二项式的展 开式为：问题分析：若只用的数学组合数学的知识，直接建模 k=0，1，2，3n。用这个公式去计算，n+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阶杨辉三角形。,算法设计要点：除了首尾两项系数为1外，当n1时，(a+b)n的中间各项系数是(a+b)n-1的相应两项系数之和，如果把(a+b)n的n+1的系数列为数
4、组c，则除了c(1)、c(n+1)恒为1外，设(a+b)n的系数为c(i)，(a+b)n-1 的系数设为c(i)。则有：c(i)=c(i)+c(i-1)而当n=1时，只有两个系数 c(1)和 c(2)(值都为1)。不难看出，对任何n,(a+b)n的二项式系数可由(a+b)n-1的系数求得，直到n=1时，两个系数有确定值，故可写成递归子算法。,coeff(int a,int n)if(n=1)a1=1;a2=1;else coeff(a,n-1);an+1=1;for(i=n;i=2;i-)ai=ai+ai-1;a1=1;,main()int a100,i,n;input(n);for(i=1;
5、i=n;i=i+1)input(ai);coeff(a,n);for(i=1;i=n;i=i+1)print(ai);,2.3.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 remainder of?0yo
6、ur number divided by 7 has a remainder of?5let me think a momentyour number was 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的余数也是一样的。证明如下：c 除以 3余数为1，记c=3*k+1，则s=u+3*k*u+3*v+3*w，由1)的结论，上述结论正确。记a，b，c分别为所猜数据d除以3，5，7后的余数
7、，则 d=70*a+21*b+15*c。为问题的数学模型，其中70称作a的系数，21称作b的系数,15称作c的系数。,由以上数学常识，a、b、c的系数必须满足：1）b、c的系数能被3整除，且a的系数被3整除余1；这样d除以3的余数与a相同。2）a、c的系数能被5整除，且b的系数被5整除余1；这样d除以5的余数与b相同。3)a、b的系数能被7整除，且c的系数被7整除余1；这样d除以7的余数与c相同。由此可见：c的系数是3和5的最公倍数且被7整除余1，正好是15；a的系数是7和5的最公倍数且被3整除余1，最小只能是70；b的系数是7和3的最公倍数且被5整除余1，正好是21。,算法设计：用以上模型求
8、解的数d，可能比100大，这时只要减去3，5，7的最小公倍数就是问题的解了。main()int a,b,c,d;print(“please think of a number between 1 and 100.”);print(“your number divided by 3 has a remainker of”);input(a);print(“your number divided by 5 has a remainker of”);input(b);print(“your number divided by 7 has a remainker of”);input(c);print
9、(“let me think a moment”);for(i=1,i105)d=d-105;print(“your number was”,d);,2.3.3 递推关系求解方程,【例】核反应堆中有和两种粒子，每秒钟内一个粒子可以反应产生3个粒子，而一个粒子可以反应产生1个粒子和2个粒子。若在t=0时刻的反应堆中只有一个粒子，求在t时刻的反应堆中粒子和粒子数。数学模型1：本题中共涉及两个变量，设在i时刻粒子数为ni，粒子数为mi，则有：n0=1,m0=0,ni=mi1，mi=3ni1+2mi1 算法设计1：本题方便转化为求数列N和M的第t项，可用递推的方法求得nt和mt，此模型的算法如下：,m
10、ain（）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);/输出结果 print(mt);,算法分析1：此模型的空间需求较小，时间复杂度为O（n），但随着n的增大，所需时间越来越大，即：,数学模型2：设在t时刻的粒子数为f（t），粒子数为g(t)，依题可知：g(t)=3f(t-1)+2g(t-1)（1）f(t)=g(t-1)（2）g(0)=0,f(0)=1 下面求解这个递归函数的非递归形式 由（2）得f(t-1)=g(t-2)（3）将（3）
11、代入（1）得 g(t)=3g(t-2)+2g(t-1)（t2）（4）g(0)=0,g(1)=3（4）式的特征根方程为：x22x3=0其特征根为x1=3,x2=-1,所以该式的递推关系的通解为g(t)=C13t+C2(-1)t代入初值g(0)=0,g(1)=3得C1+C2=03C1C2=3解此方程组所以该递推关系的解为g(t)=即,由数学模型2，设计算法2如下main（）int t,i;input(t);n=int(exp(t*ln(3);m=int(exp(t+1)*ln(3);if(t mod 2=1)n=n-3;m=m+3;else n=n+3;m=m-3;n=int(n/4);/4|n m=int(m/4);/4|m print(n);print(m);,算法分析：在数学模型2中，运用数学的方法建立了递归函数并转化为非递归函数。它的优点是算法的复杂性与问题的规模无关。针对某一具体数据，问题的规模对时间的影响微乎其微。,
