算法基本工具幻灯片.ppt

《算法基本工具幻灯片.ppt》由会员分享，可在线阅读，更多相关《算法基本工具幻灯片.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法基本工具算法基本工具1第1页，共70页，编辑于2022年，星期一3.1.1 循环与递归循环与递归n设计算法重复处理大量数据的思路：设计算法重复处理大量数据的思路：以不变应万变；以不变应万变；n两种思路：两种思路：循环、递归。循环、递归。n1循环设计要点循环设计要点q例例3.1求完数求完数q例例3.2打印数字图形打印数字图形q例例3.3求级数求级数n2递归设计思路递归设计思路(运行机制、复杂度分析运行机制、复杂度分析)q例例3.4累加求和累加求和n3递归设计要点递归设计要点q例例3.5hanoi塔塔n4非递归非递归(循环循环)/递归比较递归比较2第2页，共70页，编辑于2022年，星期一1

2、循环设计要点循环设计要点n循环控制循环控制-熟悉；熟悉；n设计要点：设计要点：q注意算法的效率注意算法的效率q“自顶向下自顶向下”的设计方法的设计方法 q由具体到抽象设计循环结构由具体到抽象设计循环结构3第3页，共70页，编辑于2022年，星期一1 循环设计要点循环设计要点-例例1(注意算法效率）注意算法效率）n例例1求级数求级数n求：求：1/1!-1/3!+1/5!-1/7!+(-1)n+1/(2n-1)!n问题分析：此问题中既有累加又有累乘，累加的对象是累乘问题分析：此问题中既有累加又有累乘，累加的对象是累乘的结果。的结果。数学模型数学模型1：Sn=Sn-1+(-1)n+1/(2n-1)!

3、算法设计算法设计1：直接利用题目中累加项通式，构造出循环体不变：直接利用题目中累加项通式，构造出循环体不变式为：式为：S=S+(-1)n+1/(2n-1)!需要用二重循环来完成算法。需要用二重循环来完成算法。n算法设计算法设计1：q外层循环求累加外层循环求累加S=S+A;q内层循环求累乘内层循环求累乘A=(-1)n+1/(2n-1)!。4第4页，共70页，编辑于2022年，星期一1 循环设计要点循环设计要点-例例1n算法分析：算法分析：n以上算法是二重循环来完成以上算法是二重循环来完成，但算法的效率却太低，但算法的效率却太低O(n2)。n数学模型数学模型2：Sn=Sn-1+(-1)n+1An；

4、An=An-1*1/(2*n-2)*(2*n-1)n其原因是，当前一次循环已求出其原因是，当前一次循环已求出7！，当这次要想求！，当这次要想求9！时，没！时，没必要再从必要再从1去累乘到去累乘到9，只需要充分利用前一次的结果，用，只需要充分利用前一次的结果，用7！*8*9即可得到即可得到9！，模型为！，模型为An=An-1*1/(2*n-2)*(2*n-1)。n算法分析：按照数学模型算法分析：按照数学模型2，只需一重循环就能解决问题，只需一重循环就能解决问题算法的时间复杂性为算法的时间复杂性为O(n)。5第5页，共70页，编辑于2022年，星期一1 循环设计要点循环设计要点-例例2（自顶向下的

5、设计方法）（自顶向下的设计方法）n例例2.编算法找出编算法找出1000以内所有完数。以内所有完数。n如：如：28的因子为的因子为1、2、4、7，14，而，而28=1+2+4+7+14。因此。因此28是是“完数完数”。编算法找出。编算法找出1000之内的所有完数，并按下面格之内的所有完数，并按下面格式输出其因子：式输出其因子：28itsfactorsare1，2，4，7，14。n问题分析：问题分析：n1、这里、这里不是要质因数不是要质因数，所以找到因数后也无需将其从数据中，所以找到因数后也无需将其从数据中“除除掉掉”。n2、每个因数只记一次每个因数只记一次，如，如8的因数为的因数为1，2，4而不

6、是而不是1，2，2，2，4。(注：本题限定因数不包括这个数本身注：本题限定因数不包括这个数本身)6第6页，共70页，编辑于2022年，星期一1 循环设计要点循环设计要点-例例2n核心算法设计核心算法设计qfor(i=0;in;i=i+1)判断判断i是否是完数是否是完数;if是是“完数完数”则按规则输出则按规则输出;自顶向下，逐步求精自顶向下，逐步求精n判断判断i是否是完数是否是完数qfor(j=2;ji;j=j+1)找找i的因子，并累加；的因子，并累加；if累加值等于累加值等于i，则，则i是完数；是完数；n判断判断i是否是完数是否是完数qs=1；for(j=2;ji;j=j+1)if(imod

7、j=0)s=s+j;if(s=i)i是是“完数完数”;判断是否是完数的方法是判断是否是完数的方法是“不变不变”，被判断的数是，被判断的数是“万变万变”。7第7页，共70页，编辑于2022年，星期一输出数据的方法是输出数据的方法是“不变不变”，被输出的数是，被输出的数是“万变万变”。1 循环设计要点循环设计要点-例例2n考虑到要按格式输出结果，应该开辟数组存储数据考虑到要按格式输出结果，应该开辟数组存储数据i的所有的所有因子，并记录其因子的个数，因此算法细化如下：因子，并记录其因子的个数，因此算法细化如下：qinta100，s=1,k=0;for(j=2;ji;j=j+1)if(imodj=0)

8、s=s+j;ak=j;k=k+1;if(s=i)print(s,“itsfactorsare:”,1);for(j=0;jk;j+)print(“,”,ak)8第8页，共70页，编辑于2022年，星期一1 循环设计要点循环设计要点-例例3（从具体到抽象设计循环）（从具体到抽象设计循环）n对于不太熟悉的问题，其对于不太熟悉的问题，其“不变不变”不易抽象；不易抽象；162107313118415141295n=5n例例3编写算法：根据参数编写算法：根据参数n打印具有下面规律的图形，如，当打印具有下面规律的图形，如，当n=4时，图形如下：时，图形如下：q1q52q863q109749第9页，共70页

9、，编辑于2022年，星期一1 循环设计要点循环设计要点-例例315286310974n问题分析：问题分析：q容易发现图形中数据排列的规律。容易发现图形中数据排列的规律。q另一种思路另一种思路n先用一个数组按此顺序存储数据，先用一个数组按此顺序存储数据，再正常输出；再正常输出；15286310974q可不可以从可不可以从1最大数，通过循环，直接输出？最大数，通过循环，直接输出？nprintf是按照从左至右、从上至下的顺序；若想直接输出，是按照从左至右、从上至下的顺序；若想直接输出，只有找出公式，循环计算得到序列：只有找出公式，循环计算得到序列：1-n-5-2-n-8-6-3-n-10-9-7-4

10、.n为数组赋值，也要用循环，如何循环？为数组赋值，也要用循环，如何循环？又要回到找规律公式的路上吗？又要回到找规律公式的路上吗？n斜着能循环吗？斜着能循环吗？10第10页，共70页，编辑于2022年，星期一1 循环设计要点循环设计要点-例例3n用斜行、列描述新的循环方向。用斜行、列描述新的循环方向。15286310974斜斜1，1a1,1斜斜1，2a2,2斜斜1，3a3,3斜斜1，4a4,4斜斜2，1a2,1斜斜2，2a3,2斜斜2，3a4,3n列号相同；列号相同；n行号行号(显然行号与列号有关显然行号与列号有关)q第第1斜行，对应行号斜行，对应行号1n，行号与列号，行号与列号j同；同；q第第

11、2斜行，对应行号斜行，对应行号2n，行号比列号，行号比列号j大大1；q第第3斜行，对应行号斜行，对应行号3n，行号比列号，行号比列号j大大2；斜斜3，1a3,1斜斜3，2a4,2斜行斜行i取值取值(1n)列列j取值取值(1n+1-i)ai-1+jjn这样可以描述循环。但数组元素的存取还是基这样可以描述循环。但数组元素的存取还是基于于“行列行列”，能否简单转换？，能否简单转换？n关键问题：第关键问题：第i斜行、斜行、j列的数据对应于第几列的数据对应于第几行第几列的元素？行第几列的元素？斜斜4，1a4,111第11页，共70页，编辑于2022年，星期一1 循环设计要点循环设计要点-例例3main(

12、)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)1528631097412第12页，共70页，编辑于2022年，星期一2 递归设计思路递归设计思路-例例4n程序结构化设计的三种基本结构，顺序、选择、循环是不程序结构化设计的三种基本结构，顺序、选择、循环是不是必须的？是必须的？n例例4根

