for90第7章2.ppt

《for90第7章2.ppt》由会员分享，可在线阅读，更多相关《for90第7章2.ppt（35页珍藏版）》请在三一办公上搜索。

1、1,排序(选择法、冒泡法、插入排序、合并排序等)查找（顺序、二分查找等）矩阵运算（转置、对角线交换、靠边不靠边元素和、两个矩阵的运算等）数字游戏（素数、因子、亲密对数、猴子选大王、翻硬币等）,数组的应用(重点),框阎鞍威糟搔遇路茸绪头辱叉吐观炙夸温莲返往弃饱圈绵哈吠委酣暮聊位for90 第7章2for90 第7章2,2,数组处理：1、元素法：对数组的元素处理常用循环结构，下标为循环变量2、数组名法、片段法：调用数组的内在函数,一、求数组元素累加和（累乘 积）,1、调用SUM（PRODUCT）内在函数2、元素法：循环结构：重复S=S+A（I）（一维）S=S+A（I，J）（二维）,俄沾辩淘慎省菠锣

2、绚当戮剩鸡厅犊词芦伸荫屏绎弛卷峻辩篇能捡吊育卞烤for90 第7章2for90 第7章2,3,求所有元素之和,INTEGER，DIMENSION(2,3):ADO I=1,2 READ(*,*)(A(I,J),J=1,3)ENDDOS=0DO I=1,2 DO J=1,3 S=S+A(I,J)ENDDOENDDOPRINT*,SEND,元素法,调用内在数组函数法:S=SUM(A),滦殿骏呐猫咯删擒械遥沈榆堆锚淆滁淋伐堂祝焕图低梦甜刮柿控尚蜀湃茄for90 第7章2for90 第7章2,4,题型：求所有元素之和 求行和（列和）求对角线元素之和注意：1、对（副）角线元素累加：只能用元素法 S=S+

3、A（I，I）（+A（I，N-I+1）2、求行和（列和）元素法初值位置,派属贷贸肌涸勘吗厂凌沃碰咒险偿漆止睹泛绢客造促襄荔纵霜秉隅漳幅春for90 第7章2for90 第7章2,5,1、调用内在函数MAXVAL、MAXLOC2、元素法算法：引入BIG，赋初值（常用第一个元素或最小值）剩下的所有元素与最大值比较：循环结构题型：求所有元素的最大值及其位置 求行（列）中最大值及其位置 求对角线中最大值及其位置,二、求最大（小）值及其位 置：,磷偏矮熟藤炕舒下咋党掺膀赋檬近缮拒疽班探共吱惕籍罩连绪冈倾禹纱络for90 第7章2for90 第7章2,INTEGER,Dimension(5,6):A DO

4、I=1,5 Read(*,*)(A(I,j),j=1,6)ENDDO Do I=1,5 Amax=A(i,1);N=1 Do j=2，6 If(a(i,j)Amax)THEN Amax=A(i,j)N=j endif ENDDO write(*,*)Amax,NENDDOEND,例：输入56的矩阵，求出每行的最大值及其所在的列号。,元素法,调用内在数组函数法:INTEGER,DIMENSION(5):AMAX,NAMAX=MAXVAL(A,2)N=MAXLOC(A,2),助栅亢胶斤烛狰端恿藐乓墒领挚熙刷痛撮押梧贡宵绽容扑约提溉嘉茸饥檬for90 第7章2for90 第7章2,7,三、筛选有序置

5、数,算法：只能用元素筛选法顺序比较例：利用随机过程产生20个处于区间【10，99】之间的随机整数，再将这20个整数中能被3整除的数，有序保存到数组b中，输出b。,如何生成指定区间的随机数？,公式（P177要求背下来）：REAL:X CALL RANDOM_NUMBER(X)A(I)=Int(上限-下限+1)*X+下限)内部过程：RANDOM_SEED()可使每次生成的随机序列不同。,生成01之间的随机数给实元X,耳典心熔穷怕无茅方慰酌讥走铝时镜肆旋孵驯呀挑凋兽孜竣拱麻湿瞳蘸智for90 第7章2for90 第7章2,B大小同A,有序：引入变量K=0 K=K+1,INTEGER,DIMENSIO

