1、2.12.1算法的概念及描述算法的概念及描述农夫如何安全带这三样东西过河？农夫如何安全带这三样东西过河？一个农夫带着一条狼、一头山羊和一篮蔬菜要过河，但只有一条船。乘船时，农夫在场的时候，这三样东西相安无事。一旦农夫不在，狼会吃羊，羊会吃菜。船很小，只够农夫带一样东西过河。农夫该如何解此难题？方法一：方法一：1、农夫带羊过河,农夫回来；2、把狼带过河,把羊带回来；3、带蔬菜过河,农夫回来；4、把羊带过河。方法二：方法二：1、农夫带羊过河，农夫回来；2、带蔬菜过河，把羊带回来；3、把狼带过河，农夫回来；4、把羊带过河。农夫如何安全带这三样东西过河？农夫如何安全带这三样东西过河？2.1.1 2.1
2、.1 算法的概念算法的概念 广义：广义：“算法算法”指的是解决问题或完成任务的指的是解决问题或完成任务的一系列步骤。一系列步骤。不仅仅指计算任务（算术），也可以是社会生活中各种事务的处理。计算机科学计算机科学领域：领域：“算法算法”指的是用指的是用计算机解决问题的步骤，是计算机解决问题的步骤，是为了为了解决问题解决问题而需要让计算机而需要让计算机有序执行的、无歧义的、有限步骤的集合有序执行的、无歧义的、有限步骤的集合。不仅包含了数值计算，还包含了非数值计算的数据处理。1.1.算法的定义算法的定义 为了让计算机理解算法中的步骤，用计算机能理解的语言来描述算法并将其输入到计算机中，这个过程就称为计
3、算机程序设计。否否是是高一新生报到流程高一新生报到流程例：用求根公式求解一元二次方程的算法例：用求根公式求解一元二次方程的算法 一元二次方程的解的意义：能使一元二次方程左右两边相等的未知数的值称为一元二次方程的解。利用一元二次方程根的判别式（）可以判断方程的根的情况。acb42过程方法具体描述：过程方法具体描述：ax+bx+c=0ax+bx+c=0（1）输入一般形式下的二次项系数a，一次项系数b，常数项c；（2）计算判别式 的值；（3）若 ，则计算 ，输出字符串“方程有实数解”，并输出x的值；否则，输出字符串“方程无实数解”。acb420abx2特征特征含义含义有穷性有穷性一个算法的处理步骤必
4、须是有限的可行性可行性一个算法中的每一步操作与要求都应该是算法执行者（人或机器）可以实施的，同时在现实环境中能做到并且能在有限时间内完成确定性确定性算法中对于每个步骤的执行描述必须是明确的0 0个个或多个输入或多个输入数据可从外部输入，也可包含在算法中（可以没有输入）1 1个个或多个输出或多个输出算法必须包含至少一个输出，以告诉外界问题求解的结果（必须有输出）2.2.算法的特征算法的特征不是算法，不满足算法的可行性。是算法。思考：思考：求根公式求解一元二次方程的算法求根公式求解一元二次方程的算法：（1）输入一般形式下的二次项系数a，一次项系数b，常数项c（2）计算判别式 的值（3）若 ，则计算
5、 ，输出字符串“方程有实数解”，并输出x的值；否则，输出字符串“方程无实数解”acb420abx2要素要素含义含义数据数据明确参与运算的明确参与运算的初始数据初始数据、运算时产生的、运算时产生的中间数据中间数据以以及代表问题解决的及代表问题解决的结果数据结果数据运算运算明确每一步的明确每一步的运算是什么运算是什么、对、对哪些数据哪些数据进行运算等进行运算等控制转移控制转移有时需要有时需要根据数据或运算结果的特点进行不同的处理根据数据或运算结果的特点进行不同的处理，这时就需要运用控制转移来执行不同的操作这时就需要运用控制转移来执行不同的操作3.3.算法的要素算法的要素a,b,c,x加减乘除，加减
6、乘除，开根，平方开根，平方若若.,则则.;否则否则.2.1.2 2.1.2 算法的描述算法的描述 设计出一个解决问题的算法，也需要用能被算法执行者理解的形式加以设计出一个解决问题的算法，也需要用能被算法执行者理解的形式加以呈现，才能被算法执行者（人或计算机）理解并执行。呈现，才能被算法执行者（人或计算机）理解并执行。算法的这种呈现算法的这种呈现就称就称为为算法的描述算法的描述。常见的算法描述方式有常见的算法描述方式有自然语言、流程图、伪代码、计算机程序设计语言自然语言、流程图、伪代码、计算机程序设计语言等。等。2.1.2 2.1.2 算法的描述算法的描述 自然语言是人们在自然语言是人们在日常生
7、活中交流使用的语言日常生活中交流使用的语言，如汉语、英语、德语、，如汉语、英语、德语、日语等。用自然语言描述算法通俗易懂，且不需要进行专门的学习和训练。日语等。用自然语言描述算法通俗易懂，且不需要进行专门的学习和训练。阅读：停车场车位探测中的算法，尝试用自然语言描述该算法。阅读：停车场车位探测中的算法，尝试用自然语言描述该算法。自然语言描述如下：（1）输入变量变量flag的值。（2）若flag的值为1,则设置指示灯为绿色，输出“空车位”；否则，设置指示灯为红色，输出“非空车位。1.1.自然语言描述算法自然语言描述算法 流程图用一些流程图用一些图形符号图形符号表示表示规定的操作规定的操作，并用，
8、并用带箭头的流程线带箭头的流程线连接这些图连接这些图形符号，表示形符号，表示操作进行方向操作进行方向。2.2.流程图描述算法流程图描述算法自然语言描述如下：（1）输入变量变量flag的值。（2）若flag的值为1,则设置指示灯为绿色，输出“空车位”；否则，设置指示灯为红色，输出“非空车位。2.2.流程图描述算法流程图描述算法图形图形名称名称功能功能开始/结束框表示算法的开始或结束输入/输出框表示算法中数据的输入或输出处理框表示算法中数据的运算处理判断框表示算法中的条件判断流程线表示算法中的流向连接框表示算法中的转接尝试画出求根公式的流程图尝试画出求根公式的流程图2.2.流程图描述算法流程图描述
9、算法开始开始输入二项系数输入二项系数a，一项系数一项系数b，常数，常数c计算判别式计算判别式acb420？abx2计算计算输出方程输出方程无实数根无实数根输出方程有实数根输出方程有实数根输出输出x x结束结束否是 “N-S图”是由美国学者纳西（Nassi）和斯奈德曼（Shneiderman）提出的一种在流程图中完全去掉流程线，全部算法写在一个矩形框内的算法描述方式。相比于原来的流程图描述，结构性显得更好，也更有助于高效地编写程序。前面车位探测中的算法，可用N-S图表示成如下形式。输入输入flagflag的值的值指示灯绿色指示灯红色输出“空车位”输出“非空车位”flag=1?是否拓展链接拓展链接
10、 伪代码指的是一种伪代码指的是一种比较直观简洁的、符号接近计算机程序代码的算法描述方式比较直观简洁的、符号接近计算机程序代码的算法描述方式，其风格很像计算机程序设计语言，但又其风格很像计算机程序设计语言，但又不是真正的可以被计算机理解的代码。不是真正的可以被计算机理解的代码。求根公式算法求根公式算法3.3.伪代码描述算法伪代码描述算法格式格式1:1:If 条件 then （语句序列1)Else （语句序列2)格式格式2:2:If 条件 then （语句序列1)条件判断语句条件判断语句 格式：格式：while 条件 （循环体）循环语句循环语句车位探测算法车位探测算法flag车位探测结果；If f
11、lag=1 then (指示灯绿色 输出“空车位”）Else (指示灯红色 输出“非空车位”)为了让计算机为了让计算机真正解决问题真正解决问题，需要将算法用某种，需要将算法用某种计算机程序设计语言来描述计算机程序设计语言来描述，这个过程称为这个过程称为程序编写（或称代码编写）程序编写（或称代码编写）。4.4.计算机程序语言描述算法计算机程序语言描述算法车位探测算法车位探测算法flag=int(input(“输入车位状态值：”）if flag=1:print(“绿色”)print(“空车位”)else:print(“红色”)print(“非空车位”)求根公式算法求根公式算法a=int(input
12、(“输入二次项系数：”）b=int(input(“输入一次项系数：”）c=int(input(“输入常数项系数：”）ref=b*2-4*a*cif ref=0:x1=(-b)+math.sqrt(ref)/(2*a)x2=(-b)-math.sqrt(ref)/(2*a)printf(“方程有实数解”)printf(“x1=”,x1)printf(“x2=”,x2)else:printf(“方程无实数解”)求两个正整数的最大公约数问题求两个正整数的最大公约数问题(1)输入两个正整数m和n。(2)若mn,则交换m和n的值。(3)以m除以n，相除得到的余数为r。(4)若r=0，则输出n的值，算法结
13、束；否则，执行步骤(5)。(5)令m=n，n=r，返回步骤(3)继续执行。辗转相除法辗转相除法更相减损术更相减损术(1)输入两个正整数m和n。(2)判断两个数是否都是偶数,若是，则用2约简，直至出现奇数。(3)以较大的数(被减数)减去较小的数(减数)，得到差。(4)若减数与差相等，则第二步约掉的若干个2与差的乘积就是最大公约数，算法结束；否则，执行步骤(5)。(5)将减数与差作为比较的数，返回步骤(3)继续执行。体验算法多样性体验算法多样性1.算法的概念算法的概念解决问题或完成任务的一系列步骤；为了解决问题而需要让计算机有序执行的、无歧义的、有限步骤的集合2.算法的特征算法的特征有穷性；可行性；确定性；0个或多个输入；1个或多个输出3.算法的要素算法的要素数据，运算，控制转移4.算法的描述算法的描述自然语言、流程图、伪代码、计算机程序设计语言小结小结作业本作业本P29-32P29-32作 业作 业
