《第3章 算法基本工具和优化技巧.ppt》由会员分享,可在线阅读,更多相关《第3章 算法基本工具和优化技巧.ppt(88页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第3章章算法基本工具和优化技巧算法基本工具和优化技巧31循环与递归循环与递归32算法与数据结构算法与数据结构33算法优化基本技巧算法优化基本技巧34优化算法的数学模型优化算法的数学模型1.1.循环设计要点循环设计要点2.2.递归设计要点递归设计要点3.3.递归与循环的比较递归与循环的比较3.1循环与递归循环与递归 1设计中要注意算法的效率 2“自顶向下”的设计方法 3由具体到抽象设计循环结构 一、循环设计要点一、循环设计要点 循环体的特点是:循环体的特点是:“以不变应万变以不变应万变”。所谓所谓“不变不变”是指循环体内运算的表现是指循环体内运算的表现形式是不变的,而每次具体的执行内容却是形式
2、是不变的,而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。形式去描述各种相似的重复运算。1 1循环循环设计设计中要注意算法的效率中要注意算法的效率【例例】求求数学模型数学模型1 1:main()main()intint i,n,j,sign=1;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(i=2;i=n;i=i+1)t=1;t=1;/求阶乘求阶乘 for(j=1;j=2*i-1;j=j+1
3、)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(“SumSum=”,s);,s);算法的时间复杂度:算法的时间复杂度:O(n2)效率较低!效率较低!(2n-1)!=(2(n-1)-1)!*(2n-2)*(2n-1)数学模型数学模型2 2:main()main()intint i,n,sign;i,n,sign;
4、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(“Sum=”,s);print(“Sum=”,s);算法的时间复杂度:算法的时间复杂度:O(n)2 2“自自顶顶向下向下”的的设计设计方法方法 自自顶顶向下的方法是从全局走向局部、从向下的方法是从全局走向局部、从概略概略走向走向详详尽的尽的设
5、计设计方法。自上而下是系方法。自上而下是系统统分解和分解和细细化的化的过过程。程。【例例】一一个个数数如如果果恰恰好好等等于于它它的的因因子子之之和和(包包括括1 1,但但不不包包括括这这个个数数本本身身),这这个个数数称称为为“完完数数”。编编算算法找出法找出10001000以内所有完数。以内所有完数。例例如如,2828的的因因子子为为1 1、2 2、4 4、7 7,1414(每每个个因因数数只只记记一一次次),而而28=1+2+4+7+1428=1+2+4+7+14。因因此此2828是是“完完数数”。输输出出格格式式如如下下:28 28 its its factors factors ar
6、e are 1 1,2 2,4 4,7 7,1414。1)顶层算法 for(i=2;i=1000;i=i+1)判断i是否为“完数”;是“完数”则按格式输出;2)判断i是否为“完数”for(j=2;ji;j=j+1)找i的因子,并累加如果累加值为i,则是“完数”3)进一步细化判断i是否“完数”算法s=1;for(j=2;ji;j=j+1)if(i mod j=0)s=s+j;if(s=i)i是“完数”;4 4)考虑输出格式)考虑输出格式判断判断i i是否是否“完数完数”算法算法 考考虑虑到到要要按按格格式式输输出出结结果果,应应该该开开辟辟数数组组存存储储数数据据i i的所有因子,并记录其因子的
7、个数,因此算法细化如下:的所有因子,并记录其因子的个数,因此算法细化如下:定义数组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)按格式输出结果 算法如下:算法如下:main()int i,k,j,s,a20;for(i=1;i=1000;i+)s=1;k=0;for(j=2;ji;j+)if(i mod j=0)s=s+j;ak=j;k+;if(i=s)print(s,“its factors are:”,1);for(j=0;ik;j+)print(“,”,ak);对于不太熟悉的问题,其数学模型
8、或“机械化操作步骤”的不易抽象,下面看一个由具体到抽象设计循环细节的例题。【例】编写算法:打印具有下面规律的图形。1 5 2 8 6 3 10 9 7 4 3 3由具体到抽象设计循环结构由具体到抽象设计循环结构main()int i,j,a100100,n,k;input(n);k=1;for(i=0;i=n-1;i=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;
9、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);循环算法如下:循环算法如下:f4(n)f4(n)if(n10)if(n=n;i-)for(i=1;i=n;i-)for(j=1;j=n;j-)for(j=1;j=n;j-)for(k=1;k=n;k-)for(k=1;k=n;k-)if(iif(i j)and(jj)and(jk)k)t=t+1;t=t+1;print(total=,t);print(total=,t);时间复杂度时间复杂度O(nO(n3 3)循环算法循环算法2:constit
10、ute2()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);return s;r r层递归,每个算法层递归,每个算法递归递归n-r+1n-r+1次。因此次。因此时间复杂度为时间复杂度为O(nO(n*r)*r)算法分析算法分析n递归的层次是可以控制的,而循环嵌套的递归的层次是可以控制的,而循环嵌套的层次只能是固定的层次只能是固定的递归递归非递归非递归程序可读性程序可读性易易难难代码量大小代码量大小小小大大时间时间长长短短占用空间占用空间
11、大大小小适用范围适用范围广广窄窄设计难度设计难度易易难难递归与非递归的比较:递归与非递归的比较:3.2算法与数据结构算法与数据结构数据的逻辑结构常分为四大类:数据的逻辑结构常分为四大类:(1 1)集合结构)集合结构 (2 2)线性结构)线性结构 (3 3)树形结构)树形结构(4 4)图结构(网结构)图结构(网结构)存储结构可以分为:连续存储和链式存储。存储结构可以分为:连续存储和链式存储。连续存储又可以分为:静态存储和动态存储连续存储又可以分为:静态存储和动态存储 1 1、常用的几种数据结构、常用的几种数据结构顺序存储的优点:顺序存储的优点:(1)方法简单,各种高级语言中都提供数组结方法简单,
12、各种高级语言中都提供数组结构,容易实现。构,容易实现。(2)不用为表示结点间的逻辑关系而增加额外不用为表示结点间的逻辑关系而增加额外的存储开销。的存储开销。(3)顺序表具有按元素序号随机访问的特点。顺序表具有按元素序号随机访问的特点。2 2、连续存储和链式存储比较、连续存储和链式存储比较顺序存储的缺点:顺序存储的缺点:(1)在顺序表中做插入删除操作时,平均在顺序表中做插入删除操作时,平均移动大约表中一半的元素,因此对移动大约表中一半的元素,因此对n较大的顺序较大的顺序表效率低。表效率低。(2)需要预先分配足够大的存储空间,估需要预先分配足够大的存储空间,估计过大,可能会导致顺序表后部大量闲置;
13、预先计过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。分配过小,又会造成溢出。温馨提示:温馨提示:链表的优缺点恰好与顺序表相反。链表的优缺点恰好与顺序表相反。3 3、在选取存储结构时权衡因素有:、在选取存储结构时权衡因素有:)基于存储的考虑)基于存储的考虑 顺序表的存储空间是静态分配的,在程顺序表的存储空间是静态分配的,在程序执行之前必须明确规定它的存储规模,也就序执行之前必须明确规定它的存储规模,也就是说事先对是说事先对“MAXSIZEMAXSIZE”要有合适的设定,过要有合适的设定,过大造成浪费,过小造成溢出。可见对线性表的大造成浪费,过小造成溢出。可见对线性表的长度或长度
14、或存储规模存储规模难以估计时,不宜采用顺序表;难以估计时,不宜采用顺序表;链表不用事先估计存储规模,但链表的链表不用事先估计存储规模,但链表的存储密存储密度度较低。较低。)基于运算的考虑)基于运算的考虑 在顺序表中按序号访问在顺序表中按序号访问a ai i的时间性能时的时间性能时O(1)O(1),而链表中按序号访问的时间性能而链表中按序号访问的时间性能O(n)O(n),所以如果所以如果经常做的运算是按序号经常做的运算是按序号访问数据元素访问数据元素,显然顺序表,显然顺序表优于链表;但对于优于链表;但对于插入插入、删除删除操作,则后者优于前操作,则后者优于前者。者。)基于环境的考虑)基于环境的考
15、虑 顺序表容易实现,任何高级语言中都有数组顺序表容易实现,任何高级语言中都有数组类型,链表的操作是基于指针的,操作简单。类型,链表的操作是基于指针的,操作简单。一、原始信息与处理结果对应存储一、原始信息与处理结果对应存储 每每一一个个问问题题中中的的信信息息往往往往是是多多方方面面的的,在在算算法法中中一一般般有有输输入入信信息息、输输出出信信息息和和信信息息加加工工处处理理过过程程中中的的中中间间信信息息。那那么么哪哪些些信信息息需需要要用用数数组组进进行行存存储储,数数组组元元素素下下标标与与信信息息怎怎么么样样对对应应等等问问题题的的确确定定,在在很很大大程程度度上上影影响着算法的编写效
16、率和运行效率。响着算法的编写效率和运行效率。【例例】某校决定由全校学生选举学生会主席。有某校决定由全校学生选举学生会主席。有5 5个候选个候选人,编号分别为人,编号分别为1 1,2 2,3 3,4 4,5 5,选举其中一人为学生会,选举其中一人为学生会主席,每个学生一张选票,只能填写一人。请编程完成主席,每个学生一张选票,只能填写一人。请编程完成统计选票的工作。统计选票的工作。算法如下:算法如下:vote()vote()intint i,xp,a5=0 i,xp,a5=0,0 0,0 0,0 0,0;0;input(xpinput(xp););while(xpwhile(xp!=-1)!=-1
17、)if(if(xpxp=1 and=1 and xpxp=5)=5)axpaxp=axp+1;=axp+1;else else print(xpprint(xp,input error!);,input error!);input(xpinput(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);【例例】编程统计身高(单位为厘米)。统计分编程统计身高(单位为厘米)。统计分150150154154;155159155159;160164160164;16516
18、9165169;170170174174;175179175179及低于是及低于是150150、高于是、高于是179179共八档次进行。共八档次进行。算法设计:算法设计:算法如下:算法如下:main()main()intint i,xp,a8;i,xp,a8;input(sginput(sg););while(sgwhile(sg-1)-1)if(sgif(sg179)a7=a7+1179)a7=a7+1;else else if(sgif(sg150)a0=a0+1150)a0=a0+1;else aelse asg/5-29sg/5-29=a=asg/5-29sg/5-29+1+1;inp
19、ut(sginput(sg););for(i=0;i=7;i=i+1)for(i=0;i=7;i=i+1)print(i+1,print(i+1,“field the number of peoplefield the number of people:”,ai);,ai);二、二、数组使信息有序化数组使信息有序化 当当题题目目中中的的数数据据缺缺乏乏规规律律时时,很很难难把把重重复复的的工工作作抽抽象象成成循循环环不不变变式式来来完完成成,但但先先用用数数组组结结构构存储这些地信息后,问题就迎刃而解了,存储这些地信息后,问题就迎刃而解了,【例例】编程将编号编程将编号“翻译翻译”成英文。例成英
20、文。例35706“35706“翻译翻译”成成three-five-seven-zero-sixthree-five-seven-zero-six。main()main()intint i,a10,ind;long num1,num2;i,a10,ind;long num1,num2;char eng106=char eng106=“zero”,”one”,”two”,”three”,”four”,”five”,”six”,”seven”,“eight”,”nine”;input(num1);num2=num1;input(num1);num2=num1;indind=0;=0;while(nu
21、m20)while(num20)aindaind=num2 mod 10;=num2 mod 10;indind=ind+1;=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);三、三、数组记录状态信息数组记录状态信息问题提出:问题提出:有有的的问问题题会会限限定定在在现现有有数数据据中中,每每个个数数据据只只能能被被使使用用一一次次,怎怎么么样样表表示示一一个个数数据据“使使用过用过”还是没有还是没有“使用过使用过”?一一个个
22、朴朴素素的的想想法法是是:用用数数组组存存储储已已使使用用过过的的数数据据,然然后后每每处处理理一一个个新新数数据据就就与与前前面面的的数数据据逐逐一一比比较较看看是是否否重重复复。这这样样做做,当当数数据量大时,判断工作的效率就会越来越低。据量大时,判断工作的效率就会越来越低。【例例】求求X X,使,使X X2 2为一个各位数字互不相同的九位数。为一个各位数字互不相同的九位数。总总体体分分析析:只只能能用用枚枚举举法法尝尝试试完完成成此此题题。由由X X2 2为为一一个个九九位数,估算位数,估算X X应在应在10000320001000032000之间。之间。main()longlong x
23、,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);四、大整数的存储及运算四、大整数的存储及运算 计算机存储数据是按类型分配空间的。在微型计算机存储数据是按类型分配空间的。在微型机上为整型提供机上为整型提供2 2个字节个字节16
24、16位的存储空间,则整型数位的存储空间,则整型数据的范围为据的范围为-3276832767-3276832767;为长整型提供;为长整型提供4 4个字个字节节3232位的存储空间,则长整型数据的范围为位的存储空间,则长整型数据的范围为-2147483648214748364721474836482147483647;为实型也是提供;为实型也是提供4 4个字个字节节3232位的存储空间,但不是精确存储数据,只有六位的存储空间,但不是精确存储数据,只有六位精度,数据的范围位精度,数据的范围(3.4e-383.4e+38);为双精为双精度型数据提供度型数据提供8 8个字节个字节6464位的存储空间,
25、数据的范围位的存储空间,数据的范围(1.7e-3081.7e+308),其精确位数是其精确位数是1717位。位。【例例】编程求当编程求当N=100N=100时,时,N N!的准确值的准确值问问题题分分析析:问问题题要要求求对对输输入入的的正正整整数数N N,计计算算N N!的的准准确确值值,而而N N!的的增增长长速速度度仅仅次次于于指指数数增增长长的的速速度度,所所以以这是一个高精度计算问题。这是一个高精度计算问题。例例如如:9 9!=362880=362880100100!=93 326215 443944 152681 699263 =93 326215 443944 152681 69
26、9263 856266 700490 715968 264381 621468 592963856266 700490 715968 264381 621468 592963895217 599993 229915 608914 463976 156578895217 599993 229915 608914 463976 156578286253 697920 827223 758251 185210 916864286253 697920 827223 758251 185210 916864000000 000000 000000000000 000000000000 000000000
27、000 main()long a256=0,b,d;int m,n,i,j,r;input(n);m=m=log(nlog(n)*n/6+2;)*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=d;m=m+1;print(n,“!=”);print(am);for(i=m-1;i=1;i-)if(ai99999)print(ai);else if(ai9999)print(“0”,ai);else if(ai999)pri
28、nt(“00”,ai);else if(ai99)print(“000”,ai);else if(ai9)print(“0000”,ai);else print(“00000”,ai);/for 五、构造趣味矩阵五、构造趣味矩阵趣味矩阵趣味矩阵经常用二维数组来解决经常用二维数组来解决 根据趣味矩阵中的数据规律,设计算法把要输出的数据存储到根据趣味矩阵中的数据规律,设计算法把要输出的数据存储到一个二维数组中,最后按行输出该数组中的元素。一个二维数组中,最后按行输出该数组中的元素。基本常识:基本常识:1 1)当当对对二二维维表表按按行行进进行行操操作作时时,应应该该“外外层层循循环环控控制制行行;
29、内内层层循循环环控控制制列列”;反反之之若若要要对对二二维维表表按按列列进进行行操操作作时时,应应该该“外外层层循循环环控制列;内层循环控制行控制列;内层循环控制行”。2 2)二维表和二维数组的)二维表和二维数组的显示输出显示输出,只能按行从上到下连续进行,只能按行从上到下连续进行,每行各列则只能从左到右连续输出。所以,只能用每行各列则只能从左到右连续输出。所以,只能用“外层循环控制外层循环控制行行;内层循环控制列;内层循环控制列”。2 2 3 3)用用i i代代表表行行下下标标,以以j j代代表表列列下下标标(除除特特别别声声明明以以后后都都遵遵守守此此约定),则对约定),则对n*nn*n矩
30、阵有以下常识:矩阵有以下常识:主对角线元素主对角线元素i=ji=j;副对角线元素副对角线元素:下标下界为下标下界为1 1时时 i+j=n+1i+j=n+1,下标下界为下标下界为0 0时时 i+ji+j=n-1=n-1;主上三角主上三角元素元素:i=j:i=j:i=j;次上三角次上三角元素:下标下界为元素:下标下界为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;【例例】编程打印形如下规律的编程打印形如下规律的n*nn*n方阵。方阵。例如下图:使左对角线和右对角线上的元素
31、为例如下图:使左对角线和右对角线上的元素为0,0,它们上方的元素它们上方的元素为为1,1,左方的元素为左方的元素为2,2,下方元素为下方元素为3,3,右方元素为右方元素为4,4,下图是一个符合下图是一个符合条件的阶矩阵。条件的阶矩阵。0 1 1 1 00 1 1 1 0 2 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 0main()main()intint i,j,a100100,n;i,j,a100100,n;input(n);input(n);for(i=1;i=n;i=i+1)fo
32、r(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=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)pri
33、nt(“print(“换行符换行符”););for(j=1;j=n;j=j+1)for(j=1;j=n;j=j+1)print(aij);print(aij);n=3 n=3 输出:输出:1 8 71 8 7 2 29 69 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值,按如下螺旋的方式输出方阵:值,按如下螺旋的方式输出方阵:算法设计:算法设计:算算法法设设计计1 1:此此例例可可以以按按照照“摆摆
34、放放”数数据据的的过过程程,逐逐层层(圈圈)分分别别处处理理每每圈圈的的左左侧侧、下下方方、右右侧侧、上上方方的的数数据据。以以n=4n=4为为例例详详细细设设计计如下:如下:把把“1 11212”看看做做一一层层(一一圈圈)“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。i i层内层内“摆
35、放摆放”数据的四个过程为(四角元素分别归四个边):数据的四个过程为(四角元素分别归四个边):1 1)i i列列(左侧左侧),从,从i i行到行到n-in-i行行 (n=4n=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行(上方),从行(上方)
36、,从n+1-in+1-i列到列到i+1i+1列列 (n=4n=4,i=1i=1时时 “摆放摆放1010,1111,1212”)四个过程通过四个循环实现,用四个过程通过四个循环实现,用j j表示表示i i层内每边中行或列的下标。层内每边中行或列的下标。main()main()intint i,j,a100100,n,k;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;/
37、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+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
38、=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);3.3算法优化基本技巧算法优化基本技巧【例例】一次考试,共考了五门课。统计五十个学生中至少有一次考试,共考了五门课。统计五十个学生中至少有三门课成绩高于三门课成绩高于9090分的人数。分的人数。main()main()intint a5,i,j,s,num=0;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+
39、1)for(j=0;j=90)if(aj=90)s=s+1;s=s+1;if(s=3)if(s=3)num=num+1;num=num+1;print(“The number is”,num);print(“The number is”,num);一、算术运算的妙用一、算术运算的妙用算法说明:对于计算其成绩高于算法说明:对于计算其成绩高于9090分的课程数目,还可以简分的课程数目,还可以简单地这样实现:单地这样实现:s=0s=0;for(j=0;j=4;j+)for(j=0;j=90);s=s+(ai=90);二、标志量的妙用二、标志量的妙用【例例】冒泡排序算法的改进冒泡排序算法的改进main
40、()main()intint i,j,t,n,a100,flag;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(
41、i=0;in;i+)print(ai);print(ai);三、信息数字化三、信息数字化 【例例】警察局抓了警察局抓了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将四个
42、人进行编号,号码分别将四个人进行编号,号码分别为为1 1,2 2,3 3,4 4。则问题可用枚举尝试法来解决。则问题可用枚举尝试法来解决。算算法法设设计计:用用变变量量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的的枚枚举举过过程程中中,当当这这四四个个逻逻辑辑
43、式式的的值值相相加加等等于于3 3时时,即即表表示示“四四个个人人中中三三人人说说的的是是真真话话,一一人人说说的的是是假假话话”。main()main()intint x;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),“is a thief.”);print(chr(64+x),“is a thief.”);运行结果:运行结果:c is a thief.c is a thief.【例例】编写算法对输入的一个整数,判断它能否被编写算法对输入的
44、一个整数,判断它能否被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任一个整除。任一个整除。main()main()long n;long n;intint k;k;print(“Please enter a number:”);print(“Please enter a number:”);input(n
45、);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(“n All”);break;case 3:print(“n All”);break;case 2:print(“n two”);break;case 2:print(“n two”);break;case 1:print(“n one”);break;case 1:print(“n one”);break;case 0:print(“n none“);break;case 0:
46、print(“n none“);break;算法算法1 1:main()main()long n;long n;intint k;k;print(“Please enter a number:”);print(“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(“All”);case 7:print(“All”);breskbresk;case 6:
47、print(“5 and 7”);break;case 6:print(“5 and 7”);break;case 5:print(“3 and 7”);break;case 5:print(“3 and 7”);break;case 4:print(“7 ”);break;case 4:print(“7 ”);break;case 3:print(“3 and 5 ”);break;case 3:print(“3 and 5 ”);break;case 2:print(“5 ”);break;case 2:print(“5 ”);break;case 1:print(“3 ”);break;
48、case 1:print(“3 ”);break;case 0:print(“none“);break;case 0:print(“none“);break;算法算法2 2:3.4优化算法的数学模型优化算法的数学模型1认识数学模型和数学建模认识数学模型和数学建模【例例】已知有已知有5个数,求前四个数与第五个数个数,求前四个数与第五个数分别相乘后的最大值。分别相乘后的最大值。intmax2(inta,b,c,d,e)intxif(ab)x=a;elsex=b;if(cx)x=c;if(dx)x=d;x=x*e;return(x);intmax1(inta,b,c,d,e)intx;a=a*e;b
49、=b*e;c=c*e;d=d*e;if(ab)x=a;elsex=b;if(cx)x=c;if(dx)x=d;return(x);操作算法 乘法赋值条件判断 Max1 4 7 3 Max2 1 4 3以上两个算法以上两个算法基于的数学模型是不同的,基于的数学模型是不同的,一个算法先积再求最大值,另一个算法先求一个算法先积再求最大值,另一个算法先求最大值再求积,求从上表可以看出,后一个最大值再求积,求从上表可以看出,后一个算法的效率明显要高于前一个算法。算法的效率明显要高于前一个算法。数学建模数学建模就是把现实世界中的实际问题加以提炼,抽象为数学模型,求出模型的解,验证模型的合理性,并用该数学模型所提供的解答来解释现实问题,我们把数学知识的这一应用过程称为数学建模。2数学建模的基本方法数学建模的基本方法从分析问题的几种简单的、特殊的情从分析问题的几种简单的、特殊的情况中,发现一般规律或作出某种猜想,从况中,发现一般规律或作出某种猜想,从而找到解决问题的途径。这种研究问题方而找到解决问题的途径。这种研究问题方法叫做法叫做归纳法归纳法。即归纳法是从简单到复杂,。即归纳法是从简单到复杂,由个别到一般的一种研究方法。由个别到一般的一种研究方法。数学模型的应用n杨辉三角形n最大公约数n公倍数n斐波那契数列n特征根求解递推方程
限制150内