算法基本工具

《算法基本工具》由会员分享，可在线阅读，更多相关《算法基本工具（69页珍藏版）》请在装配图网上搜索。

1、13.1.1 循环与递归循环与递归n设计算法重复处理大量数据的思路：设计算法重复处理大量数据的思路：以不变应万变；以不变应万变；n两种思路：两种思路：循环、递归。循环、递归。n1 循环设计要点循环设计要点q例例3.1 求完数求完数q例例3.2 打印数字图形打印数字图形q例例3.3 求级数求级数n2 递归设计思路递归设计思路(运行机制、复杂度分析运行机制、复杂度分析)q例例3.4 累加求和累加求和n3 递归设计要点递归设计要点q例例3.5 hanoi塔塔n4 非递归非递归(循环循环)/递归比较递归比较21 循环设计要点循环设计要点n循环控制循环控制-熟悉；熟悉；n设计要点：设计要点：q注意算法的

2、效率注意算法的效率q“自顶向下自顶向下”的设计方法的设计方法 q由具体到抽象设计循环结构由具体到抽象设计循环结构31 循环设计要点循环设计要点-例例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)!算法设计算法设计1：直接利用题目中累加项通式，构造出循环体：直接利用题目中累加项通式，构造出循环体不变式为：不变式为：S=S+(-

3、1)n+1/(2n-1)!需要用二重循环来完成算法。需要用二重循环来完成算法。n算法设计算法设计1：q外层循环求累加外层循环求累加S=S+A;q内层循环求累乘内层循环求累乘A=(-1)n+1/(2n-1)!。41 循环设计要点循环设计要点-例例1n算法分析：算法分析：n以上算法是二重循环来完成以上算法是二重循环来完成，但算法的效率却太低，但算法的效率却太低O(n2)。n数学模型数学模型2：Sn=Sn-1+(-1)n+1An；An=An-1*1/(2*n-2)*(2*n-1)n其原因是，当前一次循环已求出其原因是，当前一次循环已求出7！，当这次要想求！，当这次要想求9！时，！时，没必要再从没必要

4、再从1去累乘到去累乘到9，只需要充分利用前一次的结果，只需要充分利用前一次的结果，用用7！*8*9即可得到即可得到9！，模型为！，模型为An=An-1*1/(2*n-2)*(2*n-1)。n算法分析：按照数学模型算法分析：按照数学模型2，只需一重循环就能解决问题，只需一重循环就能解决问题算法的时间复杂性为算法的时间复杂性为O(n)。51 循环设计要点循环设计要点-例例2（自顶向下的设计方法）（自顶向下的设计方法）n例例2.编算法找出编算法找出1000以内所有完数。以内所有完数。n如：如：28的因子为的因子为1、2、4、7，14，而，而28=1+2+4+7+14。因此因此28是是“完数完数”。编

5、算法找出。编算法找出1000之内的所有完数，之内的所有完数，并按下面格式输出其因子：并按下面格式输出其因子：28 its factors are 1，2，4，7，14。n问题分析：问题分析：n1、这里、这里不是要质因数不是要质因数，所以找到因数后也无需将其从数，所以找到因数后也无需将其从数据中据中“除掉除掉”。n2、每个因数只记一次每个因数只记一次，如，如8的因数为的因数为1，2，4而不是而不是1，2，2，2，4。(注：本题限定因数不包括这个数本身注：本题限定因数不包括这个数本身)61 循环设计要点循环设计要点-例例2n核心算法设计核心算法设计qfor(i=0;in;i=i+1)判断判断i是否

6、是完数是否是完数;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(i mod j=0)s=s+j;if (s=i)i是是“完数完数”;判断是否是完数的方法是判断是否是完数的方法是“不变不变”，被判断的数是，被判断的数是“万变万变”。7输出数据的方法是输出数据的方法是“不不变变”，被输出的数是，被输出的数是“万万变变”。1

7、循环设计要点循环设计要点-例例2n考虑到要按格式输出结果，应该开辟数组存储数据考虑到要按格式输出结果，应该开辟数组存储数据i的所的所有因子，并记录其因子的个数，因此算法细化如下：有因子，并记录其因子的个数，因此算法细化如下：qint a100，s=1,k=0;for(j=2;ji;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;jk;j+)print(“,”,ak)81 循环设计要点循环设计要点-例例3（从具体到抽象设计循环）（从具体到抽象设计循环）n对于不太熟悉的问题，其对于不太

