最新1.1算法与程序框图课件PPT.ppt 94页

'1.1算法与程序框图 问题的提出有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？方法和过程：1、带羊到对岸，返回；2、带菜到对岸，并把羊带回；3、带狼狗到对岸，返回；4、带羊到对岸。 [问题1]请你写出解二元一次方程组的详细求解过程. 算法的特征一.确定性:每一步必须有确切的定义。二.有效性：原则上必须能够精确的运行。三.有穷性：一个算法必须保证执行有限步后结束算法的优缺点一.缺点:算法一般是机械的,有时需要进行大量重复的计算.二.优点:算法是一种通法,只要按照步骤去做,总能得到结果. 广播操图解是广播操的算法；菜谱是做菜的算法；歌谱是一首歌曲的算法；空调说明书是空调使用的算法等我们身边的算法 算法学的发展随着科学技术的日新月异,算法学也得到了前所未有的发展,现在已经发展到了各个领域.有遗传算法,排序算法,加密算法,蚁群算法等,与生物学,计算机科学等有着很广泛的联系,尤其是在现在的航空航天中,更是有着更广泛的应用.很多复杂的运算都是借助计算机和算法来完成的,在高端科学技术中有着很重要的地位. 应用举例例1.(1)设计一个算法判断7是否为质数.第一步,用2除7,得到余数1.因为余数不为0，所以2不能整除7.第二步,用3除7,得到余数1.因为余数不为0，所以3不能整除7.第三步,用4除7,得到余数3.因为余数不为0，所以4不能整除7.第四步,用5除7,得到余数2.因为余数不为0，所以5不能整除7.第五步,用6除7,得到余数1.因为余数不为0，所以6不能整除7.因此，7是质数. 应用举例例1.(2)设计一个算法判断35是否为质数.第一步,用2除35,得到余数1.因为余数不为0，所以2不能整除35.第二步,用3除35,得到余数2.因为余数不为0，所以3不能整除35.第三步,用4除35,得到余数3.因为余数不为0，所以4不能整除7.第四步,用5除35,得到余数0.因为余数为0，所以5能整除35.因此，35不是质数. “判断整数n（n>2）是否为质数”的算法步骤如何？第一步，给定一个大于2的整数n；第二步，令i=2；第三步，用i除n，得到余数r；第四步，判断“r=0”是否成立.若是，则n不是质数，结束算法；否则，将i的值增加1，仍用i表示；第五步，判断“i>(n-1)”是否成立，若是，则n是质数，结束算法；否则，返回第三步. 应用举例例2.用二分法设计一个求方程的近似根的算法. 探究解决对于区间[a,b]上连续不断、且f(a)f(b)<0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法. 解决问题×第四步,若f(a)·f(m)<0,则含零点的区间为［a,m］；第一步,令.给定精确度d.第二步,给定区间［a,b］,满足f(a)·f(b)＜0．第三步,取中间点　　　　　．第五步,判断［a,b］的长度是否小于d或者f(m)是否等于０.将新得到的含零点的仍然记为［a,b］.否则，含零点的区间为［m,b］.若是，则m是方程的近似解;否则，返回第三步． 解决问题abmf(m)d121.50.25111.51.25-0.43750.51.251.51.375-0.1093750.251.3751.51.43750.066406250.1251.3751.43751.40625-0.022460940.06251.406251.43751.4218750.0217285160.031251.406251.4218751.4140625-0.000427250.0156251.41406251.4218751.417968750.0106353760.00781251.41406251.4179691.416015630.005100250.00390625当d=0.05时评析:实际上,上述步骤就是在求的近似值. 与一般的解决问题的过程比较,算法有以下特征:①设计一个具体问题的算法时,与过去熟悉地解数学题的过程有直接的联系,但这个过程必须被分解成若干个明确的步骤,而且这些步骤必须是有效的.②算法要“面面俱到”,不能省略任何一个细小的步骤,只有这样,才能在人设计出算法后,把具体的执行过程交给计算机完成. 练习一:任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.算法分析:第一步:输入任意一个正实数r;第二步:计算以r为半径的圆的面积S=πr2;第三步:输出圆的面积.课本5页1 练习二:任意给定一个大于1的正整数n,设计一个算法求出n的所有因数.算法分析:第一步:依次以2~(n-1)为除数去除n,判断余数是否为0,若是,则是n的因数;若不是,则不是n的因数.第二步:在n的因数中加入1和n;第三步:输出n的所有因数.课本5页2 计算机解决任何问题都要依赖于算法.只有将解决问题的过程分解为若干个明确的步骤,即算法,并用计算机能够接受的“语言”准确地描述出来,计算机才能够解决问题. 1.1.2程序框图 问题提出1.算法的含义是什么？在数学中，按照一定规则解决某一类问题的明确和有限的步骤称为算法.2.算法是由一系列明确和有限的计算步骤组成的，我们可以用自然语言表述一个算法，但往往过程复杂，缺乏简洁性，因此，我们有必要探究使算法表达得更加直观、准确的方法，这个想法可以通过程序框图来实现. 知识探究（一）：算法的程序框图思考1:“判断整数n（n>2）是否为质数”的算法步骤如何？第一步，给定一个大于2的整数n；第二步，令i=2；第三步，用i除n，得到余数r；第四步，判断“r=0”是否成立.若是，则n不是质数，结束算法；否则，将i的值增加1，仍用i表示；第五步，判断“i>(n-1)”是否成立，若是，则n是质数，结束算法；否则，返回第三步. 开始输入ni=2求n除以i的余数ri的值增加1仍用i表示i≥n或r=0?n不是质数结束是否是n是质数否r=0?i=i+1思考2：为了使算法的程序或步骤表达得更为直观,我们更经常地用图形方式来表示它. 程序框图又称流程图,是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形.通常,程序框图由程序框和流程线组成.一个或几个程序框的组合表示算法中的一个步骤;流程线是方向箭头,按照算法进行的顺序将程序框连接起来. 思考3：基本的程序框和它们各自表示的功能？图形符号名称功能终端框(起止框)表示一个算法的起始和结束输入、输出框表示一个算法输入和输出的信息处理框(执行框)判断某一条件是否成立,成立时在出口处标明“是”或“Y”；不”成立时标明“否”或“N”.判断框赋值、计算流程线连接程序框连接点连接程序框图的两部分 开始输入ni=2求n除以i的余数ri的值增加1仍用i表示i≥n或r=0?n不是质数结束是否是n是质数否r=0?设n是一个大于2的整数.一般用i=i+1表示.i=i+1说明:i表示从2~(n-1)的所有正整数,用以判断例1步骤2是否终止,i是一个计数变量,有了这个变量,算法才能依次执行.逐步考察从2~(n-1)的所有正整数中是否有n的因数存在. 思考4：通过上述算法的两种不同表达方式的比较,你觉得用程序框图来表达算法有哪些特点?用程序框图表示的算法更加简练,直观,流向清楚. 开始输入ni=2求n除以i的余数ri=i+1i≥n或r=0?n不是质数结束是否是n是质数否r=0?顺序结构思考:5：用程序框图来表示算法，有几种不同的基本逻辑结构？条件结构循环结构 知识探究（二）：算法的顺序结构思考1:任何一个算法各步骤之间都有明确的顺序性，在算法的程序框图中，由若干个依次执行的步骤组成的逻辑结构，称为顺序结构，用程序框图可以表示为：步骤n步骤n+1在顺序结构中可能会用到哪几种程序框和流程线？? 思考2:若一个三角形的三条边长分别为a，b，c，令，则三角形的面积.你能利用这个公式设计一个计算三角形面积的算法步骤吗？第一步，输入三角形三条边的边长a，b，c.第二步，计算.第三步，计算.第四步，输出S. 思考3:上述算法的程序框图如何表示？开始结束输出S输入a，b，c 练习：1.就（1）、（2）两种逻辑结构，说出各自的算法功能开始输入a，b结束sum=a+b输出sum开始输入a，b输出结束（1）（2）答案：（1）求直角三角形斜边长；（2）求两个数的和． 顺序结构的程序框图的基本特征：顺序结构知识小结（2）各程序框从上到下用流程线依次连接.（1）必须有两个起止框，穿插输入、输出框和处理框，没有判断框.（3）处理框按计算机执行顺序沿流程线依次排列. 条件结构r=0?N不是质数n是质数是否知识探究（三）：算法的条件结构 条件结构---在一个算法中,经常会遇到一些条件的判断,算法的流向根据条件是否成立有不同的流向.条件结构就是处理这种过程的结构.满足条件?是否步骤A步骤B满足条件?是否步骤A 课本例4:任意给定3个正实数,设计一个算法,判断分别以这3个数为三边边长的三角形是否存在.画出这个算法的程序框图.算法分析:第一步:输入3个正实数a,b,c;第二步:判断a+b>c,a+c>b,b+c>a是否同时成立,若是,则能组成三角形;若否,则组不成三角形. 程序框图:开始输入a,b,ca+b>c,a+c>b,b+c>a是否同时成立?是存在这样的三角形不存在这样的三角形否结束 算法步骤如下（课本例5）： 开始输入a，b，cX1=p+qX2=p-q输出x1,x2输出“方程没有实数根”输出p结束否是否是 是练习2：设计一个求任意数的绝对值的算法,并画出程序框图.算法分析:第一步:输入数x;第二步:判断x≥0是否成立?若是,则|x|=x;若否,则|x|=-x.程序框图:开始输入xx≥0?输出x否输出-x结束 练习3：画程序框图,对于输入的x值,输出相应的y值.开始程序框图x<0?是y=0否0≤x<1?是y=1否y=x输出y结束输入x P:50页A组T1(2)开始程序框图x<0?是y=(x+2)2否x=0?是y=4否输出y结束输入xy=(x-2)2 练习5：1.就逻辑结构，说出其算法功能．开始结束输入xx>3?y=x-2输出yy=4-x否是开始max=a输入bmax>b？输出max结束max=b是否2.此为某一函数的求值程序图，则满足该流程图的函数解析式为（）（不能写成分段函数）．3.求函数的值的算法流程图．开始输入xX<2?y=－2输出y结束否是答案:1.求两个数中的最大值.答案:2.y=|x-3|+1. 循环结构i=i+1i>n-1,或r=0?否是求n除以i的余数r循环结构---在一些算法中,也经常会出现从某处开始,按照一定条件,反复执行某一步骤的情况,这就是循环结构.反复执行的步骤称为循环体.知识探究（四）：算法的循环结构 引例：设计一算法，求和:1+2+3+…+100第一步：确定首数a，尾数b，项数n；第二步：利用公式“总和=(首数+尾数）×项数/2”求和；第三步：输出求和结果。算法1：开始结束输入a,b,nS=(a+b)*n/2输出S 课本例6:设计一个计算1+2+3+……+100的值的算法,并画出程序框图.算法分析:第1步:0+1=1;第2步:1+2=3;第3步:3+3=6;第4步:6+4=10…………第100步:4950+100=5050.第(i-1)步的结果+i=第i步的结果各步骤有共同的结构:为了方便有效地表示上述过程,我们引进一个变量S来表示每一步的计算结果,从而把第i步表示为S=S+iS=0S=S+1S=S+2S=S+3…S=S+100 求和:1+2+3+…+100S=S+i怎么用程序框图表示呢？思考1：i有什么作用?S呢？i=i+1S=S+iS=0S=S+1S=S+2S=S+3…S=S+100累加变量S来表示每一步的计算结果,从而把第i步表示为S=S+iS的初始值为0,i依次取1,2,…,100,由于i同时记录了循环的次数,所以i称为计数变量. i=i+1S=S+i解决方法就是加上一个判断，判断是否已经加到了100，如果加到了则退出，否则继续加。试分析两种流程的异同点直到型结构当型结构S=S+ii=i+1是否S=S+ii=i+1否是i<=100?i>100?请填上判断的条件。 程序框图:开始i=1S=0S=S+ii=i+1i>100?是输出S结束否直到型循环结构开始i=1S=0i≤100?是S=S+ii=i+1否输出S结束当型循环结构 思考2：若将“i=1”改成“i=0”，则程序框图怎么改？开始结束输出SS=0否是i=0S=S+ii=i+1i>=100?开始结束输出Sum否是S=0i=0S=S+ii=i+1i<100?直到型循环结构当型循环结构 结束S=S+ii=i+1i<=100?输出S否是i=1，S=0开始步骤A步骤B思考:3:将步骤A和步骤B交换位置，结果会怎样？能达到预期结果吗？为什么？要达到预期结果，还需要做怎样的修改？答：达不到预期结果；当i=100时，没有退出循环，i的值为101加入到S中；修改的方法是将判断条件改为i<100 是循环体满足条件？否Until（直到型）循环说明（1）循环结构分为两种------当型和直到型.当型循环在每次执行循环体前对循环条件进行判断,当条件满足时执行循环体,不满足则停止;(当条件满足时反复执行循环体)直到型循环在执行了一次循环体之后,对控制循环条件进行判断,当条件不满足时执行循环体,满足则停止.(反复执行循环体,直到条件满足)循环体满足条件？是否While（当型）循环 （2）注意:循环结构不能是永无终止的“死循环”,一定要在某个条件下终止循环,这就需要条件结构来作出判断,因此,循环结构中一定包含条件结构.说明:一般地,循环结构中都有一个计数变量和累加变量.计数变量用于记录循环次数,同时它的取值还用于判断循环是否终止,这个变量的取值一般都含在执行或终止循环体的条件中。累加变量用于输出结果.累加变量和计数变量一般是同步执行的,累加一次,记数一次. 结束输出Si=0，S=0开始i=i+1S=S+ii>=n?否是输入n改进上面的算法，表示输出1,1+2,1+2+3,…,1+2+3+…+(n-1)+n()的过程。 练习巩固1、设计一算法，求积:1×2×3×…×100，画出流程图结束输出Ai=0，A=1开始i=i+1A=A*ii>=100?否是思考：该流程图与前面的课本例6中求和的流程图有何不同？ 课本例7：某工厂2005年的年生产总值为200万，技术革新以后每年的年生产总值比上一年增长5％。设计一个程序框图，输出预计年生产总值超过300万元的最早年份。算法分析：第一步，输入2005年的年生产总值。第二步，计算下一年的年生产总值。第三步，判断所得的结果是否大于300.若是，则输出该年的年份；否则，返回第二步 由于“第二步”是重复操作的步骤，所以可以用循环结构来实现。我们按照“确定循环体”“初始化变量”“设定循环控制条件”的顺序来构造循环结构。（2）初始化变量：若将2005年的年生产总值堪称计算的起始点，则n的初始值为2005，a的初始值为200.（3）设定循环控制条件：当“年生产总值超过300万元”时终止循环，所以可通过判断“a>300”是否成立来控制循环。（1）确定循环体：设a为某年的年生产总值，t为年生产总值的年增长量，n为年份，则循环体为 程序框图:开始n=2005a=200t=0.05an=n+1a>300?是输出n结束否a=a+t 小结1、循环结构的特点2、循环结构的框图表示3、循环结构有注意的问题避免死循环的出现，设置好进入（结束）循环体的条件。当型和直到型重复同一个处理过程 【答案】D 【答案】C 【答案】B. 【答案】B 作业:课本P20页A组2; 第九讲进程同步与通信目的与要求：掌握信号量解决进程同步互斥问题的方法，掌握进程通信的基本实现方法。重点与难点：信号量的典型应用，通信实现。作业：15，16，17。 4.2.5进程同步与互斥举例一、有限缓冲区问题问题描述：设有n个缓冲区，一组生产者进程往缓冲区写数据，一组消费者进程从缓冲区取数据，写取都以一个缓冲区为单位。说明：将缓冲池看做是共享数据，对缓冲区的操作必须是互斥操作。如果n个缓冲区全满，生产者进程必须等待。如果缓冲区全空，消费者进程必须等待。 有限缓冲区的生产者/消费者问题（生产者和消费者共享一个产品缓冲池）。共享N个缓冲区P1P2…PmC1C2…Cn生产者消费者缓冲池 解：设置以下信号量mutex,初值为1，控制互斥访问缓冲池。full,初值为0，表示当前缓冲池中满缓冲区数，用于同步。empty,初值为n，表示当前缓冲池中空缓冲区数，用于同步。有限缓冲区生产者/消费者进程描述如下：typeitem=…;varbuffer=…;full,empty,mutex:semaphor;nextp,nextc:item;beginfull:=0;empty:=n;mutex:=1; P(empty);P(mutex);addnextptobuffer;V(mutex);V(full);untilfalse;end;ParbeginProducer:beginrepeat…produceaniteminnextp;... …consumetheiteminnextc;…untilfalse;end;Parend;consumer:beginrepeatP(full);P(mutex);removeanitemfrombuffertonextc释放缓冲区V(mutex);V(empty); 若存在一共享数据A，那些对它进行读访问者叫Reader，对它进行写访问者叫做Writer。第一类Reader/Writer问题：Reader和Writer争夺访问共享数据A时，Reader有较高优先数。表现在：除了某个Writer正在访问数据之外，任何情况下Reader欲访问数据均可以直接进行访问。二、Readers/Writers问题 该问题可具体描述为：1.如果当前无人访问数据，则Reader/Writer欲访问即可访问。2.如果已存在一个Reader正在访问数据，其他欲访问Reader可马上访问（这体现Reader有较高优先权）；而欲访问的Writer必须等待。3.若某个Writer正访问数据，则欲访问的Reader/Writer都必须等待。 （续）4.当最后一个结束访问数据的Reader发现有Writer正在等待时，则将其中一个唤醒。5.当某个Writer结束访问时，若只有Writer在等待，则唤醒某个Writer，若既有Writer也有Reader；则按FIFO或某它原则唤醒一个Writer或所有Reader。 Reader的一般结构为：P(mutex)；readcount:=readcount+1;Ifreadcount=1thenP(wrt);V(mutex)；读数据AP（mutex）；readcount:=readcount-1;Ifreadcount=0thenV(wrt);V(mutex); Writer的一般结构为：P（wrt）;写数据AV（wrt）; 三、哲学家就餐问题问题描述：五个哲学家五只筷子，哲学家循环做着思考和吃饭的动作，吃饭程序是：先取左边筷子，再取右边筷子，再吃饭，再放筷子。 实现：为每个筷子设一把锁（信号量，初值为1）每个哲学家是一个进程。共享数据结构为：VarChopstick;array[0,4]ofsemaphore;第i个进程描述为(i=0,…,4)repeatP（chopstick[i]）;P(chopstick[(i+1)mod5])；吃V(chopstick[i]);V(Chopstick[(i+1)mod5]；思考untilfalse;(这可能导致死锁) 4.3进程通信两种基本进程通信方法：1.共享存储（Shared-memory）：相互通信的进程有共享存储区。进程间可以通过直接读写共享存储区的变量来交互数据，同步与互斥在并发程序设计时安排进入程序。操作系统提供这样的共享存储区及某些同步互斥工具。2.消息传递(message-passing)：若进程间无共享空间，则必须通过消息传递通信，且必须通过OS系统调用实现。 消息传递系统调用语句的一般形式:发送：Send&消息to目的地标识接收：Receive&消息from源地址标识.一、消息传递方法1.直接通信法基本思想：进程在发送和接收消息时直接指明接收者或发送者进程ID。缺点：必须指定接收进程ID（UNIX的信号机制类似这种形式）。4.3.1消息传递通信原理 举例：（UNIX中两进程利用信号通信）。ProcessA┆kill(1040,SIGUSR1);#向1040号进程发送一个SIGUSR1信号。ProcessB┆Signal(SIGUSR1,func);#当收到SIGUSR1信号时，就执行func(),如果SIGUSR1信号未到，则系统登记func函数，待其信号到时再调用执行。┆┆ 2.间接通信法（信箱命名法〕基本思想：系统为每个信箱设一个消息队列，消息发送和接收都指向该消息队列，（每个进程可以对消息队列发送并接收/只发送/只接收)缺点：必须有一个通信双方共享的一个逻辑消息队列（UNIX的PIPE，FIFO及IPC消息传递机制都属于这种形式），使用时消息发送者约定写方式打开信箱,消息接收者约定读方式打开信箱或同时读写打开。优点：很容易建立双向通信链(只要对信箱说明为读写打开)。 逻辑通信链容量：在通信发送者和接收者之间存在一条逻辑通信链，设链的容量是指该链暂存消息的能力。1.容量为0，表示链中无缓冲(不计链头的发送缓冲和链尾的接收缓冲)，这要求接收方必须在发送方之前发接收请求，否则发送失败。2.有限容量，表示链中有有限缓冲区、发送者不必等接收者发出接收请求，不必等接收者准备好接收缓冲区，即可将消息存于通信链中的缓冲区中。3.消息从发送方缓冲进入系统缓冲区，即可再次发新消息，无需等上一消息被完全接收。二、缓冲与同步 发送者执行send()的同步问题：1.将发送者消息拷入通信链缓冲区，即将控制返回发送者。2.在将消息从硬通信通道发出后，将控制返回发送者。3.在消息由接收方节点的系统收到后，再将控制返回发送者。4.在消息由接收方收到后，再将控制返回发送者。5.在消息由接收方处理完后，再将控制返回发送者（RPC，LPC）。为实现3.,4.情形同步，需要建立回送到发送者所在系统的通信链，5.的情形需要建立回送到发送者的通信链。 4.3.2进程通信示例直接通信消息系统的两个基本操作为：send(A)：A指向含接收者pid和消息正文的空间。Receive(A)：A指向缓冲区用于接收消息，该系统调用函数返回值是消息发送者pid。实现：系统有一用于进程通信的缓冲池，池中缓冲区用于存放消息及消息发送者pid和消息链指针(用pid定位进程PCB表)。Sender’spid消息正文Link消息缓冲区 每个进程有一个消息队列，存放发送给该进程的消息，队列头存于PCB中，同时在PCB中设一互斥信号量mutex(初值为1)和一同步通信的信号量Sm（初值为0），Sm也用于计录消息队列中的消息数。...mutexSm...Sender’spidtextSender’spidtextReceiver’sPCBmessagemessageHptr Send(A):beginNew(p)；从缓冲池得一个buffer...置sender’spid；将A中消息送bufferp；获得Receiver’spid；P(mutex)；将bufferp挂入相应的消息队列；V(Sm)；V(mutex)；end； Receive(A)：beginP(Sm)；P(mutex)；从本进程的消息队列取一个bufferf；V(mutex)；从bufferf中取得消息正文送A,并得到sender’spid作为Receive()的返回值；...dispose(f)；#释放bufferf到缓冲池…end；注:new,dispose函数对缓冲池的访问也需要互斥.'