辗转相除法原理

1

算法案例——辗转相除法

育才中学潘敏

一、教材分析

选自苏教版普通高中课程标准实验教科书必修3第一章第4节。

1、地位作用：

与传统教学内容相比，《算法初步》为新增内容，算法是计算机科学的重要基础，从日

常生活的电子邮件发送到繁忙的交通管理，从与人们生产、生活息息相关的天气预报到没有

硝烟的战争模拟等等都离不开计算机算法。算法思想已经渗透到社会的方方面面，算法思想

也逐渐成为每个现代人应具有的数学素养。

在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量

的算法思想，如四则运算的过程，求解方程的步骤，以及将要学习的数列求和等等，完成这

些工作都需要一系列程序化的步骤，这就是算法思想。

本节内容是探究古代算法案例――辗转相除法，巩固算法三种描述性语言（自然语言、

流程图和伪代码），提高学生分析和解决问题的能力。

2、教学目标：

（1）知识目标：

①理解辗转相除法原理；

②能用自然语言、流程图和伪代码表达辗转相除法；

③能应用迭代算法思想。

（2）能力目标：

①培养学生把具体问题抽象转化为算法语言的能力；

②培养学生自主探索和合作学习的能力。

（3）情感目标：

①使学生进一步了解从具体到抽象，抽象到具体的辨证思想方法，对学生进行辨证唯物主义

教育；

②创设和谐融洽的教学氛围和阶梯形问题，使学生在活动中获得成功感，从而培养学生热爱

数学、积极学习数学、应用数学的热情。

3、教学重点与难点：

（1）教学重点：

①理解辗转相除法原理；

②能用自然语言、流程图和伪代码表达辗转相除法。

（2）教学难点：

①理解和区分两种循环结构表达辗转相除法；

②能应用迭代算法思想。

二、教法学法

1、教法：以问题为载体，有引导的对话，让学生经历知识的形成过程和发展过程，从而突

出教学重点，并采用多媒体教学，增加课堂容量，有利于学生活动的充分展开。

2、学法：以观察、讨论、思考、分析、动手操作、自主探索、合作学习多种形式相结合，

引导学生多角度、多层面认识事物，突破教学难点。

2

三、教学过程设计：

1、情景设置――感知辗转相除法

（发给每位学生一张长为22cm，宽为6cm的纸条）

【问1】这张长方形的纸，先拿短边往长边上折，得到一个正方形，从长方形上裁掉这个正

方形后继续将短边往长边上折，一直到最后剩下来的是正方形为止，最后得到的边长是几的

正方形？

【师生互动解答】22＝6×3＋4；

6＝4×1＋2；

4＝2×2＋0＝>最后正方形的边长为2cm。

【设计意图】通过动手操作，直观感受辗转相除法的具体做法。

2、理解辗转相除法原理

【问2】22与6的最大公约数？

【设计意图】把辗转相除法和情景设置联系起来，承上启下，顺利过渡。

【问3】204与85的最大公约数？

【师板书】204＝85×2＋34

85＝34×2＋17

34＝17×2＋0＝>204与85最大公约数为17。

【师引导】总结辗转相除法具体步骤。

【师讲解】辗转相除法原理：（204，85）＝（85，34）＝（34，17）。

【练1】求678与35的最大公约数？

【设计意图】具体动手操作，巩固新知。

3、设计辗转相除法算法