13、据参数根据参数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);ni sumn回答：在很多高级语言中，不是。可以抛弃谁呢？回答：在很多高级语言中，不是。可以抛弃谁呢？n递归能取代循环的作用递归能取代循环的作用。13第13页，共70页，编辑于2022年，星期一2 递归设计思路递归设计思路-例例4n例例4根据参数根据参数n，计算，计算1+2+n。int sum_recursive(int n)int sum=0;if(n=1)sum=1;else sum=sum_rec

14、ursive(n-1)+n;printf(nsum=%d,sum);return sum;sum(n)sum(n-1)n+sum(n-2)n-1+.sum(n-3)n-2+1n递归算法是一个模块递归算法是一个模块(函数、过程函数、过程)除了可调用其它模除了可调用其它模块块(函数、函数、过程过程)外，还可以直接或间接地调用自身的算法。直接外，还可以直接或间接地调用自身的算法。直接/间接递归调间接递归调用。用。n代入代入n=4，走一遍。，走一遍。递归树！递归树！sum(1)2+14第14页，共70页，编辑于2022年，星期一2 递归设计思路递归设计思路-例例4n例例4根据参数根据参数n，计算，计算

15、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)出栈出栈 进栈进栈 栈底元素栈底元素 栈顶元素栈顶元素栈顶元素栈顶元素 n sumn-1 sum.;2 sum1 sum表面上是一个变量，表面上是一个变量，实际上是一个实际上是一个栈栈15第15页，共70页，编辑于2022年，星期一2 递归设计思路递归设计思路-例例4n例例4根据参数根据参数n，计算，计算1+2+n。int su

