1、第十章算法初步10.1算法与程序框图1了解算法的含义，了解算法的思想2理解程序框图的三种基本逻辑结构：顺序、条件分支、循环本部分是近几年高考的必考内容，试题难度不大，且多以选择、填空题的形式出现1算法的概念及特点(1)算法的概念在数学中，算法通常是指按照一定_解决某一类问题的_和_的步骤(2)算法的特点之一是具有_性，即算法中的每一步都应该是确定的，并能有效的执行，且得到确定的结果，而不应是模棱两可的；其二是具有_性，即算法步骤明确，前一步是后一步的前提，只有执行完前一步才能进行后一步，并且每一步都准确无误才能解决问题；其三是具有_性，即一个算法应该在有限步操作后停止，而不能是无限的；另外，算
2、法还具有不唯一性和普遍性，即对某一个问题的解决不一定是唯一的，可以有不同的解法，一个好的算法应解决的是一类问题而不是一两个问题2程序框图(1)程序框图的概念程序框图又称流程图，是一种用 、 及 来表示算法的图形(2)构成程序框图的图形符号、名称及其功能图形符号名称功能表示一个算法的起始和结束表示一个算法输入和输出的信息赋值、计算判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N”连接程序框连接程序框图的两部分3. 算法的基本逻辑结构(1)顺序结构顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按_的顺序进行的它是由若干个_的步骤组成的，它是任何一个算法都离
3、不开的基本结构顺序结构可用程序框图表示为如图所示的形式：(2)条件结构在一个算法中，经常会遇到一些条件的判断，算法的流程根据条件是否成立有不同的流向常见的条件结构可以用程序框图表示为如图所示的两种形式：(3)循环结构在一些算法中，经常会出现从某处开始，按照一定的条件反复执行某些步骤的情况，这就是 反复执行的步骤称为 循环结构有如下两种形式：如图1，这个循环结构有如下特征：在执行了一次循环体后，对条件进行判断，如果条件不满足，就继续执行循环体，直到条件满足时终止循环因此，这种循环结构称为_如图2表示的也是常见的循环结构，它有如下特征：在每次执行循环体前，对条件进行判断，当条件满足时，执行循环体，
4、否则终止循环因此，这种循环结构称为_【自查自纠】1(1)规则明确有限(2)确定有序有穷2(1)程序框流程线文字说明(2)终端框(起止框)输入、输出框处理框(执行框)判断框流程线 连接点3(1)从上到下依次执行(3)循环结构循环体直到型循环结构当型循环结构下面对算法描述正确的一项是()A算法只能用自然语言来描述B算法只能用图形方式来表示C同一问题可以有不同的算法D同一问题的算法不同，结果必然不同解：A，B显然错误，由算法的不唯一性知C正确，对于D，同一问题的算法不同，但结果可以相同，D错，故选C.下列说法不正确的是()A任何一个算法一定含有顺序结构B任何一个算法都可能由顺序结构、条件结构、循环结
5、构构成C循环结构中一定包含条件结构D条件结构中一定包含循环结构解：顺序结构、条件结构、循环结构按照顺序，后一种结构包含前一种结构，但反过来不一定包含所以条件结构中不一定包含循环结构，故选D.执行如图所示的程序框图，输出的S值为()A2 B4 C8 D16解：第一次循环结束时，S1，k1；第二次循环结束时，S2，k2；第三次循环结束时，S8，k3，此时循环结束，输出的S值为8.故选C.()执行如图所示的程序框图，如果输入a1，b2，则输出的a的值为_解：输入a1，b2，第一次循环得a3；第二次循环得a5；第三次循环得a7；第四次循环得a9，此时退出循环，输出a9.故填9.()如图所示，程序框图(
6、算法流程图)的输出结果是_解：初始值s0，n2.第一次循环得s，n4；第二次循环得s，n6；第三次循环得s，n8，此时退出循环，输出的s.故填.类型一算法的概念下列语句是算法的个数为()从济南到巴黎：先从济南坐火车到北京，再坐飞机到巴黎；统筹法中“烧水泡茶”的故事；测量某棵树的高度，判断其是否为大树；已知三角形的两边及夹角，利用三角形的面积公式求出该三角形的面积A1B2C3D4解：中勾画了从济南到巴黎的行程安排，完成了任务；中节约时间，烧水泡茶完成了任务；中对“树的大小”没有明确的标准，无法完成任务，不是有效的算法构造；是纯数学问题，利用三角形的面积公式求出三角形的面积故选C.【评析】算法过程
7、要做到一步一步地执行，每一步执行的操作必须确切，不能含糊不清，且在有限步后必须得到问题的结果下列叙述中，不正确的是()A解决一个问题的算法不是唯一的B算法必须能够解决一类问题C在计算机上算法能够执行D一个算法可以分为n(nN*)步，n可以无限地取值解：算法由各步骤构成，但步骤是有限的故选D.类型二经典算法“韩信点兵”问题韩信是汉高祖刘邦手下的大将，为了保守军事机密，他在点兵时采用下述方法：先令士兵从13报数，结果最后一个士兵报2；再令士兵从15报数，结果最后一个士兵报3；又令士兵从17报数，结果最后一个士兵报4.这样，韩信很快就知道了自己部队士兵的总人数请设计一个算法，求出士兵至少有多少人解：
8、在本题中，士兵从13报数，最后一个士兵报2，说明士兵的总人数是除以3余2，其他两种情况依此类推(算法一)步骤如下：第一步：先确定最小的满足除以7余4的数是4；第二步：依次加7就得到所有满足除以7余4的数：4，11，18，25，32，39，46，53，60，；第三步：在第二步所得的一列数中确定最小的满足除以5余3的正整数：18；第四步：依次加上35，得18，53，88，；第五步：在第四步得到的一列数中，找到最小的满足除以3余2的正整数：53，这就是我们要求的数(算法二)步骤如下：第一步：先确定最小的满足除以3余2的数是2；第二步：依次加3就得到所有满足除以3余2的数：2，5，8，11，14，17
9、，20，23，26，29，32，35，38，41，44，47，50，53，56，；第三步：在第二步所得的一列数中确定最小的满足除以5余3的正整数：8；第四步：然后依次加15就得8，23，38，53，不难看出，这些数既满足除以3余2，又满足除以5余3；第五步：在第四步所得的一列数中找到满足除以7余4的最小数是53，这就是我们要求的数【评析】给出一个问题，设计算法时要注意：(1)认真分析问题，研究解决此问题的一般方法；(2)将解决问题的过程分解成若干步骤；(3)用简练的语言将各步骤表示出来；(4)把解题过程条理清楚地表达出来，就得到一个明确的算法对于同一问题，可以设计不同的算法，其最终的结果是一样
10、的，但解决问题的繁简程度不同，我们要寻找最优算法一位商人有9枚银元，其中有一枚略轻的是假银元请设计一种算法，用天平(不用砝码)将假银元找出来解：算法如下：第一步：把银元分成3组，每组3枚；第二步：先将两组分别放在天平的两边，如果天平不平衡，那么假银元就在轻的那一组；如果天平左右平衡，则假银元就在未称的第3组内；第三步：取出含假银元的那一组，从中任取两枚银元放在天平的两边如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元类型三顺序结构已知点P(x0，y0)和直线l：AxByC0，求点P(x0，y0)到直线l的距离d，写出其算法并画出流程图解：算法如下：第一步：输入
11、x0，y0及直线方程的系数A，B，C.第二步：计算z1Ax0By0C.第三步：计算z2A2B2.第四步：计算d.第五步：输出d.流程图如图所示：【评析】顺序结构是一种最简单、最基本的结构，可严格按照传统的解题思路写出算法步骤，画出程序框图注意语句与语句之间，框与框之间是按从上到下的顺序进行的写出求两个正整数相除(ab)的商q及余数r的算法，并画出程序框图解：设ab的商为q及余数为r，则abqr，其中0r10，则输出S，否则，返回第二步程序框图如图所示：【评析】如果算法问题里涉及的运算进行了许多次重复的操作，且先后参与运算的数之间有相同的规律，就可引入变量循环参与运算(我们称之为循环变量)，应用
12、循环结构在循环结构中，要注意根据条件设计合理的计数变量、累加和累乘变量及其个数等，特别要使条件的表述恰当、准确()如图是用模拟方法估计圆周率值的程序框图，P表示估计结果，则图中空白框内应填入()AP BPCP DP解：当循环结束时，如图，M表示落入扇形的点的个数，1000表示落入正方形的点的个数，则点落入扇形的概率为，由几何概型知，点落入扇形的概率为， 则 ， P.故选D.1设计算法时，要根据题目进行选择，以简单、程序短、易于在计算机上执行为原则2在画程序框图时首先要进行结构的选择，套用格式若求只含有一个关系式的函数的函数值时，只用顺序结构就能够解决；若是分段函数或执行时需要先判断才能执行后继
13、步骤的，就必须引入条件结构；如果问题里涉及的运算进行了许多重复的步骤，且数之间有相同的规律，就可引入变量，应用循环结构当然，应用循环结构一定要用到顺序结构与条件结构3循环结构的循环控制通过累加变量记录循环次数，通过判断框决定循环终止与否用循环结构来描述算法，在画出算法程序框图之前，需要确定的三件事是：(1)确定循环变量与初始条件；(2)确定循环体；(3)确定终止条件注意区别直到型循环与当型循环，二者的判断框内的条件表述在解决同一问题时恰好相反4在具体绘制程序框图时，要注意以下几点：(1)流程线上要标有执行顺序的箭头(2)判断框后边的流程线应根据情况标注“是(Y)”或“否(N)”(3)框图内的内容包括累加(积)变量初始值，计数变量初始值，累加值，前后两个变量的差值都要仔细斟酌，不能有丝毫差错(4)判断框内条件有用“”、“”、“”、“”、“”等形式，它们的含义是各不相同的，要根据所选循环结构的类型，正确地进行选择5解决循环结构框图问题，要先找出控制循环的变量的初值、步长、终值(或控制循环的条件)，然后看循环体，循环次数比较少时，可依次列出，循环次数较多时，可先循环几次，找出规律，要特别注意最后输出的是什么，不要出现多一次或少一次循环的错误
