算法基本工具和优化技巧精品文稿.ppt

《算法基本工具和优化技巧精品文稿.ppt》由会员分享，可在线阅读，更多相关《算法基本工具和优化技巧精品文稿.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法基本工具和优化技巧第1页，本讲稿共88页31循环与递归循环与递归32算法与数据结构算法与数据结构33算法优化基本技巧算法优化基本技巧34优化算法的数学模型优化算法的数学模型第2页，本讲稿共88页1.1.循环设计要点循环设计要点2.2.递归设计要点递归设计要点3.3.递归与循环的比较递归与循环的比较3.1循环与递归循环与递归第3页，本讲稿共88页 1设计中要注意算法的效率 2“自顶向下”的设计方法 3由具体到抽象设计循环结构 一、循环设计要点一、循环设计要点第4页，本讲稿共88页 循环体的特点是：循环体的特点是：“以不变应万变以不变应万变”。所谓所谓“不变不变”是指循环体内运算的表现形是指循

2、环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形式去相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。描述各种相似的重复运算。1 1循环循环设计设计中要注意算法的效率中要注意算法的效率第5页，本讲稿共88页【例例】求求数学模型数学模型1 1：第6页，本讲稿共88页main()main()int i,n,j,sign=1;int i,n,j,sign=1;float s,t=1;float s,t=1;input(n);input(n);s=1 s=1；for(i=2;i=n;i=i+1)for(

3、i=2;i=n;i=i+1)t=1;t=1;/求阶乘求阶乘 for(j=1;j=2*i-1;j=j+1)for(j=1;j=2*i-1;j=j+1)t=t*j;t=t*j;sign=1;/sign=1;/求（求（-1-1）n+1 for(j=1;j=i+1;j=j+1)for(j=1;j=i+1;j=j+1)sign=sign*(-1);sign=sign*(-1);s=s+sign/t;s=s+sign/t;print(print(“Sum=Sum=”,s);,s);算法的时间复杂度：算法的时间复杂度：O（n2）效率较低！效率较低！(2n-1)!=(2(n-1)-1)!*(2n-2)*(2n

4、-1)第7页，本讲稿共88页数学模型数学模型2 2：main()main()int i,n,sign;int i,n,sign;float s,t=1;float s,t=1;input(n);input(n);s=1 s=1；sign=1;sign=1;for(i=2;i=n;i=i+1)for(i=2;i=n;i=i+1)sign=-sign;t=t*(2*i-2)*(2*i-1);t=t*(2*i-2)*(2*i-1);s=s+sign/t;s=s+sign/t;print(print(“Sum=Sum=”,s);,s);算法的时间复杂度：算法的时间复杂度：O(n)第8页，本讲稿共88页

5、2 2“自自顶顶向下向下”的的设计设计方法方法 自自顶顶向下的方法是从全局走向局部、从向下的方法是从全局走向局部、从概略概略走向走向详详尽的尽的设设计计方法。自上而下是系方法。自上而下是系统统分解和分解和细细化的化的过过程。程。【例例】一一个个数数如如果果恰恰好好等等于于它它的的因因子子之之和和（包包括括1 1，但但不不包包括括这这个个数数本本身身），这这个个数数称称为为“完完数数”。编编算算法法找找出出10001000以内所有完数。以内所有完数。例例如如，2828的的因因子子为为1 1、2 2、4 4、7 7，1414（每每个个因因数数只只记记一一次次），而而28=1+2+4+7+1428=

6、1+2+4+7+14。因因此此2828是是“完完数数”。输输出出格格式式如下：如下：28 it28 its factors are 1s factors are 1，2 2，4 4，7 7，1414。第9页，本讲稿共88页1）顶层算法 for(i=2;i=1000;i=i+1)判断i是否为“完数”；是“完数”则按格式输出；2）判断i是否为“完数”for(j=2;ji;j=j+1)找i的因子，并累加如果累加值为i，则是“完数”第10页，本讲稿共88页3）进一步细化判断i是否“完数”算法s=1;for(j=2;ji;j=j+1)if(i mod j=0)s=s+j;if(s=i)i是“完数”;第1