16、m_recursive(int n)int sum=0;if(n=1)sum=1;else sum=sum_recursive(n-1)+n;printf(nsum=%d,sum);return sum;nT(n)=T(n-1)+O(1)sum(1)sum(n)sum(n-1)n+sum(n-2)n-1+.sum(n-3)n-2+2+1=T(n-2)+O(1)+O(1)=.=n*O(1)=O(n)16第16页，共70页，编辑于2022年，星期一“收敛收敛”3 递归设计要点递归设计要点n递归的关键在于找出递归的关键在于找出递归方程式递归方程式和和递归终止条件递归终止条件。q递归定义：使问题向边界

17、条件转化的规则。递归定义必递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。须能使问题越来越简单。q递归边界条件：也就是所描述问题的最简单情况，它本递归边界条件：也就是所描述问题的最简单情况，它本身不再使用递归的定义。身不再使用递归的定义。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)sum(n-1)n+sum(n-2)n-1+.sum(n-3)n-2+sum(1)2+117第17页，共70页，

18、编辑于2022年，星期一例例1.1 欧几里德算法欧几里德算法ngcd(m,n)=gcd(n,m mod n)n输入输入 正整数正整数m和和n 输出输出 m和和n的最大公因子的最大公因子1.如果如果n=0,计算停止返回计算停止返回m,m即为结果；否则继续即为结果；否则继续2。2.记记r为为m除以除以n的余数，即的余数，即r=m mod n。3.把把n赋值给赋值给m，把，把r赋值给赋值给n，继续，继续1。n伪代码如下伪代码如下(循环循环)：Euclid(m,n)while n 0 r=m mod n;m=n;n=r;递归代码：递归代码：GCD(m,n)/约定约定mn/if n=0 return(m

19、)else return(GCD(n,m mod n)18第18页，共70页，编辑于2022年，星期一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第19页，共70页，编辑于2022年，星期一3 递归设计要点递归设计要点-hanoi塔塔nHanoi塔塔qhanoi河内河内越南首都越南首都q古代有一个梵塔，塔内有古代有一个梵塔，塔内有3个基座个基座A、B、C，q开始时开始时A基座上有基座

20、上有64个盘子，盘子大小不等，大的在下，个盘子，盘子大小不等，大的在下，小的在上。小的在上。q有一个老和尚想把这有一个老和尚想把这64个盘子从个盘子从A座移到座移到B座，但每次座，但每次只允许移动一个盘子，且在移动过程中在只允许移动一个盘子，且在移动过程中在3个基座上的个基座上的盘子都始终保持大盘在下，小盘在上。盘子都始终保持大盘在下，小盘在上。q在移动过程中可以利用在移动过程中可以利用C基座做辅助。基座做辅助。q请编程打印出移动过程请编程打印出移动过程。q约定盘子自上而下的编号为约定盘子自上而下的编号为1，2，3，n。20第20页，共70页，编辑于2022年，星期一3 递归设计要点递归设计要

21、点-hanoi塔塔n首先看一下首先看一下2阶汉诺塔问题的解，不难理解以下移动过程：阶汉诺塔问题的解，不难理解以下移动过程：n初始状态为初始状态为A(1,2)B()C()q第一步后第一步后A(2)B()C(1)q第二步后第二步后A()B(2)C(1)q第三步后第三步后A()B(1,2)C()n用递归思路考虑用递归思路考虑21第21页，共70页，编辑于2022年，星期一3 递归设计要点递归设计要点-hanoi塔塔n把把n个盘子抽象地看作个盘子抽象地看作“两个盘子两个盘子”，上面，上面“一个一个”由由1n-1号号组成，下面组成，下面“一个一个”就是就是n号盘子。移动过程如下：号盘子。移动过程如下：n

22、第一步：先把上面第一步：先把上面“一个一个”盘子以盘子以a基座为起点借助基座为起点借助b基座移到基座移到c基基座。座。n第二步：把下面第二步：把下面“一个一个”盘子从盘子从a基座移到基座移到b基座。基座。n第三步：再把第三步：再把c基座上的基座上的n-1盘子借助盘子借助a基座移到基座移到b基座。基座。22第22页，共70页，编辑于2022年，星期一3 递归设计要点递归设计要点-hanoi塔塔n把把n阶的汉诺塔问题的模块记作阶的汉诺塔问题的模块记作hanoi(n,a,b,c)qa代表每一次移动的起始基座；代表每一次移动的起始基座；qb代表每一次移动的终点基座；代表每一次移动的终点基座；qc代表每

23、一次移动的辅助基座代表每一次移动的辅助基座；q则则hanoi(n,a,c,b)，表示把，表示把n个盘子从个盘子从a搬到搬到c，可以借助，可以借助b；qhanoi(5,c,a,b)，表示把，表示把5个盘子从个盘子从c搬到搬到a，可以借助，可以借助b。n则汉诺塔问题则汉诺塔问题hanoi(n,a,b,c)等价于以下三步：等价于以下三步：q第一步，第一步，hanoi(n-1,a,c,b)；q第二步，把下面第二步，把下面“一个一个”盘子从盘子从a基座移到基座移到b基座；基座；q第三步，第三步，hanoi(n-1,c,b,a)。n至此找出了大规模问题与小规模问题的关系。至此找出了大规模问题与小规模问题的

24、关系。23第23页，共70页，编辑于2022年，星期一3 递归设计要点递归设计要点-hanoi塔塔nhanoi(n,a,b,c)qa：起始基座：起始基座qb：终点基座：终点基座qc：辅助基座：辅助基座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)24第24页，共70页，编辑于2022年，星期一

