算法及算法的描述主讲人:林鸿瑶单位:汕头市澄海华侨中学1、算法的概念•一个农夫带着一只狼,一只羊和一筐菜,欲从河的左岸坐船到右岸,由于船太小,农夫每次只能带一样东西过河,并且没有农夫看管的话,狼会吃掉羊,羊会吃菜。设计一个方案,使农夫可以无损失的过河,并把详细步骤写出来。AABB羊狼菜怎么办呢1、算法的概念•第一步:人和羊过河,人返回,留下羊;•第二步:人和狼过河,人和羊返回,留下狼;•第三步:人和菜过河,人返回,留下菜;•第四步:人和羊过河。第二步:人和菜过河,人和羊返回,留下菜第三步:人和狼过河,人返回,留下狼1、算法的概念算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。欧几里得是古代最有名望的学者之一,古希腊数学家,几何学的鼻祖。公元前300年左右,他所著《几何原本》十三卷,是世界上最早公理化的数学著作。在《几何原本》中,他充分总结了前任的生产经验和研究成果,从公立和公设出发,运用演绎法,经过逻辑推理和数学运算,创立了著名的欧几里得几何(简称欧氏几何)。在《几何原本》中,欧几里得阐述了关于求两个整数的最大公约数的过程,这就是注明的欧几里得算法——辗转相除法,其具体过程如下:设给定的两个正整数为m和n,求它们的最大公约数的步骤为:①以m除以n,令所得的余数为r。②若r=0,则输出结果n,算法结束;否则,继续步骤③。③令m=n,n=r,并返回步骤①继续进行。•实践设给定的两个正整数m=112和n=64,利用辗转相除法,求它们的最大公约数。1、算法的概念算法如下:1、112除以64,余数为48;2、64除以48,余数为16;3、48除以16,余数为0。答:112和64的最大公约数为16。1、算法的特征一个算法应该具有以下五个方面的重要特征:(1)输入。一个算法有零个或多个输入,以刻画运算对象的初始情况。例如,在欧几里得算法中,有两个输入,即m和n(2)确定性。算法的每一步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定,不能有歧义性。例如,在欧几里得算法中,步骤①中明确的规定“以m除以n”,而不能有类似“以m除以n或n除以m”这类有两种可能做法的规定。(3)有穷性。一个算法在执行有穷步之后必须结束。也就是说,一个算法,它所包含的计算步骤是有限的。例如,在欧几里得算法中,由于m和n均为正整数,在步骤①之后,r必小于n,若r‡0,下一次进行步骤①时,n的值已经减小,而正整数的递降序列最后必然要终止。因此,无论给定m和n的原始值有多大,步骤①的执行都是有穷次。(4)输出。算法有一个或多个的输出,即与输入有某个特定关系的量,简单地说就是算法的最终结果。例如,在欧几里得算法中只有一个输出,即步骤②中的n。(5)能行性。算法中有待执行的运算和操作必须是相当基本的,换言之,它们都是能够精确地进行的,算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作,并最终得出正确的结果。1、算法的特征2、算法的描述(1)自然语言;设给定的两个正整数为m和n,求它们的最大公约数的步骤为:①以m除以n,令所得的余数为r。②若r=0,则输出结果n,算法结束;否则,继续步骤③。③令m=n,n=r,并返回步骤①继续进行。(2)流程图流程图的基本图形及功能开始输出n的值输入正整数m和nr=m除以n的余数r=0结束m=n,n=r是否实践:用流程图描述算法•设计一个算法,求实数a的绝对值开始输入aa>0输出a的值结束输出-a的值否是INPUTm,nr=mmodnDOWHILEr<>Om=nn=rr=mmodnLOOPPRINTn(3)伪代码;伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。