文档介绍：第三章11974年图灵奖获得者DonaldErvinKnuth:、:古希腊著名数学家欧几里得提出求最大公约数的一种算法,即辗转相除法又称欧几里得算法。公元263年:三国魏人刘徽注释《九章算术》中不仅对原书的方法、公式和定理进行一般的解释和推导,而且在其论述中多有创造。如他运用割圆术得出圆周率的近似值3927/1250=。公元825年:波斯数学家al-Khwarizmi撰写了著名的PersianTextbook中概括了进行四则算术运算的法则。Algorithm(算法)一词就来源于这位数学家的名字。3二、算法的定义[]欧几里得算法。输入:正整数m、n输出:m、n的最大公约数①r=mmodn②若r=0,输出最大公约数n③若r≠0,令m=n,n=r,转①:是解决某一特定问题的一组有穷规则的集合。算法:对特定问题求解步骤的一种描述,是由若干条指令组成的有穷集合。4三、算法的特征确定性:算法中每一个步骤都是清晰的、无歧义有穷性:算法必须在有限步内终止输入:有零个或多个输入,作为初始状态输出:有一个或多个输出,作为计算结果可行性::正确性:在合理输入下能在有限时间内得出正确结果可读性:算法主要是为了人的阅读与交流,其次执行健壮性:算法应具备检查错误和对错误进行处理能力效率:、,如汉语、英语等优点:通俗易懂,即使没有学过算法也能看懂算法执行缺点:不够严谨,容易出现歧义和错误[例题]利用自然语言描述欧几里得算法。①输入m、n②判断n是否为0,如果不为0,转步骤③,否则转④③m对n取余,其结果赋值给r,n赋给m,r赋给n,转②④输出m,算法结束7二、流程图常用来描述算法的图形工具有:流程图或程序框图、N-S图和PAD图。优点:直观形象,简洁明了。缺点:画起来费事,不易修改。:8[例题]利用流程图描述欧几里得算法。、,但是它不是C、C++、Java等通常使用的程序设计语言,而是算法步骤的描述。伪代码介于自然语言和程序设计语言之间。伪代码的具体表示:赋值语言:←分支语句:if…then…[else]循环语句:while,for,repeatuntil转向语句:goto输出语句:return调用:注释://…10