25、3 递归设计要点递归设计要点-hanoi塔塔nhanoi(intn,chara,charb,charc)/*a,b,c初值为初值为”A”,”B”,”C”*/if(n0)/*0阶的汉诺塔问题当作停止条件阶的汉诺塔问题当作停止条件*/hanoi(n-1,a,c,b);输出输出“Movedish”,n.”frompile”,a,”to”b);hanoi(n-1,c,b,a);25第25页，共70页，编辑于2022年，星期一4 非递归非递归(循环循环)/递归比较递归比较-非递归非递归hanoi塔塔n递归思路不适合人类使用：人脑的逆推深度是有限的，而递归思路不适合人类使用：人脑的逆推深度是有限的，而计算

26、机要比人脑深很多，论记忆的准确性，计算机要比人计算机要比人脑深很多，论记忆的准确性，计算机要比人脑强很多。脑强很多。q你用递归的程序，用你用递归的程序，用n=10，试试看？，试试看？q通过分析可以找到非递归的思路，而这种思路是未学过递归思想通过分析可以找到非递归的思路，而这种思路是未学过递归思想的人常用的。的人常用的。26第26页，共70页，编辑于2022年，星期一4 非递归非递归(循环循环)/递归比较递归比较-转化转化n设计算法重复处理大量数据的思路：以不变应万变；设计算法重复处理大量数据的思路：以不变应万变；n两种思路：非递归两种思路：非递归(循环循环)、递归。、递归。n1、有些问题可以方