【问4】写出两个正整数)(,baba的最大公约数的一个算法。

【师初步分析】运用辗转相除法，产生一列数：0,,,,,,,

121nn

rrrrba



。这列数从第三项开

始，每项都是前两项相除所得的余数，余数为0的前一项

n

r，既是a和

b

的最大公约数。

递推关系：),mod(

21



nnn

rrr（其中),mod(

1

bar，),mod(

12

rbr）

【问5】可选用什么结构书写此算法？

【生答】循环结构。

【生分组讨论】共分为两个小组，分别用直到型和当型循环结构写算法、画流程图和写伪代

码，并派代表演板流程图和伪代码。

【幻灯片显示】

直到型循环结构算法：

S1输入两个正整数)(,baba；

S2

bar

的余数；

S3rbba,；

S4若

0r

，则输出最大公约数a；

若

0r

，则转S2。

当型循环结构算法：

S1输入两个正整数)(,baba；

S2若0),mod(ba，则输出最大

公约数b；若

0r

，则转S3。

S3

bar

的余数；

S4rbba,；

3

【师点评结果】通过演板的流程图和伪代码的对比，梳理算法，

强调选择不同的循环结构导致输出结果不同。

【设计意图】

①多角度分析问题，加强综合运用知识能力；

②通过小组合作探索，激发学生兴趣，巩固新知；

③渗透从具体到抽象的数学思想方法，体会迭代

的算法思想。

4、应用辗转相除法算法

【练2】右面一段伪代码的目的是：()

A.求x,y的最小公倍数B.求x,y的最大公约数

C.求x被y整除的商D.求y被x整除的商

【生答】B

【设计意图】会“识”直到型循环语句描述的应用辗转相除法求最大公约数。

当型循环结构伪代码：

Readba,

Whilemod(0),ba

rb

ba

bar





),mod(

EndWhile

Printb

直到型循环结构伪代码：

10Readba,

20),mod(bar

30

ba

40

rb

50If

0r

thengoto20

60Printa

直到型循环结构流程图：

输入a,b

),mod(bar

ba

rb

输出a

0r

Y

N

当型循环结构流程图：

输入a,b

),mod(bar

ba

rb

输出b

0),mod(ba

N

Y

10Readx,y

20mx

30ny

40cm-int(m/n)×n

50mn

60nc

70Ifm/n=int(m/n)thengoto40

80Printm

（练2）

4

【练3】右面一段伪代码的输出结果是：（）

A.1B.429

C.190D.6

【生答】A

【设计意图】会“识”当型循环语句描述辗转相除法

并且会“算”最大公约数。

【练4】设计计算两个正整数)(,baba的

最小公倍数的算法。

【设计意图】会“用”辗转相除法的算法语句。

【师提示】最小公倍数＝

最大公约数

ba

【生演板】

【师点评】易错点为：

【问6】：还有其他算法吗？

【生答】运用案例1穷举算法方法

【设计意图】①巩固练习辗转相除法算法；②重温上节课孙子问题的穷举算法思想。

Read)(,baba

S

ba

Whilemod0),(ba

rb

ba

bar





),mod(

EndWhile

Print

b

S

Read)(,baba

Whilemod0),(ba

rb

ba

bar





),mod(

EndWhile

Print

b

ba

Read)(,baba

1x

Whilemod0),(ax

andmod0),(bx

1xx

EndWhile

Printx

1048a

429b

Whilemod(0),ba

rb

ba

bar





),mod(

EndWhile

Printb

(练3)

5

5、课堂小结：

【问7】①今天这节课主要学习了什么内容？

②在问题的解决过程中，我们运用了那些数学思想？

【答】①回顾从具体到抽象的研究方法；

②掌握运用辗转相除法求两个正整数的最大公约数；

③体会迭代算法思想。

【设计意图】使学生对本节课所学知识的结构有一个清晰的认识，对本节课所用的迭代算法

数学思想方法有一个明确的了解。

6、布置作业：

①必做题：写出3428与736的最大公约数和最小公倍数的算法；

②选做题：课本P23：4（斐波那契数列）；

③拓展延伸：阅读课本P28《辗转相除与更相减损》

【设计意图】

①必做题让所有学生再次巩固本节课所学内容；

②选作题体现迭代算法思想，可供学生提高之用；

③阅读中国古代类似算法――更相减损法，体会中国古代数学对世界数学发展的贡献，增强

民族自豪感。

7、板书设计：

辗转相除法

1、分析3、流程图5、演板练习

2、算法4、伪代码

四、评价分析：

1、指导思想：

①新知识与旧知识相结合的原则；

②掌握知识与发展智力、能力相统一的原则；

③教师的主导作用与学生的主体作用相结合的原则。

2、本节课特点：

①教学模式

打破了传统的教学模式，采用了以问题为载体，以老师引导和小组合作探究为主要形式。

②教学设计符合学生的认知规律

在整个教学过程中，始终体现这一思想，如：让学生动手操作，组织讨论，学生演板，

辗转相除法的算法的引出从特殊到一般。

③强化学生的应用意识

新课的导入，设计了与本课密切相关的实际问题，结束前又运用所学知识解决问题，

课后的选作题是迭代算法思想的进一步应用。