学年高中数学第二章算法初步21算法的基本思想学案北师大版必修3Word文件下载.docx
《学年高中数学第二章算法初步21算法的基本思想学案北师大版必修3Word文件下载.docx》由会员分享，可在线阅读，更多相关《学年高中数学第二章算法初步21算法的基本思想学案北师大版必修3Word文件下载.docx（14页珍藏版）》请在冰点文库上搜索。
排列，是信息处理中一项基本的工作，通常称为排序．
3．有序列：
按
顺序排列的数据列为有序列．
[看名师·
疑难剖析]
1．对算法含义的理解
（1）算法是机械的
算法的设计要“面面俱到”不能省略任何一个小小的步骤，有时可能要进行大量重复计算，但只要按步骤一步一步地执行，总能得到结果．算法的这种机械化的特点，在设计出算法后，便于把具体过程交给计算机去完成．
（2）算法是普遍存在的
实际上处理任何问题都需要算法，如国际象棋的棋谱、走法、胜负的评判标准，邮寄物品的相关手续，求一个二元一次方程组的解等等．
（3）求解某个具体问题的算法一般是不唯一的
算法实际上是解决问题的步骤和方法，求解问题的出发点不同，就会得到不同的算法．如求二元一次方程组的解有代入消元法和加减消元法，但不同的算法可能会有“优劣”之分．
2．算法与数学问题解法的区别与联系
（1）联系
算法与解法是一般与特殊的关系，也是抽象与具体的关系．如，由具体的二元一次方程组的求解过程（解法）出发，归纳出了二元一次方程组求解的步骤；
同时指出，这样的求解步骤也适合有限制条件的二元一次方程组，这些步骤就构成了二元一次方程组的算法．算法的获得要借助一般意义上具体问题的求解方法，而任何一个具体问题都可利用这类问题的一般算法解决．
（2）区别
算法是解决某一类问题所需要的程序和步骤的统称，也可理解为数学中的“通法通解”；
而解法是解决某一个具体问题的过程和步骤，是具体的解题过程．
考点一算法的概念
例1 下列关于算法的描述正确的是（ ）
A．算法与求解一个问题的方法相同
B．算法只能解决一个问题，不能重复使用
C．算法过程要一步一步执行，每步执行的操作必须确切
D．有的算法执行完后，可能无结果
[分析] 由题目可获取以下主要信息：
①给出的四个选项均与算法含义和特点有关；
②对各选项要做正误判断．
解答本题要先弄清楚算法的含义和特点，然后逐一判定选项命题的真假即可．
[解析] 算法与求解一个问题的方法既有区别又有联系，故A不对；
算法能重复使用，故B不对；
每个算法执行后必须有结果，故D不对；
由算法的有序性和确定性可知C正确．
[答案] C
类题通法
算法实际上是解决问题的一种程序性方法，它通常指向某一个或一类问题，而解决的过程是程序性和构造性的.算法也可以看成解决问题的特殊的、有效的方法.
下列关于算法的说法，正确的有（ ）
①求解某一类问题的算法是唯一的；
②算法必须在有限步操作之后停止；
③算法的每一步操作必须是明确的，不能有歧义和模糊；
④算法执行后一定产生确定的结果．
A．1个B．2个C．3个D．4个
答案 C
解析 本题是在熟练掌握算法概念的基础上的一个跃升，即对算法概念进行进一步的挖掘，理解其内涵．从而借助概念分析、解决问题．由于算法具有有穷性、确定性和可执行性，因而②③④正确．解决问题的算法不一定是唯一的，从而①错，故选C.
考点二数值计算问题的算法设计
例2 写出一个算法，求二元一次方程组
的解．
[分析] 联系该方程组的实际解法过程，但要注意对待定系数的分类讨论．
因为是二元一次方程组，所以a1、a2不能同时为0，b1，b2也不能同时为0.
[解] 算法如下：
1.若a1≠0，
由①×
＋②，得到
y＝c2－
.即方程组化为
2．若a1b2－a2b2≠0，解③得y＝
.④
3.将④代入①，整理得x＝
.
4.输出结果x，y.
5.如果a1b2－a2b1＝0，从③可以看出，方程组无解或有无穷多组解．
6.如果a1＝0，则b1≠0，所以y＝
.⑤
7.将⑤代入②，得x＝
8.输出结果x，y.
对于设计数值计算问题的算法，可以借助数学的常规解法或数学公式，将过程分解成清晰的步骤，使之条理化，但应注意多个数进行四则运算时应分步计算，依次进行，直到算出结果.本题中，把解方程组的过程转化为算法的步骤，应用了数学的转化思想.
写出解方程x2－2x－3＝0的一个算法．
解 解法一：
第一步，移项，得x2－2x＝3.①
第二步，①两边同加1并配方，得（x－1）2＝4.②
第三步，②式两边开方，得x－1＝±
2.③
第四步，解③，得x＝3或x＝－1.
解法二：
第一步，计算方程的判别式并判断其符号：
Δ＝22＋4×
3＝16>
0.
第二步，将a＝1，b＝－2，c＝－3代入求根公式x＝
，得x1＝3，x2＝－1.
考点三判断性问题的算法设计
例3 设计一个算法，判断7是否为质数．
[分析] 只能被1和自身整除的大于1的整数叫质数．因而要判断一个数是否为质数，只需用比这个数小的任一个大于1的整数来除该数，然后利用余数是否为0来判断．
[解] 算法步骤如下：
（1）用2除7，得到余数1.因为余数不为0，所以2不能整除7.
（2）用3除7，得到余数1.因为余数不为0，所以3不能整除7.
（3）用4除7，得到余数3.因为余数不为0，所以4不能整除7.
（4）用5除7，得到余数2.因为余数不为0，所以5不能整除7.
（5）用6除7，得到余数1.因为余数不为0，所以6不能整除7.
（6）判断7是否为质数：
7是质数．
从本例可以看出，本类问题的算法具有很强的机械重复性，因而对于任意给定一个大于2的整数n，我们判断它是否为质数的算法为：
第一步：
令i＝2.第二步，用i除n，得余数r.第三步，判断“r＝0”是否成立，若是，则n不是质数，结束算法；
否则，将i的值增加1，仍用i表示.第四步，判断“i>
n－1”是否成立，若是，则n是质数，结束算法；
否则，返回第二步.分步处理是本类问题的特色，也是算法思想的重要体现.
设计算法，将1260分解成素因数的乘积．
解 算法步骤如下：
（1）判断1260是否为素数：
否．
（2）确定1260的最小素因数：
2.1260＝2×
630.
（3）判断630是否为素数：
（4）确定630的最小素因数：
2.630＝2×
315.
（5）判断315足否为素数：
（6）确定315的最小素因数：
3.315＝3×
105.
（7）判断105是否为素数：
（8）确定105的最小素因数：
3.105＝3×
35.
（9）判断35是否为素数：
（10）确定35的最小素因数：
5.35＝5×
7.
（11）判断7是否为素数：
7是素数，所以分解结束．分解结果是：
1260＝2×
2×
3×
5×
考点四关于整除性问题的算法设计
例4 设计一个算法，求1764与840的最大公约数．
[分析] 首先，将两个数分别进行素因数分解，1764＝22×
32×
72,840＝23×
7.其次，确定两个数的公共素因数2,3,7.接着，确定公共素因数的指数：
对于公共素因数2,22是1764的因数，23是840的因数，因此22是这两个数的公因数，同样可以确定公因数3和7的指数均为1.这样就确定了1764与840的最大公因数为22×
7＝84.
（1）将1764进行素因数分解，1764＝22×
72.
（2）将840进行素因数分解，840＝23×
（3）确定它们的公共素因数为2,3,7.
（4）确定公共素因数的指数．公共素因数2,3,7的指数分别为2,1,1.
（5）最大公因数为22×
31×
71＝84.
1正确理解算法的概念，一个程序的算法要本着方便简捷的原则，还要讲求科学性，算法的步骤是按照一定顺序进行的，不具有可逆性.,2在设计算法的过程当中要牢固把握住它的五个特性：
有限性、确定性、可行性、输入、输出.
求8251与6105的最大公因数．
（1）先将8251进行素因数分解：
8251＝37×
223；
（2）然后将6105进行素因数分解：
6105＝3×
11×
37；
（3）确定它们的公共素因数：
（4）确定公共素因数的指数：
1；
（5）最大公因数为37.
考点五排序问题的算法设计
例5 对于有序列{32,36,50,56,81}，现在要将数据51插入到有序列中．请设计算法确定数据51在有序列中的位置，并用自然语言描述算法．
[分析] 我们可以将51与有序列中的数据从右到左依次进行比较，来确定51在有序列中的位置，也可以将51与有序列中的数据从左向右依次进行比较，来确定51在有序列中的位置．
[解] 将51与有序列中的数据从右向左逐个进行比较，从而确定51在有序列中的位置．其算法如下：
1.比较51与81,51<
81.
2.比较51与56,51<
56.
3.比较51与50,51>
50.
4.将51插入到56和50之间，得到一个新的有序列{32,36,50,51,56,81}．
本例的排序算法是有序列直接插入排序，解决本类问题也可以用折半插入排序法进行.
将52插入有序列{13,27,38,39,43,47,48,51,57,66,74,82}中，构成一个新的有序列．
解 首先选择有序列中具有中间位置序号的数据47，将52与47进行比较，显然52>
47，故52不能插入到47的左边的任何位置．所以，应该排在47的右边，再将余下数据的中间位置的数据57与52比较，显然52<
57，因此应插到57的左边，又51<
52，则52插入到51的右边，57的左边，即可得到52的位置.
考点六实际问题的算法设计
例6 汉诺塔问题：
如图三根柱子，甲柱上从大到小放置了三个圆环A、B、C，现在要将这三个圆环移至乙柱，也要从大到小放置．要求一次移动一个，移动过程中，大圆环不能放于小圆环上，应如何移动？
[分析] 这是一个古典的数学问题．要把甲柱的n个环移到乙柱，必须先把上面的n－1个环移到丙柱，然后把第n个环移到乙柱，最后再把丙柱的第n－1个环移过来．解决n个环的问题，先要解决n－1个环的问题，而这个问题与前一个是类似的，可以用相同的办法解决．最终，得到只有一个环的情况，很简单，直接把环从甲柱移到乙柱即可．
[解] 如果移动一次算一步，则可按以下步骤进行：
第一步，将C环移至乙柱．
第二步，将B环移至丙柱．
第三步，将C环移至丙柱．
第四步，将A环移至乙柱．
第五步，将C环移至甲柱．
第六步，将B环移至乙柱．
第七步，将C环移至乙柱．
一个人带着三只狼和三只羊过河，只有一条船，该船可容纳一个人和两只动物；
没有人在的时候，如果狼的数量不少于羊的数量，狼就会吃羊，该人如何能将动物转移过河？
请设计算法．
解 第一步，人带两只狼过河，并自己返回；
第二步，人带一只狼过河，自己返回；
第三步，人带两只羊过河，并带两只狼返回；
第四步，人带一只羊过河，自己返回；
第五步，人带两只狼过河．
规范解答分段函数的算法设计
[例] （12分）已知分段函数
f（x）＝
请设计一个算法，输入任意一个不小于－1的实数x0，输出相应的f（x0）的值．
（一）精妙思路点拨
（二）分层规范细解
1．输入x0；
3分
2.
①，则输出“输入的数据有误”，结束算法，否则执行第3步；
6分
3．若－1≤x0≤1，则f（x0）＝x
－1，否则f（x0）＝lnx0；
9分
4.
②，结束算法.12分
（三）来自一线的报告
通过阅卷后分析，对解答本题的失分警示和解题启示总结如下：
（注：
此处的①②见分层规范细解过程）
（四）类题练笔掌握
已知函数f（x）＝
解 1.输入x0；
2．若x0≤1，则计算f（x0）＝2x0－1，否则执行第3步；
3．若x0≤4，则计算f（x0）＝
，否则执行第4步；
4．计算f（x0）＝x0－2；
5．输出f（x0）的值，结束算法．
（五）解题设问
解答本题时，需对谁进行分类讨论？
________.
答案 自变量x
1.以下给出关于算法的几种说法，其中正确的是（ ）
A．算法就是某一个问题的解题方法
B．对于给定的一个问题，其算法不一定是唯一的
C．一个算法可以不产生确定的结果
D．算法的步骤可以无限地执行下去不停止
答案 B
解析 算法是做某一件事的步骤或程序，不是解决问题的方法，所以A不正确；
一个算法产生的结果是确定的，所以C不正确；
一个算法的步骤是有限的，它应在有限步骤之后停止，而不能是无限的，所以D不正确；
求解某一个问题可以有不同的算法，所以B正确．
2．下面四种叙述能称为算法的是（ ）
A．在家里一般是妈妈做饭
B．做米饭需要刷锅、淘米、添水、加热这些步骤
C．在野外做饭叫野炊
D．做饭必须有米
解析 四个选项中仅有B是表达解决问题的步骤．
3．下列对算法的理解不正确的是（ ）
A．算法有一个共同特点就是对一类问题都有效（而不是个别问题）
B．算法要求是一步一步地执行，每一步都能得到唯一的结果
C．算法一般是机械的，有时要进行大量重复的计算，它是一种通法
D．任何问题都可以用算法来解决
答案 D
解析 算法是解决问题的步骤的描述，但是并不是所有的问题都可以用算法来解决．
4．写出解方程ax＋b＝0（a≠0）的一个算法的过程．第一步：
将不含x的常数项移到方程右边，并改变常数项的符号；
第二步：
答案 方程两边同除以a
解析 利用等式的性质将方程变成一边是x，另一边为常数的形式即得方程的解．
5．设计算法，求一元二次方程ax2＋bx＋c＝0（a≠0）的根．
（1）计算Δ＝b2－4ac；
（2）判断Δ的值，若Δ<
0，则方程无实数根；
若Δ＝0，则方程有两个相等的实数根，x1＝x2＝－
；
若Δ>
0，则方程有两个不等的实数根，x1＝
，x2＝
（3）输出结果．
升级会员 