27、便的用循环、有些问题可以方便的用循环/递归两种思路处理；递归两种思路处理；q如例如例4累加求和；累加求和；在后面的课程中，会常遇到递归算法，以及同一问题在后面的课程中，会常遇到递归算法，以及同一问题的递归、非递归算法。的递归、非递归算法。n2、有些问题用递归比较方便；转换成非递归过程可通过模拟、有些问题用递归比较方便；转换成非递归过程可通过模拟递归过程的执行过程来实现；其基本思想是在程序中设置一个递归过程的执行过程来实现；其基本思想是在程序中设置一个栈；栈；q如例如例5hanoi塔。塔。同一个问题干嘛要学两种同一个问题干嘛要学两种方法？方法？27第27页，共70页，编辑于2022年，星期一从算

28、法设计的从算法设计的角度角度递归函数调用引起递归函数调用引起的栈操作的栈操作4 非递归非递归(循环循环)/递归比较递归比较递归递归非递归非递归程序可读性程序可读性易易难难代码量大小代码量大小小小大大时间时间长长短短占用空间占用空间大大小小适用范围适用范围广广窄窄设计难度设计难度易易难难n并不是每一门语言都支持并不是每一门语言都支持/很好的支持递归；很好的支持递归；n有助于理解递归的本质；有助于理解递归的本质；n有助于理解栈有助于理解栈,树等数据结构；树等数据结构；n两者各有利弊：两者各有利弊：28第28页，共70页，编辑于2022年，星期一n1数据结构的选择很重要数据结构的选择很重要q例例6大

29、整数存储及运算大整数存储及运算n2算法和数据结构不分离算法和数据结构不分离q例例7线性表的实现线性表的实现n3数组与指针数组与指针q例例7线性表的实现线性表的实现q一聚，一散一聚，一散q一静，一动一静，一动q静中有动静中有动q高级语言的支持高级语言的支持3.2 算法与基本数据结构算法与基本数据结构29第29页，共70页，编辑于2022年，星期一1 数据结构的选择很重要数据结构的选择很重要n计算机解决问题是对计算机解决问题是对“数据数据”加工处理。加工处理。n例例6编程求当编程求当N=100时，时，N！的准确值。！的准确值。n问题分析：问题分析：q例如：例如：q9！=362880q100！=93

30、326215443944152681699263856266700490715968264381621468592963895217599993229915608914463976156578286253697920827223758251185210916864000000000000000000000000n处理对象的情况严重影响处理过程、效果。处理对象的情况严重影响处理过程、效果。n数值问题数值问题/非数值问题。非数值问题。30第30页，共70页，编辑于2022年，星期一1 DS选择选择-例例6-问题分析问题分析n计算机存储数据是按类型分配空间的。在计算机存储数据是按类型分配空间的。在P

31、C上：上：q整型：整型：2个字节个字节16位，则整型数据的范围为位，则整型数据的范围为-3276832767；q长整型：长整型：4个字节个字节32位，则长整型数据的范围为位，则长整型数据的范围为-21474836482147483647；q实型：实型：4个字节个字节32位，但非精确存储数据，只有六位精位，但非精确存储数据，只有六位精度，数据的范围度，数据的范围(3.4e-383.4e+38)；q双精度型：双精度型：8个字节个字节64位的存储空间，数据的范围位的存储空间，数据的范围(1.7e-3081.7e+308)，其精确位数是，其精确位数是17位。位。n这些类型无法存储这些类型无法存储100

