算法基本工具.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法基本工具,1,3,.1,循环与递归,设计算法重复处理大量数据的思路：,以不变应万变；,两种思路：,循环、递归。,1,循环设计要点,例,3.1,求完数,例,3.2,打印数字图形,例,3.3,求级数,2,递归设计思路,(,运行机制、复杂度分析,),例,3.4,累加求和,3,递归设计要点,例,3.5,hanoi,塔,4,非递归,(,循环,)/,递归比较,2,1,循环设计要点,循环控制,-,熟悉；,设计要点：,注意算法的效率,“,自顶向下,”,的设计方法,由具体到抽象设计循环结构,3,1,循环设计要点,-,例,1(,注意算法效率）,例,1,求级数,求：,1/1!-1/3!+1/5!-1/7!+(-1),n+1,/(2n-1)!,问题分析：此问题中既有累加又有累乘，累加的对象是累乘的结果。数学模型,1,：,S,n,=S,n-1,+(-1),n+1,/(2n-1)!,算法设计,1,：直接利用题目中累加项通式，构造出循环体不变式为：,S=S+(-1),n+1,/(2n-1)!,需要用二重循环来完成算法。,算法设计,1,：,外层循环求累加,S=S+A;,内层循环求累乘,A=(-1),n+1,/(2n-1)!,。,4,1,循环设计要点,-,例,1,算法分析：,以上算法是二重循环来完成，但算法的效率却太低,O(n,2,),。,数学模型,2,：,S,n,=S,n-1,+(-1),n+1,A,n,；,A,n,=A,n-1,*1/(2*n-2)*(2*n-1),其原因是，当前一次循环已求出,7,！，当这次要想求,9,！时，没必要再从,1,去累乘到,9,，只需要充分利用前一次的结果，用,7,！*,8*9,即可得到,9,！，模型为,A,n,=A,n-1,*1/(2*n-2)*(2*n-1),。,算法分析：按照数学模型,2,，只需一重循环就能解决问题算法的时间复杂性为,O(n,),。,5,1,循环设计要点,-,例,2,（自顶向下的设计方法）,例,2.,编算法找出,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,核心算法设计,for(i,=0;i,n;i,=i+1),判断,i,是否是完数,;,if,是“完数”则按规则输出,;,自顶向下，逐步求精,判断,i,是否是完数,for(j,=2;j,i;j,=j+1),找,i,的因子，并累加；,if,累加值等于,i,，则,i,是完数；,判断,i,是否是完数,s=1,；,for(j,=2;j,i;j,=j+1),if(i mod j=0)s=,s+j,;,if (s=i)i,是“完数”,;,判断是否是完数的方法是“不变”，被判断的数是“万变”。,7,输出数据的方法是“不变”，被输出的数是“万变”。,1,循环设计要点,-,例,2,考虑到要按格式输出结果，应该开辟数组存储数据,i,的所有因子，并记录其因子的个数，因此算法细化如下：,int,a100,，,s=1,k=0;,for(j,=2;j,i;j,=j+1),if(i mod j=0),s=,s+j,;,ak,=j;,k=k+1;,if(s,=i),print(s,“its factors are:”,1);,for(j,=0;j,k;j,+),print(“,”,ak,),8,1,循环设计要点,-,例,3,（从具体到抽象设计循环）,对于不太熟悉的问题，其“不变”不易抽象；,1,6 2,10 7 3,13 11 8 4,15 14 12 9 5,n=5,例,3,编写算法：根据参数,n,打印具有下面规律的图形，如，当,n=4,时，图形如下：,1,5 2,8 6 3,10 9 7 4,9,1,循环设计要点,-,例,3,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,循环设计要点,-,例,3,用斜行、列描述新的循环方向。,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,循环设计要点,-,例,3,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,2,递归设计思路,-,例,4,程序结构化设计的三种基本结构，顺序、选择、循环是不是必须的？,例,4,根据参数,n,，计算,1+2+n,。,void,sum_loop(int,n),int,i,sum,=0;,for(i=1;in/,if n=0,return(m,),else return(,GCD(n,m,mod n),18,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;,19,3,递归设计要点,-,hanoi,塔,Hanoi,塔,hanoi,河内,越南首都,古代有一个梵塔，塔内有,3,个基座,A,、,B,、,C,，,开始时,A,基座上有,64,个盘子，盘子大小不等，大的在下，小的在上。,有一个老和尚想把这,64,个盘子从,A,座移到,B,座，但每次只允许移动一个盘子，且在移动过程中在,3,个基座上的盘子都始终保持大盘在下，小盘在上。,在移动过程中可以利用,C,基座做辅助。,请编程打印出移动过程。,约定盘子自上而下的编号为,1,，,2,，,3,，,，,n,。,20,3,递归设计要点,-,hanoi,塔,首先看一下,2,阶汉诺塔问题的解，不难理解以下移动过程：,初始状态为,A(1,2)B()C(),第一步后,A(2)B()C(1),第二步后,A()B(2)C(1),第三步后,A()B(1,2)C(),用递归思路考虑,21,3,递归设计要点,-,hanoi,塔,把,n,个盘子抽象地看作“两个盘子”，上面“一个”由,1n-1,号组成，下面“一个”就是,n,号盘子。移动过程如下：,第一步：先把上面“一个”盘子以,a,基座为起点借助,b,基座移到,c,基座。,第二步：把下面“一个”盘子从,a,基座移到,b,基座。,第三步：再把,c,基座上的,n-1,盘子借助,a,基座移到,b,基座。,22,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),。,至此找出了大规模问题与小规模问题的关系。,23,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(2,n,),24,3,递归设计要点,-,hanoi,塔,hanoi,(,int,n,char,a,char,b,char,c),/*,a,b,c,初值为”,A”,”B”,”C”*/,if(n,0)/*0,阶的汉诺塔问题当作停止条件*,/,hanoi(n-1,a,c,b);,输出“,Move dish”,n.”from,pile”,a,”,to”b,);,hanoi(n-1,c,b,a);,25,4,非递归,(,循环,)/,递归比较,-,非递归,hanoi,塔,递归思路不适合人类使用：人脑的逆推深度是有限的，而计算机要比人脑深很多，论记忆的准确性，计算机要比人脑强很多。,你用递归的程序，用,n=10,，试试看？,通过分析可以找到非递归的思路，而这种思路是未学过递归思想的人常用的。,26,4,非递归,(,循环,)/,递归比较,-,转化,设计算法重复处理大量数据的思路：以不变应万变；,两种思路：非递归,(,循环,),、递归。,1,、有些问题可以方便的用循环,/,递归两种思路处理；,如例,4,累加求和；,在后面的课程中，会常遇到递归算法，以及同一问题的递归、非递归算法。,2,、有些问题用递归比较方便；转换成非递归过程可通过模拟递归过程的执行过程来实现；其基本思想是在程序中设置一个栈；,如例,5,hanoi,塔。,同一个问题干嘛要学两种方法？,27,从算法设计的角度,递归函数调用引起的栈操作,4,非递归,(,循环,)/,递归比较,递归,非递归,程序可读性,易,难,代码量大小,小,大,时间,长,短,占用空间,大,小,适用范围,广,窄,设计难度,易,难,并不是每一门语言都支持,/,很好的支持递归；,有助于理解递归的本质；,有助于理解栈,树等数据结构；,两者各有利弊：,28,1,数据结构的选择很重要,例,6,大整数存储及运算,2,算法和数据结构不分离,例,7,线性表的实现,3,数组与指针,例,7,线性表的实现,一聚，一散,一静，一动,静中有动,高级语言的支持,3.2,算法与基本数据结构,29,1,数据结构的选择很重要,计算机解决问题是对“数据”加工处理。,例,6,编程求当,N=100,时，,N,！的准确值。,问题分析：,例如：,9,！,=362880,100,！,=,93 326215 443944 152681 699263,856266 700490 715968 264381 621468 592963,895217 599993 229915 608914 463976 156578,286253 697920 827223 758251 185210 916864,000000,000000,000000,000000,处理对象的情况严重影响处理过程、效果。,数值问题,/,非数值问题。,30,1,DS,选择,-,例,6-,问题分析,计算机存储数据是按类型分配空间的。在,PC,上：,整型：,2,个字节,16,位，则整型数据的范围为,-3276832767,；,长整型：,4,个字节,32,位，则长整型数据的范围为,-21474836482147483647,；,实型：,4,个字节,32,位，但非精确存储数据，只有六位精度，数据的范围,(3.4e-383.4e+38),；,双精度型：,8,个字节,64,位的存储空间，数据的范围,(1.7e-3081.7e+308),，其精确位数是,17,位。,这些类型无法存储,100,！这样的“大整数”。,需要使用更复杂、更有针对性的数据结构。,31,1,DS,选择,-,例,6-,算法设计,每一位数，都是一个,10,以内数字。多个，相同属性的，,数组是有头有尾的：,a1an,。高位、低位谁头谁尾？,低位固定，而高位不定。最低位为,a1,，且在高端要为问题最大存储数据留够空位。,基于存储的考虑,int,an,32,1,DS,选择,-,例,6-,算法设计,100,！,=1*2*3*99*100,。,按此方法计算，最困难的操作是：,大整数*乘数，其中乘数,=100,。,基于功能的考虑,原来一个元素存一位，现在是否要改变？改变是否有用？,问题出在哪里？,当低位元素计算后的值超过,9,时，需向高位元素进位。,如何进位？,33,1,DS,选择,-,例,6-,算法设计,int,an,中的数组元素可以存放更大的数。如，每个存,3,位。,基于性能的考虑,进位,4,次。,进位几次？,进位需要特殊的处理；减少进位的处理，可以提高效率。,每个元素处理的位数越多，进位次数越少。,在前面提到的四种数据类型的基础上，粗略估计一下，本问题中，每个元素最多可以存储几位数据？,34,1,DS,选择,-,例,6-,算法实现,main(),long,ab256,b,d;,int,m,n,i,j,r,;,input(n,);,m=,log(n,)*n/6+2;,ab1=1;,for,(i=2;i=,m;i,+),abi,=0;,d=0;,for,(i=2;i=,n;i,+),for,(j=1;j=1;i-),if,(,abi,=0)continue;,else,r=i;break;,print(n,“!=”);,print(abr,);,for,(i,=r-1;i=1;i-),if,(,abi,99999),print(abi,);,continue,;,if,(,abi,9999)print(“0”,abi);,continue,;,if,(,abi,999)print(“00”,abi);,continue,;,if,(,abi,99)print(“000”,abi);,continue,;,if,(,abi,9)print(“0000”,abi);,continue,;,print(“00000”,abi);,/for,B,存储计算的中间结果，,d,存储超过,6,位数后的进位，,ab,数组存储每次累乘的结果，每个元素存储,6,位数字,35,算法说明,m=,log(n,)*n/6+2;,是对,n!,位数的粗略估计，这样做算法简单，但是效率低。改进方法：记录当前积所占数组元素的个数，初值为,1,，每次有进位时,m,增加,1,。将第二个,for,循环中,if,语句改为,if(d0),aj,=d;m=m+1;,输出时，首先计算结果的准确位数,r,，然后输出最高位数据，输出其他单元数据要注意，如若结果为,123 000001,，,ab1,中是,1,，不是,000001,36,1,数据结构的选择很重要,-,总结,基于存储的考虑,基于功能的考虑,基于性能的考虑,37,2,数组与指针,一聚，一散,一动，一静,静中有动,高级语言的支持,数组和指针在程序设计、数据结构中占重要角色。,在基础类型上的扩展；,构成复杂数据类型的基础和重要方式。,数据的逻辑结构常分为四大类：,集合结构,线性结构,树形结构,图结构（网结构）,数组和指针均可实现,38,3,数组与指针,一聚，一散,连续存储,可随机存取,(,通过数组名、下标便可以访问,),；,L,a,1,a,2,a,n,a,1,a,2,a,i,a,n,链式存储,在内存中方便利用碎片存储。,例,7,线性表的实现,无需多余存储单元，空间效率高。,39,3,数组与指针,一动，一静,L,a,1,a,2,a,n,a,1,a,2,a,i,a,n,例,7,线性表的实现,连续存储,数组的空间在分配后相对固定；,链式存储,可以方便的进行插入、删除操作。,但也有变通方法，静中有动。,40,3,数组与指针,静中有动,动态声明数组：,动态数组,动态声明,C,不支持,C+,通过指针支持,Java,支持,C,语言不支持：,int,n;,scanf(%d,&n,);,int,an,;,C+,语言利用指针支持：,int,len,;,cin,len,;,int,*p=new,intlen,;,Java,语言支持：,int,a,；,输入,len,值；,a=new,intlen,；,41,3,数组与指针,静中有动,初始化后改变长度,动态数组,初始化后可变长,C,Realloc,帮助实现；,C+,不支持，有类支持；,Java,数组不支持，有,ArrayList,、,Vector,类支持。,List,lst,=new,ArrayList,();,lst.add(new,Integer(37);,一个整型值,37,用于构造一个,Integer,封装类对象，然后那个对象被加入到列表。,42,3,数组与指针,高级语言的支持,在本课程的算法实现中，使用类,C,语言，在可能的情况下均使用数组，数组使用静态数组。,这符合“简单明了,”,的表达原则。,指针,C,支持,C+,支持,Java,不支持，通过“引用”部分的实现指针功能,Strings=new,String(“how,much?);,43,3.,从算法到实现,-,算法基本技巧举例,a.,算术运算的妙用,例,8,开灯问题,b.,巧用“标志量”,例,9,判定输入,n,个数据互不相等,例,10,冒泡排序,c.,信息数字化,例,11,警察抓小偷,d.,学会找规律,例,12,数组移位,44,a.,算术运算的妙用,-,例,8,开灯问题,算术运算：加减乘除。,例,8,开灯问题,有从,1,到,n,依次编号的,n,个同学和,n,盏灯。,1,号同学将所有的灯都关掉；,2,号同学将编号为,2,的倍数的灯都打开；,3,号同学则将编号为,3,的倍数的灯作相反处理（该号灯如打开的，则关掉；如关闭的，则打开）；以后的同学都将自己编号的倍数的灯，作相反处理。,问：经,n,个同学操作后，哪些灯是打开的？,45,问题分析：,1,）用数组表示某种状态，这里定义有,n,个元素的,a,数组，它的每个下标变量,ai,视为一灯，,i,表示其编号。,ai,=1,表示灯处于打开状态，,ai,=0,表示灯处于关闭状态。,此用法也称为“乒乓开关”。简化逻辑表达式、减少条件判断,2,）实现将第,i,灯作相反处理的操作：,条件语句,if,表示：,if,ai,=1,ai,=0,；,if,ai,=0,ai,=1,；,通过算术运算更简练、逼真：,ai,=1-ai,。,a.,算术运算的妙用,-,例,8,问题分析,/,建模,46,a.,算术运算的妙用,-,例,8-,算法设计,int,a1000;,输入,n,的数值,；,关闭所有灯，即,a1an,置为,0,；,第,2,个学生,-,第,n,个学生,(,学生,i),进行操作：,操作对象：,数组,a,，灯编号含因数,i,，即,ai,*k,；,操作：,ai,*k=1-,ai,*k,；,输出灯的开关状态。,47,建立一个充分大的数组,int,a1000;,输入,n,的数值；,关闭所有灯，即,a1an,置为,0,；,第,2-,第,n,个学生,(,每个学生,i),进行操作：,操作对象：数组,a,，,灯编号含因数,i,，即,ai,*k,操作：,ai,*k=1-,ai,*k,；,输出灯的开关状态。,void,main(),int,n,a1000,i,k;,scanf(%d,&n,);,for,(i=1;i=,n;i,+),ai,=0;,for,(i=2;i=,n;i,+),k=1;,while,(i*k=n),ai,*k=1-,ai,*k;,k=k+1;,for,(i=1;i,第,n-1,个,(,每个元素,i),操作,与第,i+1,第,n,元素,(,每个元素,j),比较，若相等则标志量置,0,，循环中断；,若,flag=1,，则无重复；反之，有重复。,b,巧用“标志量”,-,例,9,算法设计,50,b,巧用“标志量”,-,例,9,实现,void,main(),int,a100,i,j,flag,n;,scanf(%d,&n,);,for,(i=1;i=,n;i,=i+1),scanf(%d,&ai,);,flag=1;,for,(i=1;i=n-1;i=i+1),for,(j=i+1;j=,n;j,=j+1),if,(ai,=,aj,),flag=0;,break;,if,(flag=1),printf(No,repeatn);,else,printf(Repeatn,);,51,例,10,冒泡排序,排序过程,1,、比较第一个记录与第二个,记录，若,关键字,为逆序,则交换；然,后比较第二个记录与第三个记录；,依次类推，直至第,n,-1,个记录和第,n,个记录比较为止,第一趟冒泡,排序,，结果关键字最大的记录被安,置在最后一个记录上。,2,、,对前,n,-1,个记录进行第二,趟冒泡排序，结果使关键字次大的,记录被安置在第,n,-1,个记录位置。,3,、,重复上述过程，直到,“在,一趟排序过程中没有进行过交换记,录的操作”,为止。,初,始,关,键,字,49,38,65,97,76,13,27,49,第,一,趟,排,序,49,38,49,97,76,97,97,13,97,97,27,97,97,49,97,38,49,65,76,13,27,49,97,38,49,65,13,27,49,76,第,二,趟,排,序,38,49,13,27,49,65,第,三,趟,排,序,38,13,27,49,49,第,四,趟,排,序,13,27,38,49,第,五,趟,排,序,13,27,38,第,六,趟,排,序,for(,j,=1;,j,n,;,j,+),if (r,j,+1,r,j,),r,j,r,j,+1 ;,for(,j,=1;,j,n,-1,;,j,+),if (r,j,+1 1;,i,-),i,;,while(,i,1),/while,i,=,n,;,i,=,k,;,Void,BubbleSort(SqList,&L),冒泡排序算法,初,始,关,键,字,49,38,65,97,76,13,27,49,k,=,j,;/,交换的位置,k,=1;,52,冒泡算法改进,如果原有数据有序，冒泡算法仍要做,n-1,趟比较。事实上一趟比较下来，如果发现没有交换，就说明数据已经有序，无须后续操作了,数据原本有序概率不高，但经过少于,n-1,次比较后，有序概率就非常高了,改进：设置标志位，检测数据是否有序,flag=0,表示没有进行交换，一旦有交换则置,flag=1.,当一趟比较交换完成后，若,flag,仍为,0,，则无须进行下一趟操作。,算法略,53,c,信息数字化,-,例,11,警察抓小偷,一些表面上看是非数值的问题，但经过进行数字化后，就可方便进行算法设计。,例,1.5,警察抓小偷,警察局抓了,a,，,b,，,c,，,d,四名偷窃嫌疑犯，其中只有一人是小偷。审问中,a,说：“我不是小偷。”,b,说：“,c,是小偷。”,c,说：“小偷肯定是,d,。”,d,说：“,c,在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？,54,c,信息数字化,-,例,11-,问题分析,问题分析：可通过循环，每次假设一名嫌疑犯为小偷，代入问题系统，检验是否只有一句假话。,这种让所有可能解都进行检验，以求得真解的方法称为“枚举尝试法”，也是“蛮力法”、“暴力法,”,。,为方便设计程序，将,a,b,c,d,将四个人进行编号，号码分别为,1,，,2,，,3,，,4,。,55,c,信息数字化,-,例,11-,算法设计,算法设计：用变量,x,存放小偷的编号，则,x,的取值范围从,1,取到,4,，就假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成：,a,说的话：,x1,b,说的话：,x=3,c,说的话：,x=4,d,说的话：,x4,或,not(x,=4),注意,:,在,x,的枚举过程中，当这四个,逻辑式的值相加等于,3,时，即表示“四个人中三人说的是真话，一人说的是假话”。,if(x!=1)+(x=3)+(x=4)+(x!=4)=3),56,c,信息数字化,-,例,11-,实现,#,include,stdafx.h,void,main(),int,x;,for,(x,=1;x=4;x=x+1),if,(x!=1)+(x=3)+(x=4)+(x!=4)=3),printf(%c,is a thief,char,(64+x);,57,3.4,优化算法的数学模型数学建模方法主要是归纳法。归纳法是从简单到复杂，由个别到一般的一种研究方法，也就是“找规律”。学会找规律,-,例,12,数组移位,例,12,数组中有,n,个数据，要将它们顺序循环向后移,k,位，即前面的元素向后移,k,位，后面的元素则循环向前移,k,位，例：,0,、,1,、,2,、,3,、,4,循环移,3,位后为：,2,、,3,、,4,、,0,、,1,。考虑到,n,会很大，不允许用,2*n,以上个空间来完成此题。,58,d,学会找规律,-,例,12-,问题分析,(,思路,1),问题分析,1,：,若题目中没有关于存储空间的限制，我们可以方便地开辟两个一维数组，一个存储原始数据，另一个存储移动后的数据。,开始部分的元素从前向后移，容易确定；但数组中后,k,个元素是从后向前移，如何确定？,59,d,学会找规律,-,例,12-,问题分析,(,思路,1),void,alg1(),int,a100,b100,i,n,k;,scanf(%d,%d,&n,&k,);,for,(i=0;i,n;i,=i+1),scanf(%d,&ai,);,for,(i=0;i,n;i,=i+1),b(k+i,)%n=,ai,;,for,(i=0;in,，这样移动会出现重复操作,可以在输入数据后，执行,k=k mod n;,以保证不出现重复移动的问题。这个算法的移动（赋值）次数为,k*n,。当,n,较大时不是一个好的算法。,void,alg2(),int,a100,i,j,n,k,temp;,scanf(%d,%d,&n,&k,);,for,(i=0;i,n;i,=i+1),scanf(%d,&ai,);,for,(i=0;i0;j=j-1),aj,=aj-1;,a0=temp;,for,(i=0;i,n;i,=i+1),printf(%d,ai,);,printf(n,);,62,d,学会找规律,-,例,12-,问题分析,(,思路,3),问题分析,3,：利用,一个临时存储空间,，把每一个数据,一次移动到位,。,1,）一组循环移动的情况：,通过计算我们可以确定某个元素移动后的具体位置，如,n=5,k=3,时：,0,、,1,、,2,、,3,、,4,循环移,3,位后为,2,、,3,、,4,、,0,、,1,。,可通过计算得出,0,移到,3,的位置，,3,移到,1,的位置，,1,移到,4,的位置，,4,移到,2,的位置，,2,移到,0,的位置；一组移动（,0-3-1-4-2-0,）正好将全部数据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次移动就可完成整个移动过程。,如果算法就这样按一组移动去解决问题，就错了。因为还有其它情况。,63,2,）多组循环移动的情况：算法不能只按一组移动去解决问题。,看下一个例子，当,n=6,，,k=3,时，,0,、,1,、,2,、,3,、,4,、,5,经移动的结果是,3,、,4,、,5,、,0,、,1,、,2.,共要进行三组循环移动（,0-3,，,1-4,，,2-5,）才能将全部数据操作完毕,。,循环移动的组数，与,k,、,n,是怎么样的关系呢？,我们再看一个例子，当,N=6,，,K=2,时,，,0,、,1,、,2,、,3,、,4,、,5,经移动的结果是,4,、,5,、,0,、,1,、,2,、,3,。,0,移到,2,的位置，,2,移到,4,的位置，,4,移到,0,的位置，一组移动完成了,3,个数据的移动，接下来，还有一组,1-3-5-1,。共进行二组循环移动，就能将全部数据移动完毕。,d,学会找规律,-,例,12-,问题分析,(,思路,3),64,d,学会找规律,-,例,12-,建模,/,算法设计,(,思路,3),数学模型：循环移动的组数等于,N,与,K,的,最大公约数。,算法设计：,1,）编写函数，完成求,n,k,最大公约数,m,的功能。,2,）进行,m,组循环移动。,3,）每组移动，和算法,2,一样，通过计算可以确定某个元素移动后的具体位置。在移动之前，用临时变量存储需要被覆盖的数据。,65,d,学会找规律,-,例,12-,实现,(,思路,3),void,alg3(),int,a100,b0,b1,i,j,n,k,m,tt;,scanf(%d,&n,);,scanf(%d,&k,);,for,(i,=0;i,n;i,=i+1),scanf(%d,&ai,);,m=,gcd(n,k,);,for,(j,=0;j,m;j,=j+1),b0=,aj,;,tt,=j;,for,(i,=0;i,n/m;i,=i+1),tt,=(,tt+k,)%n;,b1=,att,;,att,=b0;,b0=b1;,for,(i,=0;i,n;i,=i+1),printf(%d,ai,);,printf(n,);,66,4,算法为魂,有人也许会说：“今天计算机这么快，算法还重要吗？”其实永远不会有太快的计算机，因为我们总会想出新的应用。,日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。,互联网的信息流量和日志容量也在飞快增长。,在网络时代，越来越多的挑战需要靠卓越的算法来解决。,算法的力量,李开复,算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门，就产生了一种误解，认为学计算机就是学各种编程语言。编程语言虽然应该学，但是学习计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论。,67,4,算法为魂,现在你应该明白为什么我说“算法为魂，程序为衣”了吧，而且那只是若干件衣中的一件而已。,算法为魂,凌小宁,在大多数算法教材中，算法常常是用伪程序来描述的。伪程序较接近高级计算机语言，但更易写易懂。其实算法的表达可以有多种形式：自然语言,(,英文，中文，,.),，各种计算机程序设计语言，甚至硬件。由此可见，算法的本质是问题解决过程的概念，而相应的程序只是一种它的表述。,68,小结,理解循环与递归的意义；,理解算法与数据结构的关系。,掌握循环和递归的基本使用方法；,掌握算法设计中对数据结构的选择。,69,作业,P117 4,8,13,要求：,C,语言程序编写；要有算法分析；交电子稿,70,