7、1页，本讲稿共88页4 4）考虑输出格式）考虑输出格式判断判断i i是否是否“完数完数”算法算法 考考虑虑到到要要按按格格式式输输出出结结果果，应应该该开开辟辟数数组组存存储储数数据据i i的的所所有有因子，并记录其因子的个数，因此算法细化如下：因子，并记录其因子的个数，因此算法细化如下：定义数组a，s=1;k=0;for(j=2;ji;j=j+1)if(i mod j=0)(j是i的因素)s=s+j;ak=j;k=k+1;if(s=i)按格式输出结果 第12页，本讲稿共88页算法如下：算法如下：main()inti,k,j,s,a20;for(i=1;i=1000;i+)s=1;k=0;fo

8、r(j=2;ji;j+)if(imodj=0)s=s+j;ak=j;k+;if(i=s)print(s,“itsfactorsare:”,1);for(j=0;ik;j+)print(“,”,ak);第13页，本讲稿共88页 对于不太熟悉的问题，其数学模型或“机械化操作步骤”的不易抽象，下面看一个由具体到抽象设计循环细节的例题。【例】编写算法：打印具有下面规律的图形。1 5 2 8 6 3 10 9 7 4 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构第14页，本讲稿共88页main()int i,j,a100100,n,k;input(n);k=1;for(i=0;i=n-1;i=

9、i+1)for(j=0;j=n-i;j=j+1)ai-1+jjai-1+jj=k;k=k+1;for(i=0;i=n-1;i=i+1)print(“换行符”);for(j=0;j=10)while(n=10)ai=n mod 10;ai=n mod 10;i=i+1;i=i+1;n=n10;n=n10;ai=n;ai=n;for(j=i;j=0;j=j-1)for(j=i;j=0;j=j-1)print(n);print(n);循环算法如下：循环算法如下：第21页，本讲稿共88页f4(n)f4(n)if(n10)if(n=n;i-)for(i=1;i=n;i-)for(j=1;j=n;j-)f

10、or(j=1;j=n;j-)for(k=1;k=n;k-)for(k=1;k=n;k-)if(ij)and(jk)if(ij)and(jk)t=t+1;t=t+1;print(total=,t);print(total=,t);时间复杂度时间复杂度O(nO(n3 3)第25页，本讲稿共88页循环算法循环算法2：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=r-1;i-)s=s+comb(i,r-1);returns;r r层递归，每个算法递层递归，每个

11、算法递归归n-r+1n-r+1次。因此时间复次。因此时间复杂度为杂度为O(n*r)O(n*r)第28页，本讲稿共88页算法分析算法分析n递归的层次是可以控制的，而循环嵌套的递归的层次是可以控制的，而循环嵌套的层次只能是固定的层次只能是固定的第29页，本讲稿共88页递归递归非递归非递归程序可读性程序可读性易易难难代码量大小代码量大小小小大大时间时间长长短短占用空间占用空间大大小小适用范围适用范围广广窄窄设计难度设计难度易易难难递归与非递归的比较：递归与非递归的比较：第30页，本讲稿共88页3.2算法与数据结构算法与数据结构第31页，本讲稿共88页数据的逻辑结构常分为四大类：数据的逻辑结构常分为四

12、大类：（1 1）集合结构）集合结构 （2 2）线性结构）线性结构 （3 3）树形结构）树形结构（4 4）图结构（网结构）图结构（网结构）存储结构可以分为：连续存储和链式存储。连存储结构可以分为：连续存储和链式存储。连续存储又可以分为：静态存储和动态存储续存储又可以分为：静态存储和动态存储 1 1、常用的几种数据结构、常用的几种数据结构第32页，本讲稿共88页顺序存储的优点：顺序存储的优点：(1)方法简单，各种高级语言中都提供数组结构，容易方法简单，各种高级语言中都提供数组结构，容易实现。实现。(2)不用为表示结点间的逻辑关系而增加额外的存不用为表示结点间的逻辑关系而增加额外的存储开销。储开销。