32、！这样的！这样的“大整数大整数”。n需要使用更复杂、更有针对性的数据结构。需要使用更复杂、更有针对性的数据结构。31第31页，共70页，编辑于2022年，星期一1 DS选择选择-例例6-算法设计算法设计n每一位数，都是一个每一位数，都是一个10以内数字。多个，相同属性的，以内数字。多个，相同属性的，n数组是有头有尾的：数组是有头有尾的：a1an。高位、低位谁头谁尾？。高位、低位谁头谁尾？n低位固定，而高位不定。最低位为低位固定，而高位不定。最低位为a1，且在高端要为问题最大存，且在高端要为问题最大存储数据留够空位。储数据留够空位。基于存储的考虑基于存储的考虑 int an32第32页，共70页

33、，编辑于2022年，星期一1 DS选择选择-例例6-算法设计算法设计n100！=1*2*3*99*100。n按此方法计算，最困难的操作是：按此方法计算，最困难的操作是：大整数大整数*乘数，其中乘数乘数，其中乘数=100。基于功能的考虑基于功能的考虑 n原来一个元素存一位，现在是否要改变？改变是否有用？原来一个元素存一位，现在是否要改变？改变是否有用？n问题出在哪里？问题出在哪里？n当低位元素计算后的值超过当低位元素计算后的值超过9时，需向高位元素进位。时，需向高位元素进位。如何进位？如何进位？33第33页，共70页，编辑于2022年，星期一1 DS选择选择-例例6-算法设计算法设计nintan

34、中的数组元素可以存放更大的数。如，每个存中的数组元素可以存放更大的数。如，每个存3位。位。基于性能的考虑基于性能的考虑 进位进位4次。次。进位几次？进位几次？n进位需要特殊的处理；减少进位的处理，可以提高效率。进位需要特殊的处理；减少进位的处理，可以提高效率。n每个元素处理的位数越多，进位次数越少。每个元素处理的位数越多，进位次数越少。n在前面提到的四种数据类型的基础上，粗略估计一下，本问题在前面提到的四种数据类型的基础上，粗略估计一下，本问题中，每个元素最多可以存储几位数据？中，每个元素最多可以存储几位数据？34第34页，共70页，编辑于2022年，星期一1 DS选择选择-例例6-算法实现算

35、法实现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=m;j+)b=abj*i+d;abj=b mod 1000000;d=b/1000000;if(d0)aj=d;for(i=m;i=1;i-)if(abi=0)continue;else r=i;break;print(n,“!=”);print(abr);for(i=r-1;i=1;i-)if(abi99999)print(abi);continue;if (

36、abi9999)print(“0”,abi);continue;if (abi 999)print(“00”,abi);continue;if (abi99)print(“000”,abi);continue;if (abi9)print(“0000”,abi);continue;print(“00000”,abi);/for B存储计算的中间结果，存储计算的中间结果，d存储超过存储超过6位数位数后的进位，后的进位，ab数组存储每次累乘的结果，数组存储每次累乘的结果，每个元素存储每个元素存储6位数字位数字35第35页，共70页，编辑于2022年，星期一算法说明算法说明nm=log(n)*n/6

37、+2;是对是对n!位数的粗略估计，这样做算法简位数的粗略估计，这样做算法简单，但是效率低。改进方法：记录当前积所占数组元素的单，但是效率低。改进方法：记录当前积所占数组元素的个数，初值为个数，初值为1，每次有进位时，每次有进位时m增加增加1。将第二个。将第二个for循环循环中中if语句改为语句改为if(d0)aj=d;m=m+1;n输出时，首先计算结果的准确位数输出时，首先计算结果的准确位数r，然后输出最高位数，然后输出最高位数据，输出其他单元数据要注意，如若结果为据，输出其他单元数据要注意，如若结果为123000001，ab1中是中是1，不是，不是00000136第36页，共70页，编辑于2

