2.1算法的基本思想教学设计 教案 (北师大必修3)

2.1算法的基本思想教学设计 教案 (北师大必修3)

1.2.1算法的基本思想教学设计 教案 (北师大必修3) 篇一

第二章算法初步 本章归纳整合

知识归纳

专题一 算法的含义及算法设计

算法不同于一般意义上解决某个问题的方法，它是对一类问题的一般解法的抽象和概括，它要借助一般问题的解决方法，又要包含这类问题的所有可能情形．设计算法往往把问题的解法划分为若干个可执行的步骤，有些甚至重复多次，但必须在有限步之内完成．

用自然语言描述算法，大体可分以下三步完成：

第一步：明确问题的性质，分析题意，我们可将问题简单的分为数值型问题和非数值型问题，不同类型的问题

可以有针对性地采用不同的方法进行处理．

第二步：建立问题的描述模型．对于数值型问题，可以建立数学模型，通过数学语言来描述问题；对于非数值型问题，我们可以建立过程模型，通过过程模型来描述问题．

第三步：设计确立算法．对于数值型问题，我们可以采用数值分析的方法进行处理，数值分析中有许多现成的固定算法，我们可以直接使用，当然我们可以根据问题的实际情况设计算法．对于非数值型问题，根据过程模型分析算法与设计算法，也可以选择一些成熟的办法进行处理，如排序、递推等． 【例1】

韩信是汉高祖刘邦部下的大将，他英勇善战，智谋超群，为建立汉朝立下了汗马功劳，据说他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，采用下述点兵的方法：先令士兵从1～3报数，结果最后一个士兵报2；再令士兵从1～5报数，结果最后一个士兵报3；又令士兵从1～7报数，结果最后一个士兵报4.这样，韩信很快就算出了自己部队士兵的总人数．请你设计一个算法，求出士兵至少有多少人？

解 第一步，首先确定最小的除以7余4的正整数：4.第二步，依次加7就得到所有除以7余4的正整数：4，11，18，25，32，39，46，53，60，….第三步，在第二步得到的一列数中确定最小的除以5余3的正整数：18.第四步，然后依次加上35，得到18，53，88，….1 第五步，在第四步得到的一列数中找出最小的满足除以3余2的正整数：53.这就是我们要求的数．

规律方法 本题直接通过列方程组显然无法求解，故根据题设运用列举法分步求解．我们将7，5，3的顺序颠倒一下，也能解答此题，不妨试一试．

专题二 顺序结构与选择结构

1．顺序结构是由若干个依次执行的处理步骤组成的逻辑结构，这是任何一个程序都离不开的基本结构．

2．在一个算法中，经常会遇到一些条件的判断，算法的流程根据条件是否成立有不同的流向，这种算法结构即选择结构．

【例2】

用顺序结构表示：利用尺规作图，确定线段AB的4等分点的算法． [思路探索] 先写出作法，由作法写出算法．

解 作法：如图，第一步：过A作射线AP，在AP上任取一点C，得线段AC； 第二步：在射线AP上作线段AC＝CD＝DE＝EP；

第三步：连接BP，过C作CF∥BP，交AB于F，同理，作出点M，N； 第四步：F，M，N为所作的AB的三个4等分点．

算法：

【例3】

设计判断正整数p是否是正整数q的约数的算法并画出框图．

[思路探索] 判断正整数p是否是正整数q的约数，即是看正整数q能否被正整数p整除，如果能，则p是q的约数；如果不能，则p不是q的约数，从分析上看，该题应用选择结构．

解 算法如下：

第一步：输入p，q；

第二步：判断p除q的余数r是否为0，如果r＝0，则p是q的约数，否则p不是q的约数．

算法框图如图所示．

规律方法 解本题要熟练掌握约数的概念，本题由于要判断余数是否为0，即要用到分类讨论的思想，故采用选择结构． 专题三 循环结构

循环结构是指运算过程中根据指定条件决定是否重复执行一条或多条指令的控制结构．其中重复执行的步骤叫循环体．循环结构中包含条件结构．

1．涉及多项的和或积的程序框图要用到循环和分支结构，画图时应注意三个量：循环变量的初值、终值、循环变量的增量在程序中的作用与位置．

2．利用循环结构可寻数．使用循环结构寻数时，要明确数字的结构特征，决定循环的终止条件与数的结构特征的关系及循环次数，尤其是统计数时，注意要统计的数的出现次数与循环次数的区别．

3．循环结构是执行算法流程的重要组成部分．

【例4】

阅读程序框图，运行相应的程序，则输出s的值为()．

A．－1 B．0 C．1 D．3 [思路探索] 按程序框图进行计算，注意循环体执行的次数． 解析 当i>4时共进行四次运算： s＝3，i＝2；

s＝3×(3－2)＋1＝4，i＝3； s＝1，i＝4； s＝0，i＝5.答案 B

专题四 条件语句与循环语句