13、(3)顺序表具有按元素序号随机访问的特点。顺序表具有按元素序号随机访问的特点。2 2、连续存储和链式存储比较、连续存储和链式存储比较第33页，本讲稿共88页顺序存储的缺点：顺序存储的缺点：(1)在顺序表中做插入删除操作时，平均移动大在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对约表中一半的元素，因此对n较大的顺序表效率低。较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大，需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。又会造成溢出。温馨提示：温馨提示：链表的优缺点恰好与

14、顺序表相反。链表的优缺点恰好与顺序表相反。第34页，本讲稿共88页3 3、在选取存储结构时权衡因素有：、在选取存储结构时权衡因素有：）基于存储的考虑）基于存储的考虑 顺序表的存储空间是静态分配的，在程顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就序执行之前必须明确规定它的存储规模，也就是说事先对是说事先对“MAXSIZEMAXSIZE”要有合适的设定，过要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的大造成浪费，过小造成溢出。可见对线性表的长度或长度或存储规模存储规模难以估计时，不宜采用顺序表；难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的

15、链表不用事先估计存储规模，但链表的存储密存储密度度较低。较低。第35页，本讲稿共88页）基于运算的考虑）基于运算的考虑 在顺序表中按序号访问在顺序表中按序号访问a ai i的时间性能时的时间性能时O(1)O(1)，而，而链表中按序号访问的时间性能链表中按序号访问的时间性能O(n)O(n)，所以如果经常做，所以如果经常做的运算是按序号的运算是按序号访问数据元素访问数据元素，显然顺序表优于链表；，显然顺序表优于链表；但对于但对于插入插入、删除删除操作，则后者优于前者。操作，则后者优于前者。）基于环境的考虑）基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，顺序表容易实现，任何高级语言中都

16、有数组类型，链表的操作是基于指针的，操作简单。链表的操作是基于指针的，操作简单。第36页，本讲稿共88页一、原始信息与处理结果对应存储一、原始信息与处理结果对应存储 每每一一个个问问题题中中的的信信息息往往往往是是多多方方面面的的，在在算算法法中中一一般般有有输输入入信信息息、输输出出信信息息和和信信息息加加工工处处理理过过程程中中的的中中间间信信息息。那那么么哪哪些些信信息息需需要要用用数数组组进进行行存存储储，数数组组元元素素下下标标与与信信息息怎怎么么样样对对应应等等问问题题的的确确定定，在在很很大大程程度度上上影影响着算法的编写效率和运行效率。响着算法的编写效率和运行效率。第37页，本

17、讲稿共88页【例例】某校决定由全校学生选举学生会主席。有某校决定由全校学生选举学生会主席。有5 5个候选人，个候选人，编号分别为编号分别为1 1，2 2，3 3，4 4，5 5，选举其中一人为学生会主席，每个，选举其中一人为学生会主席，每个学生一张选票，只能填写一人。请编程完成统计选票的工作。学生一张选票，只能填写一人。请编程完成统计选票的工作。第38页，本讲稿共88页算法如下：算法如下：vote()vote()int i,xp,a5=0 int i,xp,a5=0，0 0，0 0，0 0，0;0;input(xp);input(xp);while(xp!=-1)while(xp!=-1)if

18、(xp=1 and xp=1 and xp=5)axp=axp+1;axp=axp+1;else else print(xp,input error!);print(xp,input error!);input(xp);input(xp);for(i=1;i=5;i+)for(i=1;i=5;i+)print(i,number get,ai,votes);print(i,number get,ai,votes);第39页，本讲稿共88页【例例】编程统计身高（单位为厘米）。统计分编程统计身高（单位为厘米）。统计分150150154154；155155159159；160160164164；165