8、熟悉的问题，其“不变不变”不易抽象；不易抽象；1 6 2 10 7 3 13 11 8 4 15 14 12 9 5n=5n例例3 编写算法：根据参数编写算法：根据参数n打印具有下面规律的图形，如，打印具有下面规律的图形，如，当当n=4时，图形如下：时，图形如下：q1 q5 2 q8 6 3 q10 9 7 4 91 循环设计要点循环设计要点-例例3 1 5 2 8 6 3 10 9 7 4 n问题分析：问题分析：q容易发现图形中数据排列的规律。容易发现图形中数据排列的规律。q另一种思路另一种思路n先用一个数组按此顺序存储数据，先用一个数组按此顺序存储数据，再正常输出；再正常输出；1 5 2

9、8 6 3 10 9 7 4 q可不可以从可不可以从1最大数，通过循环，直接输出？最大数，通过循环，直接输出？nprintf是按照从左至右、从上至下的顺序；若想直接是按照从左至右、从上至下的顺序；若想直接输出，只有找出公式，循环计算得到序列：输出，只有找出公式，循环计算得到序列：1-n-5-2-n-8-6-3-n-10-9-7-4.n为数组赋值，也要用循环，如何循环？为数组赋值，也要用循环，如何循环？又要回到找规律公式的路上吗？又要回到找规律公式的路上吗？n斜着能循环吗？斜着能循环吗？101 循环设计要点循环设计要点-例例3n用斜行、列描述新的循环方向。用斜行、列描述新的循环方向。1 5 2

10、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,3n列号相同；列号相同；n行号行号(显然行号与列号有关显然行号与列号有关)q第第1斜行，对应行号斜行，对应行号1n，行号与列号，行号与列号j同；同；q第第2斜行，对应行号斜行，对应行号2n，行号比列号，行号比列号j大大1；q第第3斜行，对应行号斜行，对应行号3n，行号比列号，行号比列号j大大2；斜斜3，1a3,1斜斜3，2a4,2斜行斜行i取值取值(1n)列列j取值取值(1n+1-i)ai-1+jjn这样可以描述循环。但数组元素的存取这样可以

11、描述循环。但数组元素的存取还是基于还是基于“行列行列”，能否简单转换？，能否简单转换？n关键问题：第关键问题：第i斜行、斜行、j列的数据对应于列的数据对应于第几行第几列的元素？第几行第几列的元素？斜斜4，1a4,1111 循环设计要点循环设计要点-例例3main()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)列列

12、j取值取值(1n+1-i)1 5 2 8 6 3 10 9 7 4 122 递归设计思路递归设计思路-例例4n程序结构化设计的三种基本结构，顺序、选择、循环是不程序结构化设计的三种基本结构，顺序、选择、循环是不是必须的？是必须的？n例例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);ni sumn回答：在很多高级语言中，不是。可以抛弃谁呢？回答：在很多高级语言中，不是。可以抛弃谁呢？n递归能取代循环的作用递归能取代循环的作用。132 递归设计思路

13、递归设计思路-例例4n例例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)sum(n-1)n+sum(n-2)n-1+.sum(n-3)n-2+1n递归算法是一个模块递归算法是一个模块(函数、过程函数、过程)除了可调用其它模除了可调用其它模 块块(函数、过程函数、过程)外，还可以直接或间接地调用自身的算法。外，还可以直接或间接地调用自身的算法。直接直接/间接递归调用。间接

14、递归调用。n代入代入n=4，走一遍。，走一遍。递归树！递归树！sum(1)2+142 递归设计思路递归设计思路-例例4n例例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)出栈出栈 进栈进栈 栈底元素栈底元素 n sumn-1 sum.;2 sum1 sum表面上是一个变量，表面上是一个变量，实际上是一个实际上是一个栈栈152 递归设计思路递

15、归设计思路-例例4n例例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;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“收敛收敛”3 递归设计要点递归设计要点n递归的关键在于找出递归的关键在于找出递归方程式递归方程式和和递归终止条件

16、递归终止条件。q递归定义：使问题向边界条件转化的规则。递归定义必递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。须能使问题越来越简单。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+su

17、m(1)2+117例例1.1 欧几里德算法欧几里德算法ngcd(m,n)=gcd(n,m mod n)n输入输入 正整数正整数m和和n 输出输出 m和和n的最大公因子的最大公因子n如果如果n=0,计算停止返回计算停止返回m,m即为结果；否则继续即为结果；否则继续2。n记记r为为m除以除以n的余数，即的余数，即r=m mod n。n把把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)else

