1、121.1.1 算法的概念算法的概念3问题的提出问题的提出 有一个农夫带一条狼狗、一只羊和有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小，狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如只够农夫带一样东西过河。问农夫该如何解此难题？何解此难题？方法和过程方法和过程：1、带羊到对岸，返回；带羊到对岸，返回；2、带菜到对岸，并把羊带回；带菜到对岸，并把羊带回；3、带狼狗到对岸，返回；带狼狗到对岸，返回；4、带羊到对岸。带羊到对岸。4问题问题请你写出解二元一次方程组的详细求解过请你写出解二元一
2、次方程组的详细求解过程程.2121xyxy 第一步第一步:-2得得:5y=3 第二步第二步:解解得得:35y 第三步第三步:将将 代入代入,解得解得 .35y 15x 对于一般的二元一次方程组对于一般的二元一次方程组其中其中 也可以按照上述步骤求解也可以按照上述步骤求解.111222a x b yca x b yc1 22 10aba b5这些步骤就构成了解二元一次方程组的这些步骤就构成了解二元一次方程组的算法算法,我们可以根据这一算法编制计算机程序我们可以根据这一算法编制计算机程序,让计算机来解二元一次方程组让计算机来解二元一次方程组.算法的概念与特征算法的概念与特征算法算法(algorit
3、hm)这个词出现于这个词出现于12世纪世纪,指的是用阿拉伯数字进行算术运算的过程指的是用阿拉伯数字进行算术运算的过程.在数学上在数学上,现代意义上的现代意义上的“算法算法”通常是指可通常是指可以用计算机来解决的某一类问题的以用计算机来解决的某一类问题的程序或步程序或步骤骤,6算法的概念算法的概念:算法是指解决给定问题的算法是指解决给定问题的有穷有穷操作步骤操作步骤的描述，简单的说，算法的描述，简单的说，算法就是解决问题的步骤和方法。就是解决问题的步骤和方法。7说明说明:(1)事实上算法并没有精确化的定义事实上算法并没有精确化的定义.(2)算法虽然没有一个明确的定义算法虽然没有一个明确的定义,但
4、其特点但其特点是鲜明的是鲜明的,不仅要注意不仅要注意算法的程序性、有限算法的程序性、有限性、构造性、精确性的特点，还应该充分性、构造性、精确性的特点，还应该充分理解算法问题的指向性，即算法往往指向理解算法问题的指向性，即算法往往指向解决某一类问题，泛泛地谈算法是没有意解决某一类问题，泛泛地谈算法是没有意义的。义的。8算法学的发展 随着科学技术的日新月异,算法学也得到了前所未有的发展,现在已经发展到了各个领域.有遗传算法遗传算法,排序算法排序算法,加密算法加密算法,蚁蚁群算法群算法等,与生物学,计算机科学等有着很广泛的联系,尤其是在现在的航空航天中,更是有着更广泛的应用.很多复杂的运算都是借助计
5、算机和算法来完成的,在高端科学技术中有着很重要的地位.9王小云：王小云：1966年生，年生，1983年年至至1993年就读于山年就读于山东大学数学系，先后东大学数学系，先后获得学士、硕士和博获得学士、硕士和博士学位，士学位，1993年毕年毕业后留校任教。业后留校任教。2005年月受聘为年月受聘为清华大学高等研究中清华大学高等研究中心杨振宁讲座教心杨振宁讲座教授，现为清华大授，现为清华大学长江学者特聘教学长江学者特聘教授授 10王小云破译了美国政府使用的密码王小云破译了美国政府使用的密码密码算法，运算量达到的次方。即使采密码算法，运算量达到的次方。即使采用现在最快的巨型计算机，也要运算万年以上才
6、用现在最快的巨型计算机，也要运算万年以上才能破解。但王小云和她的研究小组用普通的个人电脑，能破解。但王小云和她的研究小组用普通的个人电脑，几分钟内就可以找到有效结果。几分钟内就可以找到有效结果。密码算法，由美国专门制定密码算法的密码算法，由美国专门制定密码算法的标准机构美国国家标准技术研究院与美国国家安标准机构美国国家标准技术研究院与美国国家安全局设计，早在年就被推荐给美国政府和金融全局设计，早在年就被推荐给美国政府和金融系统采用，是美国政府目前应用最广泛的密码算法。系统采用，是美国政府目前应用最广泛的密码算法。2005年初，王小云和她的研究小组宣布，成功破解年初，王小云和她的研究小组宣布，成
7、功破解邮箱密码。邮箱密码。崩溃！密码学的危机崩溃！密码学的危机，美国，美国新科学家新科学家杂志用这样富有惊耸的标题概括王小云里程碑式的成就。杂志用这样富有惊耸的标题概括王小云里程碑式的成就。因为王小云的出现，美国国家标准与技术研究院宣布，因为王小云的出现，美国国家标准与技术研究院宣布，美国政府年内将不再使用，取而代之的是美国政府年内将不再使用，取而代之的是更为先进的新算法，微软、和等知名更为先进的新算法，微软、和等知名公司也纷纷发表各自的应对之策。公司也纷纷发表各自的应对之策。11 例例1 设计一算法：设计一算法：输入圆输入圆的半径的半径,输出圆的面积输出圆的面积算法分析算法分析：第一步：第一
8、步：输入圆的半径输入圆的半径第二步：第二步：利用公式利用公式“圆的面积圆的面积=圆周率圆周率（半径的平方）（半径的平方）”计算圆的计算圆的面积；面积；第三步：第三步：输出圆的面积。输出圆的面积。说明说明:用语言描述一个算法用语言描述一个算法,最便捷的方式就是按最便捷的方式就是按解决问题的步骤进行描述解决问题的步骤进行描述.每一步做一件事情每一步做一件事情.12 例例2 2 设计房租收费的算法设计房租收费的算法,其要求是其要求是:住房面积住房面积8080平方米以内平方米以内,每平方米收费每平方米收费3 3元元,住房面积超过住房面积超过8080平方米时平方米时,超过部分超过部分,每平方米收费每平方
9、米收费5 5元元.输入住房面积数输入住房面积数,输出输出应付的房租应付的房租.算法分析：算法分析：第一步：第一步：输入住房面积输入住房面积S第二步：第二步：根据面积选择计费方式：如果根据面积选择计费方式：如果S小于或等于小于或等于80，则租金为，则租金为M=S3，否则，否则为为M=240+(S-80)5第三步：第三步：输出房租输出房租M的值。的值。13 若是若是,则则m为所求为所求;例例3:用二分法设计一个求方程用二分法设计一个求方程x2-2=0的近似根的近似根的算法的算法.精确度为精确度为0.005算法分析算法分析:第一步第一步:令令f(x)=x2-2.因为因为f(1)0,所以设所以设a=1
10、,b=2.第二步第二步:令令,2abm判断判断f(m)是否为是否为0.若否若否,则继续判断则继续判断f(a)f(m)大于大于0还是小于还是小于0.第三步第三步:若若f(a)(m)0,则令则令a=m;否则否则,令令b=m.第四步第四步:判断判断|a-b|7时时)20解解:y与与x之间的函数关系为之间的函数关系为:1.2,1.94.9xyx(当当0 x7时时)(当当x7时时)求该函数值的算法分析求该函数值的算法分析:第一步第一步:输入每月用水量输入每月用水量x;第二步第二步:判断判断x是否不超过是否不超过7.若是若是,则则y=1.2x;若否若否,则则y=1.9x-4.9.第三步第三步:输出应交纳的水费输出应交纳的水费y.21作业作业:课本课本P6页页T2(只需用自然语言写出算法步骤只需用自然语言写出算法步骤)22再再 见见