1．条件语句

计算机通常是按照算法中语句出现的先后顺序依次往下执行的，但有时需要根据某个 4 给定的条件是否满足来决定所要执行的语句，这时就需要用到条件语句．算法中的选择结构由条件语句来表达．因此，在条件语句中要体现出对条件的判断及执行语句的顺序．条件语句主要是If——Then——Else语句，在某些情况下，也可以只使用If——Then语句，无Else分支语句．

2．循环语句

算法中的循环结构由循环语句来实现．循环语句一般分为For、Do Loop语句．

【例5】 用循环语句描述计算1＋12＋13＋14＋…＋110 000的值的 一个算法．

[思路探索] 求1＋1＋1＋1＋…＋123410 000的值与求1＋2 ＋3＋4＋…＋10 00的值有相似之处，只要将后者的S＝ 1 S＋i变为S＝S＋i即可． 解 用For语句描述： S＝0 For i＝1 To 10 000 S＝S＋1/i Next 输出S

用Do Loop语句描述：

i＝1 S＝0 Do S＝S＋1/i i＝i＋1 Loop While i<＝10 000 输出 S

规律方法 本题的两种书写方式具有普遍性和广泛的应用 1111性．若将S＝S＋变为S＝S＋2则算法变为求1＋2＋2＋…ii23

1＋的值的算法．若将Do Loop语句中的i＝i＋1变为i 10 00021111

＝i＋2，则成了求S＝1＋＋＋＋…＋的值，我们可3579 999

以举一反三，以达到真正掌握知识的目的． 专题五折半插入排序法

折半插入排序：折半插入排序的基本思想是先将新数据与有序列中“中间位置”的那个数据进行比较，如果与之相等，则可确定其插入位置及序号；若不相等，中间位置的数据将数据列分为两半，当新数据较小时，它的位置应在靠左的一半，否则在靠右的一半．反复进行这种查找的方法，直到确定新数据的位置．通过前面的研究我们知道，折半插入排序方法中应用了二分法的思想后，少了多次无用的比较．相比较前面的有序列直接插入排序算法，会减少一些资源的浪费．对折半插入排序的理解：

一般地，对于一个有序列：a1≤a2≤a3≤…≤an，欲将新数据A插入到有序列中，形成新的有序列，其做法是：将数据A与原有序列中的数据从右到左依次进行比较，直到发现某一数据ai，使得ai≤A，把A插入到ai的右边；如果数据A小于原有序列中的所有数据，则将A插入到原序列的最左边．上面的排序算法通常称为有序列直接插入排序的算法．

【例6】 把8插入到1,3,5,7,9,11,13中．

解：首先，将8与13比较，显然8比13小，所以它要插在13之前；再将它与11比较，显然它比11小，所以8插在11前；同样地，8插在9前；接着，将8与7比较，显然它比7大，所以，完成8的插入排序操作．

评析：将8与数列中的数进行比较，可找到它的正确位置． 变式练习6 完成无序列{5,1,3,6}的排序． [解] 其算法如下：

S1 因为5>1，输出1,5；

S2 因为3<5，则5后移一位空出第二位；

S3 因为3>1，输出1,3,5； S4 因为6>5，输出1,3,5,6.专题六折半插入排序法

折半插入排序：折半插入排序的基本思想是先将新数据与有序列中“中间位置”的那个数据进行比较，如果与之相等，则可确定其插入位置及序号；若不相等，中间位置的数据将数据列分为两半，当新数据较小时，它的位置应在靠左的一半，否则在靠右的一半．反复进行这种查找的方法，直到确定新数据的位置．通过前面的研究我们知道，折半插入排序方法中应用了二分法的思想后，少了多次无用的比较．相比较前面的有序列直接插入排序算法，会减少一些资源的浪费．对折半插入排序的理解：

先将新数据与有序列中“中间位置”的数据进行比较，若有序列有2n＋1个数据，则“中间位置”的数据指的是第n＋1个数据，若有2n个数据，则“中间位置”的数据指的是第n个数据，如果新数据小于中间位置的数据，则新数据插入的位置应该在靠左边的一半；如果新数据等于中间位置的数据，则将新数据插入到中间位置的数据的右边；如果新数据大于中间位置的数据，则新数据插入的位置应该在靠右边的一半．也就是说，一次比较就排除了数据中一半的位置．反复进行这种比较，直到确定新数据的位置．

例七将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的位置．

评析：用折半插入排序法向有序列中插入新数据时，首先确定原有序列中数据的个数是偶数2n还是奇数2n＋1.若为偶数，则“中间位置”的数据是第n个数据；若为奇数，则“中间位置”的数据为第n＋1个数据，然后将新数据与“中间位置”的数据比较，若新数据大于“中间位置”的数据，则在右半边进行下一步骤；若新数据小于“中间位置”的数据，则在左半边进行下一步骤；依次类推，就可以确定新数据在序列中的位置．