19、165169169；170170174174；175175179179及及低于是低于是150150、高于是、高于是179179共八档次进行。共八档次进行。算法设计：算法设计：第40页，本讲稿共88页算法如下：算法如下：main()main()int i,xp,a8;int i,xp,a8;input(sg);input(sg);while(sg-1)while(sg-1)if(sg179)a7=a7+1 if(sg179)a7=a7+1；else if(sg150)a0=a0+1else if(sg150)a0=a0+1；else aelse asg/5-29sg/5-29=a=asg/5-2

20、9sg/5-29+1+1；input(sg);input(sg);for(i=0;i=7;i=i+1)for(i=0;i=7;i=i+1)print(i+1,“field the number of peopleprint(i+1,“field the number of people：”,ai);,ai);第41页，本讲稿共88页二、数组使信息有序化二、数组使信息有序化 当当题题目目中中的的数数据据缺缺乏乏规规律律时时，很很难难把把重重复复的的工工作作抽抽象象成成循循环环不不变变式式来来完完成成，但但先先用用数数组组结结构构存存储储这这些些地地信信息后，问题就迎刃而解了，息后，问题就迎刃而解

21、了，第42页，本讲稿共88页【例例】编程将编号编程将编号“翻译翻译”成英文。例成英文。例3570635706“翻译翻译”成成three-five-three-five-seven-zero-sixseven-zero-six。main()main()int i,a10,ind;long num1,num2;int i,a10,ind;long num1,num2;char eng106=char eng106=“zero”,”one”,”two”,”three”,”four”,”five”,”six”,”seven”,“eight”,”nine”;input(num1);num2=num1;i

22、nd=0;input(num1);num2=num1;ind=0;while(num20)while(num20)aind=num2 mod 10;aind=num2 mod 10;ind=ind+1;ind=ind+1;num2=num2/10;num2=num2/10;for(i=ind-2;i=0;i=i-1)for(i=ind-2;i=0;i=i-1)print(print(“-”，engai);engai);第43页，本讲稿共88页三、数组记录状态信息三、数组记录状态信息问题提出：问题提出：有有的的问问题题会会限限定定在在现现有有数数据据中中，每每个个数数据据只只能能被被使使用用一一

23、次次，怎怎么么样样表表示示一一个个数数据据“使使用过用过”还是没有还是没有“使用过使用过”？一一个个朴朴素素的的想想法法是是：用用数数组组存存储储已已使使用用过过的的数数据据，然然后后每每处处理理一一个个新新数数据据就就与与前前面面的的数数据据逐逐一一比比较较看看是是否否重重复复。这这样样做做，当当数数据量大时，判断工作的效率就会越来越低。据量大时，判断工作的效率就会越来越低。第44页，本讲稿共88页【例例】求求X X，使，使X X2 2为一个各位数字互不相同的九位数。为一个各位数字互不相同的九位数。总总体体分分析析：只只能能用用枚枚举举法法尝尝试试完完成成此此题题。由由X X2 2为为一一个

24、个九九位位数数，估估算算X X应在应在10000100003200032000之间。之间。第45页，本讲稿共88页main()longlong x,y1,y2;int p10,i,t,k,num=0;for(x=10000;x32000;x=x+1)for(i=0;i=9;i=i+1)pi=1;y1=x*x;y2=y1;k=0;for(i=1;i=9;i=i+1)t=y2 mod 10;y2=y2/10;if(pt=1)k=k+1;pt=0;else break;if(k=9)num=num+1;print(“No.”,num,“：n=”,x,“n2=”,y1);第46页，本讲稿共88页四、大

25、整数的存储及运算四、大整数的存储及运算 计算机存储数据是按类型分配空间的。在微型机上为整计算机存储数据是按类型分配空间的。在微型机上为整型提供型提供2 2个字节个字节1616位的存储空间，则整型数据的范围为位的存储空间，则整型数据的范围为-32768327683276732767；为长整型提供；为长整型提供4 4个字节个字节3232位的存储空间，位的存储空间，则长整型数据的范围为则长整型数据的范围为-2147483648-214748364821474836472147483647；为；为实型也是提供实型也是提供4 4个字节个字节3232位的存储空间，但不是精确存位的存储空间，但不是精确存储数

