算法和算法的描述(精品).ppt

《算法和算法的描述(精品).ppt》由会员分享，可在线阅读，更多相关《算法和算法的描述(精品).ppt（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二节第二节 算法和算法的描算法和算法的描述述授课人：王乐授课人：王乐 第一章第一章揭开计算机解决问题的神秘面纱揭开计算机解决问题的神秘面纱1 1、请计算出、请计算出100100和和2020的最大公约数。的最大公约数。202 2、请求出给定的两个正整数、请求出给定的两个正整数m m和和n n的最大的最大 公约数。公约数。被称为被称为“数学之父数学之父”，他最著名的著作，他最著名的著作几何原本几何原本是欧洲数学是欧洲数学的基础，发展欧几里德几何，被广泛的认为是历史上最成功的教的基础，发展欧几里德几何，被广泛的认为是历史上最成功的教科书。科书。欧欧几几里里得得欧欧几里德算法的步几里德算法的步骤为：

2、步骤步骤1 1：以以m除以除以n，令所得的余数为，令所得的余数为r步骤步骤2 2：若若r=0，则输出结果，则输出结果n，算法，算法结束；束；否则，继续步骤（否则，继续步骤（3 3）步骤步骤3 3：令令m=n，n=r，并返回步骤，并返回步骤（1）继续进行）继续进行欧欧几里德算法几里德算法辗转相除法相除法一、概念一、概念 算法是在有限步骤内求解某算法是在有限步骤内求解某一问题所使用的一组定义明确的一问题所使用的一组定义明确的规则。规则。二、特征二、特征输输入入确确定定性性有有穷穷性性输输出出能能行行性性算法算法r=0输入正整入正整数数m和和n令令m除以除以n的余数为的余数为r输出出n的的值是是否否

3、结束结束开始开始m=n,n=r用用流流程程图图描描述述欧欧几几里里得得算算法法 图形图形 名称名称功能功能开始/结束框算法的开始或结束输入/输出框变量的输入或输出处理框变量的计算与赋值判断框算法中的条件判断流程线算法中的流向Input m,nr=m mod nDo while r0m=n,n=rr=m mod nLoop Print n用用伪伪代代码码描描述述欧欧几几里里得得算算法法巩固练习巩固练习鸡兔同笼问题。一个笼子里有鸡和兔，现在只知道里面一共有鸡兔同笼问题。一个笼子里有鸡和兔，现在只知道里面一共有35个头，个头，94只脚，鸡和兔各有多少只？试设计一个求解的算法。只脚，鸡和兔各有多少只？

4、试设计一个求解的算法。设计算法：设计算法：（1 1）输入）输入a a和和b b的值的值（2 2）求）求x=2a-b/2x=2a-b/2（3 3）求）求y=b/2-ay=b/2-a（4 4）输出）输出x x、y y的值的值（5 5）结束）结束鸡和兔一共头数为鸡和兔一共头数为a，脚数为，脚数为b。解：解：设鸡的数量为设鸡的数量为x,兔的数量为兔的数量为y；x+yx+y=a=a2x+4y=b2x+4y=bx=2a-b/2x=2a-b/2y=b/2-ay=b/2-a带入带入a a和和b b的值，得的值，得x=23x=23，y=12y=12。答：鸡有答：鸡有2323只，兔有只，兔有1212只。只。小结：小结：概念概念 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则特征特征输入确定性 有穷性输出能行性描述方法描述方法自然语言流程图伪代码作业作业求求200-500能被能被5整除的所有正整数。整除的所有正整数。再见再见