复习参考题教学设计第二课时

算法

|||| 数学经典简介 |||| 1．《数书九章》

《数书九章》成书于1247年，是南宋数学家秦九韶唯一的数学著作，在长期艰苦的环境中写成的．全书共十八卷，分“大衍”“天时”“田域”“测望”“赋役”“钱谷”“营建”“军旅”“市物”等九类，每类九个问题，共81题．《数书九章》是一部划时代的巨著，内容丰富，精湛绝伦．秦九韶在《数书九章》中所发明的“大衍求—术”，即现代数论中一次同余式组解法，是中世纪世界数学的最高成就，比西方数学家高斯建立的同余理论早500多年，被西方称为“中国剩余定理”．此外，秦九韶还创拟了正负开方术，即任意高次方程的数值解法，也是中世纪世界数学的最高成就，秦九韶所发明的此项成果比1819年英国人霍纳的同样解法早500多年．

2．《算数书》

《算数书》是目前已知最早的数学著作.1983年底至1984年初在湖北省江陵县张家山出土．全书约有竹简200余支(完整的185支)．《算数书》是一部数学问题集，体例与后来的《九章算术》基本一致．全部算题分门别类采用“问题集”的形式，已经清理出来的小标题有“分乘”“增减分”“相乘”“合分”“经分”“里田”“税田”“金价”“程禾”等60余个．按现代数学的分类，《算数书》可分算术和几何两大类，有完整的分数约分、加法、减法、乘法、除法法则，有公式，有例题，有答案．

|||| 典型例题赏析 |||| (2015·全国卷Ⅱ)下边程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”．执行该程序框图，若输入的a，b分别为14,18，则输出的a＝(

)

A．0 B．2 C．4 D．14 [思路分析] 此题以《九章算术》中的“更相减损术”为载体考查程序框图，可逐次运行程序，直至程序结束得出a的值；也可根据程序的功能是求两数的最大公约数，故可直接求出最大公约数得到结果．

(方法一)逐次运行程序，直至程序结束得出a值．

输入a＝14，b＝18. 第一次循环，14≠18且14<18，b＝18－14＝4；

第二次循环，14≠4且14>4，a＝14－4＝10；

第三次循环，10≠4且10>4，a＝10－4＝6；

第四次循环，6≠4且6>4，a＝6－4＝2；

第五次循环，2≠4且2<4，b＝4－2＝2；

第六次循环，a＝b＝2，跳出循环，输出的a＝2，故选B. (方法二)此程序的功能是求18,14的最大公约数，

因为18,14的最大公约数为2，所以输出的a＝2，选B.

B

■■■

试题赏析

■■■

此题源于《九章算术·方田》，后人称之为“更相减损术”．“更相减损术”实质上是用来求两数的最大公约数，国外的欧几里得算法也可以解决这个问题，但是我国的算法比国外的算法更简单，操作起来更方便，更符合算法要求．此题以“更相减损术”为载体，考查程序框图的应用，这样的设计，不仅可以让学生了解数学文化，形成理性思维，同时也能使学生感受我国古代数学的成就，增强民族自豪感.

(2018·安徽二校联考)如图所示的程序框图的算法数学思想源于数学名著《几何原本》中的“辗转相除法”，执行该程序框图(图中“mMODn”表示m除以n的余数)，若输入的m，n分别为495,135，则输出的m＝(

)

A．0 B．5 C．45 D．90 [思路分析] 求解此题，关键是理解程序的功能．此程序功能是求两正整数的最大公约数，明确了程序的功能，求出两数的最大公约数即可．

该程序框图是求495与135的最大公约数，

由495＝135×3＋90,135＝90×1＋45,90＝45×2，

所以495与135的最大公约数是45，所以输出的结果是45.

C

■■■

试题赏析

■■■

读懂程序，明确此题就是“欧几里得算法”求两数的最大公约数．求解本题可直接求出最大公约数得出结果，也可按程序一步一步地执行，得到结果，同学们不妨试一试.

秦九韶是我国南宋时期的数学家，他在所著的《数书九章》中提出的多项式求值的秦九韶算法，至今仍是比较先进的算法．如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例，若输入n，x的值分别为3,4，

则输出的v的值为(

)

A．6 B．25 C．100 D．400 [思路分析] 此题以我国古代数学“秦九韶算法”为载体．考查程序框图的基本知识，按照框图箭头方向和每个框的指令，逐次执行程序，直至程序结束，即可得到输出的值s.

输入n＝3，x＝4. 第一次循环：v＝1，i＝3－1＝2；

第二次循环：v＝1×4＋2＝6，i＝2－1＝1；

第三次循环：v＝6×4＋1＝25，i＝1－1＝0；

第四次循环：v＝25×4＝100，i＝0－1＝－1<0. 程序结束，输出的v的值是100. C

■■■

试题赏析

■■■

本题程序框图中的算法思路源于《数书九章》中多项式求值的“秦九韶算法”，秦九韶算法是我国南宋时期的数学家秦九韶提出的一种多项式简化算法．秦九韶算法是一种将一元n次多项式的求值问题转化为n个一次多项式的算法．其大大简化了计算过程，即使在现代，利用计算机解决多项式的求值问题时，秦九韶算法依然是最优的算法. 公元263年左右，我国古代数学家刘徽用圆内接正多边形的面积去逼近圆的面积求圆周率π.他从圆内接正六边形算起，令边数一倍一倍地增加，即12,24,48，…，逐个算出正六边形，正十二边形，正二十四边形，……的面积，这些数值逐步地逼近圆的面积，刘徽一直计算到正3072边形，得到了圆周率π的近似值3.1416.刘徽称这个方法为“割圆术”，并且把“割圆术”的特点概括为“割之弥细，所失弥少，割之又割，以至于不可割，则与圆周合体而无所失矣”．刘徽这种想法的可贵之处在于用已知的、可求的来逼近未知的、要求的，用有限来逼近无限．这种思想极其重要，对后世产生了巨大影响．如图是利用刘徽的“割圆术”思想设计的一个程序框图．若运行该程序(参考数据：3≈1.732，sin 15°≈0.2588，sin 7.5°≈0.1305)，则输出的n的值为(

)

