程序设计公开课-最大公约数

〖课　　题〗最大公约数求解〖目标〗1．知识目标（1）掌握最大公约数的编程方法（2）掌握实现算法的基本方法2．能力目标逐步培养学生的编程能力、运用知识能力、解决问题的能力。3．情感目标通过本节课的内容渗透，培养学生乐于探索编程的不同方法，具有一定的探索精神和创新意识，自主性学习、乐于合作交流、积极主动的学习态度。〖重点难点〗不同算法的实现〖课时〗1课时〖教学过程〗一、导入新课数学问题是程序设计中的典型题，是高考中出现频率较高的题型之一。如：从键盘输入一个分数的分子和分母，要求输出其最简分数。6/12→1/2同除以69/21→3/7同除以3[思考]6、3与分子分母的关系？最大公约数本题只需求出分子、分母的最大公约数便可解决问题，两数的最大公约数又如何得到呢？——最大公约数、最小公倍数的不同求解二、理解概念一、知识点1、最大公约数：正整数a，b，能同时整除a、b的最大整数（如：8，12的最大公约数4）2、最小公倍数：正整数a，b，能同时被a、b整除的最小整数（如：8，12的最小公倍数 24）三、分析算法1．辗转相除思路：将a，b中的大数作为被除数，小数作为除数，求余数。若余数不为0，把除数作为大数，余数作为小数，再求余数，直到余数为0，则这时的除数为最大公约数。abcabc81281510512841050840算法：①amodb→c②判断c0，若是，则b→a，c→b，计算amodb→c，返回②，若不是，循环结束执行③③b中为最大公约数程序段：inta,b,c,x,y;scanf(“%d%d”,&a,&b);x=a;y=b;c=a%b;while(c!=0){a=b;b=c;c=a%b;}printf(“最大公约数为%d,最小公倍数为%d”,b,x*y/b);[思考]程序中画线部分的语句的功能是什么？ 2.反复相减思路：比较a、b，若不相等，则将大数-小数→大数中，如此循环，直到a=babab8121510451045算法：①比较a=b，若不等，大数-小数→大数，循环再比，若相等，则循环结束，执行②②a或b为最大公约数。程序段：x=a;y=b;while(a!=b)if(a>b)a=a-b;elseb=b-a;printf(“最大公约数为%d,最小公倍数为%d”,b,x*y/b);3、穷举法思路：从a，b中小的数开始，依次递减到3，2，1为止，用a和b分别除以它，最先能同时整除a和b的那个数就是最大公约数。ab87654ab109876581215101015算法：①比较得出较小的数，放入b中②从bto1，依次除a、b，若能同时整除a/b，则这个数便为两数的最大公约数 程序段：inta,b,c,x,y;scanf(“%d%d”,&a,&b);if(a=1;i--)if(a%i==0&&b%i==0)break;printf(“最大公约数为%d,最小公倍数为%d”,i,a*b/i);四、拓展提高最大公约数的求解在历届的高考题中出现较多，下面我们用它来解决编程输出最简分数的问题。inta,b,c,x,y;x=a:y=b;printf(“原分数%d/%d”;a,b);c=a&bwhile(c!=0){a=b;b=c;c=a%b;}printf(“最简分数为%d”,x/b,y/b);五、巩固练习1、已知5个正整数，编程输出它们的最大公约数。2、…… x=a；y=b；do{c=a%b；a=b；b=c；}while(c!=0)’printf(“最大公约数为%d”,);六、小结提升最大公约数的求解共有三种算法：辗转相除、连续相减、穷举求因子七、作业布置思考题：如何不通过最大公约数直接求解最小公倍数。八、板书设计（见附录）九、教学反思在本课教学中，我从实际应用入手，引导学生由数学问题向C语言问题转换，提高学生的思维能力。在课堂上，我们不能以老师的讲解分析来代替学生的思考领悟，任何时候都不能忘记“学生是学习的主体”，教师不能越俎代庖。所以整个教学过程应该是教师—学生—问题三者之间的交融和对话，要加强师生互动，生生互动。在教学设计上，我以问题导入—分析概念—实现算法—巩固提升这样循序渐进的方式引导学生，培养他们的思维能力。 ①A%B→C②判断C!=0，若是，则B→A，C→B，计算A%B→C，返回②，若不是，循环结束执行③③B中为最大公约数[附]板书设计一、知识点1、最大公约数：能同时整除A、B的最大整数2、最小公倍数：能同时被A、B整除的最小整数二、解决方法1、辗转相除2、反复相减3、穷举求因子从键盘输入一个分数的分子和分母，要求输出其最简分数。从键盘输入两个正整数，编程求出两数的最大公约数与最小公倍数。ABAB81215104545ABCABC81281510512841050840①比较A!=B，若否，大数-小数→大数，返回①，若是，则循环结束,执行②②A或B为最大公约数。