26、据，只有六位精度，数据的范围储数据，只有六位精度，数据的范围(3.4e-383.4e+38)；为双精度型数据提供；为双精度型数据提供8 8个字节个字节6464位的存储位的存储空间，数据的范围空间，数据的范围(1.7e-3081.7e+308)，其精确位数是，其精确位数是1717位。位。第47页，本讲稿共88页【例例】编程求当编程求当N=100N=100时，时，N N！的准确值！的准确值问问题题分分析析：问问题题要要求求对对输输入入的的正正整整数数N N，计计算算N N！的的准准确确值值，而而N N！的的增增长长速速度度仅仅次次于于指指数数增增长长的的速速度度，所所以以这这是是一一个个高高精精度

27、计算问题。度计算问题。例如：例如：9 9！=362880=362880100100！=93 326215 443944 152681 699263 =93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963856266 700490 715968 264381 621468 592963895217 599993 229915 608914 463976 156578895217 599993 229915 608914 463976 156578286253 697920 827223 758251 18

28、5210 916864286253 697920 827223 758251 185210 916864000000 000000 000000 000000 000000 000000 000000 000000 第48页，本讲稿共88页main()long a256=0,b,d;int m,n,i,j,r;input(n);m=log(n)*n/6+2;m=log(n)*n/6+2;粗略估计粗略估计n!n!的位数的位数 a1=1;d=0;for(i=2;i=n;i+)for(j=1;j=m;j+)b=aj*i+d;aj=b mod 1000000;d=b/1000000;if(d0)aj=

29、d;m=m+1;第49页，本讲稿共88页 print(n,“!=”);print(am);for(i=m-1;i=1;i-)if(ai99999)print(ai);else if(ai9999)print(“0”,ai);else if(ai999)print(“00”,ai);else if(ai99)print(“000”,ai);else if(ai9)print(“0000”,ai);else print(“00000”,ai);/for 第50页，本讲稿共88页五、构造趣味矩阵五、构造趣味矩阵趣味矩阵趣味矩阵经常用二维数组来解决经常用二维数组来解决 根据趣味矩阵中的数据规律，设计算

30、法把要输出的数据存储到一个二根据趣味矩阵中的数据规律，设计算法把要输出的数据存储到一个二维数组中，最后按行输出该数组中的元素。维数组中，最后按行输出该数组中的元素。基本常识：基本常识：1 1）当当对对二二维维表表按按行行进进行行操操作作时时，应应该该“外外层层循循环环控控制制行行；内内层层循循环环控控制制列列”；反反之之若若要要对对二二维维表表按按列列进进行行操操作作时时，应应该该“外外层层循循环环控控制制列列；内层循环控制行内层循环控制行”。2 2）二维表和二维数组的）二维表和二维数组的显示输出显示输出，只能按行从上到下连续进行，每行各列则，只能按行从上到下连续进行，每行各列则只能从左到右连

31、续输出。所以，只能用只能从左到右连续输出。所以，只能用“外层循环控制行外层循环控制行；内层循环控制列；内层循环控制列”。第51页，本讲稿共88页2 2 3 3）用用i i代代表表行行下下标标，以以j j代代表表列列下下标标（除除特特别别声声明明以以后后都都遵遵守守此此约约定定），则对则对n*nn*n矩阵有以下常识：矩阵有以下常识：主对角线元素主对角线元素i=ji=j；副对角线元素副对角线元素:下标下界为下标下界为1 1时时 i+j=n+1i+j=n+1，下标下界为下标下界为0 0时时 i+j=n-1i+j=n-1；主上三角主上三角元素元素:i=j:i=j:i=j；次上三角次上三角元素：下标下界