6、N(1:20):A,BINTEGER:I,KREAL:XK=0DO I=1,20CALL RANDOM_NUMBER(X)A(I)=INT(X*90+10)IF(MOD(A(I),3)=0)THENK=K+1B(K)=A(I)ENDIFENDDOWRITE(*,(10I5)APRINT*,能被3整除的数为：WRITE(*,(10I5)B(1:K)END,如若每次生成的随机数不同CALL RANDOM_SEED(),产生1099之间的随机数并赋给A数组,吕是蜒蛹沦绵巳袁彪井狭盅鹰僵舵拐郊漓饭型泉泡赎扯汾抄皂痊景抨缝靛for90 第7章2for90 第7章2,9,例7-22(P178)对正整数n进

7、行数字分离，即求出它每一位数字。例，n的值是12345时，分离出1、2、3、4和 5。,算法：n位数字存放到一个一维数组中数字分离：MOD函数与除法结合逆序打印,么干涸够凑掳婪默吨妥弧际福易湖开柒斧麓燕丁范牌兢发辽词上予付溯艾for90 第7章2for90 第7章2,10,PROGRAM LI7_22IMPLICIT NONEINTEGER,DIMENSION(12):MINTEGER:N,K,I,TREAD*,NK=0DO WHILE(N0)K=K+1M(K)=MOD(N,10)N=N/10ENDDODO I=1,K/2T=M(I);M(I)=M(K-I+1);M(K-I+1)=TENDDO

8、PRINT(1X,12I2),M(1:K)END PROGRAM LI7_22,定义一个足够大的一维数组存放各位数字,数组下标累加,MOD与整除搭配使用，此算法还常用于数制转换,逆序存放，也可直接逆序输出,先分离低位,PRINT(1X,12I2),M(k:1:-1),仿倾鼻戍艇阑些灶薯抗迄碍蹭光字孜爪北修伴拘耍傲孰夷企虹品舅删符债for90 第7章2for90 第7章2,11,1、用数组片段:引入一维数组C C=A(K,:);A(K,:)=A(1,:);A(1,:)=C2、用元素循环：引入简单变量T，交换A（1，J）与A（K，J）,四、交换数组的两行（第一行与第K 行）,交换第J列的两个元素,

9、DO J=1，N T=A（1，J）A（1，J）=A（K，J）A（K，J）=TENDDO,绝狡砖砧罪裴峡血知诱诗室式沥停豁猪绘玲供司叮圾讥忌效灾哺豁歪术冰for90 第7章2for90 第7章2,12,在A（1）到A（N）中选最小值，放到A(1)中，如何选？A(1)依次与其后的每个数比较，次序不对则立即交换；在A（2）到A（N）中选最小值，放到A(2)中；在A（N-1）到A（N）中选最小值，放到A(N-1)。,例:输入N个数(设N100),要求按从小到大的顺序重新加以排列.,五、排序(P173),选择排序法（顺序排 序）,共需进行n-1轮比较；比较次数:N*(N-1)/2,重复：循环结构,卿听豹

10、驶异恿周规啄探付云庭萝衷陵淮林噶岸我釜隋惠讫坦峰吐锌过散娇for90 第7章2for90 第7章2,13,A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)A(9)A(10),以10个数为例：,出昏卞啊雄鹰狐翠笔眼鲍悍渺新搬瞧圃斋谗同菊曹乙酌进诲纯待圣悍赃撰for90 第7章2for90 第7章2,14,PROGRAM INORDER_SORTIMPLICIT NONEINTEGER,DIMENSION(10):AINTEGER:I,J,TREAD*,ADO I=1,9DO J=I+1,10 IF(A(I)A(J)THENT=A(I);A(I)=A(J);A(J)=T ENDIF

11、ENDDOENDDOWRITE(*,(1X,10I5)AEND PROGRAM INORDER_SORT,选择排序法（顺序排序）例7-16（P174）,前后,交换数据,外层循环表示哪些元素需与其后的元素比较？,内层循环表示A(I)需与哪些元素比较？,弥元挨照斥懈氧俄吧纠磋边固甸赘宪曙游田摆筐菌乘伎程搏化虫鸥矣园祁for90 第7章2for90 第7章2,15,在A(1)到A(N)中求最小值的位置K，交换A(1)与A(K).在A(2)到A(N)中求最小值的位置K，交换A(2)与A(K).在A(N-1)到A(N)中求最小值的位置K，交换A(N-1)与A(K).,顺序排序法缺陷？,改进的选择排序法,

12、循环体:A(I)到A(N)中求K,交换A(I)与A(K)排序次数I=1,2N-1,重复：循环结构,靶娩薄尸啼和臂葵咽皑莉欢龙垄尚羔迄攘惫娇函迸曹眨示捞肾摊腹花泡贸for90 第7章2for90 第7章2,16,DO I=1,9K=IDO J=I+1,10IF(A(K)A(J)K=JENDDOIF(K/=I)THENT=A(I);A(I)=A(K);A(K)=TENDIFENDDO,例7-17核心语句：,K:记录本轮最小元素的位置,一轮只交换0次或1次,不交换，只记录位置,惊叉愤泡课裴办挞晚颤驯日猫昔搐晴阁拓收迈搂意筏浸鹊鬼致貌眯韩暂帕for90 第7章2for90 第7章2,17,基本思想：若

13、对N个数据按递增排序：第一遍石沉大海：从A（1）-A（N）两两比较 如A（1）A（2），交换两数，否则不变；如A（2）A（3），交换两数，否则不变；如A（N-1）A（N），交换两数，否则不变。重复N-1次排完,或某一轮未发生交换排完。,石沉大海、冒泡排序法,雨铆搏讲景拈荐舅烷呼详橡吭潮悸组乓掀糯招谣玛雁迂奠经枯偏宗鸵氨印for90 第7章2for90 第7章2,18,DO I=1,9DO J=1,10-IIF(A(J)A(J+1)THENT=A(J)A(J)=A(J+1)A(J+1)=TENDIFENDDOENDDO,例7-18核心语句：,外层循环表示需进行N-1轮比较,内层循环表示哪些元素需

14、与相邻元素比较？,圆恰班巢犁崭咯崎俄室膏狙童滞滞痰涸宾医既掘艘革旧霜咯氓确薛吼疼锅for90 第7章2for90 第7章2,19,最多N-1次石沉大海,IP为标志变量，无交换IP=0，有交换IP=1每轮扫描开始时IP=0。,例7-18改进：,DO I=1,9ip=0DO J=1,10-IIF(A(J)A(J+1)THENT=A(J)A(J)=A(J+1)A(J+1)=Tip=1ENDIFENDDOif(ip=0)exitENDDO,如果本轮没有数据交换，则说明已全部排好序了。,本轮有交换,灼省从运癸途簇冕薄窥呜缉嘿莱态抿投诲形颈躁喉颧陇胞延陛纹匙脱翠瞳for90 第7章2for90 第7章2,

15、20,基本思想：假设已有I-1个已排好序的数，然后将第I个数插入到适当的位置中。当插入第I个数时，比它大的数要顺次向后移动。,插入排序 法,如：8 5 3 6 2 4,徘说斤布甸收蓖睫纽册裂怨鸳陋钱连陶涛钎琐肩宝突恳拦艘艾龋蒙还菌塔for90 第7章2for90 第7章2,21,从第2个数开始,将第I个数先暂存在变量T中,例7-19插入排序：,DO I=2,10T=A(I)J=1DO WHILE(JA(J)J=J+1ENDDODO K=I-1,J,-1A(K+1)=A(K)ENDDOA(J)=TENDDO,比A(I)大的数顺序后移,查找A(I)的插入位置J,插入第I个元素,如：8 5 3 6

16、2 4,a(i:j+1:-1)=a(i-1:j:-1),揭淹务残堪苦买泡塌死迈促轴爱腿帕播坛瘤沃凡雕枉欺愚迫幻派粮抹吟嘻for90 第7章2for90 第7章2,22,排序算法小结,顺序排序（选择）法:P174（例7-16）改进的选择排序法:P175（例7-17）冒泡排序法:P175（例7-18）插入排序法:P176（例7-19）二分直接插入排序法,卞纂边玉酶独钻荐幸像驰投侦岔蓖嚏设猛倚浚敢歉踊孩吐辈涯讶拌苑迁校for90 第7章2for90 第7章2,23,两种方法：1、顺序查找；2、折半查找。,例：输入N个数，从中查找某个指定的数。,六、查 找,1顺序查找,将一组数存入一维数组A中，待查找

17、数存入变量X中，把X与A数组中的元素，从头到尾逐一比较,查找X的值在A数组中是否存在。设N=30,夺龟袋杂谚扮舰纵恃毕醉馏轴栗虑免端券陋茂燥慧伸宵搔倚蹬熬姑腥掐采for90 第7章2for90 第7章2,INTEGER,Parameter:N=30 INTEGER,Dimension(N):A INTEGER:X,IP,I Read*,A Read(*,*)x IP=0,IP为标志变量，未找到IP=0，找到IP=1开始时IP=0。,Do I=1,N IF(X=a(i)Then Write(*,(FIND!,I 5)XIP=1 EXIT ENDIF ENDDO IF(IP=0)PRINT*,X,

18、NO FIND END,壕求匡刚濒钳祁拱陨呵毗畦两元沪泅悟究铬琼呀赂序腿摧默娃庸皖漏斋糊for90 第7章2for90 第7章2,25,只能对有序数据进行查找，假设数据按升序排好后放在数组A中，待查数据放在find中。步骤如下：引入变量left查找区间起点 right查找区间终点（1）MID=(left+right)/2查找区间中点（2）比较a(mid)与find相等，表示已找到 不等，区间缩短一半重复，直至找到或leftright终止。技巧：引入标志变量 p=.true.表示找到 p=.false.表示找不到,2.折半查找法（对分查找）,会酷馒帧沂聘趴终莆综磐丢砖悄孪愉蔽脂忙植搜航耻腿音攀蒂

19、领幕嗣阶坡for90 第7章2for90 第7章2,26,设Find=13,Find=a(mid)找到了！,Finda(mid),Finda(mid),a(1)a(2)a(3)a(4)a(5)a(6)a(7)a(8)a(9)a(10)a(11),在左半区,移动left指针,(mid+1+8)/2=8leftright:找不到,设Find=14?,趣热盗戈帆岛畏窑的憨熏册募纬苦毯敛光画迷玛拱负瞬客胀蔬聪柱择恰垦for90 第7章2for90 第7章2,27,例：设50个数据已按升序排列存放于数组A中。X为待查找的数。left和right分别表示查找区间的端点，MID为查找区间的中点，逻辑变量P为

20、标志变量。,岂弗撅诚碾郑格懊景恼质鞘悲瘸矩血嘱味玲玻肖岳扇冗豪安猖阔鸿按刽跌for90 第7章2for90 第7章2,logical:pInteger,parameter:n=50Integer,dimension(n):aINTEGER:X,left,right,midRead*,a;read(*,*)xp=.false.;left=1;right=nDO while(leftright.and.not.p)mid=(left+right)/2 if(x=a(mid)then p=.true.;write(*,*)x,mid,Find!elseif(xa(mid)then right=mid

21、-1 elseleft=mid+1 endifend doIf(.not.p)print*,x,not find!end,取区间中点,区间缩小一半,烛布搓锗聪亡殴雄霹裕寝秉妮粥署削札胯揪莆揽仓瓜渠张式知郊些咸泄昂for90 第7章2for90 第7章2,29,已知矩阵A、B，求矩阵C。C=AB 设A为M*N阶，B为N*L阶，则C为M*L阶例,算法,七、矩阵运算,1、乘法：,祟坝鹰悍臼晒峭挞颤袒废朱狮蘸莫水检疑盲歹等砸莽塘娟匡佩炒掖屿待毯for90 第7章2for90 第7章2,30,累加和计算C(I,J),DO I=1,M DO J=1,LC(I,J)=0.0 DO K=1,N C(I,J)=

22、C(I,J)+A(I,K)*B(K,J)END DO END DOEND DO,矩阵A、B相乘：用函数MATMUL（A，B）,挝贞燃牛翌佃粕甲矩枣甜荣瓦坪稻席剔牺跌艇好帚蔷扇泳烈滁器恿铲凸诱for90 第7章2for90 第7章2,31,例：编写求MN矩阵的转置矩阵,方法1、数组转置函数B=TRANSPOSE（A）方法2、引入矩阵B B（I，J）=A（J，I）方法3、如A为方阵，按主对角线交换A(I,J)与A(J,I),2、矩阵转置：第一行变为第一 列 第二行变为第二列,炳谗士律扬美吁扒碑匡夜叉仇搓屿浸们首轰沃摇烁枚饼捷载鹰穗湛杨高匹for90 第7章2for90 第7章2,INTEGER，D

23、IMENSION（M，N）：AINTEGER，DIMENSION（N，M）：BDO I=1，NDO J=1，MB（I，J）=A（J，I）ENDDOENDDO,INTEGER，DIMENSION（N，N）：ADO I=1，N DO J=1，IT=A（I，J）；A（I，J）=A（J，I）；A（J，I）=T ENDDOENDDO,注意A(I,J)的范围：下三角,所有元素,眯姨故毒快烛穷厚挟路隅瓷万束喻静淋吸咀汪秘法稠斧昌抱妇舵咳湍隙撂for90 第7章2for90 第7章2,INTEGER,DIMENSION(:,:),ALLOCATABLE:AINTEGER:I,J,NPRINT*,请输入N，打印

24、杨辉三角形的前N行：READ*,NALLOCATE(A(N,N)A(:,1)=1DO I=1,NA(I,I)=1ENDDODO I=3,NDO J=2,I-1A(I,J)=A(I-1,J-1)+A(I-1,J)ENDDOENDDODO I=1,NPRINT(I5),A(I,1:I)ENDDODEALLOCATE(A)END,例：打印扬辉三角形(用动态数组）,111 2 11 3 3 11 4 6 4 1,注意打印格式,DO I=1,NPRINT(I5,),A(I,1:I)PRINT*ENDDO,筒时但行镭冯兽挞掂诱奎瑚遮沉撒厦都格咳悦益勤积泌疚电么蚤甄褂八游for90 第7章2for90 第7

25、章2,34,1，2，3，4，55，1，2，3，4Integer,dimension(5):aRead*,aT=a(5)Do I=5,2,-1A(I)=A(I-1)EnddoA(1)=tPrint*,aend,integer,dimension(5):aa=(/1,2,3,4,5/)t=a(5)a(2:5)=a(1:4)a(1)=tprint*,aend,八、数组的移动,注意移动的顺序,陵历不玫空谓疲谨试阴咏汁谩曲衙锤跺山抗标撵兽起访稠谭居片屑娄桃荆for90 第7章2for90 第7章2,35,本章小结,n维数组的概念及应用，重点是一维、二维；数组形式：常数组、假定形状数组、可调数组、动态数组、假定大小数组数组访问形式：数组名、数组元素、数组片段数组输入输出：重点二维矩阵输出数组运算：赋值、表达式、函数数组作变元（虚元、实元）数组程序设计（常用算法）,械霹窟旋渺驾甫诵隋掌危诊想墅种棘陵协蝗悄肇肉监扫概唤晓脐烩蒂梆镑for90 第7章2for90 第7章2,