算法基本工具-pa.ppt

1,算法基本工具,主要内容,2.1 循环与递归2.2 算法与数据结构2.3 优化算法的数学模型,2,3,2.1 循环与递归,设计算法重复处理大量数据的思路：以不变应万变；所谓“不变”是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。两种思路：循环、递归。,1 循环设计要点2 递归设计思路(运行机制、复杂度分析)3 递归设计要点4 非递归(循环)/递归比较,4,1 循环设计要点,循环控制-熟悉；设计要点：“自顶向下”的设计方法 由具体到抽象设计循环结构注意算法的效率,5,1 循环设计要点-例2.1,例2.1 编算法找出1000以内所有完数。如：28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数，并按下面格式输出其因子：28 its factors are 1，2，4，7，14。,问题分析：1、这里不是要质因数，所以找到因数后也无需将其从数据中“除掉”。2、每个因数只记一次，如8的因数为1，2，4而不是1，2，2，2，4。(注：本题限定因数不包括这个数本身),6,1 循环设计要点-例2.1,核心算法设计for(i=0;in;i=i+1)判断i是否是完数;if是“完数”则按规则输出;,自顶向下，逐步求精,判断i是否是完数for(j=2;ji;j=j+1)找i的因子，并累加；if 累加值等于i，则i是完数；,判断i是否是完数s=1；for(j=2;ji;j=j+1)if(i%j=0)s=s+j;if(s=i)i是“完数”;,判断是否是完数的方法是“不变”，被判断的数是“万变”。,7,1 循环设计要点-例2.1,考虑到要按格式输出结果，应该开辟数组存储数据i的所有因子，并记录其因子的个数，因此算法细化如下：,int a100，s=1,k=0;for(j=2;ji;j=j+1)if(i%j=0)s=s+j;ak=j;k=k+1;,if(s=i)print(s,“its factors are:”,1);for(j=0;jk;j+)print(“,”,aj);,8,1 循环设计要点-例2.2,对于不太熟悉的问题，其“不变”不易抽象；,1 6 2 10 7 3 13 11 8 4 15 14 12 9 5n=5,例2.2 编写算法：根据参数n打印具有下面规律的图形，如，当n=4时，图形如下：1 5 2 8 6 3 10 9 7 4,9,1 循环设计要点-例2.2,1 5 2 8 6 3 10 9 7 4,问题分析：容易发现图形中数据排列的规律。,另一种思路先用一个数组按此顺序存储数据，再正常输出；,1 5 2 8 6 3 10 9 7 4,可不可以从1最大数，通过循环，直接输出？,printf是按照从左至右、从上至下的顺序；若想直接输出，只有找出公式，循环计算得到序列：1-n-5-2-n-8-6-3-n-10-9-7-4.,为数组赋值，也要用循环，如何循环？又要回到找规律公式的路上吗？,斜着能循环吗？让循环泼辣一点。,10,1 循环设计要点-例2.2,用斜行、列描述新的循环方向。,1 5 2 8 6 3 10 9 7 4,斜1，1a1,1斜1，2a2,2斜1，3a3,3斜1，4a4,4,斜2，1a2,1斜2，2a3,2斜2，3a4,3,列号相同；行号(显然行号与列号有关)第1斜行，对应行号1n，行号与列号j同；第2斜行，对应行号2n，行号比列号j大1；第3斜行，对应行号3n，行号比列号j大2；,斜3，1a3,1斜3，2a4,2,斜行i取值(1n)列j取值(1n+1-i),ai-1+jj,这样可以描述循环。但数组元素的存取还是基于“行列”，能否简单转换？,关键问题：第i斜行、j列的数据对应于第几行第几列的元素？,斜4，1a4,1,11,1 循环设计要点-例2.2,main()int i,j,a100100,n,k;input(n);k=1;for(i=1;i=n;i=i+1)for(j=1;j=n+1-i;j=j+1)ai-1+jj=k;k=k+1;for(i=1;i=n;i=i+1)print(“换行符”);for(j=1;j=i;j=j+1)print(aij);,斜行i取值(1n)列j取值(1n+1-i),1 5 2 8 6 3 10 9 7 4,12,1 循环设计要点-例2.3,例2.3 求级数求：1/1!-1/3!+1/5!-1/7!+(-1)n+1/(2n-1)!,问题分析：此问题中既有累加又有累乘，累加的对象是累乘的结果。数学模型1：Sn=Sn-1+(-1)n+1/(2n-1)!算法设计1：直接利用题目中累加项通式，构造出循环体不变式为：S=S+(-1)n+1/(2n-1)!需要用二重循环来完成算法。,算法设计1：外层循环求累加S=S+A;内层循环求累乘A=(-1)n+1/(2n-1)!。,算法如下：,求（-1）n+1 for(j=1;j=i+1;j=j+1)sign=sign*(-1);s=s+sign/t;print(“Snm=”,s);,main()int i,n,j,sign=1;float s,t=1;input(n);s=1；for(i=2;i=n;i=i+1)t=1;求阶乘 for(j=1;j=2*i-1;j=j+1)t=t*j;sign=1;,14,1 循环设计要点-例2.3,以上算法是二重循环来完成，但算法的效率却太低O(n2)。,数学模型2：Sn=Sn-1+(-1)n+1An；An=An-1*1/(2*n-2)*(2*n-1),其原因是，当前一次循环已求出7！，当这次要想求9！时，没必要再从1去累乘到9，只需要充分利用前一次的结果，用7！*8*9即可得到9！，模型为An=An-1*1/(2*n-2)*(2*n-1)。,15,main()int i,n,sign;float s,t=1;input(n);s=1；sign=1;for(i=2;i=n;i=i+1)或 for(i=1;i=n-1;i=i+1)sign=-sign;sign=-sign;t=t*(2*i-2)*(2*i-1);t=t*2*i*(2*i+1);s=s+sign/t;s=s+sign/t;print(“Sum=”,s);,算法分析：按照数学模型2，只需一重循环就能解决问题算法的时间复杂性为O(n)。,16,2 递归设计思路-例2.4,程序结构化设计的三种基本结构，顺序、选择、循环是不是必须的？,例2.4根据参数n，计算1+2+n。,void sum_loop(int n)int i,sum=0;for(i=1;i=n;i+)sum=sum+i;printf(nsum=%d,sum);,回答：在很多高级语言中，不是。可以抛弃谁呢？,递归能取代循环的作用。,17,2 递归设计思路-例2.4,例2.4 根据参数n，计算1+2+n。,int sum_recursive(int n)int sum=0;if(n=1)sum=1;else sum=sum_recursive(n-1)+n;printf(nsum=%d,sum);return sum;,sum(n),递归算法是一个模块(函数、过程)除了可调用其它模 块(函数、过程)外，还可以直接或间接地调用自身的算法。直接/间接递归调用。,代入n=4，走一遍。,递归树！,18,2 递归设计思路-例2.4,例2.4 根据参数n，计算1+2+n。,int sum_recursive(int n)int sum=0;if(n=1)sum=1;else sum=sum_recursive(n-1)+n;printf(nsum=%d,sum);return sum;,栈顶(top),栈底(bottom),出栈,进栈,栈底元素,栈顶元素,表面上是一个变量，实际上是一个栈,19,2 递归设计思路-例2.4,例2.4 根据参数n，计算1+2+n。,int sum_recursive(int n)int sum=0;if(n=1)sum=1;else sum=sum_recursive(n-1)+n;printf(nsum=%d,sum);return sum;,T(n)=T(n-1)+O(1),=T(n-2)+O(1)+O(1),=.,=n*O(1)=O(n),20,“收敛”,3 递归设计要点,递归的关键在于找出递归方程式和递归终止条件。递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。递归边界条件：也就是所描述问题的最简单情况，它本身不再使用递归的定义。,int sum_recursive(int n)int sum=0;if(n=1)sum=1;else sum=sum_recursive(n-1)+n;printf(nsum=%d,sum);return sum;,21,例1.1 欧几里德算法,gcd(m,n)=gcd(n,m mod n)输入 正整数m和n 输出 m和n的最大公因子如果n=0,计算停止返回m,m即为结果；否则继续2。记r为m除以n的余数，即r=m mod n。把n赋值给m，把r赋值给n，继续1。伪代码如下(循环)：Euclid(m,n)while n 0 r=m n;m=n;n=r;,递归代码：GCD(m,n)/约定mn/if n=0 return(m)else return(GCD(n,m mod n),22,GCD(22,8),GCD(8,6),GCD(6,2),GCD(2,0),2,递推,递推,递推,递推,回归,回归,回归,回归,结果为GCD(22,8)=2,例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;,23,3 递归设计要点-hanoi塔,Hanoi塔hanoi河内越南首都古代有一个梵塔，塔内有3个基座A、B、C，开始时A基座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A座移到B座，但每次只允许移动一个盘子，且在移动过程中在3个基座上的盘子都始终保持大盘在下，小盘在上。在移动过程中可以利用C基座做辅助。请编程打印出移动过程。约定盘子自上而下的编号为1，2，3，n。,24,3 递归设计要点-hanoi塔,首先看一下2阶汉诺塔问题的解，不难理解以下移动过程：初始状态为 A(1,2)B()C()第一步后 A(2)B()C(1)第二步后 A()B(2)C(1)第三步后 A()B(1,2)C(),用递归思路考虑,25,3 递归设计要点-hanoi塔,把n个盘子抽象地看作“两个盘子”，上面“一个”由1n-1号组成，下面“一个”就是n号盘子。移动过程如下：第一步：先把上面“一个”盘子以a基座为起点借助b基座移到c基座。第二步：把下面“一个”盘子从a基座移到b基座。第三步：再把c基座上的n-1盘子借助a基座移到b基座。,递归：领导的艺术,26,3 递归设计要点-hanoi塔,把n阶的汉诺塔问题的模块记作hanoi(n,a,b,c)a代表每一次移动的起始基座；b代表每一次移动的终点基座；c代表每一次移动的辅助基座；则hanoi(n,a,c,b)，表示把n个盘子从a搬到c，可以借助b；hanoi(5,c,a,b)，表示把5个盘子从c搬到a，可以借助b。,则汉诺塔问题hanoi(n,a,b,c)等价于以下三步：第一步，hanoi(n-1,a,c,b)；第二步，把下面“一个”盘子从a基座移到b基座；第三步，hanoi(n-1,c,b,a)。至此找出了大规模问题与小规模问题的关系。,27,3 递归设计要点-hanoi塔,hanoi(n,a,b,c)a：起始基座b：终点基座c：辅助基座,hanoi(n,a,b,c),hanoi(n-1,a,c,b),hanoi(n-1,c,b,a),移,hanoi(n-2,a,b,c),hanoi(n-2,b,c,a),移,hanoi(2,.,.,.),hanoi(2,.,.,.),移,hanoi(1,.,.,.),移,hanoi(1,.,.,.),hanoi(0,.,.,.),/,hanoi(0,.,.,.),O(2n),28,3 递归设计要点-hanoi塔,hanoi(int n,char a,char b,char c)/*a,b,c 初值为”A”,”B”,”C”*/if(n0)/*0阶的汉诺塔问题当作停止条件*/hanoi(n-1,a,c,b);输出“Move dish”,n.”from pile”,a,”to”b);hanoi(n-1,c,b,a);,3 递归设计要点-整数的分划问题,对于一个正整数n的分划就是把n写成一系列正整数之和的表达式。例如，对于正整数n=6，它可以分划为：6 5+1 4+2,4+1+1 3+3,3+2+1,3+1+1+1 2+2+2,2+2+1+1,2+1+1+1+1 1+1+1+1+1+1,根据例子发现“包括第一行以后的数据不超过6，包括第二行的数据不超过5，第6行的数据不超过1”。因此，定义一个函数Q(n,m)，表示整数n的“任何被加数都不超过m”的分划的数目，n的所有分划的数目P(n)=Q(n,n)。,模型建立：,一般地Q(n.m)有以下递归关系：1)Q(n,n)=1+Q(n,n-1)（m=n）Q(n,n-1)表示n的所有其他分划，即最大被加数m=n-1的划分。2)Q(n,m)=Q(n,m-1)+Q(n-m,m)(mn)Q(n,n-1)表示被加数中不包含m的分划的数目；Q(n-m,m)表示被加数中包含(注意不是小于)m的分划的数目，,递归的停止条件：1)Q(n,1)=1，表示当最大的被加数是1时，该整数n只有一种分划，即n个1相加；2)Q(1,m)=1，表示整数n=1只有一个分划，不管最大被加数的上限m是多大。,算法如下：,Divinteger(n,m)if（n n）Error(“输入参数错误”)；/*nm Q(n,m)是无意义的*/else if（n=1 or m=1）return（1）；else if（n m）return Divinteger(n,n)else if（n=m）return(1+Divinteger(n,n-1)else return(Divinteger(n,m-1)+Divinteger(n-m,m);,31,递归与循环的比较,递归与循环都是解决“重复操作”的机制。递归使一些复杂的问题处理起来简单明了。就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间（调用和返回均需要额外的时间）与存贮空间（用来保存不同次调用情况下变量的当前值的栈栈空间），也限制了递归的深度。每个迭代算法原则上总可以转换成与它等价的递归算法；反之不然。递归的层次是可以控制的，而循环嵌套的层次只能是固定的，因此递归是比循环更灵活的重复操作的机制。,32,下面通过几个具体的例子来说明循环和递归的差异和优劣。【例1】任给十进制的正整数，请从低位到高位逐位输出各位数字。循环算法设计：从题目中我们并不能获知正整数的位数，再看题目的要求，算法应该从低位到高位逐位求出各位数字并输出。详细设计如下：1）求个位数字的算式为 n mod 102）为了保证循环体为“不变式”，求十位数字的算式仍旧为n mod 10，这就要通过算式n=n10，将n的十位数变成个位数。,33,循环算法如下：f1(n)while(n=10)print(n mod 10);n=n10;print(n);,34,递归算法设计：1）同上，算法从低位到高位逐位求出各位数字并输出，求个位数字的算式为 n mod 10，下一步则是递归地求n10的个位数字。2）当n10时，n为一位数停止递归。递归算法如下：f2(n)if(n10)print(n);else print(n mod 10);f2(n10);,35,36,【例2】任给十进制的正整数，请从高位到低位逐位输出各位数字。循环算法设计：本题目中要求“从高位到低位”逐位输出各位数字，但由于我们并不知道正整数的位数，算法还是“从低位到高位”逐位求出各位数字比较方便。这样就不能边计算边输出，而需要用数组保存计算的结果，最后倒着输出。,循环算法如下：f3(n)int j,i=0,a16;while(n=10)ai=n mod 10;i=i+1;n=n10;ai=n;for(j=i;j=0;j=j-1)print(aj);,递归算法设计：与f2不同，递归算法是先递归地求n10的个位数字，然后再求个位数字n的个位数字并输出。这样输出操作是在回溯时完成的。递归停止条件与f2相同为n10。递归算法如下：f4(n)if(n10)print(n);else f4(n10);print(n mod 10);,【例3】找出n个自然数(1,2,3,n)中r个数的组合。,例如，当n=,r=3时，所有组合为：1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 total=10 组合的总数,算法设计1：,1）n个数中r的组合，其中每r个数中，数不能相同；2）任何两组组合的数，所包含的数也不应相同。例如，、与、。为此，约定前一个数应小于后一个数。将上述两条作为约束条件；3）当r=3时，可用三重循环进行枚举。,算法1如下：,constitute1（）int n=5,i,j,k,t;t=0;for(i=1;ij)and(ik)and(ij)and(jk)t=t+1;print(i,j,k);print(total=,t);,或者constitute2（）int n=5,r=3,i,j,k,t;t=0;for(i=1;i=n-r+1;i=i+1)for(j=i+1;j=n-r+2;j=j+1)for(k=j+1;k=n-r+3;k=k+1)t=t+1;print(i,j,k);print(total=,t);,在循环算法设计中，对n=5的实例，每个组合中的数据从小到大排列或从大到小排列一样可以设计出相应的算法。但用递归思想进行设计时，每个组合中的数据从大到小排列却是必须的；因为递归算法设计是要找出大规模问题与小规模问题之间的关系。,用递归法设计此题：,例如，当n=,r=3时，所有组合为：total=10,分析n=5,r=3时的10组组合数。1）首先固定第一个数，其后就是n=4,r=2的组合数，共6个组合。2）其次固定第一个数4，其后就是n=3,r=2的组合数，共3个组合。3）最后固定第一个数3，其后就是n=2,r=2的组合数，共1个组合。至此找到了“个数中个数的组合”与“个数中个数的组合、3个数中个数的组合、2个数中个数的组合”的递归关系。,则递归算法的三个步骤为：,1）一般地：n个数中r个数组合递推到“n-1个数中r-1个数有组合，n-2个数中r-1个数有组合，,r-1个数中r-1个数有组合”，共n-r+1 次递归。2）递归的边界条件是的r=1。3）函数的主要操作就是输出，每当递归到r=1时就有一组新的组合产生，输出它们和一个换行符。注意n=5,r=3的例子中的递归规律，先固定5，然后要进行多次递归也就是说，数字5要多次输出，所以要用数组存储以备每一次递归到r=1时输出。同样每次向下递归都要用到数组，所以将数组设置为全局变量。,递归算法如下：,int a100;comb(int m,int k)int i,j;for(i=m;i=k;i-)ak=i;if(k1)comb(i-1,k-1);else for(j=a0;j0;j-)print(aj);print(“换行符”);,constitute3()int n,r;print(“n,r=”);input(n,r);if（rn）print(“Input n,r error!”);else a0=r;comb(n,r);/调用递归过程/,分析：算法2递归的深度是r，每个算法要递归m-k+1次，所以的时间复杂性是O（r*n）。,递归是一种强有力的算法设计方法。递归是一种比循环更强、更好用的实现“重复操作”的机制。因为递归不需要编程者（算法设计者）自己构造“循环不变式”，而只需要找出递归关系和最小问题的解。递归在很多算法策略中得以运用，如：分治策略、动态规划、图的搜索等算法策略。综合以上讨论，可以得出以下结论：,