下载文档原格式
普通高中课程标准数学3（必修）1.1.1第法的概念C约2课时J* ☆—、夏目引入算法作为一个名词，在中学教科书中并没有出现过，我们在基础教育阶段还没有接触算法概念。
但是我们却从小学就开始接触算法，熟悉许多问题的算法。
如，做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法,至于乘法□诀、珠算□诀更是算法的具体体现。
广义地说，算法就是做某一件事的步骤或程菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。
在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。
（古代的计算工具：算筹与算盘.20世纪最伟大的发明：计算机，计算机是强大的实现各种算法的工具。
）f、夏目引入问：要把大象装冰箱，分几步？哈哈二、理凹问题2、现有九枚硬币，有一枚略重，你能用天平（不用 决这一问题。
S2：在重的一份里取两枚放天 平的两边，若平衡则剩下的一 枚就是所找的，若不平衡则重 的那枚就是所要找的。
祛码）将其找出来吗？设廿种最有效的方法，解S1：把九枚硬币平均分成三份, 若平衡则重的在剩下的一份里, 取其中两份放天平上称， 若不平衡则在重的一份里;二、理凹问题3•—个农夫带着一只狼、一头山羊和一篮蔬菜要过河，但只有一条小船。
乘船时，农夫只能带一样东西。
当农夫在场的时候，这三样东西相安无事，一旦农夫不在，狼会吃羊，羊会吃菜。
请设计一个方案，使农夫能安全地将这三样东西带过河。
IIS1：农夫带羊过河；S3:农夫带狼过河；S5:农夫带蔬菜过河; S7 :农夫带羊过河。
S2:农夫独自回来; S4:农夫带羊S6:农夫独自回来;概念1 .算法(algorithm)算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必须是明确的和有效的，而且能够在有限步之内完成的。
• • •—般来说, “用算法解决问题”可以利用计算机帮助完成。
例1・写出交换两个大小相同的杯子中的液体（A水、B酒）的一个算法。
图1.1.1-1 1.1.1算法的概念【目标要求】1．了解算法的概念，了解算法的确定性、能行性、有穷性和有输出性等特征.2．初步了解用高斯消去法的思想.3．初步掌握Scilab 程序指令解二元一次方程组的方法.【巩固教材——稳扎马步】1.下面的结论正确的是 （ ）A. 一个程序的算法步骤是可逆的B.一个算法可以无止境地运算下去的C. 完成一件事情的算法有且只有一种D.设计算法要本着简单方便的原则2. 早上从起床到出门需要洗脸刷牙(5 min)、刷水壶(2 min)、烧水(8 min)、泡面(3 min)、吃饭(10 min)、听广播(8 min)几个步骤、从下列选项中选最好的一种算法 ( )A. S1 洗脸刷牙、S2刷水壶、S3 烧水、S4 泡面、S5 吃饭、S6 听广播B. S1刷水壶 、S2烧水同时洗脸刷牙、S3泡面、S4吃饭、S5 听广播C. S1刷水壶 、S2烧水同时洗脸刷牙、S3泡面、S4吃饭 同时 听广播D. S1吃饭 同时 听广播、S2泡面、S3烧水同时洗脸刷牙、S4刷水壶3.对算法的描述有①对一类问题都有效；②对个别问题有效；③计算可以一步步地进行，每一步都有惟一的结果；④是一种通法，只要按部就班地做，总能得到结果．以上正确描述算法的有 ( )A ．1个B ．2个C ．3个D ．4个4.用Scilab 指令解二元一次方程组2121x y x y -=-⎧⎨+=⎩时, 在界面上的输入应该是( ) A ．[1,2,2,1][1,1]A B =-=- B ．[1,2;2,1][1;1]A B =-=- C ．[1,2,2,1][1,1]A B =-=- D ．[1,2;2,1][1;1]A B =-=- 5.以下对算法的描述中，正确的有 （ ） ①对一类问题都有效 ②对个别问题有效 ③计算可以一步步地进行，每一步都有唯一的结果 ④是一种通法，只要按部就班地做，总能得到结果. A ． 1个 B. 2个 C. 3个 D. 4个 【重难突破——重拳出击】 6. 阅读图1.1.1-1流程图，则输出的结果是 ( ) A ．4 B ．5 C ．6 D ．13 7. 写出求 1+2+3+4+5+6……+100 的一个算法, 可运用公式 1+2+3+……+ n=2)1(+n n 直接计算 .其一个算法为: S1 ;S2 ;S3 输出计算结果8. 已知一个学生的语文成绩为89，数学成绩为96，外语成绩为99.求他的总分和平均成绩的一个算法为：S1 取A=89 ， B =96 C=99 ；S2 ; S3 ; S4 输出计算的结果9. 写出解二元一次方程组21(1)21(2)x yx y-=-⎧⎨+=⎩的算法.10.用二分法设计一个求方程250x-=的近似根的算法.【巩固提高——登峰揽月】11．写出求过两点M(-2,-1)、N(2,3)的直线与坐标轴围成面积的一个算法.12. 用Scilab 计算指令解方程组2065237x y z x y z x y z ++=⎧⎪--=-⎨⎪+-=-⎩.13. “鸡兔同笼“是我国隋朝时期的数学著作《孙子算经》中的一个有趣而具有深远影响的题目：“今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何.用方程组的思想不难解决这一问题，请你设计一个这类问题的通用算法.【课外拓展——超越自我】14. 写出交换两个大小相同的杯子中的液体(A 水、 B 酒) 的两个算法.1. D2. C3. C4. B5. C6. D7.第一步 取n=100 ;第二步 计算2)1(+n n . 8. S2 计算总分D=A+B+C ; S3 计算平均成绩E=3D . 9. 解：S1:(2)-(1)×2得53y = (3) ；S2: 解(3) 得35y = ; S3: 将35y =代入(1)，得15x = . 10. 解析:S1:令2()5f x x =- .因为(2)0,(3)0f f <>, 所以设122,3x x == .S2: 令122x x m +=, 判断()f m 是否为0 .若是, 则m 为所求; 若否,则继续判断1()()f x f m 大于0还是小于0 .S3: 若1()()0f x f m >, 则令1x m =; 否则令2x m = .S4: 判断12||0.005x x -<是否成立? 若是, 则1x 、2x 之间的任意取值均为满足条件的近似根; 若否, 则返回第二步.S5 输出计算的结果 .11. 解：算法：S1：取x 1=-2，y 1=-1，x 2=2，y 2=3；S2：计算121121x x x x y y y y --=--； S3：在第二步结果中令x =0得到y 的值m ，得直线与y 轴交点(0,m)；S4：在第二步结果中令y =0得到x 的值n ，得直线与x 轴交点(n,0)；S5：计算S=1||||2m n ⋅； S6：输出运算结果12. 解: 输入方程组的系数与常数项[2,1,1;1,1,1;5,2,3][0;6;7](,)!2!!3!!1!A B linsolve A B ans ->=---->=--->=-这个方程组的解是2,3,1x y z =-== . 13. 解析: 鸡兔同笼，设鸡兔总头数为H ，总脚数为F ，求鸡兔各有多少只.算法如下： S1 输入总头数H ，总脚数F ；S2 计算鸡的个数 x=(4*H －F)/ 2S3 计算兔的个数 y=(F －2*H)/2;S4 输出 x y14. 算法1S1:找一个大小与A 相同的空杯子CS2:将A 中的水倒入C 中S3:将B 中的酒精倒入A 中S4:将C 中的水倒入B 中，结束.算法2S1:再找两个空杯子C 和DS2:将A 中的水倒入C 中，将B 中的酒倒入D 中；S3:将C 中的水倒入B 中，将D 中的酒倒入A 中，结束注意： 一个算法往往具有代表性，能解决一类问题，如，例一可以 引申为：交换两个变量的值.。
高中数学 1.1.1算法的概念讲解新人教A版必修3 1．算法的概念：对一类问题的机械的、统一的求解方法．算法是由基本运算及规定的运算顺序所构成的完整的解题步骤，或者是按照要求设计好的有限的计算序列，并且这样的步骤或序列能解决一类问题．2．算法的重要特征：（1）有限性：一个算法在执行有限步后必须结束；（2）确定性：算法的每一个步骤和次序必须是确定的；（3）输入：一个算法有0个或多个输入，以刻划运算对象的初始条件．所谓0个输入是指算法本身定出了初始条件．（4）输出：一个算法有1个或多个输出，以反映对输入数据加工后的结果．没有输出的算法是毫无意义的．算法作为一个名词，在中学教科书中并没有出现过，我们在基础教育阶段还没有接触算法概念。
但是我们却从小学就开始接触算法，熟悉许多问题的算法。
如，做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体体现。
我们知道解一元二次方程的算法，求解一元一次不等式、一元二次不等式的算法，解线性方程组的算法，求两个数的最大公因数的算法等。
因此，算法其实是重要的数学对象。
算法(al gorithm)一词源于算术(algorism)，即算术方法，是指一个由已知推求未知的运算过程。
后来，人们把它推广到一般，把进行某一工作的方法和步骤称为算法。
广义地说，算法就是做某一件事的步骤或程序。
菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。
在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。
比如解方程的算法、函数求值的算法、作图的算法，等等。
要点一：算法的有限性和确定性例1 任意给定一个大于1的整数n，试设计一个程序或步骤对n是否为质数做出判定。
解析：根据质数的定义判断解：算法如下：第一步：判断n是否等于2，若n=2，则n是质数；若n>2，则执行第二步。
第二步：依次从2至（n-1）检验是不是n的因数，即整除n的数，若有这样的数，则n不是质数；若没有这样的数，则n是质数。
![高中数学必修三[人教B版]1.1.1《算法的概念》ppt课件6](https://img.taocdn.com/s1/m/2389b05ac8d376eeafaa3166.png)
1.1.1 算法的概念算法是指完成一个任务所需要的具体步骤和方法。
也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。
算法常常含有重复的步骤和一些比较或逻辑判断。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
〖算法的历史〗“算法” (algorithm)来自于9世纪波斯数学家比阿勒•霍瓦里松的名字al-Khwarizmi ,比阿勒•霍瓦里松在数学上提出了算法这个概念。
“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm" 第一次编写算法是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。
因为巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。
因为"well-defined procedure" 缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。
20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。
图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。
〖算法的特征〗一个算法应该具有以下五个重要的特征:有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义；输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的；可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
§1.1.1 算法的概念（两个课时）教学目标: (1)了解算法的含义，体会算法的思想。
(2)能够用自然语言叙述算法。
(3)掌握正确的算法应满足的要求。
(4)会写出解线性方程（组）的算法。
(5)会写出一个求有限整数序列中的最大值的算法。
教学重点: 算法的含义、解二元一次方程组和判断一个数为质数的算法设计。
.教学难点: 把自然语言转化为算法语言。
.学法：1、写出的算法，必须能解决一类问题(如：判断一个整数n(n>1)是否为质数；求任意一个方程的近似解；……)，并且能够重复使用。
2、要使算法尽量简单、步骤尽量少。
3、要保证算法正确，且计算机能够执行，如：让计算机计算1×2×3×4×5是可以做到的，但让计算机去执行“倒一杯水”“替我理发”等则是做不到的。
教学过程一、章头图体现了中国古代数学与现代计算机科学的联系，它们的基础都是“算法”。
算法作为一个名词，在中学教科书中并没有出现过，我们在基础教育阶段还没有接触算法概念。
但是我们却从小学就开始接触算法，熟悉许多问题的算法。
如，做四则运算要先乘除后加减，从里往外脱括弧，竖式笔算等都是算法，至于乘法口诀、珠算口诀更是算法的具体体现。
广义地说，算法就是做某一件事的步骤或程序。
菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。
在数学中，主要研究计算机能实现的算法，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。
(古代的计算工具：算筹与算盘. 20世纪最伟大的发明：计算机，计算机是强大的实现各种算法的工具。
)例1：解二元一次方程组： ⎩⎨⎧=+-=-②y x ①y x 1212 分析：解二元一次方程组的主要思想是消元的思想，有代入消元和加减消元两种消元的方法，下面用加减消元法写出它的求解过程.解：第一步：② - ①×2，得： 5y=3； ③第二步：解③得 53=y ； 第三步：将53=y 代入①，得 51=x . 学生探究：对于一般的二元一次方程组来说，上述步骤应该怎样进一步完善？老师评析：本题的算法是由加减消元法求解的，这个算法也适合一般的二元一次方程组的解法。
课题：§算法的概念
一、教学目标：
1、知识目标：
⑴使学生理解算法的概念。
⑵掌握简单问题算法的表述。
⑶初步了解高斯消去法的思想．
⑷了解利用scilab求二元一次方程组解的方法。
2、能力目标：
①逻辑思维能力：通过分析、抽象、程序化高斯消去法的过程，体会算法的思想，发展有条理
地清晰地思维的能力，提高学生的算法素养。
②创新能力：通过分析高斯消去法的过程，发展对具体问题的过程与步骤的分析能力，发
展从具体问题中提炼算法思想的能力。
3、情感目标：
通过体验算法表述的过程，培养学生的创新意识和逻辑思维能力；通过
应用数学软件解决问题，感受算法思想的重要性，感受现代信息技术的
威力，提高学生的学习兴趣。
二、重点与难点
重点：算法的概念和算法的合理表述。
难点：算法的合理表述、高斯消去法．。
三、教学方法与手段：
采用“问题探究式”教学法，以多媒体为辅助手段，让学生主动发现问
题、分析问题、解决问题，培养学生的探究论证、逻辑思维能力。
三、教学过程：。
1.1.1 算法的概念算法是指完成一个任务所需要的具体步骤和方法。
也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。
算法常常含有重复的步骤和一些比较或逻辑判断。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
〖算法的历史〗“算法” (algorithm)来自于9世纪波斯数学家比阿勒•霍瓦里松的名字al-Khwarizmi ,比阿勒•霍瓦里松在数学上提出了算法这个概念。
“算法”原为"algorism"，意思是阿拉伯数字的运算法则，在18世纪演变为"algorithm" 第一次编写算法是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。
因为巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。
因为"well-defined procedure" 缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。
20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。
图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。
〖算法的特征〗一个算法应该具有以下五个重要的特征:有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义；输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的；可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
〖形式化算法〗算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。
一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。
〖算法的实现〗算法不单单可以用计算机程序来实现，也可以在神经网络、电路或者机械设备上实现。
•例子这是算法的一个简单的例子。
我们有一串随机数列。
我们的目的是找到这个数列中最大的数。
如果将数列中的每一个数字看成是一颗豆子的大小，可以将下面的算法形象地称为“捡豆子”：首先将第一颗豆子放入口袋中。
从第二颗豆子开始检查，直到最后一颗豆子。
如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先口袋中的豆子。
最后口袋中的豆子就是所有的豆子中最大的一颗。
下面是一个形式算法，用近似于编程语言的伪代码表示给定：一个数列“list"，以及数列的长度"le ngth(list)"largest = list[1]for coun ter = 2 to len gth(list):if list[co un ter] > largest:largest = list[co un ter]print largest符号说明：=用于表示赋值。
即：右边的值被赋予给左边的变量。
List[counter] 用于表示数列中的第counter项。
例如：如果counter的值是5,那么List[counter] 表示数列中的第5项。
<=用于表示“小于或等于”。
==例子==求两个自然数的最大公约数设两个变量M和N 1.如果M < N,则交换M和N2.以N除以M,得到余数R3.判断R = 0,正确则N即为“最大公约数”，否则下一步4.将N赋值给M,将R赋值给N，重做第一步。
用“ Basic代码”表示——If M < N The n Swap M,N Do While R <> 0R = M Mod NM = NN = RLoop Print R〖算法设计和分析的基本方法〗分治法：字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）……动态规划：动态规划在查找有很多重叠子问题的情况的最优解时有效。
它将问题重新组合成子问题。
为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。
因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
贪心法（亦作饕餮法）：就是一种在每一步选择中都采取在当前状态下最好/优的选择，从而希望导致结果是最好/优的算法。
贪心法可以解决一些最优性问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。
一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。
由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
〖算法的分类〗•基本算法〔枚举搜索（深度优先搜索广度优先搜索启发式搜索遗传算法）〕•数据结构的算法•数论与代数算法•计算几何的算法（凸包算法）•图论的算法（哈夫曼编码树的遍历最短路径算法最小生成树算法最小树形图网络流算法匹配算法）•动态规划•其他（数值分析加密算法排序算法检索算法随机化算法）还可以分成串行算法、并行算法。
〖算法的复杂性〗算法的复杂性是算法效率的度量，在评价算法性能时，复杂性是一个重要的依据。
算法的复杂性的程度与运行该算法所需要的计算机资源的多少有关，所需要的资源越多，表明该算法的复杂性越高；所需要的资源越少，表明该算法的复杂性越低。
计算机的资源，最重要的是运算所需的时间和存储程序和数据所需的空间资源，算法的复杂性有时间复杂性和空间复杂性之分。
算法在计算机上执行运算，需要一定的存储空间存放描述算法的程序和算法所需的数据，计算机完成运算任务需要一定的时间。
根据不同的算法写出的程序放在计算机上运算时，所需要的时间和空间是不同的，算法的复杂性是对算法运算所需时间和空间的一种度量。
不同的计算机其运算速度相差很大，在衡量一个算法的复杂性要注意到这一点。
对于任意给定的问题，设计出复杂性尽可能低的算法是在设计算法时考虑的一个重要目标。
另外，当给定的问题已有多种算法时，选择其中复杂性最低者，是在选用算法时应遵循的一个重要准则。
因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
在讨论算法的复杂性时，有两个问题要弄清楚：(1) 一个算法的复杂性用怎样的一个量来表达；(2) 怎样计算一个给定算法的复杂性。
找到求解一个问题的算法后，接着就是该算法的实现，至于是否可以找到实现的方法，取决于算法的可计算性和计算的复杂性，该问题是否存在求解算法，能否提供算法所需要的时间资源和空间资源。
筛选法求质数质数亦叫作素数，是大于1 的自然数，并且除了该数本身和1 以外没有其它的数能整除它，女口2, 3, 5, 7, 11, 13,…，质数有无穷多个。
(1 )判断143 是否为质数。
解：Stepl : 143—2不为整数;Step2: 143-3不为整数；Step3: 143-4不为整数；Step4: 143-5不为整数；Step5: 143-6不为整数；Step6: 143-7不为整数；Step7: 143-8不为整数；Step8: 143-9不为整数；Step9: 143—10不为整数；StepIO: 143- 11=13, 143 能被11 整除;Stepll:结论：143不是质数。
（2）判断17 是否为质数。
解:Step1 : 17 + 2不为整数；Step2: 17 + 3不为整数；Step3: 17 + 4不为整数；Step4: 17 + 5不为整数；Step5: 17 + 6不为整数；Step6: 17 + 7不为整数；Step7: 17 + 8不为整数；Step8: 17 + 9不为整数；Step9: 17 - 10不为整数；Step1O: 17—11 不为整数;Stepll: 17—12 不为整数;Step12: 17—13 不为整数;Step13: 17—14 不为整数;Step14: 17—15 不为整数;Step15: 17—16 不为整数;Step16:结论：17是质数。
3）判断216091 是不是质数该题的计算量非常大，我们可以把算法编为程序，由计算机帮我们计算。
（4）设计一个算法，输入大于2的整数n由计算机判断它是不是质数。
解: Step1 :输入整数n;Step2 :依次检验2~（n-1）是不是n的因数，若有这样的数，则n不是质数，否则，n为质数。
Step3 :输出结果。
说明:其中第3 步在计算机中可以通过一个循环来实现，今后会学到。