38、022年，星期一1 数据结构的选择很重要数据结构的选择很重要-总结总结n基于存储的考虑基于存储的考虑n基于功能的考虑基于功能的考虑n基于性能的考虑基于性能的考虑37第37页，共70页，编辑于2022年，星期一2 数组与指针数组与指针n一聚，一散一聚，一散n一动，一静一动，一静n静中有动静中有动n高级语言的支持高级语言的支持n数组和指针在程序设计、数据结构中占重要角色。数组和指针在程序设计、数据结构中占重要角色。q在基础类型上的扩展；在基础类型上的扩展；q构成复杂数据类型的基础和重要方式。构成复杂数据类型的基础和重要方式。n数据的逻辑结构常分为四大类：数据的逻辑结构常分为四大类：q集合结构集合结

39、构q线性结构线性结构q树形结构树形结构q图结构（网结构）图结构（网结构）数组和指针均可实现数组和指针均可实现 38第38页，共70页，编辑于2022年，星期一3 数组与指针数组与指针一聚，一散一聚，一散n连续存储连续存储q可随机存取可随机存取(通过数组名、下标便可以访问通过数组名、下标便可以访问)；L a1a2an a1 a2 ai an n链式存储链式存储q在内存中方便利用碎片存储。在内存中方便利用碎片存储。n例例7线性表的实现线性表的实现q无需多余存储单元，空间效率高。无需多余存储单元，空间效率高。39第39页，共70页，编辑于2022年，星期一3数组与指针数组与指针一动，一静一动，一静L

40、 a1a2an a1 a2 ai an n例例7线性表的实现线性表的实现n连续存储连续存储q数组的空间在分配后相对固定；数组的空间在分配后相对固定；n链式存储链式存储q可以方便的进行插入、删除操作。可以方便的进行插入、删除操作。q但也有变通方法，静中有动。但也有变通方法，静中有动。40第40页，共70页，编辑于2022年，星期一3数组与指针数组与指针静中有动静中有动n动态声明数组：动态声明数组：动态数组动态数组动态声明动态声明C不支持不支持C+通过指针支持通过指针支持Java支持支持nC语言不支持：语言不支持：intn;scanf(%d,&n);intan;nC+语言利用指针支持：语言利用指针

