算法初步1

1.1.2 程序框图 1.1.3 算法的三种基本逻辑结构和框图表示（3）A级基础巩固一、选择题1．算法共有三种逻辑结构，即顺序结构、条件结构、循环结构，下列说法正确的是导学号 95064111( D )A．一个算法只能含有一种逻辑结构B．一个算法最多可包含两种逻辑结构C．一个算法必须含有上述三种逻辑结构D．一个算法可以含有上述三种逻辑结构的任意组合[解析]一个算法可以含有一种逻辑结构，也可以含有两种逻辑结构，还可以含有三种逻辑结构，故选D．2．下列判断正确的是导学号 95064112( B )A．条件结构中必有循环结构B．循环结构中必有条件结构C．顺序结构中必有条件结构D．顺序结构中必有循环结构[解析]由循环结构的定义知B正确．3．下面关于当型循环结构和直到型循环结构的说法，不正确的是导学号 95064113( D ) A．当型循环结构是先判断后循环，条件成立时执行循环体，条件不成立时结束循环B．直到型循环结构要先执行循环体再判断条件，条件成立时结束循环，条件不成立时执行循环体C．设计程序框图时，两种循环结构可以任选其中的一个，两种结构也可以相互转化D．设计循环结构的程序框图时只能选择这两种结构中的一种，除这两种结构外，再无其他循环结构[解析]循环结构的程序框中必须包含条件结构，故选项D的说法是错误的．4．(2015·福建文，4)阅读如图所示的程序框图，运行相应的程序，若输入x的值为1，则输出y的值为导学号 95064114( C )A ．2B ．7C ．8D ．128[解析] 由题意得，该程序是求分段函数y ＝⎩⎪⎨⎪⎧2x ，x≥29－x ，x<2的函数值，则f (1)＝9－1＝8，故选C ．二、填空题导学号 95064115__.4__＝n ，则输出的0.8＝p ．执行下面的程序框图，若5[解析] 第一次循环后：S ＝12，n ＝2；第二次循环后：S ＝12＋14＝34，n ＝3；第三次循环后：S ＝12＋14＋18＝78，n ＝4，此时循环结束．6．(2016·山东文)执行下面的程序框图，若输入n 的值为3，则输出的S 的值为导学号 95064116__.1__。

