《-算法与程序框图-ppt》由会员分享，可在线阅读，更多相关《-算法与程序框图-ppt（22页珍藏版）》请在金锄头文库上搜索。
1、算法与程序框图,1.1.1 算法的概念,问题的提出,有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？,方法和过程：,1、带羊到对岸，返回；,2、带菜到对岸，并把羊带回；,3、带狼狗到对岸，返回；,4、带羊到对岸。,第一步:-2得: 5y=3 ,第二步: 解得:,第三步: 将 代入,解得 .,对于一般的二元一次方程组 其中 也可以按照上述步骤求解.,这些步骤就构成了解二元一次方程组的算法,我们可以根据这一算法编制计算机程序,让计算机来解二元一次方程组.,算法的概念与特征,算法(algorithm)这
2、个词出现于12世纪,指的是用阿拉伯数字进行算术运算的过程.,在数学上,现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成.,算法的概念:,算法是指解决给定问题的有穷操作步骤的描述，简单的说，算法就是解决问题的步骤和方法。,说明: (1)事实上算法并没有精确化的定义. (2)算法虽然没有一个明确的定义,但其特点是鲜明的,不仅要注意算法的程序性、有限性、构造性、精确性的特点，还应该充分理解算法问题的指向性，即算法往往指向解决某一类问题，泛泛地谈算法是没有意义的。,算法学的发展,随着科学技术的日新月异,算法学也得到了前所
3、未有的发展,现在已经发展到了各个领域.有遗传算法,排序算法,加密算法,蚁群算法等,与生物学,计算机科学等有着很广泛的联系,尤其是在现在的航空航天中,更是有着更广泛的应用. 很多复杂的运算都是借助计算机和算法来完成的,在高端科学技术中有着很重要的地位.,王小云： 1966年生，1983年至1993年就读于山东大学数学系，先后获得学士、硕士和博士学位，1993年毕业后留校任教。2005年月受聘为清华大学高等研究中心杨振宁讲座教授，现为清华大学特聘教授,王小云破译了美国政府使用的密码 密码算法，运算量达到的次方。即使采用现在最快的巨型计算机，也要运算万年以上才能破解。但王小云和她的研究小组用普通的个
4、人电脑，几分钟内就可以找到有效结果。 密码算法，由美国专门制定密码算法的标准机构美国国家标准技术研究院与美国国家安全局设计，早在年就被推荐给美国政府和金融系统采用，是美国政府目前应用最广泛的密码算法。 2005年初，王小云和她的研究小组宣布，成功破解邮箱密码。崩溃！密码学的危机，美国新科学家杂志用这样富有惊耸的标题概括王小云里程碑式的成就。因为王小云的出现，美国国家标准与技术研究院宣布，美国政府年内将不再使用，取而代之的是更为先进的新算法，微软、和等知名公司也纷纷发表各自的应对之策。,例1 设计一算法：输入圆的半径,输出圆的面积,算法分析：,第一步：输入圆的半径,第二步：利用公式“圆的面积=
5、圆周率（半径的平方）”计算圆的面积；,第三步：输出圆的面积。,说明:用语言描述一个算法,最便捷的方式就是按解决问题的步骤进行描述.每一步做一件事情.,例2 设计房租收费的算法,其要求是:住房面积80平方米以内,每平方米收费3元,住房面积超过80平方米时,超过部分,每平方米收费5元.输入住房面积数,输出应付的房租.,算法分析：,第一步：输入住房面积S,第二步：根据面积选择计费方式：如果S小于或等于80，则租金为M=S3，否则为M=240+(S-80)5,第三步：输出房租M的值。,若是,则m 为所求;,例3:用二分法设计一个求方程x2-2=0的近似根的算法.精确度为0.005,算法分析:,第一步:
6、令f(x)=x2-2.,因为f(1)0,所以设a=1,b=2.,第二步:令,判断f(m)是否为0.,第四步:判断|a-b|0.005,是否成立?若是,则a或b为满足条件的近似根;若否,则返回第二步.,算法的基本特点,1、有穷性,一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束。,2、确定性,算法的计算规则及相应的计算步骤必须是唯一确定的，既不能含糊其词，也不能有二义性。,3、可行性,算法中的每一个步骤都是可以在有限的时间内完成的基本操作，并能得到确定的结果 。,注:与一般的解决问题的过程比较,算法有以下特征: 设计一个具体问题的算法时,与过去熟悉地解数学题的过程有直接的联系,但这个
7、过程必须被分解成若干个明确的步骤,而且这些步骤必须是有效的. 算法要“面面俱到”,不能省略任何一个细小的步骤,只有这样,才能在人设计出算法后,把具体的执行过程交给计算机完成.,计算机解决任何问题都要依赖于算法.只有将解决问题的过程分解为若干个明确的步骤,即算法,并用计算机能够接受的“语言”准确地描述出来,计算机才能够解决问题.,练习一:任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,算法分析:,第一步:输入任意一个正实数r; 第二步:计算以r为半径的圆的面积S=r2; 第三步:输出圆的面积.,练习二:任意给定一个大于1的正整数n,设计一个算法求出n的所有因数.,算法分析:,第一步
8、:依次从2(n-1)为除数去除n,判断余数是否为0,若是,则是n的因数;若不是,则不是n的因数. 第二步:在n的因数中加入1和n; 第三步:输出n的所有因数.,练习三:为了加强居民的节水意识,某市制订了以下生活用水收费标准:每户每月用水未超过7m3时,每立方米收费1.0元,并加收0.2元的城市污水处理费;超过7m3的部分,每立方米收费1.5元,并加收0.4元的城市污水处理费,请你写出某户居民每月应交纳的水费y(元)与用水量x(m3)之间的函数关系,然后设计一个求该函数值的算法.,解:y与x之间的函数关系为:,(当0x7时) (当x7时),解:y与x之间的函数关系为:,(当0x7时) (当x7时),求该函数值的算法分析:,第一步:输入每月用水量x; 第二步:判断x是否不超过7.若是,则y=1.2x;若否,则y=1.9x-4.9. 第三步:输出应交纳的水费y.,作业: 课本P6页T2 (只需用自然语言写出算法步骤),再 见,