32、为元素：下标下界为1 1时时i+j=n+1i+j=n+1，下标下界为下标下界为0 0时时i+j=n-1i+j=n+1i+j=n+1，下标下界为下标下界为0 0时时i+j=n-1i+j=n-1；第52页，本讲稿共88页【例例】编程打印形如下规律的编程打印形如下规律的n*nn*n方阵。方阵。例如下图：使左对角线和右对角线上的元素为例如下图：使左对角线和右对角线上的元素为0,0,它们上方的元素为它们上方的元素为1,1,左左方的元素为方的元素为2,2,下方元素为下方元素为3,3,右方元素为右方元素为4,4,下图是一个符合条件的阶矩阵。下图是一个符合条件的阶矩阵。0 1 1 1 00 1 1 1 0 2

33、 0 1 0 4 2 0 1 0 4 2 2 0 4 4 2 2 0 4 4 2 0 3 0 4 2 0 3 0 4 0 3 3 3 0 0 3 3 3 0第53页，本讲稿共88页main()main()int i,j,a100100,n;int i,j,a100100,n;input(n);input(n);for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1)for(j=1;j=n;j=j+1)for(j=1;j=n;j=j+1)if(i=j or i+j=n+1)a ij=0;if(i=j or i+j=n+1)a ij=0;if(i+jn+1 and ij)a ij=

34、1;if(i+jn+1 and ij)a ij=1;if(i+jj)a ij=2;if(i+jj)a ij=2;if(i+jn+1 and ij)a ij=3;if(i+jn+1 and ij)a ij=3;if(i+jn+1 and in+1 and ij)a ij=4;for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1)print(print(“换行符换行符”););for(j=1;j=n;j=j+1)for(j=1;j=n;j=j+1)print(aij);print(aij);第54页，本讲稿共88页n=3 n=3 输出：输出：1 8 71 8 7 2 29 69

35、6 3 34 54 5n=4 n=4 输出：输出：1 12 11 101 12 11 10 2 213 16 913 16 9 3 314 15 814 15 8 4 5 6 7 4 5 6 7【例例】螺旋阵：任意给定螺旋阵：任意给定n n值，按如下螺旋的方式输出方阵：值，按如下螺旋的方式输出方阵：第55页，本讲稿共88页算法设计：算法设计：算算法法设设计计1 1：此此例例可可以以按按照照“摆摆放放”数数据据的的过过程程，逐逐层层（圈圈）分分别别处处理理每每圈的左侧、下方、右侧、上方的数据。以圈的左侧、下方、右侧、上方的数据。以n=4n=4为例详细设计如下：为例详细设计如下：把把“1 1121

36、2”看看做做一一层层（一一圈圈）“13-1613-16”看看做做二二层层以以层层做做为为外外层层循循环环，下下标标变变量量为为i i。由由以以上上两两个个例例子子，n=3n=3、4 4均均为为两两层层，用用n2n2表表示示下下取取整整，这这样样（n+1n+1）/2/2下下好好表表示示对对n/2n/2上上取取整整。所所以以下下标标变变量量i i的的范范围围1 1（n+1n+1）/2/2。第56页，本讲稿共88页i i层内层内“摆放摆放”数据的四个过程为（四角元素分别归四个边）：数据的四个过程为（四角元素分别归四个边）：1 1）i i列列(左侧左侧)，从，从i i行到行到n-in-i行行 （n=4

37、n=4，i=1i=1时时 “摆放摆放1 1，2 2，3 3”）2 2）n+1-in+1-i行（下方），从行（下方），从i i列到列到n-in-i列列 （n=4n=4，i=1i=1时时 “摆放摆放4 4，5 5，6 6”）3 3）n+1-in+1-i列（右侧），从列（右侧），从n+1-in+1-i行到行到i+1i+1行行 （n=4n=4，i=1i=1时时 “摆放摆放7 7，8 8，9 9”）4 4）i i行（上方），从行（上方），从n+1-in+1-i列到列到i+1i+1列列 （n=4n=4，i=1i=1时时 “摆放摆放1010，1111，1212”）四个过程通过四个循环实现，用四个过程通过四个