41、支持：intlen;cinlen;int*p=newintlen;nJava语言支持：语言支持：inta；输入输入len值；值；a=newintlen；41第41页，共70页，编辑于2022年，星期一3 数组与指针数组与指针静中有动静中有动n初始化后改变长度初始化后改变长度动态数组动态数组初始化后可变长初始化后可变长CRealloc帮助实现；帮助实现；C+不支持，有类支持；不支持，有类支持；Java数组不支持，有数组不支持，有ArrayList、Vector类支持。类支持。Listlst=newArrayList();lst.add(newInteger(37);一个整型值一个整型值37用于构

42、造一个用于构造一个Integer封装类对象，然后那个对封装类对象，然后那个对象被加入到列表。象被加入到列表。42第42页，共70页，编辑于2022年，星期一3 数组与指针数组与指针高级语言的支持高级语言的支持n在本课程的算法实现中，使用类在本课程的算法实现中，使用类C语言，在可能的情况下语言，在可能的情况下均使用数组，数组使用静态数组。均使用数组，数组使用静态数组。n这符合这符合“简单明了简单明了”的表达原则。的表达原则。指针指针C支持支持C+支持支持Java不支持，通过不支持，通过“引用引用”部分部分的实现指针功能的实现指针功能Strings=newString(“howmuch?);43第

43、43页，共70页，编辑于2022年，星期一3.从算法到实现从算法到实现-算法基本技巧举例算法基本技巧举例na.算术运算的妙用算术运算的妙用q例例8开灯问题开灯问题nb.巧用巧用“标志量标志量”q例例9判定输入判定输入n个数据互不相等个数据互不相等q例例10冒泡排序冒泡排序nc.信息数字化信息数字化q例例11警察抓小偷警察抓小偷nd.学会找规律学会找规律q例例12数组移位数组移位44第44页，共70页，编辑于2022年，星期一a.算术运算的妙用算术运算的妙用-例例8开灯问题开灯问题n算术运算：加减乘除。算术运算：加减乘除。n例例8开灯问题开灯问题n有从有从1到到n依次编号的依次编号的n个同学和个

44、同学和n盏灯。盏灯。1号同学将所有的灯都关掉；号同学将所有的灯都关掉；2号同学将编号为号同学将编号为2的倍数的灯都打开；的倍数的灯都打开；3号同学则将编号为号同学则将编号为3的倍数的灯作相反处理（该号灯如打开的，则关掉；如的倍数的灯作相反处理（该号灯如打开的，则关掉；如关闭的，则打开）；关闭的，则打开）；以后的同学都将自己编号的倍数的灯，作相反处理。以后的同学都将自己编号的倍数的灯，作相反处理。问：经问：经n个同学操作后，哪些灯是打开的？个同学操作后，哪些灯是打开的？45第45页，共70页，编辑于2022年，星期一n问题分析：问题分析：n1）用数组表示某种状态，这里定义有）用数组表示某种状态，

45、这里定义有n个元素的个元素的a数组，它的每个下标变量数组，它的每个下标变量ai视视为一灯，为一灯，i表示其编号。表示其编号。ai=1表示灯处于打开状态，表示灯处于打开状态，ai=0表示灯处于关闭状表示灯处于关闭状态。态。此用法也称为此用法也称为“乒乓开关乒乓开关”。简。简化逻辑表达式、减少条件判断化逻辑表达式、减少条件判断n2）实现将第）实现将第i灯作相反处理的操作：灯作相反处理的操作：q条件语句条件语句if表示：表示：ifai=1ai=0；ifai=0ai=1；q通过算术运算更简练、逼真：通过算术运算更简练、逼真：ai=1-ai。a.算术运算的妙用-例8问题分析/建模46第46页，共70页，

46、编辑于2022年，星期一a.算术运算的妙用-例8-算法设计nint a1000;输入输入n的数值的数值；关闭所有灯，即关闭所有灯，即a1an置为置为0；第第2个学生个学生-第第n个学生个学生(学生学生i)进行操作：进行操作：操作对象：操作对象：数组数组a，灯编号含因数，灯编号含因数i，即，即ai*k；操作：ai*k=1-ai*k；输出灯的开关状态。输出灯的开关状态。47第47页，共70页，编辑于2022年，星期一n建立一个充分大的数组建立一个充分大的数组inta1000;输入输入n的数值；的数值；关闭所有灯，即关闭所有灯，即a1an置为置为0；第第2-第第n个学生个学生(每个学生每个学生i)进

47、行操作：进行操作：操作对象：数组操作对象：数组a，灯编号含因数灯编号含因数i，即，即ai*k操作：操作：ai*k=1-ai*k；输出灯的开关状态。输出灯的开关状态。voidmain()intn,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，则无重复；反之，有重复。

48、，则无重复；反之，有重复。b 巧用巧用“标志量标志量”-例例9算法设计算法设计50第50页，共70页，编辑于2022年，星期一b 巧用“标志量”-例9 实现voidmain()inta100,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(Norepeatn);elseprintf(Repeatn);51第51页，共70页，编辑于2022年，星期一例例10冒泡排

49、序冒泡排序 v 排序过程排序过程 1、比较第一个记录与第二个、比较第一个记录与第二个 记录，若关键字为逆序则交换；然记录，若关键字为逆序则交换；然 后比较第二个记录与第三个记录；后比较第二个记录与第三个记录；依次类推，直至第依次类推，直至第 n-1 个记录和第个记录和第 n 个记录比较为止个记录比较为止第一趟冒泡第一趟冒泡第一趟冒泡第一趟冒泡 排序排序排序排序，结果关键字最大的记录被安，结果关键字最大的记录被安 置在最后一个记录上。置在最后一个记录上。2、对前、对前 n-1 个记录进行第二个记录进行第二 趟冒泡排序，结果使关键字次大的趟冒泡排序，结果使关键字次大的 记录被安置在第记录被安置在第

50、 n-1 个记录位置。个记录位置。3、重复上述过程，直到、重复上述过程，直到 “在在 一趟排序过程中没有进行过交换记一趟排序过程中没有进行过交换记 录的操作录的操作”为止。为止。初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 第第 一一 趟趟 排排 序序 49 38 49 97 76 97 97 13 97 97 27 97 97 499797 38 49 65 76 13 27 49 979738 49 65 13 27 49 76 76 第第 二二 趟趟 排排 序序 38 49 13 27 49 65 65 第第 三三 趟趟 排排 序序 38 13 27 49