18、return(GCD(n,m mod n)18GCD(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;193 递归设计要点递归设计要点-hanoi塔塔nHanoi塔塔qhanoi河内河内越南首都越南首都q古代有一个梵塔，塔内有古代有一个梵塔，塔内有3个基座个基座A、B、C，q开始时开始时A基座上有基座上有64个盘子，盘子大小不等，大的在下，个盘子，盘子大小不等，大的在下，小的在上。小的在上。q有一个

19、老和尚想把这有一个老和尚想把这64个盘子从个盘子从A座移到座移到B座，但每次座，但每次只允许移动一个盘子，且在移动过程中在只允许移动一个盘子，且在移动过程中在3个基座上的个基座上的盘子都始终保持大盘在下，小盘在上。盘子都始终保持大盘在下，小盘在上。q在移动过程中可以利用在移动过程中可以利用C基座做辅助。基座做辅助。q请编程打印出移动过程请编程打印出移动过程。q约定盘子自上而下的编号为约定盘子自上而下的编号为1，2，3，n。203 递归设计要点递归设计要点-hanoi塔塔n首先看一下首先看一下2阶汉诺塔问题的解，不难理解以下移动过程：阶汉诺塔问题的解，不难理解以下移动过程：n初始状态为初始状态为

20、 A(1,2)B()C()q第一步后第一步后 A(2)B()C(1)q第二步后第二步后 A()B(2)C(1)q第三步后第三步后 A()B(1,2)C()n用递归思路考虑用递归思路考虑213 递归设计要点递归设计要点-hanoi塔塔n把把n个盘子抽象地看作个盘子抽象地看作“两个盘子两个盘子”，上面，上面“一个一个”由由1n-1号组成，下面号组成，下面“一个一个”就是就是n号盘子。移动过程如下：号盘子。移动过程如下：n第一步：先把上面第一步：先把上面“一个一个”盘子以盘子以a基座为起点借助基座为起点借助b基座基座移到移到c基座。基座。n第二步：把下面第二步：把下面“一个一个”盘子从盘子从a基座移

21、到基座移到b基座。基座。n第三步：再把第三步：再把c基座上的基座上的n-1盘子借助盘子借助a基座移到基座移到b基座。基座。223 递归设计要点递归设计要点-hanoi塔塔n把把n阶的汉诺塔问题的模块记作阶的汉诺塔问题的模块记作hanoi(n,a,b,c)qa代表每一次移动的起始基座；代表每一次移动的起始基座；qb代表每一次移动的终点基座；代表每一次移动的终点基座；qc代表每一次移动的辅助基座代表每一次移动的辅助基座 ；q则则hanoi(n,a,c,b)，表示把，表示把n个盘子从个盘子从a搬到搬到c，可以借助，可以借助b；qhanoi(5,c,a,b)，表示把，表示把5个盘子从个盘子从c搬到搬到

22、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至此找出了大规模问题与小规模问题的关系。至此找出了大规模问题与小规模问题的关系。233 递归设计要点递归设计要点-hanoi塔塔nhanoi(n,a,b,c)qa：起始基座：起始基座qb：终点基座：终点基座qc：辅助基座：辅助基座 hanoi(n,a,b,c)hanoi(n-1,a,c,b)ha

23、noi(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)243 递归设计要点递归设计要点-hanoi塔塔nhanoi(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

24、.”from pile”,a,”to”b);hanoi(n-1,c,b,a);254 非递归非递归(循环循环)/递归比较递归比较-非递归非递归hanoi塔塔n递归思路不适合人类使用：人脑的逆推深度是有限的，而递归思路不适合人类使用：人脑的逆推深度是有限的，而计算机要比人脑深很多，论记忆的准确性，计算机要比人计算机要比人脑深很多，论记忆的准确性，计算机要比人脑强很多。脑强很多。q你用递归的程序，用你用递归的程序，用n=10，试试看？，试试看？q通过分析可以找到非递归的思路，而这种思路是未学过通过分析可以找到非递归的思路，而这种思路是未学过递归思想的人常用的。递归思想的人常用的。264 非递归非递

25、归(循环循环)/递归比较递归比较-转化转化n设计算法重复处理大量数据的思路：以不变应万变；设计算法重复处理大量数据的思路：以不变应万变；n两种思路：非递归两种思路：非递归(循环循环)、递归。、递归。n1、有些问题可以方便的用循环、有些问题可以方便的用循环/递归两种思路处理；递归两种思路处理；q如例如例4 累加求和；累加求和；在后面的课程中，会常遇到递归算法，以及同在后面的课程中，会常遇到递归算法，以及同一问题的递归、非递归算法。一问题的递归、非递归算法。n2、有些问题用递归比较方便；转换成非递归过程可通过、有些问题用递归比较方便；转换成非递归过程可通过模拟递归过程的执行过程来实现；其基本思想是

26、在程序中模拟递归过程的执行过程来实现；其基本思想是在程序中设置一个栈；设置一个栈；q如例如例5 hanoi塔。塔。同一个问题干嘛要学同一个问题干嘛要学两种方法？两种方法？27从算法设计从算法设计的角度的角度递归函数调用引递归函数调用引起的栈操作起的栈操作4 非递归非递归(循环循环)/递归比较递归比较递归递归非递归非递归程序可读性程序可读性易易难难代码量大小代码量大小小小大大时间时间长长短短占用空间占用空间大大小小适用范围适用范围广广窄窄设计难度设计难度易易难难n并不是每一门语言都支持并不是每一门语言都支持/很好的支持递归；很好的支持递归；n有助于理解递归的本质；有助于理解递归的本质；n有助于理

27、解栈有助于理解栈,树等数据结构；树等数据结构；n两者各有利弊：两者各有利弊：28n1 数据结构的选择很重要数据结构的选择很重要q例例6 大整数存储及运算大整数存储及运算n2 算法和数据结构不分离算法和数据结构不分离q例例7 线性表的实现线性表的实现n3 数组与指针数组与指针q例例7 线性表的实现线性表的实现q一聚，一散一聚，一散q一静，一动一静，一动q静中有动静中有动q高级语言的支持高级语言的支持3.2 算法与基本数据结构算法与基本数据结构291 数据结构的选择很重要数据结构的选择很重要n计算机解决问题是对计算机解决问题是对“数据数据”加工处理。加工处理。n例例6 编程求当编程求当N=100时

28、，时，N！的准确值。！的准确值。n问题分析：问题分析：q例如：例如：q9！=362880q100！=93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963895217 599993 229915 608914 463976 156578286253 697920 827223 758251 185210 916864000000 000000 000000 000000 n处理对象的情况严重影响处理过程、效果。处理对象的情况严重影响处理过程、效果。n数值问题数值问题/非数值问题。非数值问题。301 DS选

29、择选择-例例6-问题分析问题分析n计算机存储数据是按类型分配空间的。在计算机存储数据是按类型分配空间的。在PC上：上：q整型：整型：2个字节个字节16位，则整型数据的范围为位，则整型数据的范围为-3276832767；q长整型：长整型：4个字节个字节32位，则长整型数据的范围为位，则长整型数据的范围为 -21474836482147483647；q实型：实型：4个字节个字节32位，但非精确存储数据，只有六位精位，但非精确存储数据，只有六位精度，数据的范围度，数据的范围(3.4e-383.4e+38)；q双精度型：双精度型：8个字节个字节64位的存储空间，数据的范围位的存储空间，数据的范围(1.

30、7e-3081.7e+308)，其精确位数是，其精确位数是17位。位。n这些类型无法存储这些类型无法存储100！这样的！这样的“大整数大整数”。n需要使用更复杂、更有针对性的数据结构。需要使用更复杂、更有针对性的数据结构。311 DS选择选择-例例6-算法设计算法设计n每一位数，都是一个每一位数，都是一个10以内数字。多个，相同属性的，以内数字。多个，相同属性的，n数组是有头有尾的：数组是有头有尾的：a1an。高位、低位谁头谁尾？。高位、低位谁头谁尾？n低位固定，而高位不定。最低位为低位固定，而高位不定。最低位为a1，且在高端要为问，且在高端要为问题最大存储数据留够空位。题最大存储数据留够空位

31、。基于存储的考虑基于存储的考虑 int an321 DS选择选择-例例6-算法设计算法设计n100！=1*2*3*99*100。n按此方法计算，最困难的操作是：按此方法计算，最困难的操作是：大整数大整数*乘数，其中乘数乘数，其中乘数=100。基于功能的考虑基于功能的考虑 n原来一个元素存一位，现在是否要改变？改变是否有用？原来一个元素存一位，现在是否要改变？改变是否有用？n问题出在哪里？问题出在哪里？n当低位元素计算后的值超过当低位元素计算后的值超过9时，需向高位元素进位。时，需向高位元素进位。如何进位？如何进位？331 DS选择选择-例例6-算法设计算法设计nint an中的数组元素可以存放

32、更大的数。如，每个存中的数组元素可以存放更大的数。如，每个存3位。位。基于性能的考虑基于性能的考虑 进位进位4次。次。进位几次？进位几次？n进位需要特殊的处理；减少进位的处理，可以提高效率。进位需要特殊的处理；减少进位的处理，可以提高效率。n每个元素处理的位数越多，进位次数越少。每个元素处理的位数越多，进位次数越少。n在前面提到的四种数据类型的基础上，粗略估计一下，本在前面提到的四种数据类型的基础上，粗略估计一下，本问题中，每个元素最多可以存储几位数据？问题中，每个元素最多可以存储几位数据？341 DS选择选择-例例6-算法实现算法实现main()long ab256,b,d;int m,n,

33、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 (abi9999)print(“0”,abi);continue;

34、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算法说明算法说明nm=log(n)*n/6+2;是对是对n!位数的粗略估计，这样做算法简位数的粗略估计，这样做算法简单，但是效率低。改进方法：记录当前

35、积所占数组元素的单，但是效率低。改进方法：记录当前积所占数组元素的个数，初值为个数，初值为1，每次有进位时，每次有进位时m增加增加1。将第二个。将第二个for循循环中环中if语句改为语句改为 if(d0)aj=d;m=m+1;n输出时，首先计算结果的准确位数输出时，首先计算结果的准确位数r，然后输出最高位数，然后输出最高位数据，输出其他单元数据要注意，如若结果为据，输出其他单元数据要注意，如若结果为 123 000001，ab1中是中是1，不是，不是000001361 数据结构的选择很重要数据结构的选择很重要-总结总结n基于存储的考虑基于存储的考虑n基于功能的考虑基于功能的考虑n基于性能的考虑

36、基于性能的考虑372 数组与指针数组与指针n一聚，一散一聚，一散n一动，一静一动，一静n静中有动静中有动n高级语言的支持高级语言的支持n数组和指针在程序设计、数据结构中占重要角色。数组和指针在程序设计、数据结构中占重要角色。q在基础类型上的扩展；在基础类型上的扩展；q构成复杂数据类型的基础和重要方式。构成复杂数据类型的基础和重要方式。n数据的逻辑结构常分为四大类：数据的逻辑结构常分为四大类：q集合结构集合结构q线性结构线性结构q树形结构树形结构q图结构（网结构）图结构（网结构）数组和指针均可实现数组和指针均可实现 383 数组与指针数组与指针一聚，一散一聚，一散n连续存储连续存储q可随机存取可

37、随机存取(通过数组名、下标便可以访问通过数组名、下标便可以访问)；L a1a2an a1 a2 ai an n链式存储链式存储q在内存中方便利用碎片存储。在内存中方便利用碎片存储。n例例7 线性表的实现线性表的实现q无需多余存储单元，空间效率高。无需多余存储单元，空间效率高。393数组与指针数组与指针一动，一静一动，一静L a1a2an a1 a2 ai an n例例7 线性表的实现线性表的实现n连续存储连续存储q数组的空间在分配后相对固定；数组的空间在分配后相对固定；n链式存储链式存储q可以方便的进行插入、删除操作。可以方便的进行插入、删除操作。q但也有变通方法，静中有动。但也有变通方法，静

38、中有动。403数组与指针数组与指针静中有动静中有动n动态声明数组：动态声明数组：动态数组动态数组动态声明动态声明C不支持不支持C+通过指针支持通过指针支持Java支持支持nC语言不支持：语言不支持：int n;scanf(%d,&n);int an;nC+语言利用指针支持：语言利用指针支持：int len;cinlen;int*p=new intlen;nJava语言支持：语言支持：int a；输入输入len值；值；a=new intlen；413 数组与指针数组与指针静中有动静中有动n初始化后改变长度初始化后改变长度动态数组动态数组初始化后可变长初始化后可变长CRealloc帮助实现；帮助实

39、现；C+不支持，有类支持；不支持，有类支持；Java数组不支持，有数组不支持，有ArrayList、Vector类支持。类支持。List lst=new ArrayList();lst.add(new Integer(37);一个整型值一个整型值37用于构造一个用于构造一个Integer封装类对象，然后那封装类对象，然后那个对象被加入到列表。个对象被加入到列表。423 数组与指针数组与指针高级语言的支持高级语言的支持n在本课程的算法实现中，使用类在本课程的算法实现中，使用类C语言，在可能的情况下语言，在可能的情况下均使用数组，数组使用静态数组。均使用数组，数组使用静态数组。n这符合这符合“简单

40、明了简单明了”的表达原则。的表达原则。指针指针C支持支持C+支持支持Java不支持，通过不支持，通过“引用引用”部部分的实现指针功能分的实现指针功能String s=new String(“how much?);433.从算法到实现从算法到实现-算法基本技巧举例算法基本技巧举例na.算术运算的妙用算术运算的妙用q例例8 开灯问题开灯问题nb.巧用巧用“标志量标志量”q例例9 判定输入判定输入n个数据互不相等个数据互不相等q例例10 冒泡排序冒泡排序nc.信息数字化信息数字化q例例11 警察抓小偷警察抓小偷nd.学会找规律学会找规律q例例12 数组移位数组移位44a.算术运算的妙用算术运算的妙用

41、-例例8开灯问题开灯问题n算术运算：加减乘除。算术运算：加减乘除。n例例8 开灯问题开灯问题n有从有从1到到n依次编号的依次编号的n个同学和个同学和n 盏灯。盏灯。1号同学将所有的灯都关掉；号同学将所有的灯都关掉；2号同学将编号为号同学将编号为2的倍数的灯都打开；的倍数的灯都打开；3号同学则将编号为号同学则将编号为3的倍数的灯作相反处理（该号灯如打开的，则关的倍数的灯作相反处理（该号灯如打开的，则关掉；如关闭的，则打开）；掉；如关闭的，则打开）；以后的同学都将自己编号的倍数的灯，作相反处理。以后的同学都将自己编号的倍数的灯，作相反处理。问：经问：经n个同学操作后，哪些灯是打开的？个同学操作后，

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

43、、逼真：通过算术运算更简练、逼真：ai=1-ai。a.算术运算的妙用-例8问题分析/建模46a.算术运算的妙用-例8-算法设计nint a1000;输入输入n的数值的数值；关闭所有灯，即关闭所有灯，即a1an置为置为0；第第2个学生个学生-第第n个学生个学生(学生学生i)进行操作：进行操作：操作对象：操作对象：数组数组a，灯编号含因数，灯编号含因数i，即，即ai*k；操作：ai*k=1-ai*k；输出灯的开关状态。输出灯的开关状态。47n建立一个充分大的数组建立一个充分大的数组int a1000;输入输入n的数值；的数值；关闭所有灯，即关闭所有灯，即a1an置为置为0；第第2-第第n个学生个学

44、生(每个学生每个学生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，循环中断；，循环中断；若若fla

45、g=1，则无重复；反之，有重复。，则无重复；反之，有重复。b 巧用巧用“标志量标志量”-例例9算法设计算法设计50b 巧用“标志量”-例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冒泡排序冒泡排序 v 排序过程排序过程 1、比较第一个

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

47、交换记一趟排序过程中没有进行过交换记 录的操作录的操作”为止。为止。初初 始始 关关 键键 字字 49 38 65 97 76 13 27 49 第第 一一 趟趟 排排 序序 49 38 49 97 76 97 97 13 97 97 27 97 97 49 38 49 65 76 13 27 49 38 49 65 13 27 49 第第 二二 趟趟 排排 序序 38 49 13 27 49 第第 三三 趟趟 排排 序序 38 13 27 49 第第 四四 趟趟 排排 序序 13 27 38第第 五五 趟趟 排排 序序 第第 六六 趟趟 排排 序序 for(j=1;j ;j+)if (r j

48、+1 r j)r j r j+1 ;for(j=1;j ;j+)if (r j+1 1;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如果原有数据有序，冒泡算法仍要做如果原有数据有序，冒泡算法仍要做n-1趟比较。事实上趟比较。事实上一趟比较下来，如果发现没有交换，就说明数据已经有序，一趟比较下来，如果发现没有交换，就说明数据已经有序，无须后续操作了无须后续操作了n数据原本有序概率不高，但

49、经过少于数据原本有序概率不高，但经过少于n-1次比较后，有序次比较后，有序概率就非常高了概率就非常高了n改进：设置标志位，检测数据是否有序改进：设置标志位，检测数据是否有序 flag=0表示没有进行交换，一旦有交换则置表示没有进行交换，一旦有交换则置flag=1.当一趟当一趟比较交换完成后，若比较交换完成后，若flag仍为仍为0，则无须进行下一趟操作。，则无须进行下一趟操作。算法略算法略53c 信息数字化信息数字化-例例11 警察抓小偷警察抓小偷n一些表面上看是非数值的问题，但经过进行数字化后，就可方便进行一些表面上看是非数值的问题，但经过进行数字化后，就可方便进行算法设计。算法设计。n例例1

50、.5 警察抓小偷警察抓小偷警察局抓了警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷。审四名偷窃嫌疑犯，其中只有一人是小偷。审问中问中 a说：说：“我不是小偷。我不是小偷。”b说：说：“c是小偷。是小偷。”c说：说：“小偷肯定是小偷肯定是d。”d说：说：“c在冤枉人。在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？是小偷？54c 信息数字化-例11-问题分析n问题分析：可通过循环，每次假设一名嫌疑犯为小偷，代入问题问题分析：可通过循环，每次假设一名嫌疑犯为小偷，代入问题系统，检验是否只有一句假

51、话。系统，检验是否只有一句假话。n这种让所有可能解都进行检验，以求得真解的方法称为这种让所有可能解都进行检验，以求得真解的方法称为“枚举尝枚举尝试法试法”，也是，也是“蛮力法蛮力法”、“暴力法暴力法”。n为方便设计程序，将为方便设计程序，将a,b,c,d将四个人进行编号，号码分别为将四个人进行编号，号码分别为1，2，3，4。55c 信息数字化-例11-算法设计n算法设计：用变量算法设计：用变量x存放小偷的编号，则存放小偷的编号，则x的取值范围从的取值范围从1取到取到4，就，就假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别

52、写成：写成：qa说的话：说的话：x1qb说的话：说的话：x=3qc说的话：说的话：x=4qd说的话：说的话：x4或或not(x=4)n注意注意:在在x的枚举过程中，当这四个的枚举过程中，当这四个逻辑式的值相加等于逻辑式的值相加等于3时，即表示时，即表示“四个人中三人说的是真话，一人说的是假话四个人中三人说的是真话，一人说的是假话”。if(x!=1)+(x=3)+(x=4)+(x!=4)=3)56c 信息数字化-例11-实现#include stdafx.hvoid main()int x;for(x=1;x=4;x=x+1)if(x!=1)+(x=3)+(x=4)+(x!=4)=3)print

53、f(%c is a thief,char(64+x);573.4 优化算法的数学模型优化算法的数学模型数学建模方法主要是归纳法。归纳法是从简单到复杂，由个别到一般数学建模方法主要是归纳法。归纳法是从简单到复杂，由个别到一般的一种研究方法，也就是的一种研究方法，也就是“找规律找规律”。学会找规律学会找规律-例例12 数组移位数组移位n例例12 数组中有数组中有n个数据，要将它们顺序循环向后移个数据，要将它们顺序循环向后移k位，即前面的元位，即前面的元素向后移素向后移k位，后面的元素则循环向前移位，后面的元素则循环向前移k位，例：位，例：0、1、2、3、4循循环移环移3位后为：位后为：2、3、4、

54、0、1。考虑到。考虑到n会很大，不允许用会很大，不允许用2*n以上以上个空间来完成此题。个空间来完成此题。58d 学会找规律-例12-问题分析(思路1)n问题分析问题分析1：若题目中没有关于存储空间的限制，我们可以方便地开若题目中没有关于存储空间的限制，我们可以方便地开辟两个一维数组，一个存储原始数据，另一个存储移动后的数据。辟两个一维数组，一个存储原始数据，另一个存储移动后的数据。n开始部分的元素从前向后移，容易确定；但数组中后开始部分的元素从前向后移，容易确定；但数组中后k个元素是从后个元素是从后向前移，如何确定？向前移，如何确定？59d 学会找规律-例12-问题分析(思路1)void a

55、lg1()int a100,b100,i,n,k;scanf(%d,%d,&n,&k);for(i=0;in;i=i+1)scanf(%d,&ai);for(i=0;in;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

56、,%d,&n,&k);for(i=0;in;i=i+1)scanf(%d,&ai);for(i=0;i0;j=j-1)aj=aj-1;a0=temp;for(i=0;in;i=i+1)printf(%d,ai);printf(n);62d学会找规律-例12-问题分析(思路3)n问题分析问题分析3：利用：利用一个临时存储空间一个临时存储空间，把每一个数据，把每一个数据一次移动到位一次移动到位。n1）一组循环移动的情况：）一组循环移动的情况：n通过计算我们可以确定某个元素移动后的具体位置，如通过计算我们可以确定某个元素移动后的具体位置，如n=5,k=3时：时：0、1、2、3、4循环移循环移3位后为

57、位后为2、3、4、0、1。可通过计算得出可通过计算得出0移到移到3的位置，的位置，3移到移到1的位置，的位置，1移到移到4的位置，的位置，4移移到到2的位置，的位置，2移到移到0的位置；一组移动（的位置；一组移动（0-3-1-4-2-0）正好将全部数）正好将全部数据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次据按要求进行了移动。这样只需要一个辅助变量，每个数据只需一次移动就可完成整个移动过程。移动就可完成整个移动过程。n如果算法就这样按一组移动去解决问题，就错了。因为还有其它情况。如果算法就这样按一组移动去解决问题，就错了。因为还有其它情况。63n2）多组循环移动的情况：算法不能

58、只按一组移动去解决问题。）多组循环移动的情况：算法不能只按一组移动去解决问题。n看下一个例子，当看下一个例子，当n=6，k=3时，时，0、1、2、3、4、5经移动的结果是经移动的结果是3、4、5、0、1、2.共要进行三组循环移动（共要进行三组循环移动（0-3，1-4，2-5）才能将）才能将全部数据操作完毕全部数据操作完毕。n循环移动的组数，与循环移动的组数，与k、n是怎么样的关系呢？是怎么样的关系呢？n我们再看一个例子，当我们再看一个例子，当N=6，K=2时时，0、1、2、3、4、5经移动的经移动的结果是结果是4、5、0、1、2、3。0移到移到2的位置，的位置，2移到移到4的位置，的位置，4移

59、到移到0的位置，一组移动完成了的位置，一组移动完成了3个数据的移动，接下来，还有一组个数据的移动，接下来，还有一组1-3-5-1。共进行二组循环移动，就能将全部数据移动完毕。共进行二组循环移动，就能将全部数据移动完毕。d学会找规律学会找规律-例例12-问题分析问题分析(思路思路3)64d学会找规律学会找规律-例例12-建模建模/算法设计算法设计(思路思路3)n数学模型：循环移动的组数等于数学模型：循环移动的组数等于N与与K的的最大公约数。最大公约数。n算法设计：算法设计：q1）编写函数，完成求）编写函数，完成求n,k最大公约数最大公约数m的功能。的功能。q2）进行）进行m组循环移动。组循环移动

60、。q3）每组移动，和算法）每组移动，和算法2一样，通过计算可以确定某个一样，通过计算可以确定某个元素移动后的具体位置。在移动之前，用临时变量存储元素移动后的具体位置。在移动之前，用临时变量存储需要被覆盖的数据。需要被覆盖的数据。65d学会找规律-例12-实现(思路3)void alg3()int a100,b0,b1,i,j,n,k,m,tt;scanf(%d,&n);scanf(%d,&k);for(i=0;in;i=i+1)scanf(%d,&ai);m=gcd(n,k);for(j=0;jm;j=j+1)b0=aj;tt=j;for(i=0;in/m;i=i+1)tt=(tt+k)%n;

61、b1=att;att=b0;b0=b1;for(i=0;in;i=i+1)printf(%d,ai);printf(n);664 算法为魂算法为魂n有人也许会说：有人也许会说：“今天计算机这么快，算法还重要吗？今天计算机这么快，算法还重要吗？”其实永远不会有太快的计算机，因为我们总会想出新的应其实永远不会有太快的计算机，因为我们总会想出新的应用。用。n日益先进的记录和存储手段使我们每个人的信息量都在爆日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。炸式的增长。n互联网的信息流量和日志容量也在飞快增长。互联网的信息流量和日志容量也在飞快增长。n在网络时代，越来越多的挑战需要靠卓越的

62、算法来解决。在网络时代，越来越多的挑战需要靠卓越的算法来解决。算法的力量算法的力量李开复李开复 n算法是计算机科学领域最重要的基石之一，但却受到了国算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门，就产生了一种误解，认为学计算求的编程语言五花八门，就产生了一种误解，认为学计算机就是学各种编程语言。编程语言虽然应该学，但是学习机就是学各种编程语言。编程语言虽然应该学，但是学习计算机算法和理论更重要，因为计算机语言和开发平台日计算机算法和理论更重要，因为计算机语言和开发平台日新

63、月异，但万变不离其宗的是那些算法和理论新月异，但万变不离其宗的是那些算法和理论。674 算法为魂算法为魂n现在你应该明白为什么我说现在你应该明白为什么我说“算法为魂，程序为衣算法为魂，程序为衣”了吧，了吧，而且那只是若干件衣中的一件而已。而且那只是若干件衣中的一件而已。算法为魂算法为魂凌小宁凌小宁n在大多数算法教材中，算法常常是用伪程序来描述的。伪在大多数算法教材中，算法常常是用伪程序来描述的。伪程序较接近高级计算机语言，但更易写易懂。其实算法的程序较接近高级计算机语言，但更易写易懂。其实算法的表达可以有多种形式：自然语言表达可以有多种形式：自然语言(英文，中文，英文，中文，.)，各种，各种计算机程序设计语言，甚至硬件。由此可见，算法的本质计算机程序设计语言，甚至硬件。由此可见，算法的本质是问题解决过程的概念，而相应的程序只是一种它的表述。是问题解决过程的概念，而相应的程序只是一种它的表述。68小结小结n理解循环与递归的意义；理解循环与递归的意义；n理解算法与数据结构的关系。理解算法与数据结构的关系。n掌握循环和递归的基本使用方法；掌握循环和递归的基本使用方法；n掌握算法设计中对数据结构的选择。掌握算法设计中对数据结构的选择。69作业作业nP117 4,8,13n要求：要求：C语言程序编写；要有算法分析；交电子稿语言程序编写；要有算法分析；交电子稿