38、循环实现，用j j表示表示i i层内每边中行或列的下标。层内每边中行或列的下标。第57页，本讲稿共88页main()main()int i,j,a100100,n,k;int i,j,a100100,n,k;input(n);k=1;input(n);k=1;for(i=1;i=n/2;i=i+1)for(i=1;i=n/2;i=i+1)for(j=i;j=n-i;j=j+1)aji=kfor(j=i;j=n-i;j=j+1)aji=k；k=k+1;/k=k+1;/左侧左侧 for(j=i;j=n-i;j=j+1)an+1-ij=k;k=k+1;/for(j=i;j=i+1;j=j-1)ajn

39、+1-i=k;k=k+1;/for(j=n-i+1;j=i+1;j=j-1)ajn+1-i=k;k=k+1;/右侧右侧 for(j=n-i+1;j=i+1;j=j-1)aij=k;k=k+1;/for(j=n-i+1;j=i+1;j=j-1)aij=k;k=k+1;/上方上方 if(n mod 2=1)if(n mod 2=1)i=(n+1)/2;aii=n*n;i=(n+1)/2;aii=n*n;for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1)print(print(“换行符换行符”););for(j=1;j=n;j=j+1)for(j=1;j=n;j=j+1)pri

40、nt(aij);print(aij);第58页，本讲稿共88页3.3算法优化基本技巧算法优化基本技巧第59页，本讲稿共88页【例例】一次考试，共考了五门课。统计五十个学生中至少有三门一次考试，共考了五门课。统计五十个学生中至少有三门课成绩高于课成绩高于9090分的人数。分的人数。main()main()int a5,i,j,s,num=0;int a5,i,j,s,num=0;for(i=1;i=50;i=i+1)for(i=1;i=50;i=i+1)s=0;s=0;for(j=0;j=4;j=j+1)for(j=0;j=90)if(aj=90)s=s+1;s=s+1;if(s=3)if(s=

41、3)num=num+1;num=num+1;print(print(“The number isThe number is”,num);,num);一、算术运算的妙用一、算术运算的妙用第60页，本讲稿共88页算法说明：对于计算其成绩高于算法说明：对于计算其成绩高于9090分的课程数目，还可以简单地这样分的课程数目，还可以简单地这样实现：实现：s=0s=0；for(j=0;j=4;j+)for(j=0;j=90);s=s+(ai=90);第61页，本讲稿共88页二、标志量的妙用二、标志量的妙用【例例】冒泡排序算法的改进冒泡排序算法的改进main()main()int i,j,t,n,a100,f

42、lag;int i,j,t,n,a100,flag;input(n);input(n);for(i=0;in;i+)for(i=0;in;i+)input(ai);input(ai);flag=1;flag=1;保证循环开始运行保证循环开始运行 for(i=1;i=n-1 and flag=1;i+)for(i=1;i=i;j-)for(j=n-1;j=i;j-)if(ajaj-1)if(ajaj-1)t=aj;aj=aj-1;aj-1=t;flag=1;t=aj;aj=aj-1;aj-1=t;flag=1;for(i=0;in;i+)for(i=0;in;i+)print(ai);print

43、(ai);第62页，本讲稿共88页三、信息数字化三、信息数字化 【例例】警察局抓了警察局抓了a a，b b，c c，d d四名偷窃嫌疑犯，其中只有一人是小偷。四名偷窃嫌疑犯，其中只有一人是小偷。审问中审问中 a a说：说：“我不是小偷。我不是小偷。”b b说：说：“c c是小偷。是小偷。”c c说：说：“小偷肯定是小偷肯定是d d。”d d说：说：“c c在冤枉人。在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？问到底谁是小偷？问题分析：将问题分析：将a,b,c,da,b,c,d将四个人进行编号，号码分别将四个

