《算法与程序框图改jppt课件》由会员分享，可在线阅读，更多相关《算法与程序框图改jppt课件（58页珍藏版）》请在金锄头文库上搜索。
1、1.1.1 算法的概念算法的概念学学习目的：目的： 1了解算法是描画了解算法是描画处置有有限多个步置有有限多个步骤的的问题的方法的一种的方法的一种“言言语； 2会用自然言会用自然言语描画解方程描画解方程组等数学等数学问题的算的算法。法。学学习重点：能从整体上把握重点：能从整体上把握详细问题的解的解题步步骤。学学习难点：会用明确的言点：会用明确的言语描画算法的每一个步描画算法的每一个步骤。问题问题1请他写出用加减消元法解以下二元一次请他写出用加减消元法解以下二元一次方程组的详细求解过程方程组的详细求解过程. 对于普通的二元一次方程于普通的二元一次方程组也可以按照也可以按照上述步上述步骤求解求解.
2、第一步第一步:2+得得: 5x=1 第二步第二步:解解得得:x=1/5第三步第三步:将将x=1/5代入代入得得:y=3/5第四步第四步:得到方程得到方程组的解的解为: 这些步些步骤就构成了解二元一次方程就构成了解二元一次方程组的算法的算法，我，我们可以根据可以根据这一算法一算法编制制计算机程序，算机程序，“教会教会计算机解二元一次方程算机解二元一次方程组。算法的概念与特征算法的概念与特征 算法算法(algorithm)这个个词出出现于于12世世纪，指的是用阿拉伯数字指的是用阿拉伯数字进展算展算术运算的运算的过程。程。 在数学上在数学上,“算法通常是指按照一定算法通常是指按照一定规那那么么处理某
3、一理某一类问题的明确和有限的步的明确和有限的步骤。算。算法具有程序性、有限性、构造性、准确性的法具有程序性、有限性、构造性、准确性的特点。如今，算法通常可以特点。如今，算法通常可以编成成计算机程序，算机程序，让计算机算机执行并行并处理理问题。算法学的开展算法学的开展 随着科学技术的日新月异随着科学技术的日新月异, ,算法学也算法学也得到了前所未有的开展得到了前所未有的开展, ,如今曾经开展如今曾经开展到了各个领域到了各个领域. .有遗传算法有遗传算法, ,排序算法排序算法, ,加密算法加密算法, ,蚁群算法等蚁群算法等, ,与生物学与生物学, ,计算计算机科学等有着很广泛的联络机科学等有着很广
4、泛的联络, ,尤其是在尤其是在如今的航空航天中如今的航空航天中, ,更是有着更广泛的更是有着更广泛的运用运用. . 很多复杂的运算都是借助计算机很多复杂的运算都是借助计算机和算法来完成的和算法来完成的, ,在高端科学技术中有在高端科学技术中有着很重要的位置着很重要的位置. .科学家王小云主科学家王小云主导破解两大密破解两大密码算法算法获百万大百万大奖杨振宁教授振宁教授为获得得“求是出色科求是出色科学家学家奖的山的山东大大学特聘教授王小云学特聘教授王小云颁发了了获奖证书和和奖金金100万元人民万元人民币，表，表扬其密其密码学学领域的出色成就。域的出色成就。 例例1:恣意给定一个大于恣意给定一个大
5、于2的整数的整数n，试设计一个，试设计一个程序或步骤对程序或步骤对n能否为质数做出断定。能否为质数做出断定。算法分析算法分析:第一步第一步:给定大于定大于2的整数的整数n第二步：令第二步：令i=2 第三步第三步:用用i除除n，得到余数，得到余数r 第四步第四步:判判别r=0能否成立，假能否成立，假设是，那么是，那么n不不是是质数，数，终了算法；假了算法；假设否，否，i=i+1; 第五步第五步:判判别in-1能否成立，假能否成立，假设是，那么是，那么n是是质数，数，终了算法；假了算法；假设否，那么前往第三步。否，那么前往第三步。 假假设是是,那那么么m为所求所求; 例例2:用二分法用二分法设计一
6、个求方程一个求方程x2-2=0x0)的的近似根的算法近似根的算法.算法分析算法分析:设所求近似根与准确解的差的所求近似根与准确解的差的绝对值不超越不超越=0.005.第一步第一步:令令f(x)=x2-2.由于由于f(1)0,所以所以设a=1,b=2.第二步第二步:令令判判别f(m)能否能否为0.假设否假设否,那么继续判别那么继续判别f(a) f(m)大于大于0还是还是小于小于0.第三步第三步:假设假设f(a) (m)0,那么令那么令a=m;否那么否那么,令令b=m. 第四步第四步:判判别|a-b|7时)解解:y与与x之间的函数关系为之间的函数关系为:(当当0x7时)(当当x7时)求该函数值的算
7、法分析求该函数值的算法分析:第一步第一步:输入每月用水量入每月用水量x；第二步第二步:判判别x能否大于能否大于7。假。假设是，那么是，那么y=1.9x4.9；假；假设否，那么否，那么y=1.2x。第三步第三步:输出出应交交纳的水的水费y。作业作业:课本课本P51页复习参考页复习参考题题B组组T3： 设计一个算法，判设计一个算法，判别一个正的别一个正的n(n2)位位数是不是回文数？数是不是回文数？ (只需用自然言语写只需用自然言语写出算法步骤出算法步骤) 注：回文数是指从注：回文数是指从左到右读与从右到左左到右读与从右到左读都是一样的正整数，读都是一样的正整数，如如121，94249等。等。1.
8、1.2 程序框图程序框图1 学学习目的：目的： 1了解程序框了解程序框图的的顺序构造、条件构造的画序构造、条件构造的画法及功能；法及功能； 2能在能在“人肉人肉计算机中运算机中运转程序框程序框图描画的描画的算法。算法。学学习重点：重点： 启启动“人肉人肉计算机，运算机，运转大量大量简单程序。程序。学学习难点：点： 如何用多重条件构造如何用多重条件构造处置复置复杂的分的分类讨论问题。 从上节课我们知道从上节课我们知道:算法可以用自然言语来描算法可以用自然言语来描画画.如例如例1： 为了使算法的程序或步了使算法的程序或步骤表达得更表达得更为直直观,我我们更更经常地用常地用图形方式来表示它形方式来表
9、示它. 恣意给定一个大于恣意给定一个大于1的整数的整数n，试设计一个程，试设计一个程序或步骤对序或步骤对n能否为质数做出断定。能否为质数做出断定。算法分析算法分析:第一步第一步:判判别n能否等于能否等于2. 假假设n=2,那么那么n是是质数数;假假设n2,那么那么执行第二步行第二步. 第二步第二步:依次依次检验从从2到到(n-1)这些数能否整除些数能否整除n。假。假设有有这样的数，那么的数，那么n不是不是质数；假数；假设没没有有这样的数，那么的数，那么n是是质数。数。开场开场输入输入ni=2求求n除以除以i的余数的余数ri的值添加的值添加1仍用仍用i表示表示in或或r=0?n不是质数不是质数终
10、了终了是是否否是是n是质数是质数否否r=0?设设n是一个大是一个大于于2的整数的整数.普通用普通用i=i+1表示表示. i=i+1阐明明:i表示从表示从2(n-1)的一切正整数的一切正整数,用以用以判判别例例1步步骤2能否能否终止止,i是一个是一个计数数变量量,有了有了这个个变量量,算法算法才干依次才干依次执行行.逐逐渐调查从从2(n-1)的一的一切正整数中能否有切正整数中能否有n的因数存在的因数存在.思索：比较自然言语和程序框图这两种不同的思索：比较自然言语和程序框图这两种不同的表达方式，他觉得用程序框图来表达算法有哪表达方式，他觉得用程序框图来表达算法有哪些优点些优点?答：更加答：更加简约
11、，直，直观，执行的流程更明晰。行的流程更明晰。 程序框程序框图又称流程又称流程图，是一种用，是一种用规定的定的图形、形、指向指向线及文字及文字阐明来准确、直明来准确、直观地表示算法的地表示算法的图形。形。根本的程序框和它们各自表示的功能如下根本的程序框和它们各自表示的功能如下:图形符号图形符号称号称号功能功能终端框端框(起止框起止框)表示算法的起始和表示算法的起始和终了了输入、入、输出框出框表示算法表示算法输入和入和输出出的信息的信息处置框置框(执行框行框)根据某条件能否成立改根据某条件能否成立改动程序程序执行的流向行的流向判判别框框赋值、计算等算等流程流程线衔接程序框接程序框衔接点接点衔接程
12、序框接程序框图的两部分的两部分程序框图的三种根本的逻辑构造程序框图的三种根本的逻辑构造顺序构造顺序构造条件构造条件构造循环构造循环构造开场开场输入输入ni=2求求n除以除以i的余数的余数ri=i+1in或或r=0?n不是质数不是质数终了终了是是否否是是n是质数是质数否否r=0?顺序构造顺序构造用程序框图来表示算法，有用程序框图来表示算法，有三种不同的根本逻辑构造：三种不同的根本逻辑构造：条件构造条件构造循环构造循环构造(1)顺序构造顺序构造-是由假设干个依次执行的是由假设干个依次执行的处置步骤组成的。这是任何一个算法都离不处置步骤组成的。这是任何一个算法都离不开的根本构造。开的根本构造。例例1
13、:知一个三角形的三知一个三角形的三边边长分分别为2，3，4，利用海，利用海伦-秦九韶公式秦九韶公式设计一个算法，求出一个算法，求出它的面它的面积，画出算法的程序框，画出算法的程序框图。知三角形三知三角形三边长分分别为a,b,c,那么三角那么三角形的面形的面积为 其中其中 这个公式被称个公式被称为海海伦秦九韶公式秦九韶公式.算法分析算法分析:第二步第二步:计算算p的的值。第三步第三步:计算算S=第四步第四步:输出出S的的值。程序框图程序框图:开开场输出输出S终了了(2)条件构造条件构造-在一个算法中，在一个算法中，经常会遇到常会遇到一些条件的判一些条件的判别，算法的流向根据条件能，算法的流向根据
14、条件能否成立有不同的流向。条件构培育是否成立有不同的流向。条件构培育是处置置这种种过程的构造。程的构造。例例2:恣意恣意给定定3个正个正实数，数，设计一个算法，判一个算法，判别分分别以以这3个数个数为三三边边长的三角形能否存在。的三角形能否存在。画出画出这个算法的程序框个算法的程序框图。算法分析算法分析:第一步第一步:输入入3个正个正实数数a，b，c；第二步第二步:判判别a+bc，a+cb，b+ca能否同能否同时成成立。假立。假设是，那么能是，那么能组成三角形；假成三角形；假设否，那么否，那么组不成三角形。不成三角形。程序框图程序框图:开开场输入输入a,b,ca+bc,a+cb,b+ca能否能
15、否同时成立同时成立?是是存在这样的存在这样的三角形三角形不存在这样的不存在这样的三角形三角形否否终了了例例3:上节课曾经做过此题为了加强居民上节课曾经做过此题为了加强居民的节水认识，某市制定了以下生活用水收费的节水认识，某市制定了以下生活用水收费规范：每户每月用水未超越规范：每户每月用水未超越7m3时，每立方时，每立方米收费米收费1.0元，并加收元，并加收0.2元的城市污水处置元的城市污水处置费；超越费；超越7m3的部分，每立方米收费的部分，每立方米收费1.5元，元，并加收并加收0.4元的城市污水处置费，请他写出某元的城市污水处置费，请他写出某户居民每月应交纳的水费户居民每月应交纳的水费y(元
16、元)与用水量与用水量x(m3)之间的函数关系，然后设计一个求该函之间的函数关系，然后设计一个求该函数值的算法数值的算法,并画出程序框图。并画出程序框图。解解:y与与x之之间的函数关系的函数关系为:(当当0x7时)(当当x7时)解解:y与与x之间的函数关系为之间的函数关系为:(当当0x7时)(当当x7时)算法分析算法分析:第一步第一步:输入每月用水量输入每月用水量x;第二步第二步:判别判别x能否大于能否大于7。假设是，那么假设是，那么y=1.9x4.9；假设否，那么；假设否，那么y=1.2x。第三步第三步:输出应交纳的水费输出应交纳的水费y.开开场输入输入xx7?是是y=1.9x4.9否否y=1
17、.2x输出输出y终了了程序框程序框图是是练习练习1.设计一个求恣意数的绝对值的算法，并画设计一个求恣意数的绝对值的算法，并画出程序框图。出程序框图。算法分析算法分析:第一步第一步:输入数入数x;第二步第二步:判判别x0能否能否成立成立?假假设是是,那么那么|x|=x;假假设否否,那么那么|x|=-x.程序框程序框图:开开场输入输入xx0?输出输出x否否输出输出-x终了了前往前往例例4.(课本课本P50复复习参考题习参考题A组组T1(1)画程序框图画程序框图,对对于输入的于输入的x值值,输输出相应的出相应的y值值.开开场程序框程序框图x0?是是y=0否否x100?是是输出输出S终了了否否直到直到
18、型循型循环构环构造造开开场i=1S=0i100?是是S=S+ii=i+1否否输出输出S终了了当型循环当型循环构造构造阐明明:(1)普通地，循普通地，循环构造中都有构造中都有计数数变量和累量和累加加变量。量。计数数变量用于量用于记录循循环次数，同次数，同时它它的取的取值还用于判用于判别循循环能否能否终止，累加止，累加变量用量用于于输出出结果。累加和果。累加和计数操作普通是在循数操作普通是在循环体体中都作一次，即累加一次，并且中都作一次，即累加一次，并且记数一次。数一次。(2)循循环构造分构造分为两种两种-当型和直到型当型和直到型.当型循当型循环在每次在每次执行循行循环体前体前对循循环条件条件进展
19、判展判别，当条件，当条件满足足时执行循行循环体，不体，不满足足那么停那么停顿；(当条件当条件满足足时反复反复执行循行循环体体)直到型循直到型循环在在执行了一次循行了一次循环体之后，体之后，对控制循控制循环的条件的条件进展判展判别，当条件不，当条件不满足足时执行循行循环体，体，满足那么停足那么停顿。(反复反复执行循行循环体，体，直到条件直到条件满足足)程序框图程序框图:开场开场i=1S=0S=S+ii=i+1i100?是是输出输出S终了终了否否直到直到型循型循环构环构造造开场开场i=1S=0i100?是是S=S+ii=i+1否否输出输出S终了终了当型循环当型循环构造构造开场开场输入输入ni=2求
20、求n除以除以i的余数的余数ri=i+1in或或r=0?n不是质数不是质数终了终了是是否否是是n是质数是质数否否r=0?以下判别以下判别n能否为质数的程序框能否为质数的程序框图中用虚线框住的循环构造是图中用虚线框住的循环构造是当型循环，还是直到型循环？当型循环，还是直到型循环？循环构造循环构造直到型循直到型循环构造环构造 假假设是是,那那么么m为所求所求; 备用，参考上上用，参考上上节课例例题2例例6:画出用二分画出用二分法求方程法求方程x2-2=0的近似根的近似根(准确度准确度为0.005)的程的程序框序框图。算法分析算法分析:第一步第一步:令令f(x)=x2-2.由于由于f(1)0,所以所以
21、设a=1,b=2.第二步第二步:令令判判别f(m)能否能否为0.假设否假设否,那么继续判别那么继续判别f(a) (m)大于大于0还是小还是小于于0.第三步第三步:假设假设f(a) (m)0,那么令那么令a=m;否那么否那么,令令b=m. 第四步第四步:判判别|a-b|0?程序框程序框图开开场f(x)=x2-2输入误差输入误差和初值和初值a,bf(m)=0?a=m否否b=m|a-b|0?程序框图程序框图开场开场f(x)=x2-2输入误差输入误差和初值和初值a,ba=m否否b=m|a-b|100?是是输出输出S终了终了否否直到直到型循型循环构环构造造开场开场i=1S=0i100?是是S=S+i2i
22、=i+1否否输出输出S终了终了当型循环当型循环构造构造P20页页A组组T2.是是(P20页页A组组T3)程序框图程序框图:开场开场输入输入xx3?否否终了终了输入输入yy=5y=1.2x+1.4 设计一个求解二元一次方程组设计一个求解二元一次方程组其中其中 的算法的算法,并画出程序框图并画出程序框图.算法分析算法分析:第一步第一步:判判别a1能否等于能否等于0. 假假设a10,由由+u,得得 (b2+b1u)y=c2+c1u;假假设a1=0,执行第三步行第三步.第二步第二步:解解,得得输出出y.第三步第三步:将将y值代入代入,得得输出出x.P20B组组T1开开场程序框程序框图输入输入a1,b1
23、,c1,a2,b2,c2a10?是是u=-a2/a1b=b2+b1uc=c2+c1uy=c/bx=(c2-b2y)/a2否否y=c1/b1输出输出x,y终了终了 .某高中男子体育小组的某高中男子体育小组的50m跑成果跑成果(单位单位:s)为为: 6.4, 6.5, 7.0, 6.8, 7.1, 7.3, 6.9, 7.4, 7.5.设计一个算法设计一个算法,从这些成果中搜出小于从这些成果中搜出小于6.8s的成果的成果.算法分析算法分析:第一步第一步:把把计数数变量量n的初的初值设为1.第二步第二步:输入一个成果入一个成果r,判判别r与与6.8的大小的大小.假假设r6.8,那么那么执行下一步行下
24、一步;假假设r9,那么那么终了了.P20BT2开开场n=1程序框程序框图输入输入rr6.8?是是n=n+1n9?是是否否输出输出r否否终了了直到型循直到型循环构造环构造(P50页页A组组T1(1)开场开场程序框图程序框图x0?是是y=0否否0x1?是是y=1否否y=x输出输出y终了终了输入输入x(P50页页A组组T1(2)开场开场程序框图程序框图x3?是是终了终了输入输入yy=0.2y=0.1t注：注：t表示不大于表示不大于t的最大的最大整数。例如：整数。例如：3=3，3.5=3，4.2=4。开场开场i=1S=0S=S+i=i+1in?是是输出输出S终了终了否否直到直到型循型循环构环构造造开场
25、开场i=1S=0in?是是S=S+i=i+1否否输出输出S终了终了当型循环当型循环构造构造P50页页A组组T4.输入输入n输入输入n(P51页页B组组T3)设计一个算法设计一个算法,判别一个正的判别一个正的n(n2)位数是不是回文数位数是不是回文数,用自然言语描画算用自然言语描画算法步骤法步骤.算法步算法步骤:第一步第一步:输入一个正整数入一个正整数x和它的位数和它的位数.第二步第二步:判判别n是不是偶数是不是偶数,假假设是偶数是偶数,令令m=n/2;假假设是奇数是奇数,令令m=(n-1)/2.第三步第三步:当当i从从1取到取到m值时,依次判依次判别x的第的第i位位与第与第(n+1-i)位上的数字是不是相等位上的数字是不是相等,假假设都都相等相等,那么那么x是回文数是回文数;否那么否那么,x不是回文数不是回文数.回文数是指从左到右读与从回文数是指从左到右读与从右到左读都是一样的正整数右到左读都是一样的正整数,如如121，676，94249，234432等。等。开场开场程序框图程序框图输入正整数输入正整数x和它的位数和它的位数nn是偶数？是偶数？是是m=n/2否否m=(n-1)/2第第i位与第位与第(n+1-i)(i=1,2,m)位上的数字相等位上的数字相等?是是x是回文数是回文数否否x不是回文数不是回文数终了终了
