程序设计公开课最大公约数.docVIP

〖课　　题〗最大公约数求解 〖目 标〗 1．知识目标 （1）掌握最大公约数的编程方法 （2）掌握实现算法的基本方法 2．能力目标 逐步培养学生的编程能力、运用知识能力、解决问题的能力。 3．情感目标 通过本节课的内容渗透，培养学生乐于探索编程的不同方法，具有一定的探索精神和创新意识，自主性学习、乐于合作交流、积极主动的学习态度。 〖重点难点〗不同算法的实现 〖课 时〗1课时 〖教学过程〗 一、导入新课 过渡 数学问题是程序设计中的典型题，是高考中出现频率较高的题型之一。 如：从键盘输入一个分数的分子和分母，要求输出其最简分数。 6/12→1/2 同除以6 9/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，则这时的除数为最大公约数。 a b c a b c 8 12 8 15 10 5 12 8 4 10 5 0 8 4 0 算法：① a mod b→c ② 判断c0，若是，则b→a，c→b，计算a mod b→c，返回②， 若不是，循环结束执行③ ③ b中为最大公约数 程序段： int a,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=b a b a b 8 12 15 10 4 5 10 4 5 算法：① 比较a=b，若不等，大数-小数→大数，循环再比， 若相等，则循环结束，执行② ② a或b为最大公约数。 程序段： x=a;y=b; while(a!=b) if(ab)a=a-b; else b=b-a; printf(“最大公约数为%d,最小公倍数为%d”,b,x*y/b); 3、穷举法 思路：从a，b中小的数开始，依次递减到3，2，1为止，用a和b分别除以它，最先能同时整除a和b的那个数就是最大公约数。 a b 8 7 6 5 4 a b 10 9 8 7 6 5 8 12 15 10 10 15 算法：①比较得出较小的数，放入b中 ②从b to 1，依次除a、b，若能同时整除a/b，则这个数便为两数的最大公约数 程序段： int a,b,c,x,y; scanf(“%d%d”,a,b); if(ab) {a=a+b;b=a-b;a=a-b;} for(i=b;i=1;i--) if(a%i==0b%i==0) break; printf(“最大公约数为%d,最小公倍数为%d”,i,a*b/i); 四、拓展提高 过渡最大公约数的求解在历届的高考题中出现较多，下面我们用它来解决编程输出最简分数的问题。 int a,b,c,x,y; x=