44、人进行编号，号码分别为为1 1，2 2，3 3，4 4。则问题可用枚举尝试法来解决。则问题可用枚举尝试法来解决。第63页，本讲稿共88页算算法法设设计计：用用变变量量x x存存放放小小偷偷的的编编号号，则则x x的的取取值值范范围围从从1 1取取到到4 4，就就假假设设了了他他们们中中的的某某人人是是小小偷偷的的所所有有情情况况。四四个个人人所所说说的的话话就就可以分别写成：可以分别写成：a a说的话：说的话：x1x1 b b说的话：说的话：x=3x=3 c c说的话：说的话：x=4x=4 d d说的话：说的话：x4x4 注注意意:在在x x的的枚枚举举过过程程中中，当当这这四四个个逻逻辑辑式

45、式的的值值相相加加等等于于3 3时时，即即表表示示“四个人中三人说的是真话，一人说的是假话四个人中三人说的是真话，一人说的是假话”。第64页，本讲稿共88页main()main()int x;int x;for(x=1;x=4;x+)for(x=1;x=4;x+)if(if(x1)+(x=3)+(x=4)+(x4)=3(x1)+(x=3)+(x=4)+(x4)=3)print(chr(64+x),print(chr(64+x),“is a thief.is a thief.”););运行结果：运行结果：c is a thief.c is a thief.第65页，本讲稿共88页【例例】编写算法

46、对输入的一个整数，判断它能否被编写算法对输入的一个整数，判断它能否被3 3，5 5，7 7整除，并输出以下信息之一：整除，并输出以下信息之一：（1 1）能同时被能同时被3 3，5 5，7 7整除；整除；（2 2）能被其中两数（要指出哪两个）整除；能被其中两数（要指出哪两个）整除；（3 3）能被其中一个数（要指出哪一个）整除；能被其中一个数（要指出哪一个）整除；（4 4）不能被不能被3 3，5 5，7 7任一个整除。任一个整除。第66页，本讲稿共88页main()main()long n;long n;int k;int k;print(print(“Please enter a number:

47、Please enter a number:”););input(n);input(n);k=(n mod 3=0k=(n mod 3=0）+（n mod 5=0n mod 5=0）+（n mod 7=0n mod 7=0）switch(k)switch(k)case 3:print(case 3:print(“n Alln All”);break;);break;case 2:print(case 2:print(“n twon two”);break;);break;case 1:print(case 1:print(“n onen one”);break;);break;case 0:p

48、rint(case 0:print(“n nonen none“);break;);break;算法算法1 1：第67页，本讲稿共88页main()main()long n;long n;int k;int k;print(print(“Please enter a number:Please enter a number:”););input(n);input(n);k=k=（n mod 3=0n mod 3=0）+（n mod 5=0n mod 5=0）*2 2+（n mod 7=0n mod 7=0）*4 4 switch(k)switch(k)case 7:print(case 7:p

49、rint(“All All”);bresk;);bresk;case 6:print(case 6:print(“5 and 7 5 and 7”);break;);break;case 5:print(case 5:print(“3 and 7 3 and 7”);break;);break;case 4:print(case 4:print(“7 7 ”);break;);break;case 3:print(case 3:print(“3 and 5 3 and 5 ”);break;);break;case 2:print(case 2:print(“5 5 ”);break;);br

50、eak;case 1:print(case 1:print(“3 3 ”);break;);break;case 0:print(case 0:print(“none none“);break;);break;算法算法2 2：第68页，本讲稿共88页3.4优化算法的数学模型优化算法的数学模型第69页，本讲稿共88页1认识数学模型和数学建模认识数学模型和数学建模【例例】已知有已知有5个数，求前四个数与第五个数个数，求前四个数与第五个数分别相乘后的最大值。分别相乘后的最大值。第70页，本讲稿共88页intmax2(inta,b,c,d,e)intxif(ab)x=a;elsex=b;if(cx)x