课件39张PPT。第二章算法初步相传在古代印度的贝拿勒斯神庙，有一块黄铜板上插了三根宝石柱A，B，C，在其中一根宝石柱A上自上而下、由小到大地叠放着若干个大小不等的金盘．一名僧人要把这些金盘从宝石柱A移到另外一根宝石柱C上，也是自上而下、由小到大地叠放．僧人在移动金盘时遵守下面两条规则：第一，可以利用中间一根宝石柱B作为辅助，但一次只能移动一个金盘；第二，任何时候都不能把大的金盘放到小的金盘上．
如果僧人把六十四个金盘从宝石柱A全部移到另外一根宝石柱C上，世界末日就要到了．当然，从僧人搬完六十四个金盘所需时间的角度来说，即使僧人每秒都能移动一个金盘，用最优算法，那也得要几千亿年！现代社会是一个信息化的社会，知识更新特点就是一个字“快”，当我们学好了算法，我们就拥有更强的思维能力．同时，算法也是电脑编程的基础，学好了算法，再学电脑编程，更是如鱼得水．为了能跟上时代的步伐，在这个信息化的社会中表现得更优秀，请让我们一起以最认真的态度努力学好算法初步这一章．§1 算法的基本思想自主预习学案电影《神枪手》中描述的凌靖是一个天生的狙击手，他百发百中，最难打的位置对他来说也是轻而易举，是香港警察狙击手队伍的第一神枪手．
作为一名狙击手，要想成功地完成一次狙击任务，一般要按步骤完成以下几步：
第一步：观察、等待目标出现(用望远镜或瞄准镜)；
第二步：瞄准目标；
第三步：计算(或估测)风速、距离、空气湿度、空气密度；
第四步：根据第三步的结果修正弹着点；
第五步：开枪；
第六步：迅速转移(或隐蔽)．
以上这种完成狙击任务的方法、步骤在数学上我们叫算法．1．算法的概念
算法是解决某类问题的一系列________或________，只要按照这些________执行，都能使问题得到解决．一般来说，“__________________”都是可以利用计算机帮助完成的．
2．算法的基本思想
在解决某些问题时，需要设计出________________________的步骤，通过实施这些步骤来解决问题，通常把这些步骤称为解决这些问题的________.这种解决问题的思想方法称为算法的基本思想．步骤 程序 步骤 用算法解决问题 一系列可操作或可计算 算法 3．算法的特征
(1)__________：一个算法应包括有限的操作步骤，能在执行有穷的操作步骤之后结束．
(2)__________：算法的计算规则及相应的计算步骤必须是唯一确定的．
(3)__________：算法中的每一个步骤都是可以在有限的时间内完成的基本操作，并能得到确定的结果．
(4)__________：算法从初始步骤开始，分为若干个明确的步骤，前一步是后一步的前提，后一步是前一步的后续，且除了最后一步外，每一个步骤只有一个确定的后续．
(5)____________：解决同一问题的算法可以是不唯一的．有限性 确定性 可行性 顺序性 不唯一性 1．以下对算法的描述正确的个数是( )
①对一类问题都有效；
②对个别问题有效；
③计算可以一步步地进行，每一步都有唯一的结果；
④是一种通法，只要按部就班地做，总能得到结果．
A．1个 B．2个
C．3个 D．4个
[解析] ①③④正确，均符合算法的概念与要求，②不正确．C
2．下列四种叙述能称为算法的是( )
A．在家里一般是爸爸做饭
B．做饭需要刷锅、淘米、加水、加热这些步骤
C．在野外做饭叫野炊
D．做饭必须有米
[解析] B答案描述的是解决一类问题的方法，能称为算法，故选B．B3．下面给出了解决问题的算法：
S1 输入x；
S2 若x≤1，则y＝2x－1，否则y＝x2＋3；
S3 输出y.
(1)这个算法解决的问题是：_______________________________________.
(2)当输入的x值为______时，输入值与输出值相等．1 互动探究学案命题方向1 ?对算法意义的理解B 下列说法正确的是( )
A．算法就是某个问题的解题过程
B．算法执行后可以产生不同的结果
C．解决某一个具体问题时，算法不同，结果不同
D．算法执行步骤的次数不可以很大，否则无法实施[思路分析] 解答本题的关键是理解算法的意义及特征．
[解析] 选项A，算法不能等同于解法；选项C，解决某一个具体问题，算法不同结果应该相同，否则就是算法构造得有问题；选项D，算法执行的步骤可以有很多次，但不可以是无限次．『规律总结』 算法一般是机械的，有时需要进行大量的重复计算．只要按部就班地去做，总能算出结果．通常把算法过程称为“数学机械化”．数学机械化的最大优点是它可以借助计算机来完成．
〔跟踪练习1〕 指出下列哪个不是算法( )
A．解方程2x－6＝0的过程是移项和系数化为1
B．从青岛经上海再到杭州旅游要先乘轮船到上海，再转乘火车
C．解方程2x2＋x－1＝0
D．利用公式S＝πr2计算半径为3的圆的面积就是计算π×32
[解析] 由算法概念知，C不是算法，而A、B、D三项都解决了一类问题，故为算法．C命题方向2 ?筛选问题的算法设计[解析] 算法步骤如下：
1．比较a与b的大小，若a
2．比较m与c的大小，若m〔跟踪练习2〕 在下列数字序列中，写出搜索89的算法：
21,3,0,9,15,72,89,91,93.
[解析] 1.先找到序列中的第一个数m，m＝21；
2．将m与89比较，是否相等，如果相等，则搜索到89；
3．如果m与89不相等，则往下执行；
4．继续将序列中的其他数赋给m，重复第2步，直到搜索到89.命题方向3 ?数值性问题的算法『规律总结』 本题的解法二体现了算法的本质：对一类问题的机械的、统一的求解方法．将步骤一直写下去，便得到任意有限个数相加的算法．运用公式使算法显得简单，特别地，当加数的个数比较多时，解法二便显示出了它的优越性．
〔跟踪练习3〕 写出求2×4×6×8×10值的算法．
[解析] 算法如下：
1．计算2×4，得到8.
2．将第1步的运算结果8与6相乘，得到48.
3．将第2步的运算结果48与8相乘，得到384.
4．将第3步的运算结果384与10相乘，得到3 840.命题方向4 ?非数值性问题的算法 有蓝和黑两个墨水瓶，但现在却错把蓝墨水装在了黑墨水瓶中，黑墨水错装在了蓝墨水瓶中，要求将其互换，请你设计算法解决这一问题．
[思路分析] 由于两个墨水瓶中的墨水不能直接交换，故可以考虑通过引入第三个空墨水瓶的办法进行交换．[解析] 算法步骤如下：
1．取一只空的墨水瓶，设其为白色．
2．将黑墨水瓶中的蓝墨水装入白瓶中．
3．将蓝墨水瓶中的黑墨水装入黑瓶中．
4．将白瓶中的蓝墨水装入蓝瓶中．
5．交换结束．『规律总结』 对于非数值问题，应当首先建立过程模型，根据过程设计步骤，完成算法，在设计算法时应简洁、清晰，要善于分析任何可能出现的情况以体现思维的严谨性．〔跟踪练习4〕 两个大人和两个小孩一起渡河，渡口只有一条小船，每次只能渡一个大人或两个小孩，他们四人都会划船，但都不会游泳，他们如何渡河？请写出你的渡河方案及算法．
[解析] 因为一次只能渡过一个大人或两个小孩，而船还要回来渡其他人，所以只能让两个小孩先过河，渡河的方案算法为：
1．两个小孩同船渡过河去；
2．一个小孩划船回来；
3．一个大人独自划船渡过河去；
4．对岸的小孩划船回来；
5．两个小孩再同船渡过河去；
6．一个小孩划船回来；
7．余下的一个大人独自划船渡过河去；
8．对岸的小孩划船回来；
9．两个小孩再同船渡过河去． 设计一个算法，求1＋2＋4＋…＋249的值．
[错解] 算法如下：
1．令i＝0，S＝0.
2．S＝S＋2i.
3．i＝i＋1.
4．判断i是否大于等于49，若成立，则输出S，结束算法；否则返回第二步重新执行．[辨析] 判断条件是i大于49，还是大于等于49，关键是看i能否取到49.当判断条件为“i大于等于49”时实际计算的是1＋2＋4＋…＋248的值，故判断条件应为i大于49.
[正解] 算法如下：
1．令i＝0，S＝0.
2．S＝S＋2i.
3．i＝i＋1.
4．判断i是否大于49，若成立，则输出S，结束算法；否则返回第二步重新执行．分类讨论思想 写出解方程ax2＋bx＋c＝0(a、b、c为实数)的一个算法．
[思路分析] 分a＝0和a≠0两种情况讨论：当a＝0时，分①b＝0，c＝0，②b＝0，c≠0，③b≠0三种情况讨论；当a≠0时，分Δ>0，Δ＝0，Δ<0三种情况讨论．
[解析] 1.当a＝0，b＝0，c＝0时，原方程的解为全体实数．
2．当a＝0，b＝0，c≠0时，原方程没有实数解．1．下列说法中不能看成算法的是( )
A．植树需要运苗、挖坑、栽苗、浇水这些步骤
B．烹制红烧肉的菜谱
C．从山东济南乘火车到北京，再从北京乘飞机到伦敦
D．小明不会洗衣服
[解析] 只要按步骤完成某项任务就是一个算法，很明显A、B、C都是按步骤完成某项任务的，均是算法，而D中仅仅说明了一个事实，不是算法．D
2．算法的每一步都应该是正确的、能有效执行的，并且能得到明确的结果，这是指算法的( )
A．有穷性 B．确定性
C．逻辑性 D．不唯一性
[解析] 算法的过程和每一步的结果都是确定的，即确定性．B3．下列语句中是算法的个数是( )
①从广州到北京旅游，先坐火车， 再坐飞机抵达；
②解一元一次方程的步骤是去分母、去括号、移项、合并同类项、系数化为1；
③方程x2－1＝0有两个实根；
④求1＋2＋3＋4的值，先计算1＋2＝3，再由3＋3＝6,6＋4＝10得最终结果10.
A．1个 B．2个
C．3个 D．4个C[解析] ①中说明了从广州到北京的行程安排，完成任务；②中给出了一元一次方程这一类问题的解决方法；④中给出了求1＋2＋3＋4的一个过程，最终得出结果．对于③，并没有说明如何去算，故①②④是算法，③不是算法．4．设计一个算法求方程5x＋2y＝22的正整数解，其最后输出的结果应为______________.(2,6)，(4,1) 第二章 §1
A级 基础巩固
一、选择题
1．算法的有限性是指( C )
A．算法的最后必包含输出
B．算法中每个操作步骤都是可执行的
C．算法的步骤必须有限
D．以上说法均不正确
[解析] 由算法的要求可知，一个算法必须执行有限步后得出结果．
2．下面的结论正确的是( D )
A．一个程序的算法步骤是可逆的
B．一个算法可以无止境地运算下去
C．完成一件事情的算法有且只有一种
D．设计算法要本着简单方便的原则
[解析] 选项A不正确，算法只需要每一步都可以顺利进行，并且结果唯一，不能保证可逆．选项B不正确，一个算法必须在有限步内完成，不然就不符合算法的有穷性．选项C不正确 ，一般情况下，一个问题的解决办法不止一个．选项D正确，设计算法要尽量使程序运算简单，节约时间，故选D．
3．下面对算法描述正确的项是( C )
A．算法只能用自然语言来描述
B．算法只能用图形方式来表示
C．同一个问题可以有不同的算法
D．同一个问题算法不同，结果必然不同
[解析] 算法的描述方式不唯一，且同一个问题可以有不同算法，但无论哪个算法得到的结果都是一样的．
4．下列语句表达中是算法的有( C )
①从济南到巴黎可以先乘火车到北京，再坐飞机抵达；
②利用公式S＝ah计算底为1，高为2的三角形的面积；
③x>2x＋4；
④求M(1,2)与N(－3，－5)两点所在直线的方程，可先求MN的斜率，再利用点斜式求方程．
A．1个 B．2个
C．3个 D．4个
[解析] 算法是解决某类问题的步骤与过程，这个问题并不仅仅限于数学问题，①②④都表达了一种算法，故应选C．
5．下列说法中，能称为算法的是( B )
A．巧妇难为无米之炊
B．炒菜需要洗菜、切菜、刷锅、炒菜这些步骤
C．数学题真有趣
D．物理与数学是密不可分的
[解析] 算法是做一件事的步骤或程序，不是解决问题的办法，因而只有选项B正确．
6．对于一般的二元一次方程组，在写解此方程组的算法时，需要注意的是( C )
A．a1≠0 B．a2≠0
C．a1b2－a2b1≠0 D．a1b1－a2b2≠0
[解析] 采用加减法解方程组，未知数x，y的系数是a1b2－a2b1，故a1b2－a2b1≠0才能保证方程组有解．
二、填空题
7．写出1＋3＋5＋7＋9的算法的第一步是1＋3得4，第二步是将第一步中的运算结果4与5相加得9，第三步是_将第二步中的运算结果9与7相加得16___.
[解析] 注意体会这种累加法的本质，把这种累加的思想进行推广．
三、解答题
8．有人针对如何检验哥德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了如下的算法步骤：
1．验证6可以写成两个奇质数之和．
2．验证8可以写成两个奇质数之和．
3．验证10可以写成两个奇质数之和．
……
利用计算机无穷地进行下去就可以检验哥德巴赫猜想是否正确！
请指出该算法步骤中的错误．
[解析] 该例给出的不是算法，因为算法的步骤应该是明确的、有限的；而本例中的“……”所表示的步骤不确定，并且要无穷地进行下去．
9．设直线ax－y＋3＝0与圆(x－1)2＋(y－2)2＝4相交于A、B两点，且弦AB的长为2，求a的值，写出解决本题的一个算法．
[解析] 1.求出圆心到直线的距离d＝＝1.
2．根据点到直线的距离公式得＝1.
3．化简上面方程得|a＋1|＝.
4．解方程得a＝0.
B级 素养提升
一、选择题
1．已知算法：
1．输入n；
2．判断n是否是2，
若n＝2，则n满足条件；
若n>2，则执行第3步；
3．依次检验从2到n－1的整数能不能整除n，若不能整除n，满足条件．上述满足条件的数是( A )
A．质数 B．奇数
C．偶数 D．4的倍数
[解析] 由质数定义知，满足条件的数是质数．
2．早晨起床后需要：洗脸刷牙(5 min)，刷水壶(2 min)，烧水(8 min)，泡面(3 min)，吃饭(10 min)，听广播(8 min)，下列选项中最好的一种算法设计是( D )
A． B．
C． D．
[解析] 由算法的概念及特点知选D．
二、填空题
3．阅读下面的算法，回答所给问题：
第一步，输入a；
第二步，若a≥4，则执行第三步，否则执行第四步；
第三步，输出2a－1；
第四步，输出a2－2a－1.
(1)上述算法的功能是 求分段函数f(a)＝的函数值 ；
(2)当输入的a值为_1___时，输出的数值最小，其最小值为_－2___.
4．一个算法步骤如下：
1 S取值0，i取值1.
2 如果i≤10，则执行3，否则执行6.
3 计算S＋i，并让S取计算结果的值．
4 计算i＋2，并让i取计算结果的值．
5 转去执行2.
6 输出S.
运行以上步骤输出的结果为S＝_25___.
[解析] 由以上算法可知：S＝1＋3＋5＋7＋9＝25.
三、解答题
5．一个人带三只狼和三只羚羊过河，只有一条船，同船可以容一个人和两只动物，没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊．
(1)设计安全渡河的算法；
(2)思考每一步算法所遵循的共同原则是什么？
[解析] (1)
1．人带两只狼过河；
2．人自己返回；
3．人带一只狼过河；
4．人自己返回；
5．人带两只羚羊过河；
6．人带两只狼返回；
7．人带一只羚羊过河；
8．人自己返回；
9．人带两只狼过河．
(2)在人运送动物过河的过程中，人离开岸边时必须保证每个岸边的羚羊的数目大于狼的数目．
6．试描述解下面方程组的算法：
[解析] 设计如下：
1．①＋②化简得2x－y＝14.④
2．②－③化简得x－y＝9.⑤
3．④－⑤得x＝5.⑥
4．将⑥代入⑤得y＝－4.
5．将x，y代入①得z＝11.
6．输出x，y，z的值．
7．(1)试描述判断圆(x－a)2＋(y－b)2＝r2和直线Ax＋By＋C＝0位置关系的算法；
(2)写出求过点M(－2，－1)、N(2,3)的直线与坐标轴围成三角形面积的一个算法．
[解析] (1)1.输入圆心的坐标(a，b)，直线方程的系数A、B、C和半径r；
2．计算z1＝Aa＋Bb＋C；
3．计算z2＝A2＋B2；
4．计算d＝；
5．如果d>r，则相离；如果d＝r，则相切；如果d(2)已知直线上的两点M、N，由两点式可写出直线方程，令x＝0，得出与y轴交点；令y＝0，得出直线与x轴交点，求出三角形两直角边的长，根据三角形面积公式可求出其面积．
算法步骤如下：
1．取x1＝－2，y1＝－1，x2＝2，y2＝3；
2．得直线方程＝；
3．令x＝0，得y的值m，从而得直线与y轴交点的坐标(0，m)；
4．令y＝0，得x的值n，从而得直线与x轴交点的坐标(n,0)；
5．根据三角形面积公式求S＝·|m|·|n|；
6．输出算法结果．
