算法设计：第九讲2013.ppt

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）使用表达式 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; 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 优化算法的数学模型,数学模型：是利用数学语言（符号、式子与图像）模拟现实的模型。 基本特征：把现实模型抽象、简化为某种数据结构。 作用： 解释特定现象的现实状态 预测到对象的未来状况 提供处理对象的最优决策或控制,3.4 优化算法的数学模型,数学建模：数学建模就是把现实世界中的实际问题加以提炼，抽象为数学模型，求出模型的解，验证模型的合理性，并用该数学模型所提供的解答来解释现实问题，我们把数学知识的这一应用过程称为数学建模。 归纳法： 是通用而简单的数学建模方法。 从分析问题的几种简单的、特殊的情况中，发现一般规律或作出某种猜想，从而找到解决问题的途径。 归纳法是从简单到复杂，由个别到一般的一种研究方法。,3.4.1 杨辉三角形的应用,【例题】求n次二项式各项的系数。 已知二项式的展开式为： 分析：若只用的组合数学的知识，直接建模 问题：算法中也要有大量的乘法和除法运算，效率很低。,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 ); 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】利用一个临时变量，将每一个数据一次移动到位 （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）两组移动才能将全部数据操作完毕。 循环移动的组数，与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+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; /*计算移动的目标位置*/ 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并得到三个余数。你把这三个余数告诉计算机，计算机 能马上猜出你心中的这个数。游戏过程如下： Please think of a number between 1 and 100 Your number divided by 3 has a remainder of? 1 your number divided by 5 has a remainder of? 0 your number divided by 7 has a remainder of? 5 your number is 40,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 公倍数的应用,【模型建立】设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的最小公倍数。,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阶，编写算法计算共有多少种不同的上楼梯方法。 【数学模型】此问题如果按照习惯，从前向后思考，也就是从第一阶开始，考虑怎么样走到第二阶、第三阶、第四阶，则很难找出问题的规律；而反过来先思考“到第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+a9)*2 递推公式为：ai=(1+ai+1)*2 i = 9,8,7,61,【例2】穿越沙漠问题 用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。 【分析】先看一简单问题： 有一位探险家用5天的时间徒步横穿A、B两村，两村间是荒无人烟的沙漠，如果一个人只能携带3天的食物和水，那么这个探险家至少雇几个人才能顺利通过沙漠。,【例】核反应堆中有和两种粒子，每秒钟内一个粒子可以反应产生3个粒子，而一个粒子可以反应产生1个粒子和2个粒子。若在t=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(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 特征根求解递归方程,算法分析：在数学模型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：按除法枚举 将算