《算法案例(第1课时)》教学设计

1.3 第一课时辗转相除法与更相减损术、秦九韶算法学习目标1．理解辗转相除法与更相减损术的含义，了解其执行过程，并会求最大公约数．2．掌握秦九韶算法的计算过程，了解它提高计算效率的实质，并会求多项式的值．3．进一步体会算法的基本思想．基础知识1．辗转相除法与更相减损术(1)辗转相除法．①算法步骤：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，m＝n，n＝r.第四步，若r＝__，则m，n的最大公约数等于m；否则返回第__步．②程序框图如图所示．③程序：INPUT m，nDOr＝m MOD nm＝nn＝rLOOP UNTIL____PRINT__END(2)更相减损术．算法分析：第一步，任意给定两个正整数，判断它们是否都是____．若是，用__约简；若不是，执行第二步．第二步，以较大的数__去较小的数，接着把所得的差与较小的数比较，并以__数减__数．继续这个操作，直到所得的差与减数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．【做一做1】用更相减损术求294和84的最大公约数时，第一步是__________．2．秦九韶算法(1)概念：求多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求n个____多项式的值，共进行__次乘法运算和__次加法运算．其过程是：改写多项式为：f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0＝(a n x n－1＋a n－1x n－2＋…＋a1)x＋a0＝((a n x n－2＋a n－1x n－3＋…＋a2)x＋a1)x＋a0＝…＝(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0.设v1＝__________，v2＝v1x＋a n－2，v3＝v2x＋a n－3，…，v n＝____________.(2)算法步骤：第一步，输入多项式的次数n、最高次项的系数a n和x的值．第二步，将v的值初始化为a n，将i的值初始化为n－1.第三步，输入i次项的系数a i.第四步，v＝vx＋a i，i＝____.第五步，判断i是否大于或等于__．若是，则返回第三步；否则，输出多项式的值__．(3)程序框图如图所示．(4)程序：INPUT“n＝”；nINPUT“an＝”；aINPUT“x＝”；xv＝ai＝n－1WHILE______PRINT“i＝”；iINPUT“ai＝”；av＝________i＝i－1WENDPRINT__END【做一做2】设计程序框图，用秦九韶算法求多项式的值，所选用的结构是()A．顺序结构B．条件结构C．循环结构D．以上都有重点难点1．更相减损术与辗转相除法的区别与联系剖析：如表所示．辗转相除法更相减损术区别①以除法为主．②两个整数差值较大时运算次数较少．③相除余数为零时得结果.①以减法为主．②两个整数的差值较大时，运算次数较多．③相减，差与减数相等得结果．④相减前要做是否都是偶数的判断.联系①都是求最大公约数的方法．②二者的实质都是递归的过程．③二者都要用循环结构来实现.2．秦九韶算法是比较先进的算法剖析：计算机的最重要特点就是运算速度快.2003年2月26日，以色列科学家宣布研制出一台依靠DNA运行、速度达每秒运算330万亿次的生物计算机．这种计算机的运算速度比现在普通计算机的运算速度要快10万倍，但是即便如此，计算机也不是万能的．同一个问题有多种算法，如果某个算法比其他算法的步骤少，运算的次数少，那么这个算法就是比较先进的算法．算法好坏的一个重要标志就是运算的次数越少越好．求多项式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0的值时，通常是先计算a n x n，进行n次乘法运算；再计算a n－1x n－1，进行n－1次乘法运算；这样继续下去共进行n＋n－1＋…＋2＋1＝n（n＋1）2(其计算方法以后学习)次乘法运算，还需要进行n次加法运算，总共进行n（n＋1）2＋n次运算．但是用秦九韶算法时，改写多项式为f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0＝(a n x n－1＋a n－1x n－2＋…＋a1)x＋a0＝((a n x n－2＋a n－1x n－3＋…＋a2)x＋a1)x＋a0…＝(…((a n x＋a n－1)x＋…＋a2)x＋a1)x＋a0.先计算v1＝a n x＋a n－1，需1次乘法运算，1次加法运算；v2＝v1x＋a n－2，需1次乘法运算，1次加法运算；…v n ＝v n －1x ＋a 0，需1次乘法运算，1次加法运算．所以需进行n 次乘法运算，n 次加法运算，共进行2n 次运算． 由于⎣⎡⎦⎤n （n ＋1）2＋n －2n ＝n （n －1）2≥0，则n （n ＋1）2＋n ≥2n . 因此说秦九韶算法与其他算法相比运算次数少，秦九韶算法是比较先进的算法． 典型例题题型一求最大公约数【例题1】 (1)用辗转相除法求840与1 785的最大公约数； (2)用更相减损术求612与468的最大公约数．跟踪训练1.分别用辗转相除法和更相减损术求261和319的最大公约数．题型二求多项式的值【例题2】用秦九韶算法求多项式f (x )＝7x 7＋6x 6＋5x 5＋4x 4＋3x 3＋2x 2＋x 当x ＝3时的值．跟踪训练2.已知一个5次多项式为f (x )＝4x 5＋2x 4＋3.5x 3－2.6x 2＋1.7x －0.8，用秦九韶算法 求这个多项式当x ＝5时的值． 题型三易错辨析【例题3】已知f (x )＝3x 4＋2x 2＋4x ＋2，利用秦九韶算法求f (－2)的值．跟踪训练3.用秦九韶算法求多项式f (x )＝7x 7＋6x 6＋5x 5＋4x 4＋3x 3＋2x 2＋x 当x ＝3时的值．当堂检测1．用更相减损术可求得78与36的最大公约数是()A．24 B．18 C．12 D．62．用秦九韶算法计算f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值，需要进行乘法运算和加法运算的次数分别为()A．6,6 B．5,6 C．6,5 D．6,123．利用辗转相除法求3 869与6 497的最大公约数时，第二步是________．4．用秦九韶算法求多项式f(x)＝x5＋5x4＋10x3＋10x2＋5x＋1在x＝－2时的值为________．5．用辗转相除法求242与154的最大公约数．参考答案基础知识【答案】1．(1)①0二③r＝0m(2)偶数2减大小【做一做1】用2约简由于294和84都是偶数，先用2约简．【答案】2．(1)一次n n a n x＋a n－1v n－1x＋a0(2)i－10v(4)i＞＝0v x＋a v 【做一做2】【答案】D【例题1】解：(1)用辗转相除法求840和1 785的最大公约数．1 785＝840×2＋105，840＝105×8.所以840和1 785的最大公约数是105.(2)首先612和468都是偶数，所以用2约简，得到306和234，但它们还都是偶数，需要再用2约简，得到153和117，最后用更相减损术计算得153－117＝36，117－36＝81，81－36＝45，45－36＝9，36－9＝27，27－9＝18，18－9＝9.所以612和468的最大公约数是9×2×2＝36.跟踪训练1.解：辗转相除法：319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)，所以319与261的最大公约数为29.更相减损术：319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29，29－29＝0，所以319与261的最大公约数是29.【例题2】解：f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x，所以有v0＝7；v1＝7×3＋6＝27；v2＝27×3＋5＝86；v3＝86×3＋4＝262；v4＝262×3＋3＝789；v5＝789×3＋2＝2 369；v6＝2 369×3＋1＝7 108；v7＝7 108×3＝21 324.故当x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21 324. 跟踪训练2.解：将f(x)改写为f(x)＝((((4x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，由内向外依次计算一次多项式当x＝5时的值：v0＝4；v1＝4×5＋2＝22；v2＝22×5＋3.5＝113.5；v3＝113.5×5－2.6＝564.9；v4＝564.9×5＋1.7＝2 826.2；v5＝2 826.2×5－0.8＝14 130.2.∴当x＝5时，多项式的值等于14 130.2.【例题3】解：f(x)＝3x4＋0·x3＋2x2＋4x＋2＝(((3x＋0)x＋2)x＋4)x＋2，v1＝3×(－2)＋0＝－6；v2＝－6×(－2)＋2＝14；v3＝14×(－2)＋4＝－24；v4＝－24×(－2)＋2＝50.故f(－2)＝50.跟踪训练3.解：f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x所以有v0＝7，v1＝7×3＋6＝27，v2＝27×3＋5＝86，v3＝86×3＋4＝262，v4＝262×3＋3＝789，v5＝789×3＋2＝2 369，v6＝2 369×3＋1＝7 108，v7＝7 108×3＝21 324.故当x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21 324.当堂检测1．【解析】先用2约简得39,18；然后辗转相减得39－18＝21，21－18＝3，18－3＝15,15－3＝12,12－3＝9,9－3＝6，6－3＝3.所以所求的最大公约数为3×2＝6.【答案】D2．【解析】改写多项式f(x)＝(((((3x＋4)x＋5)x＋6)x＋7)x＋8)x＋1，则需进行6次乘法和6次加法运算．【答案】A3．【解析】3 869＝2 628×1＋1 241第一步：6 497＝3 869×1＋2 628，第二步：3 869＝2 628×1＋1 241.【答案】3 869＝2 628×1＋1 2414．【解析】改写多项式为f(x)＝((((x＋5)x＋10)x＋10)x＋5)x＋1，当x＝－2时，v0＝1；v1＝1×(－2)＋5＝3；v2＝3×(－2)＋10＝4；v3＝4×(－2)＋10＝2；v4＝2×(－2)＋5＝1；v5＝1×(－2)＋1＝－1；故f(－2)＝－1.【答案】－15．解：242＝154×1＋88，154＝88×1＋66，88＝66×1＋22，66＝22×3.所以242与154的最大公约数是22.。

课题进位制课型教学目标（1）了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换；学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k去余法，并理解其中的数学规律.（2）各种进位制之间的互化.（3）除k取余法的理解以及各进位制之间转换的程序框图及其程序的设计.教学过程教学内容备注一、自主学习阅读：P40-P45，思考以下问题（1）进位制的概念（2）k进制化十进制的算法（3）除k取余法二、质疑提问知识探究(一):进位制的概念思考1:进位制是为了计数和运算方便而约定的记数系统，如逢十进一，就是十进制；每七天为一周，就是七进制；每十二个月为一年，就是十二进制，每六十秒为一分钟，每六十分钟为一个小时，就是六十进制；等等.一般地，“满k进一”就是k进制，其中k称为k进制的基数.那么k是一个什么范围内的数？思考2:十进制使用0～9十个数字，那么二进制、五进制、七进制分别使用哪些数字？思考3:在十进制中10表示十，在二进制中10表示2.一般地，若k是一个大于1的整数，则以k为基数的k进制数可以表示为一串数字连写在一起的形式：anan-1…a1a0(k).其中各个数位上的数字an，an-1，…，a1，a的取值范围如何？思考4:十进制数4528表示的数可以写成4×103+5×102+2×101+8×100，依此类比，二进制数110011(2),八进制数7342(8)分别可以写成什么式子？110011(2)=1×25+1×24+0×23+0×22+1×21+1×207342(8)=7×83+3×82+4×81+2×80.思考5:一般地，如何将k进制数a n a n-1…a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式？1111)(011kakakakaaaaa nnnnknn⨯+⨯++⨯+⨯=---思考6:在二进制中，0+0，0+1，1+0，1+1的值分别是多少？三、问题探究知识探究(二):k进制化十进制的算法思考1:二进制数110011(2)化为十进制数是什么数？110011(2)=1×25+1×24+0×23+0×22+1×21+1×20 =32+16+2+1=51. 思考2:二进制数右数第i位数字a i化为十进制数是什么数？12-⨯iia例1 将下列各进制数化为十进制数.(1)10303(4)； (2)1234(5).10303(4)=1×44+3×42+3×40=307.1234(5)=1×53+2×52+3×51+4×50=194.知识探究(三):除k取余法思考1:二进制数101101(2)化为十进制数是什么数？十进制数89化为二进制数是什么数？思考2:上述化十进制数为二进制数的算法叫做除2取余法，转化过程有些复杂，观察下面的算式你有什么发现吗？思考3:上述方法也可以推广为把十进制数化为k进制数的算法，称为除k取余法，那么十进制数191化为五进制数是什么数？191=1231(5)例2 将十进制数458分别转化为四进制数和六进制数.458=13022(4)=2042(6)2122252112222442891111余数515753851911321余数4147428411444582231余数626126766458242余数。

初中信息技术《算法实例》教学设计教学设计：初中信息技术《算法实例》一、教学目标：1.了解算法的概念和基本特征；2.掌握基本的算法实例，如排序算法、查找算法等；3.能够灵活运用算法解决实际问题。

二、教学内容：1.算法的概念和基本特征；2.常见算法实例：冒泡排序、选择排序、插入排序、二分查找等；3.算法的应用举例。

三、教学过程：步骤一：导入新知识（10分钟）1.引导学生思考：我们生活中有很多重复性的操作，比如对数字排序、查找等，你们有没有想过如何通过计算机自动完成它们呢？2.引出算法的概念：算法是为解决其中一问题而规定的一系列步骤，是计算机能够理解和执行的指令。

3.引出算法的基本特征：输入、输出、有穷性、确定性、可行性。

4.通过例子解释算法的基本特征。

步骤二：介绍常见算法实例（20分钟）1.介绍冒泡排序算法：通过不断比较相邻的两个元素，把大的元素往后交换，小的元素往前交换，以此实现对一组数字的排序。

2.演示冒泡排序算法的运行过程，并给出具体代码实现。

3.介绍选择排序算法：每次从待排序的元素中找到最小的元素，将其放到已排序的序列末尾，直到所有元素排序完成。

4.演示选择排序算法的运行过程，并给出具体代码实现。

5.介绍插入排序算法：将一个元素插入到已排序的数组中，保持数组的有序性。

6.演示插入排序算法的运行过程，并给出具体代码实现。

7.介绍二分查找算法：对于有序数组，通过每次从中间位置比较，缩小查找范围，最终找到目标元素或判断该元素不存在。

8.演示二分查找算法的运行过程，并给出具体代码实现。

步骤三：算法应用举例（20分钟）1.以查找最大值为例，演示如何利用排序算法中的冒泡排序来实现。

2.以查找元素是否存在为例，演示如何利用排序算法中的二分查找来实现。

3.以排序为例，演示如何使用选择排序算法对一组数字进行排序。

4.其他算法实例的应用举例，如查找中位数、求和等。

步骤四：练习与总结（10分钟）1.给学生一些实际问题，让他们运用所学的算法来解决。

初中信息技术《算法实例》教学设计一、教学目标通过本节课的学习，学生应能够：1.了解算法的基本概念和作用；2.理解算法的实际应用和意义；3.能够使用Python语言编写常用的算法实例；4.培养学生的问题解决能力和逻辑思维能力。

二、教学重点和难点教学重点：理解算法的基本概念和作用，掌握算法的实际应用和使用Python 编写算法实例的方法。

教学难点：培养学生的问题解决能力和逻辑思维能力。

三、教学内容和教学步骤1. 算法的基本概念介绍（10分钟）教学内容：•什么是算法？•算法的基本要素：输入、输出、有限性、确定性和可行性。

•算法的分类：顺序、选择和循环。

•算法和编程的关系。

教学步骤：•通过简单的例子引入算法的概念，如制作一杯咖啡的步骤；•结合实际生活中的例子，让学生理解算法的基本要素；•以顺序、选择和循环三种算法分类为线索，帮助学生理解不同类型的算法；•结合编程的概念，说明算法和编程的关系。

2. 算法实例的介绍和编写（30分钟）教学内容：•常见的算法实例介绍，如求两个数的和、求斐波那契数列等；•使用Python编写算法实例的方法。

教学步骤：•介绍常见的算法实例，如求两个数的和、求斐波那契数列等；•通过具体的例子，讲解算法实例的编写思路；•引导学生使用Python编写算法实例，并进行实际操作；•鼓励学生尝试不同的编写方法和优化算法的思路。

3. 算法实例的应用与思考（20分钟）教学内容：•算法实例在实际生活中的应用；•深入思考和讨论算法实例的优化方法和应用场景。

教学步骤：•结合学生们日常生活的例子，探讨算法实例的实际应用；•引导学生思考如何对算法实例进行优化，提高算法的效率和准确性；•分小组进行讨论，分享各自的思考和观点；•指导学生撰写思考总结，对算法实例的应用与优化进行总结和思考。

四、教学资源•教学投影仪、电脑；•Python编程环境。

五、教学评估•学生课堂表现评估：包括课堂积极性、思考能力、问题解决能力等；•作业评估：布置编写算法实例的作业，并对学生的作业进行评估；•小组讨论评估：对学生小组讨论的贡献和表现进行评估。

算法案例教案教案标题：算法案例教案教案目标：1. 了解算法的基本概念和作用。

2. 学习分析和解决实际问题时所需的算法设计思路。

3. 运用具体的算法案例，培养学生的问题解决能力和创新思维。

教学重点：1. 算法的定义和基本特征。

2. 算法设计的思路和步骤。

3. 算法在实际问题中的应用。

教学难点：1. 算法设计的实际应用。

2. 学生对算法思维的理解和运用。

教学准备：1. 计算机或投影仪。

2. 算法案例材料。

教学过程：Step 1: 引入新知识 (5分钟)通过提问和讨论，引导学生思考算法的定义和作用。

解释算法在日常生活中的应用，例如搜索引擎的排序算法、导航系统的路径规划算法等。

Step 2: 算法概念讲解 (10分钟)讲解算法的基本概念和特征，包括输入、输出、有穷性、确定性和可行性。

通过示例解释每个概念，并与学生共同总结。

Step 3: 算法设计思路 (15分钟)介绍算法设计的思路和步骤，包括问题分析、算法设计、算法实现和算法评估。

通过具体案例演示每个步骤的操作过程，并鼓励学生积极参与讨论。

Step 4: 算法案例分析 (20分钟)提供一个具体的算法案例，如排序算法或查找算法。

引导学生分析问题，设计算法，并编写相应的伪代码或流程图。

鼓励学生在小组内合作，并就不同解决方案进行讨论和比较。

Step 5: 算法案例实现 (20分钟)学生使用编程语言（如Python）将算法案例实现，并运行测试用例进行验证。

教师可以提供必要的指导和帮助。

Step 6: 算法案例评估 (10分钟)学生对实现的算法进行评估，讨论其时间复杂度和空间复杂度。

引导学生思考算法的效率和优化方法。

Step 7: 总结与拓展 (5分钟)总结本节课的学习内容，强调算法设计的重要性和应用前景。

鼓励学生进一步探索和应用算法知识。

教学延伸：1. 鼓励学生独立设计和实现其他算法案例，如图算法、动态规划等。

2. 引导学生参与算法竞赛或编程比赛，提升算法设计和实现能力。

《算法案例》教学设计考点1 三种基本结构三种基本逻辑结构顺序结构：依次进行多个处理的结构称为顺序结构，如图(1)所示.图(1)选择结构：先根据条件作出判断，再决定执行哪一种操作的结构称为选择结构(或称为“分支结构”)，如图(2)所示.图(2)循环结构：需要重复执行同一操作的结构称为循环结构，其又可分为如下两种结构：①先判断所给条件p是否成立，若p成立，则执行A，再判断条件p是否成立；若p仍成立，则又执行A，如此反复，直到某一次条件p不成立为止.这样的循环结构称为当型循环，如图(3)所示.②先执行A，再判断所给条件p是否成立，若p不成立，则再执行A，如此反复，直到p成立，该循环过程结束，这样的循环结构称为直到型循环，如图(4)所示.图(3) 图(4)类型二流程图的算法功能例题2(2016·苏北四市期中)执行如图所示的算法流程图，则输出的结果是.(例2)【答案】-1【解析】第一次循环后，S=12，n=2；第二次循环后，S=-1，n=3；…，第七次循环后，S=12，n=8，此时n>8不成立；第八次循环，S=-1，n=9，退出循环，输出S=-1.【教学建议】循环结构中的条件主要是控制循环的变量应该满足的条件是什么.满足条件则进入循环或者退出循环，此时要特别注意当型循环与直到型循环的区别.【总结与反思】本题考查流程图与循环结构等知识，可依据题设条件顺次验算，注意理清循环体的运算次数.类型三基本算法语句根据如图所示的伪代码，当输入的x为60时，输出的y的值为.例题3【答案】31 【解析】由题意，得y=0.550250.6(-50)50.x x x x ≤⎧⎨+>⎩，，，当x=60时，y=25+0.6×(60-50)=31. 所以输出的y 的值为31. 【教学建议】本题主要考查条件语句，输入与输出语句，要注意赋值语句一般格式“←”，其实质是计算“←”右边表达式的值，并将该值赋给“←”左边的变量.【总结与反思】解决此类问题的关键是要理解各语句的含义，以及基本算法语句与算法结构的对应关系.1．(2014·宿迁一调)根据如图所示的伪代码，最后输出的a 的值为.四 、课堂运用 基础2．(2015·某某期末)运行如图所示的算法流程图，那么输出的a的值是. 3．(2015·某某、某某期末)运行如图所示的伪代码后，输出的结果为.(第3题)4．(2014·某某期末)已知一个算法的流程图如图所示，那么输出的结果S的值是.答案与解析1．【答案】48 【解析】a=1，i=2；a=1×2=2，i=4；a=2×4=8，i=6；a=8×6=48，i=8，退出循环，输出a=48．2．【答案】127 【解析】a=3；a=7；a=15；a=31；a=63；a=127，127>64，退出循环，输出a=127．3．【答案】42 【解析】第一次循环后，S=8，i=4；第二次循环后，S=22，i=7；第三次循环后，S=42，i=10，10>7，退出循环，所以输出的结果为42．4．【答案】7 【解析】第一次循环后，S=1，n=2；第二次循环后，S=3，n=3；第三次循环后，S=7，n=4，此时退出循环，所以输出的S的值为7．巩固1．(2015·某某、某某、某某、宿迁四市期末)如图是一个算法的流程图，若输入的x的值为2，则输出的y的值为.2.(2014·某某期末)执行如图所示的流程图，输出的结果S=.3.(2015·某某期末)执行如图所示的算法流程图，那么输出的x的值是.4.(2014·某某、某某一模)根据如图所示的伪代码，最后输出的S的值为.答案与解析1．【答案】7 【解析】第一次循环后，y=3，x=2；第二次循环后，y=7，x=3，|y-x|=4，此时退出循环，所以输出的y的值为7．2．【答案】-20 【解析】第一次循环后，i=2，S=-2；第二次循环后，i=4，S=-6；第三次循环后，i=6，S=-12；第四次循环后，i=8，S=-20，退出循环，输出S=-20.3．【答案】59 【解析】第一次循环后，x=3，y=7；第二次循环后，x=13，y=33；第三次循环后，x=59，y=151，此时退出循环，所以输出的结果为59．4．【答案】55 【解析】根据伪代码的原理知S=1+2+…+10=55．、拔高1.(2015·某某期末)执行如图所示的流程图，那么输出的n的值为.2.(2014·某某调研)已知实数x∈[1，9]，执行如图所示的流程图，那么输出的x不小于55的概率为.3.执行如图所示的流程图，输出的结果是.4.(2015·某某、某某、某某、某某、宿迁一调)如图是一个算法流程图，则输出的x的值为.答案与解析1．【答案】4 【解析】第一次循环后，S=255，n=2；第二次循环后，S=127，n=3；第三次循环后，S=63，n=4，此时退出循环，所以输出的结果为4．2．【答案】38【解析】若x=1，进入程序，输出x=15；…；若x=6，进入程序，输出x=55；…；若x=9，进入程序，输出x=79．所以所求概率为9-69-1=38. 3.【答案】．20162017【解析】由流程图知输出S=112⨯+123⨯+…+120162017⨯=112⎛⎫- ⎪⎝⎭+11-23⎛⎫ ⎪⎝⎭+…+1120162017⎛⎫- ⎪⎝⎭=1-12017=20162017. 4．【答案】16 【解析】执行程序可得x=12，n=2<5；x=13，n=3<5；x=14，n=4<5；x=15，n=5；x=16，n=6>5，故输出x=16.1. 本次课需要学会流程图的有关计算2. 流程图和数列求和的关系密切，也是重点3. 循环语句的终结条件是易错点。

1.3 算法案例第1课时案例1 辗转相除法与更相减损术导入新课思路1（情境导入）大家喜欢打乒乓球吧，由于东、西方文化及身体条件的不同，西方人喜欢横握拍打球，东方人喜欢直握拍打球，对于同一个问题，东、西方人处理问题方式是有所不同的.在小学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来. 当两个数公有的质因数较大时（如 8 251 与6 105），使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法——辗转相除法与更相减损术,由此可以体会东、西方文化的差异.思路2（直接导入）前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过辗转相除法与更相减损术来进一步体会算法的思想.（1）怎样用短除法求最大公约数？（2）怎样用穷举法（也叫枚举法）求最大公约数？（3）怎样用辗转相除法求最大公约数？（4）怎样用更相减损术求最大公约数？讨论结果：（1）短除法求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来.（2）穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数.（3）辗转相除法辗转相除法求两个数的最大公约数，其算法步骤可以描述如下：第一步，给定两个正整数m，n.第二步，求余数r：计算m除以n，将所得余数存放到变量r中.第三步，更新被除数和余数：m=n，n=r.第四步，判断余数r是否为0.若余数为0，则输出结果；否则转向第二步继续循环执行.如此循环，直到得到结果为止. 这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法. （4）更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术. 《九章算术》是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”翻译为现代语言如下：第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用2约简；若不是，执行第二步.第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.例1.用辗转相除法求8 251与6 105的最大公约数,写出算法分析，画出程序框图，写出算法程序.解：用两数中较大的数除以较小的数，求得商和余数：8 251=6 105×1+2 146.由此可得，6 105与2 146的公约数也是8 251与6 105的公约数，反过来，8 251与6 105的公约数也是6 105与2 146的公约数，所以它们的最大公约数相等.对6 105与2 146重复上述步骤：6 105=2 146×2+1 813.同理，2 146与1 813的最大公约数也是6 105与2 146的最大公约数.继续重复上述步骤：2 146=1 813×1+333，1 813=333×5+148，333=148×2+37，148=37×4.最后的除数37是148和37的最大公约数，也就是8 251与6 105的最大公约数.这就是辗转相除法.由除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，算法分析：从上面的例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环结构来构造算法.算法步骤如下：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数为r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.程序框图如下图：程序：INPUT m,nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND点评：从教学实践看，有些学生不能理解算法中的转化过程，例如：求8 251与6 105的最大公约数,为什么可以转化为求6 105与2 146的公约数.因为8 251=6 105×1+2 146，可以化为8 251-6 105×1=2 164，所以公约数能够整除等式两边的数，即6 105与2 146的公约数也是8 251与6 105的公约数.变式训练你能用当型循环结构构造算法，求两个正整数的最大公约数吗？试画出程序框图和程序.解：当型循环结构的程序框图如下图：程序：INPUT m，nr=1WHILE r＞0r=m MOD nm=nn=rPRINT mEND例2．用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，如下图所示.所以，98和63的最大公约数等于7.点评：更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代数学名著，但是二者的算理却是相似的，有异曲同工之妙．主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归过程．例3.用辗转相除法或者更相减损术求三个数324,243,135的最大公约数.解一：324=243×1＋81，243=81×3＋0，则324与243的最大公约数为81.又135=81×1＋54，81=54×1＋27，54=27×2＋0，则81 与135的最大公约数为27.所以,三个数324、243、135的最大公约数为27.解二：324－243=81,243－81=162,162－81=81，则324与243的最大公约数为81.135－81=54,81－54=27,54－27=27，则81与135的最大公约数为27.所以，三个数324、243.135的最大公约数为27.例4．（1）用辗转相除法求123和48的最大公约数.（2）用更相减损术求80和36的最大公约数.解：（1）辗转相除法求最大公约数的过程如下：123＝2×48＋27，48＝1×27＋21，27＝1×21＋6，21＝3×6＋3，6＝2×3+0，最后6能被3整除，得123和48的最大公约数为3.（2）我们将80作为大数，36作为小数，因为80和36都是偶数，要除公因数2.80÷2=40，36÷2=18.40和18都是偶数，要除公因数2.40÷2=20，18÷2=9.下面来求20与9的最大公约数，20－9=11，11－9=2，9－2=7，7－2=5，5－2=3，3－2=1，2－1=1，可得80和36的最大公约数为22×1=4.点评：对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等.例5.分别用辗转相除法和更相减损术求1 734，816的最大公约数．解：一、辗转相除法：1 734=816×2+102，816=102×8（余0），∴1 734与816的最大公约数是102．二、更相减损术：因为两数皆为偶数，首先除以2得到867，408，再求867与408的最大公约数．867-408=459，459-408=51，408-51=357，357-51=306，306-51=255，255-51=204，204-51=153，153-51=102，102-51=51.∴1 734与816的最大公约数是51×2=102．更相减损术可另解：1 734－816＝918，918－816＝102，816－102＝714，714－102＝612，612－102＝510，510－102＝408，408－102＝306，306－102＝204，204－102＝102.∴1 734与816的最大公约数是102．例6.求319，377，116的最大公约数．解：377=319×1+58，319=58×5+29，58=29×2.∴377与319的最大公约数为29，再求29与116的最大公约数．116=29×4.∴29与116的最大公约数为29.∴377，319，116的最大公约数为29.拓展提升试写出利用更相减损术求两个正整数的最大公约数的程序．解：更相减损术程序：INPUT “m，n=”；m，nWHILE m<>nIF m>n THENELSEm=n-mEND IFWENDPRINT mEND例7.分别用辗转相除法和更相减损术求261，319的最大公约数.分析：本题主要考查辗转相除法和更相减损术及其应用．使用辗转相除法可依据m=nq+r，反复执行，直到r=0为止；用更相减损术就是根据m-n=r，反复执行，直到n=r为止．解：辗转相除法：319=261×1+58,。