第一章 算法初步第一课时 1.1.1 算法的概念教学要求：了解算法的含义，体会算法的思想；能够用自然语言叙述算法；掌握正确的算法应满足的要求；会写出解线性方程（组）的算法、判断一个数为质数的算法、用二分法求方程近似根的算法.教学重点：解二元一次方程组等几个典型的的算法设计.教学难点：算法的含义、把自然语言转化为算法语言.教学过程：一、复习准备：1. 提问：我们古代的计算工具？近代计算手段？（算筹与算盘→计算器与计算机，见章头图）2. 提问：①小学四则运算的规则？（先乘除，后加减） ②初中解二元一次方程组的方法？（消元法） ③高中二分法求方程近似解的步骤？ （给定精度ε，二分法求方程根近似值步骤如下：A ．确定区间[,]a b ，验证()()0f a f b <，给定精度ε；B. 求区间(,)a b 的中点1x ；C. 计算1()f x ： 若1()0f x =，则1x 就是函数的零点； 若1()()0f a f x <，则令1b x =（此时零点01(,)x a x ∈）； 若1()()0f x f b <，则令1a x =（此时零点01(,)x x b ∈）；D. 判断是否达到精度ε；即若||a b ε-<，则得到零点零点值a （或b ）；否则重复步骤2~4．二、讲授新课：1. 教学算法的含义：① 出示例：写出解二元一次方程组22(1)24(2)x y x y -=⎧⎨+=⎩的具体步骤. 先具体解方程组，学生说解答，教师写解法 → 针对解答过程分析具体步骤，构成其算法第一步：②－①×2，得5y =0 ③； 第二步：解③得y =0； 第三步：将y =0代入①，得x =2.② 理解算法： 12世纪时，指用阿拉伯数字进行算术运算的过程. 现代意义上的算法是可以用计算机来解决的某一类问题的程序或步骤，程序和步骤必须是明确和有效的，且能在有限步完成. 广义的算法是指做某一件事的步骤或程序. 算法特点：确定性；有限性；顺序性；正确性；普遍性.举例生活中的算法：菜谱是做菜肴的算法；洗衣机的使用说明书是操作洗衣机的算法；歌谱是一首歌曲的算法；渡河问题.③ 练习：写出解方程组()1111221222(1)0(2)a x b y c a b a b a x b y c +=⎧-≠⎨+=⎩的算法.2. 教学几个典型的算法：① 出示例1：任意给定一个大于1的整数n ，试设计一个程序或步骤对n 是否为质数做出判断.提问：什么叫质数？如何判断一个数是否质数？ → 写出算法.分析：此算法是用自然语言的形式描述的. 设计算法要求：写出的算法必须能解决一类问题，并且能够重复使用. 要使算法尽量简单、步骤尽量少. 要保证算法正确，且计算机能够执行.② 出示例2：用二分法设计一个求方程230x -=的近似根的算法.提问：二分法的思想及步骤？如何求方程近似解→写出算法.③练习：举例更多的算法例子；→对比一般解决问题的过程，讨论算法的主要特征.3. 小结：算法含义与特征；两类算法问题（数值型、非数值型）；算法的自然语言表示.三、巩固练习：1. 写出下列算法：解方程x2－2x－3＝0；求1×3×5×7×9×11的值2. 有蓝和黑两个墨水瓶，但现在却错把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题.3. 根据教材P6 的框图表示，使用程序框表示以上算法.4. 作业：教材P4 1、2题.第二课时 1.1.2 程序框图（一）教学要求：掌握程序框图的概念；会用通用的图形符号表示算法，掌握算法的三个基本逻辑结构. 掌握画程序框图的基本规则，能正确画出程序框图. 通过模仿、操作、探索，经历通过设计程序框图表达解决问题的过程；学会灵活、正确地画程序框图.教学重点：程序框图的基本概念、基本图形符号和3种基本逻辑结构.教学难点：综合运用框图知识正确地画出程序框图教学过程：一、复习准备：1. 写出算法：给定一个正整数n，判定n是否偶数.2. 用二分法设计一个求方程320x-=的近似根的算法.二、讲授新课：1. 教学程序框图的认识：①讨论：如何形象直观的表示算法？→图形方法.教师给出一个流程图（上面1题），学生说说理解的算法步骤.②定义程序框图：程序框图又称流程图，是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形.③④阅读教材P5的程序框图. →讨论：输入35后，框图的运行流程，讨论：最大的I值.2. 教学算法的基本逻辑结构：①讨论：P5的程序框图，感觉上可以如何大致分块？流程再现出一些什么结构特征？→教师指出：顺序结构、条件结构、循环结构.②试用一般的框图表示三种逻辑结构. （见下图）③出示例3：已知一个三角形的三边分别为4,5,6，利用海伦公式设计一个算法，求出它的面积，并画出算法的程序框图. （学生用自然语言表示算法→师生共写程序框图→讨论：结构特征）④出示例4：任意给定3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在.画出这个算法的程序框图. (学生分析算法→写出程序框图→试验结果→讨论结构)⑤出示例5：设计一个计算1＋2＋3＋…＋1000的值的算法，并画出程序框图. (学生分析算法→写出程序框图→给出另一种循环结构的框图→对比两种循环结构)3. 小结：程序框图的基本知识；三种基本逻辑结构；画程序框图要注意：流程线的前头；判断框后边的流程线应根据情况标注“是”或“否”；循环结构中要设计合理的计数或累加变量等.三、巩固练习：1.练习：把复习准备题②的算法写成框图. 2. 作业：P12 A组1、2题.第三课时 1.1.2 程序框图（二）教学要求：更进一步理解算法，掌握算法的三个基本逻辑结构. 掌握画程序框图的基本规则，能正确画出程序框图.学会灵活、正确地画程序框图.教学重点：灵活、正确地画程序框图.教学难点：运用程序框图解决实际问题.教学过程：一、复习准备：1.2.顺序结构条件结构循环结构程序框图结构说明按照语句的先后顺序，从上而下依次执行这些语句. 不具备控制流程的作用. 是任何一个算法都离不开的基本结构根据某种条件是否满足来选择程序的走向.当条件满足时，运行“是”的分支，不满足时，运行“否”的分支.从某处开始，按照一定的条件，反复执行某一处理步骤的情况. 用来处理一些反复进行操作的问题二、讲授新课：1. 教学程序框图①出示例1：任意给定3个正实数，判断其是否构成三角形，若构成三角形，则根据海伦公式计算其面积. 画出解答此问题算法的程序框图.（学生试写→共同订正→对比教材P7 例3、4 →试验结果）②设计一个计算2＋4＋6＋…＋100的值的算法，并画出程序框图.（学生试写→共同订正→对比教材P9 例5 →另一种循环结构）③循环语句的两种类型：当型和直到型.当型循环语句先对条件判断，根据结果决定是否执行循环体；直到型循环语句先执行一次循环体，再对一些条件进行判断，决定是否继续执行循环体. 两种循环语句的语句结构及框图如右.说明：“循环体”是由语句组成的程序段，能够完成一项工作.注意两种循环语句的区别及循环内部改变循环的条件.④练习：用两种循环结构，写出求100所有正约数的算法程序框图.2. 教学“鸡兔同笼”趣题：①“鸡兔同笼”，我国古代著名数学趣题之一，大约在1500年以前，《孙子算经》中记载了这个有趣的问题，书中描述为：今有雏兔同笼，上有三十五头，下有九十四足，问雏兔各几何？②学生分析其数学解法. （“站立法”，命令所有的兔子都站起来；或用二元一次方程组解答.）③欣赏古代解法：“砍足法”，假如砍去每只鸡、每只兔一半的脚，则“独脚鸡”，“双脚兔”. 则脚的总数47只；与总头数35的差，就是兔子的只数，即47－35＝12（只）.鸡35－12＝23（只）.④试用算法的程序框图解答此经典问题. （算法：鸡的头数为x，则兔的头数为35－x，结合循环语句与条件语句，判断鸡兔脚数2x＋4（35－x）是否等于94.）三、巩固练习：1. 练习：100个和尚吃100个馒头，大和尚一人吃3个，小和尚3人吃一个，求大、小和尚各多少个？分析其算法，写出程序框图. 2. 作业：教材P12 A组1题.第一课时 1.2.1 输入语句、输出语句和赋值语句教学要求：正确理解输入语句、输出语句、赋值语句的结构. 让学生充分地感知、体验应用计算机解决数学问题的方法；并能初步操作、模仿. 通过实例使学生理解3种基本的算法语句（输入语句、输出语句和赋值语句）的表示方法、结构和用法，能用这三种基本的算法语句表示算法，进一步体会算法的基本思想. 教学重点：会用输入语句、输出语句、赋值语句.教学难点：正确理解输入语句、输出语句、赋值语句的作用.教学过程：一、新课导入：1. 提问：学习了哪些算法的表示形式？（自然语言或程序框图描述）算法中的三种基本的逻辑结构？（顺序结构、条件结构和循环结构）2. 导入：我们用自然语言或程序框图描述的算法，计算机是无法“看得懂，听得见”的. 因此还需要将算法用计算机能够理解的程序设计语言翻译成计算机程序. 程序设计语言有很多种. 如BASIC，Foxbase，C语言，C++，J++，VB，VC,JB 等.各种程序设计语言中都包含下列基本的算法语句：输入语句、输出语句、赋值语句条件语句和循环语句.今天，我们一起用类BASIC语言学习输入语句、输出语句、赋值语句. 基本上对应于算法中的顺序结构.二、讲授新课：1. 教学三种语句的格式及功能：①出示例1：编写程序，计算一个学生数学、语文、英语三门课的平均成绩.（分析算法→框图表示→教师给出程序，学生试说说对各语句的理解.）①出示例2：用描点法作函数y＝x3＋3x2－24x＋30的图象时，需要求出自变量和函数的一组对应值. 编写程序，分别计算当x＝－5，－4，－3，－2，－1，0，1，2，3，4，5时的函数值②出示例3：给一个变量重复赋值. （程序见P16）③出示例4：交换两个变量A和B的值，并输出交换前后的值.（教法：先分析算法→画出框图→编写程序→分析各语句→变式→小结：先写算法，再编程）3. 小结：输入、输出和赋值语句的格式；赋值“=”及表达式；编写简单程序解决数学问题.三、巩固练习：1. 练习：教材P16 1、2题 2. 作业：P16 3、4题.第二课时 1.2.2 条件语句教学要求：正确理解条件语句的概念，并掌握其结构. 会应用条件语句编写程序. 教学重点：条件语句的步骤、结构及功能.教学难点：会编写程序中的条件语句.教学过程：一、复习准备：1. 提问：算法的三种逻辑结构？条件结构的框图模式？2. 提问：输入语句、输出语句和赋值语句的格式与功能？3. 一次招生考试中，测试三门课程，如果三门课程的总成绩在200分及以上，则被录取. 请对解决此问题的算法分析，画出程序框图. （变题：…总成绩在200分以下，则不被录取）二、讲授新课：1. 教学条件语句的格式与功能：①分析：复习题③中的两种条件结构的框图模式？②给出复习题③的程序，试读懂程序，说说新的语句的结构及含义.③条件语句的一般有两种：IF—THEN语句；IF—THEN—ELSE语句. 语句格式及框图如下.分析语句执行流程，并说明：①“条件”是由一个关系表达式或逻辑表达式构成，其一般形式为“<表达式><关系运算符><表达式>”，常用的运算符有“>”（大于）、“<”（小于）、“>=”（大于或等于）、“<=”（小于或等于），“<>”（不等于）. 关系表达式的结果可取两个值，以“真”或“假”来表示，“真”表示条件满足，“假”则条件不满足. ②“语句”是由程序语言中所有语句构成的程序段，即可以是语句组. ③条件语句可以嵌套，即条件语句的THEN 或ELSE后面还可以跟条件语句，嵌套时注意内外分层，避免逻辑混乱.2. 教学典型例题：②出示例5：编写程序，输入一元二次方程ax2＋bx＋c＝0的系数，输出它的实数根.（算法分析→画程序框图→编写程序→给出系数的一组值，分析框图与程序各步结果）注意：解方程之前，先由判别式的符号判断方程根的情况. 函数SQR()的功能及格式.②讨论：例5程序中为何要用到条件语句？条件语句一般用在什么情况下？答：一般用在需要对条件进行判断的算法设计中，如判断一个数的正负，确定两个数的大小等问题，还有求分段函数的函数值等，往往要用条件语句，有时甚至要用到条件语句的嵌套③练习：编写程序，使得任意输入的2个实数从小到大排列.④出示例6：编写程序，使得任意输入的3个实数从小到大排列.（讨论：先用什么语句？→用具体的数值给a、b、c，分析计算机如何排列这些数？→写出程序→画出框图→说说算法→变式：如果是4个实数呢？3. 小结：条件语句的格式与功能及对应框图. 编程的一般步骤：①算法分析：根据提供的问题，利用数学及相关学科的知识，设计出解决问题的算法. ②画程序框图：依据算法分析，画出程序框图. ③写出程序：根据程序框图中的算法步骤，逐步写出相应的程序语句.三、巩固练习： 1. 练习：教材P22 1、2题.2. 试编写程序进行印刷品邮资的计算. （前100g 0.7元，以后每100g 0.4元）3. 作业：P22 3、4题.第三课时 1.2.3 循环语句教学要求：正确理解循环语句的概念，并掌握其结构. 会应用循环语句编写程序. 教学重点：两种循环语句的表示方法、结构和用法，用循环语句表示算法.教学难点：理解循环语句的表示方法、结构和用法，会编写程序中的循环语句. 教学过程：一、复习准备：1. 设计一个计算1+2+3+……+10的算法，并画出程序框图.2. 循环结构有哪两种模式？有何区别？相应框图如何表示？答：当型（while 型）和直到型（until 型）. 当型循环语句先对条件判断，根据结果决定是否执行循环体，可能一次也不执行循环体，也称为“前测试型”循环；直到型循环语句先执行一次循环体，再对一些条件进行判断，决定是否继续执行循环体.二、讲授新课：1. 教学两种循环语句的格式与功能：① 给出复习题①的两种循环语句的程序，试读懂程序，说说新的语句的结构及含义.② 两种循环语句的语句结构及框图如下.说明：“循环体”是由语句组成的程序段，能够完成一项工作. 当使用WHIL 语句时，循环内部应当有改变循环的条件，否则会产生无限循环. 学习时注意两种循环语句的区别.③ 讨论：两种循环语句的区别？当型循环先判断后执行，直到型循环先执行后判断，则：在WHILE 语句中，是当条件满足时执行循环体；在UNTIL 语句中，先执行循环体，再当条件不满足时再执行循环体.2. 教学例题：① 出示例：编写程序，计算1+2+3+……+99+100的值.（分析：实现累加的算法 → 分别用两种循环语句编写 → 变题：计算20以内偶数的积.② 给出下列一段程序，试读懂程序，说说各语句的作用，分析程序的功能. （见教材P24）（读，找疑问 → 说各语句 → 分析功能）③ 练习：用描点法作函数y ＝x 3＋3x 2－24x ＋30的图象时，需要求出自变量和函数的一组对应值. 编写程序，分别计算当x ＝－5，－4，－3，－2，－1，0，1，2，3，4，5时的函数值. ④ 分析右边所给出程序：当n=10时，结果是多少？程序INPUT “n=”；ni ＝1 a ＝0 WHILE i <= n a = a ＋(i ＋1)/i i = i+1WENDPRINT “…”；aEND实现功能？3. 小结：① 循环语句的两种不同形式：WHILE 语句和UNTIL 语句（还可补充了For 语句），掌握它们的一般格式.② 在用WHILE 语句和UNTIL 语句编写程序解决问题时，一定要注意它们的格式及条件的表述方法. WHILE 语句中是当条件满足时执行循环体，而UNTIL 语句中是当条件不满足时执行循环体.③ 循环语句主要用来实现算法中的循环结构，在处理一些需要反复执行的运算任务. 如累加求和，累乘求积等问题中常用到.三、巩固练习: 1. 练习：教材P24 1题.2. 编写程序，实现输出1000以内能被3和5整除的所有整数. （算术运算：5 MOD 3 =2）3. 作业：P24 2、3题.第一课时 1.3.1 算法案例---辗转相除法与更相减损术教学要求：理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析； 基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.教学重点：理解辗转相除法与更相减损术求最大公约数的方法.教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言. 教学过程：一、复习准备：1. 回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五种基本语句）.2. 提问：①小学学过的求两个数最大公约数的方法？（先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口算出36和64的最大公约数. ②除了用这种方法外还有没有其它方法？6436128=⨯+，36∴和28的最大公约数就是64和36的最大公约数，反复进行这个步骤，直至842=⨯，得出4即是36和64的最大公约数.二、讲授新课：1. 教学辗转相除法：例1：求两个正数1424和801的最大公约数.分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数. （适用于两数较大时）①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的. 利用辗转相除法求最大公约数的步骤如下：（1）用较大的数m 除以较小的数n 得到一个商0S 和一个余数0R ；（2）若0R ＝0，则n 为m ，n 的最大公约数；若0R ≠0，则用除数n 除以余数0R 得到一个商1S 和一个余数1R ；（3）若1R ＝0，则1R 为m ，n 的最大公约数；若1R ≠0，则用除数0R 除以余数1R 得到一个商2S 和一个余数2R ；……依次计算直至n R ＝0，此时所得到的1n R -即为所求的最大公约数.②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定，所以我们可以把它看成一个循环体，它的程序框图如右图：（师生共析，写出辗转相除法完整的程序框图和程序语言）练习：求两个正数8251和2146的最大公约数. （乘法格式、除法格式）2. 教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.翻译为：（1）任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.例2：用更相减损术求91和49的最大公约数.分析：更相减损术是利用减法将大数化小，直到所得数相等时，这个数（等数）就是所求的最大公约数. （反思：辗转相除法与更相减损术是否存在相通的地方） 练习：用更相减损术求72和168的最大公约数.3. 小结：辗转相除法与更相减损术及比较①都是求最大公约数的方法，辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少；②结果上，辗转相除法体现结果是以相除余数为0得到，而更相减损术则以减数与差相等而得到.三、巩固练习：1、练习：教材P35第1题 2、作业：教材P38第1题 第二课时 1.3.2 算法案例---秦九韶算法教学要求：了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数、提高计算效率的实质；理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用.教学重点：秦九韶算法的特点及其程序设计.教学难点：秦九韶算法的先进性理解及其程序设计.教学过程：一、复习准备：1. 分别用辗转相除法和更相减损术求出两个正数623和1513的最大公约数.2. 设计一个求多项式5432()254367f x x x x x x =--+-+当5x =时的值的算法. （学生自己提出一般的解决方案：将5x =代入多项式进行计算即可）提问：上述算法在计算时共用了多少次乘法运算？多少次加法运算？此方案有何优缺点？(上述算法一共做了5＋4＋3＋2＋1＝15次乘法运算，5次加法运算. 优点是简单、易懂；缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高.)二、讲授新课：1. 教学秦九韶算法：① 提问：在计算x 的幂值时，可以利用前面的计算结果，以减少计算量，即先计算2x ，然后依次计算2x x ⋅，2()x x x ⋅⋅，2(())x x x x ⋅⋅⋅的值，这样计算上述多项式的值，一共需要多少次乘法，多少次加法?（上述算法一共做了4次乘法运算，5次加法运算）② 结论：第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高运算效率，而且对于计算机来说，做一次乘法所需的运算时间比做一次加法要长得多，因此第二种做法能更快地得到结果.③ 更有效的一种算法是：将多项式变形为：5432()254367f x x x x x x =--+-+=，依次计算2555⨯-=，55421⨯-=，2153108⨯+=，10856534⨯-=，534572677⨯+=故(5)2677f =. ――这种算法就是“秦九韶算法”. （注意变形，强调格式） ④ 练习：用秦九韶算法求多项式432()2351f x x x x x =+-++当4x =时的值. （学生板书→师生共评→教师提问：上述算法共需多少次乘法运算？多少次加法运算？）⑤ 如何用秦九韶算法完成一般多项式1110()n n n n f x a x a x a x a --=++++的求值问题？改写：11101210()(()))n n n n n n n f x a x a x a x a a x a x a x a x a ----=++++=+++++. 首先计算最内层括号内一次多项式的值，即11n n v a x a -=+，然后由内向外逐层计算一次多项式的值，即212n v v x a -=+，323n v v x a -=+，，10n n v v x a -=+. ⑥ 结论：秦九韶算法将求n 次多项式的值转化为求n 个一次多项式的值，整个过程只需n 次乘法运算和n 次加法运算；观察上述n 个一次式，可发出k v 的计算要用到1k v -的值，若令0n v a =，可得到下列递推公式：01,(1,2,,)n k k n k v a v v x a k n --=⎧⎨=+=⎩.这是一个反复执行的步骤，因此可用循环结构来实现.⑦ 练习：用秦九韶算法求多项式5432()52 3.5 2.6 1.70.8f x x x x x x =++-+-当5x =时的值并画出程序框图.2. 小结：秦九韶算法的特点及其程序设计三、巩固练习：1、练习：教材P35第2题 2、作业：教材P36第2题 第三课时 1.3.3 算法案例---进位制教学要求：了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换；学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k 去余法，并理解其中的数学规律. 教学重点：各种进位制之间的互化.教学难点：除k 取余法的理解以及各进位制之间转换的程序框图及其程序的设计.教学过程：一、复习准备：1. 试用秦九韶算法求多项式52()42f x x x =-+当3x =时的值，分析此过程共需多少次乘法运算？多少次加法运算？2. 提问：生活中我们常见的数字都是十进制的，但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进制，旧式的秤是十六进制的，计算一打数值时是12进制的......那么什么是进位制？不同的进位制之间又有什么联系呢？二、讲授新课：1. 教学进位制的概念：① 进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几. 如：“满十进一”就是十进制，“满二进一”就是二进制. 同一个数可以用不同的进位制来表示，比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的. 表示各种进位制数一般在数字右下脚加注来表示，如上例中：(2)(8)(16)1110017139==② 一般地，任意一个k 进制数都可以表示成不同位上数字与基数的幂的乘积之和的形式，即1110()1...(0,n n n n k n n n n a a a a a k a a a k a k a ka k a k ----<<≤<=⨯+⨯+⨯+⨯.如：把(2)110011化为十进制数，(2)110011=1⨯25+1⨯24+0⨯23+0⨯22+1⨯21+1⨯20=32+16+2+1=51.把八进制数(8)7348化为十进制数，3210(8)7348783848883816=⨯+⨯+⨯+⨯=.2. 教学进位制之间的互化：①例1：把二进制数(2)1001101化为十进制数.（学生板书→教师点评→师生共同总结将非十进制转为十进制数的方法） 分析此过程的算法过程，编写过程的程序语言. 见P34②练习：将(5)2341、(3)121转化成十进制数.③例2、把89化为二进制数.分析：根据进位制的定义，二进制就是“满二进一”，可以用2连续去除89或所得商，然后取余数. （教师板书）上述方法也可以推广为把十进制化为k 进制数的算法,这种算法成为除k 取余法. ④练习：用除k 取余法将89化为四进制数、六进制数.⑤例3、把二进制数(2)11011.101化为十进制数.解：4(211-=⨯. （小数也可利用上述方法化进行不同进位制之间的互化. ）变式：化为八进制→方法：进制互化3. 小结：进位制的定义；进位制之间的互化.三、巩固练习：1、练习：教材P35第3题 2、作业：教材P38第3题 第四课时 1.3.4 生活中的算法实例教学要求：通过生活实例进一步了解算法思想.教学重点：生活实例的算法分析.教学难点：算法思想的理解.教学过程：一、复习准备：1. 前面学习了哪几种算法案例？每种算法的作用及操作方法是怎样的？2. 算法思想在我们的生活中无处不在，如何利用我们所学习的知识解决生活中的实际问题？二、讲授新课：1. 霍奇森算法：提问：同学们经常会面对一个共同的问题，就是有时有太多的事情要做. 例如，你可能要面临好几门课的作业的最后期限，你如何合理安排以确保每门课的作业都能如期完成？如果根本不可能全部按期完成，你该怎么办？（霍奇森算法可以。

第8课时辗转相除法与更相减损术知识点一辗转相除法1．有关辗转相除法，下列说法正确的是( )A．它和更相减损术一样是求多项式值的一种方法B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直至r<n为止C．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r(0≤r<n)，若r≠0，则将n的值赋给m，r的值赋给n，继续前面步骤，直至r＝0为止D．以上说法皆错答案 C解析由辗转相除法的步骤易知C项正确．2．90与252的最大公约数是( )A．9 B．18 C．27 D．63答案 B解析利用辗转相除法求解．252＝90×2＋7290＝72×1＋1872＝18×4＋0，∴90与252的最大公约数为18．知识点二更相减损术3．更相减损术可解决下列问题中的( )A．求两个正整数的最大公约数B．求多项式的值C．进位制的转化计算D．排序问题答案 A解析更相减损术是解决求两个或两个以上的正整数的最大公约数的．4．如图所示的程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”．执行该程序框图，若输入的a，b分别为14，18，则输出的a＝( )A．0 B．2C．4 D．14答案 B解析第一次执行，输入a＝14，b＝18，因为a<b，所以b＝18－14＝4；第二次执行，因为a＝14，b＝4，a>b，所以a＝14－4＝10；第三次执行，因为a＝10，b＝4，a>b，所以a ＝10－4＝6；第四次执行，因为a＝6，b＝4，a>b，所以a＝6－4＝2；第五次执行，因为a ＝2，b＝4，a<b，所以b＝4－2＝2，此时a＝b＝2．故选B．5．用更相减损术求319与261的最大公约数．解319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29，故319与261的最大公约数是29．易错点更相减损术求最大公约数时忽略乘约简数致误6．用更相减损术求612和468的最大公约数．易错分析当两个数均为偶数时，由于忽略用2约分，而导致错误．正解因为612和468都为偶数，所以两次用2约分化简，得153和117．用更相减损术求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．用更相减损术求得81与135的最大公约数是( )A．54 B．27 C．9 D．81答案 B解析因为135－81＝54，81－54＝27，54－27＝27，所以81与135的最大公约数是27．2．用“辗转相除法”求得459和357的最大公约数是( )A．3 B．9 C．17 D．51答案 D解析459＝357×1＋102，357＝102×3＋51，102＝51×2，所以459和357的最大公约数为51．3．用辗转相除法计算60和48的最大公约数时，需要做的除法次数是( )A．1 B．2 C．3 D．4答案 B解析60＝48×1＋12，48＝12×4＋0，故只需要做两次除法运算．4．下列说法中正确的个数为( )①辗转相除法也叫欧几里得算法；②辗转相除法的基本步骤是用较大的数除以较小的数；③求最大公约数的方法，除辗转相除法之外，没有其他方法；④编写辗转相除法的程序时，要用到循环语句．A．1 B．2 C．3 D．4答案 C解析易知①②④正确；对于③，更相减损术也可求最大公约数，故③错误．5．运行下面的程序，当输入数据为78和36时，输出的值为( )INPUT “输入两个不同正整数m，n＝”；m，nDOIF m>n THENm＝m－nELSE n＝n－mEND IFLOOP UNTIL m＝nPRINT mENDA．24 B．18 C．12 D．6答案 D解析由程序语句知，此程序是用更相减损术求输入的两个数的最大公约数，因为78－36＝42，42－36＝6，36－6＝30，30－6＝24，24－6＝18，18－6＝12，12－6＝6，所以选D．二、填空题6．用更相减损术求104与65的最大公约数是________．答案13解析由于65不是偶数，把104和65以大数减小数，并辗转相减，即104－65＝39，65－39＝26，39－26＝13，26－13＝13，所以104与65的最大公约数为13．7．三个数72，120，168的最大公约数是________．答案24解析120＝72×1＋48，72＝48×1＋24，48＝24×2，168＝24×7．8．阅读程序：INPUT “m，n＝”；m，nIF n>m THENt＝mm＝nn＝tEND IFDOr＝m MOD nm＝nn＝rLOOP UNTIL r＝0PRINT mEND若INPUT语句中输入m，n的值分别是161，368，则程序运行的结果为________．答案23解析该程序的功能是用辗转相除法求两个数的最大公约数．输入161，368，可求出它们的最大公约数为23．三、解答题9．用辗转相除法和更相减损术两种方法求80和36的最大公约数．解用辗转相除法：80＝36×2＋8，36＝8×4＋4，8＝4×2＋0．故80和36的最大公约数是4．用更相减损术：先用2约简得40和18，再用2约简得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的最大公约数是4．10．某化工厂有三种溶液，分别为4200毫升，3220毫升和2520毫升，现要将它们分别装入小瓶中，每个瓶子装入液体的体积相同，问：要使所有溶液都刚好装满小瓶且所用瓶子最少，则小瓶的容积应为多少毫升？解为了使所有溶液都装入瓶中，恰好都装满且所用瓶子最少，求所用瓶子的容积，也就是求这三种溶液的体积的最大公约数．先求4200和3220的最大公约数，4200＝3220×1＋980，3220＝980×3＋280，980＝280×3＋140，280＝140×2，所以4200和3220的最大公约数是140．再求140和2520的最大公约数，2520＝140×18，所以140和2520的最大公约数是140．综上，4200，3220和2520的最大公约数是140．所以小瓶的容积应为140毫升．。

描述：例题：高中数学必修3(人教A版)知识点总结含同步练习题及答案第一章 算法初步 1.1 算法与程序框图一、学习任务1. 了解算法的含义，了解算法的基本思想，能用自然语言描述解决具体问题的算法．2. 了解设计程序框图表达解决问题的过程，了解算法和程序语言的区别；了解程序框图的三种基本逻辑结构，会用程序框图表示简单的常见问题的算法．二、知识清单算法 程序框图三、知识讲解1.算法算法（algorithm）是指按照一定规则解决某一类问题的明确和有限的步骤 ．可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤或序列能够解决一类问题.描述算法可以有不同的方式．例如，可以用自然语言和数学语言加以描述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌.算法的要求：(1)写出的算法，必须能解决一类问题，并且能重复使用；(2)算法过程要能一步一步执行，每一步执行的操作必须确切，不能含混不清，而且经过有限步后能得到结果.下列对算法的理解不正确的是（ ）A．一个算法应包含有限的步骤，而不能是无限的B．算法中的每一个步骤都应当是确定的，而不应当是含糊的、模棱两可的C．算法中的每一个步骤都应当是有效地执行，并得到确定的结果D．一个问题只能设计出一种算法解：D算法的有限性是指包含的步骤是有限的，故 A 正确；算法的确定性是指每一步都是确定的，故 B正确；算法的每一步都是确定的，且每一步都应有确定的结果，故 C 正确；对于同一个问题可以有不同的算法，故 D 错误．下列叙述能称为算法的的个数为（ ）描述：2.程序框图程序框图简称框图，是一种用程序框、流程线及文字说明来表示算法的图形．其中，起、止框是任何流程不可少的，表明程序的开始和结束．输入和输出框可用在算法中任何需要输入、输出的位置．算法中间要处理数据或计算，可分别写在不同的处理框内．一个算法步骤到另一个算法步骤用流程线连接．如果一个框图需要分开来画，要在断开处画上连接点，并标出连接的号码．①植树需要运苗、挖坑、栽苗、浇水这些步骤；②依次进行下列运算：，，，，；③从枣庄乘火车到徐州，从徐州乘飞机到广州；④ ；⑤求所有能被 整除的正整数，即 ．A． B． C． D．解：B①、②、③为算法．1+1=22+1=33+1=4⋯99+1=1003x >x +133,6,9,12,⋯2345写出解方程组的一个算法．解：方法一：代入消元法．　第一步，由 得 ；第二步，将 代入 ，得 ，解得 ；第三步，将 代入方程 ，得 ；第四步，得到方程组的解为 ．方法二：加减消元法．第一步，方程 两边同乘以 ，得 ；第二步，将第一步所得的方程与方程 作差，消去 ，得 ，解得 ；第三步，将 代入方程 ，得 ，解得 ；第四步，得到方程组的解为 ．{2x +y =74x +5y =112x +y =7y =7−2x y =7−2x 4x +5y =114x +5(7−2x )=11x =4x =4y =7−2x y =−1{x =4y =−12x +y =7510x +5y =354x +5y =11y 6x =24x =4x =42x +y =72×4+y =7y =−1{x =4y =−1例题：画程序框图的规则（1）使用标准的图形符号．（2）框图一般按从上到下、从左到右的方向画．（3）除判断框外，大多数流程图符号只有一个进入点和一个退出点．判断框是具有超过一个退出点的惟一符号．（4）判断框分两大类，一类判断框是“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果．（5）在图形符号内描述的语言要非常简练清楚．算法的三种基本逻辑结构顺序结构：语句与语句之间，框与框之间按从上到下的顺序进行．条件分支结构：在一个算法中，经常会遇到一些条件的判断，算法的流程条件是否成立有不同的流向，条件结构就是处理这种过程的结构．循环结构：在一些算法中，经常会出现从某处开始，按照一定的条件反复执行某些步骤的情况，这就是循环结构．下列程序框图分别是解决什么问题的算法．解：（1）已知圆的半径，求圆的面积的算法．（2）求两个实数加法的算法．执行如图的程序框图，输出的 ______ ．解：T =30四、课后作业 （查看更多本章节同步练习题，请到快乐学）某程序框图如图所示，若输出的 ，则判断框内为（ ）A． B． C． D．解：AS =57k >4?k >5?k >6?k >7?已知函数 ，对每次输入的一个值，都得到相应的函数值，画出程序框图．解：f (x )={2x +3,3−x ,x 2x ⩾0x <0x答案：1. 关于算法的说法中，正确的是 A ．算法就是某个问题的解题过程B ．算法执行后可以产生不确定的结果C ．解决某类问题的算法不是唯一的D ．算法可以无限地操作下去不停止C()答案：解析：2. 下列运算不属于我们所讨论算法范畴的是 A ．已知圆的半径求圆的面积B ．随意抽 张扑克牌算到二十四点的可能性C ．已知坐标平面内两点求直线方程D ．加减乘除法运算法则B注意算法需按照一定的顺序进行．()4答案：解析：3. 执行如图所示的程序框图，如果输入的 ，则输出的 属于 ．A ．B ．C ．D ．D取 ，得输出的 ，即可判断．t ∈[−2,2]S ()[−6,−2][−5,−1][−4,5][−3,6]t =−2S =64. 某批发商按客户订单数额的大小分别给予不同的优惠折扣．计算客户应付货款的算法步骤如下： ：输入订单数额 （单位：件）；输入单价 （单位：元）；：若 ，则折扣率 ；若 ，则折扣率 ；若 ，则折扣率 ；若 ，则折扣率 ；：计算应付货款 （单位：元）；：输出应付货款 ．S 1x A S 2x <250d =0250⩽x <500d =0.05500⩽x <1000d =0.10x ⩾1000d =0.15S 3T =Ax (1−d )S 4T。

高中数学第一章算法初步1.3.3进位制练习（含解析）新人教A版必修3知识点一进位制的概念1．关于进制的说法，正确的个数为( )①“几进制”的数，其基数就是几，就“满几进一”；②计算机采用的进制一般都是二进制；③各种进制的数之间可以相互转化；④任何进制的数都必须在右下角标明基数．A．2 B．3 C．4 D．1答案 B解析①②③都是正确的，④中说法不对，因为十进制数一般省略基数．2．以下给出的各数中不可能是八进制数的是( )A．312 B．10110 C．82 D．7457答案 C解析八进制数只用到数字0，1，2，…，7，不会出现数字8．知识点二不同进位制间的转化3．将数30012(4)转化为十进制数为( )A．524 B．774 C．256 D．260答案 B解析30012(4)＝3×44＋0×43＋0×42＋1×41＋2×40＝774．4．已知10b1(2)＝a02(3)，则a＋b的值为________．答案 2解析10b1(2)＝1×20＋b×21＋0×22＋1×23＝9＋2b．a02(3)＝2×30＋0×31＋a×32＝9a＋2，因为10b1(2)＝a02(3)，b∈{0，1}，a∈{0，1，2}，且9＋2b＝9a＋2，所以a＝b＝1，所以a＋b＝2．5．把下列各数转换成十进制数．(1)101101(2)；(2)2102(3)；(3)4301(6)．解(1)101101(2)＝1×25＋0×24＋1×23＋1×22＋0×2＋1＝45．(2)2102(3)＝2×33＋1×32＋2＝65．(3)4301(6)＝4×63＋3×62＋1＝973．易错点对进位制转换的方法掌握不牢致错6．把十进制数48化为二进制数．易错分析由于基础知识，基本方法掌握不牢而错将结果写成11(2)．正解如下图所示，得48＝110000(2)．一、选择题1．将二进制数110101(2)转换成十进制数是( )A．105 B．54 C．53 D．29答案 C解析按照二进制数转换成十进制数的方法，可得十进制数是53．2．已知k进制数132与十进制数30相等，则k的值为( )A．－7或4 B．－7C．4 D．以上都不对答案 C解析132(k)＝1×k2＋3×k＋2＝k2＋3k＋2，所以k2＋3k＋2＝30，解得k＝4或k＝－7(舍去)，所以k＝4．3．如图是把二进制的数11111(2)化成十进制数的一个程序框图，则判断框内应填入的条件是( )A．i≤4? B．i≤5? C．i＞4? D．i＞5?答案 A解析11111(2)＝1×20＋1×21＋1×22＋1×23＋1×24＝2×(2×(2×(2×1＋1)＋1)＋1)＋1．(秦九韶算法)11111(2)＝31＝2×15＋1＝2×(2×7＋1)＋1＝2×(2×(2×3＋1)＋1)＋1＝2×(2×(2×(2×1＋1)＋1)＋1)＋1．故选A．4．下列各数中最小的数是( )A．101010(2) B．210(8)C．1001(16) D．81答案 A解析101010(2)＝1×25＋0×24＋1×23＋0×22＋1×21＋0×20＝42，210(8)＝2×82＋1×81＋0×80＝136，1001(16)＝1×163＋0×162＋0×16＋1×160＝4097，故选A．5．计算机中常用十六进制，采用数字0～9和字母A～F共16个计数符号，与十进制的对应关系如下表：例如用十六进制表示D＋E＝1B，则(2×F＋1)×4＝( )A．6E B．7C C．5F D．B0答案B解析(2×F＋1)×4用十进制可以表示为(2×15＋1)×4＝124，而124＝16×7＋12，所以用十六进制表示为7C，故选B．二、填空题6．若六进制数13m502(6)化为十进制数为12710，则m＝________．答案 4解析 根据将k 进制数转化为十进制数的方法有13m502(6)＝1×65＋3×64＋m×63＋5×62＋0×61＋2＝12710，解得m ＝4．7．(1)三位四进制数中的最大数等于十进制数的是________；(2)把389化为四进制数，则该数的末位是________．答案 (1)63 (2)1解析 (1)本题主要考查算法案例中进位制的原理．三位四进制数中的最大数为333(4)，则333(4)＝3×42＋3×41＋3＝63．(2)解法一：由389＝4×97＋1，97＝4×24＋1，24＝4×6＋0，6＝4×1＋2，1＝4×0＋1，389化为四进制数的末位是第一个除法代数式中的余数1．解法二：以4作为除数，相应的除法算式如图所示，所以389＝12011(4)．显然该数的末位是1．8．已知三个数12(16)，25(7)，33(4)，则它们按由小到大的顺序排列为________．答案 33(4)<12(16)<25(7)解析 将三个数都化为十进制数，则12(16)＝1×16＋2＝18，25(7)＝2×7＋5＝19，33(4)＝3×4＋3＝15，∴33(4)<12(16)<25(7)．三、解答题9．若二进制数100y011(2)(y ＝0或1)和八进制数x03(8)(0≤x≤8，x ∈N )相等，求x ＋y 的值．解 ∵100y 011(2)＝1×26＋y ×23＋1×21＋1＝67＋8y ，x 03(8)＝x ×82＋3＝64x ＋3，∴8y ＋67＝64x ＋3， y 可取0或1，x 可取1，2，3，4，5，6，7，当y ＝0时，x ＝1；当y ＝1时，64x ＋3＝75，x ＝98，不符合题意，∴x ＋y ＝1． 10．古时候，当边境有敌人来犯时，守边的官兵通过在烽火台上点火向境内报告，如下图所示，烽火台上点火表示数字1，未点火表示数字0，约定二进制数对应的十进制数的单位是1000，请你计算一下，这组烽火台表示有多少敌人入侵？解由题图可知这组烽火台表示的二进制数为11011(2)，它表示的十进制数为1×24＋1×23＋0×22＋1×21＋1×20＝27，由于二进制数对应的十进制数的单位是1000，所以入侵的敌人的数目为27×1000＝27000．。