A．48 B．36 C．30 D．24 [思路分析] 本题以刘徽的“割圆术”为背景设计的一个程序框图，只要按照程序框图的流向，一步步运行程序即可得解．

输入n的值为6；

第一次循环，S＝3sin 60°＝33<3.10，n＝12；

2第二次循环，S＝6sin 30°＝3<3.10，n＝24；

第三次循环，S＝12sin 15°≈3.1056>3.10，退出循环，则输出的n的值为24. D

■■■

试题赏析

■■■

本题是以刘徽的“割圆术”为背景设计的一个程序框图，考查了学生阅读和运行程序框图的能力，还考查了运算求解能力及估算能力．试题还展示了刘徽在数学研究中的杰出成就以及对数学发展做出的重大贡献，特别是呈现了刘徽在得到圆周率π的近似值的过程中，从圆内接正六边形算起，一直到正3072边形的艰难的探索历程，不仅能让学生们感受到中国古代数学的辉煌成就，更能激发学生为实现中国梦而努力奋斗的信心.

(2018·深圳一模)中国古代数学著作《算学启蒙》中有关于“松竹并生”的问题：松长五尺，竹长两尺，松日自半，竹日自倍，松竹何日而等长．意思是现有松树高5尺，竹子高2尺，松树每天长自己高度的一半，竹子每天长自己高度的一倍，问在第几天会出现松树和竹子一样高？如图是源于其思路的一个程序框图，若输入的x＝5，y＝2，输出的n为4，则程序框图中判断框中应填入(

)

A．y≤x? B．x≤y?

C．y

[思路分析] 依次执行程序，要特别注意满足什么条件时，输出n的值为4.

根据程序框图，输入x＝5，y＝2，n＝1. 515第一次循环，x＝5＋＝，y＝4，此时y

22第二次循环，n＝2，x＝151545＋＝，y＝8，此时y

2444545135＋＝，y＝16，此时y

488第三次循环，n＝3，x＝135135405第四次循环，n＝4，x＝＋＝，y＝32，此时y≥x，输出n的值4. 81616由此可知，应填的条件是x≤y？.

B

■■■

试题赏析

■■■

此题以中国古代数学著作《算学启蒙》中有关于“松竹并生”问题为背景，考查程序框图的基本知识．“松竹并生”问题趣味性强，易激发学生的探索热情．通过探索判断框中应填写的条件，考查了学生的分析判断能力.

(2018·华大新高考联盟教学质量测评)我国古代的劳动人民曾创造了灿烂的中华文化，戍边的官兵通过在烽火台上举火向国内报告，烽火台上点火表示数字1，不点火表示数字0.这蕴含了进位制的思想．如图所示的程序框图的算法思路就源于我国古代戍边官兵的“烽火传信”．执行该程序框图，若输入a＝110011，k＝2，n＝6，则输出b的值为(

)

A．19 B．31 C．51 D．63 [思路分析] 读懂程序框图，依次执行程序框图即可．若明确程序的功能是

将二进制数化为十进制数，可直接求解．

(方法一)输入a＝110011，k＝2，n＝6. 输入b＝0，i＝1. 第一次循环，输入t＝1，b＝0＋1×20＝1，i＝2,2>6不成立；

第二次循环，输入t＝1，b＝1＋1×21＝3，i＝3,3>6不成立；

第三次循环，输入t＝0，b＝3＋0×22＝3，i＝4,4>6不成立；

第四次循环，输入t＝0，b＝3＋0×23＝3，i＝5,5>6不成立；

第五次循环，输入t＝1，b＝3＋1×24＝19，i＝6,6>6不成立；

第六次循环，输入t＝1，b＝19＋1×25＝51，i＝7,7>6成立，退出循环，输出b的值为51. (方法二)将二进制数化为十进制数，

a＝110011(2)＝1×25＋1×24＋0×23＋0×22＋1×21＋1×20＝51. 故b的值为51.

C

■■■

试题赏析

■■■

此题以“烽火传信”为背景，不仅考查了二进制数化十进制数及程序框图等知识，还歌颂了我国古代劳动人民的聪明才智，颂扬了灿烂的中华文化．同时通过此题还说明了二进制数的广泛应用. |||| 要点归纳小结 |||| 1．从古代的算筹、算盘到现代的计算机，联系它们的其实都是算法．我国古代数学家也创造了非常多的优秀算法，如计算最大公约数的“更相减损术”，计算多项式值的“秦九韶算法”等.2015年及2016年全国卷Ⅱ对此进行了考查，弘扬了中国传统文化．

2．古代的很多算法案例都可通过程序框图来实现，因此，结合算法进行命题的资源非常丰富，如可从中国古代数学名著《九章算术》《数书九章》《算学启蒙》《割圆术》等中挖掘素材，考查学生阅读、理解能力和程序框图的基础知识．

3．求解与数学文化有关的程序框图问题，其主要方法是列举法，即按照程序框图的流程线方向和指令一步步进行运行，并注意程序的控制条件，即可得到相关结论．