1、第一章 算法初步 1.1 算法与程序框图 1.1.1 算法的概念 1.理解算法的概念,体会算法的思想;（重点）2.掌握简单问题算法的表述；(重点、难点)3.会写出解线性方程（组）的算法.2000春晚小品钟点工1.把冰箱门打开 2.把大象装进去 3.把冰箱门关上 把大象放进冰箱里需要几步？思考一：6+5(4-2)的计算步骤是什么?先进行括号里的运算；再算乘法；最后算加法.探究1：算法的概念 假设家中生火泡茶有以下几个步骤：a.生火 b.将水倒入锅中 c.找茶叶 d.洗茶壶、茶碗 e.用开水冲茶 请选出一个最优方案（）A.abcde B.bacde C.cadbe D.dcabe 广义的算法是指完
2、成某项工作的方法和步骤，那么我们可以说洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等.到底什么是算 法呢？思考二：B 算法（algorithm）一词出现于12世纪，指的是用阿拉伯数字进行算术运算的过程.在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤.现在，算法通常可以编成计算机程序，让计算机执行并解决问题.据说英文algorithm来源于阿拉伯数学家花拉子米的拉丁译名Algoritmi.算法的概念 明确性有效性有限性1.算法定义的理解 在数学中，现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限
3、步之内完成.2.算法的要求(1)写出的算法,必须能解决一类问题(例如解任意一个二元一次方程组),并且能重复使用;(2)算法过程要能一步一步执行,每一步执行的操作,必须确切,不能含混不清,而且在有限步之内完成后能得出结果.提升总结 3.算法的基本特征 明确性:算法的每一个步骤都是确切的,能有效执行且得到确定结果,不能模棱两可.有限性:算法应由有限步组成,至少对某些输入,算法应在有限多步内结束,并给出计算结果 有效性:算法从初始步骤开始,分为若干明确的步骤,每一步都只能有一个确定的继任者,只有执行完前一步才能进入到后一步,并且每一步都确定无误后,才能解决问题.不惟一性:求解某一个问题的算法不一定是
4、惟一的,对于同一个问题可以有不同的算法.写出解方程组 的步骤 第一步,（消元）+2，得 7x=11.第二步,（解一元一次方程）解得 第三步,（代入求解）将 代入,得 11x=7.11x=76y=.73x-2y=3 2x+y=4 写出解第二个方程组的算法：第一步,a2-a1 得(a2b1-a1b2)y=a2c1-a1c2.第二步,解，得 第三步,将带入得 21122112a c-a cy=a b-a b.3x-2y=32x+y=4122 12112b c-b cx=a b-a b.推广 111222a x+b y=c a x+b y=c 1221(a b-a b0)问题1：这两个解方程组算法的比
5、较.第一步,a2-a1得(a2b1-a1b2)y=a2c1-a1c2.第二步,解，得 第三步,将代入得 21122112a c-a cy=.a b-a b12212112b c-b cx=.a b-a b第一步,+2，得7x=11.第二步,解得 第三步,将 代入,得 11x=7.3x-2y=3 2x+y=4 6y=.7-11x=71111221222a x+b y=c (a b-a b0)a x+b y=c 12212112b c-b cx=a b-a b21122112a c-a cy=a b-a b3x-2y=3 2x+y=4 解方程组第一步,取 a1=3,b1=-2,c1=3,a2=2,
6、b2=1,c2=4.第二步,计算 第三步,给出运算结果.2 1122112a c-a cy=.a b-a b122 12112b c-b cx=,a b-a b问题2:你对以下的“算法”如何理解？问：要把大象装进冰箱，分几步？答：分三步,第一步,打开冰箱门.第二步,把大象装进冰箱.第三步,关上冰箱门.问题3:一位商人有9枚金币，其中有一枚略轻的假币，你能用天平（无砝码）将假币找出来吗？写出解决这一问题的算法.第一步,把9枚金币平均分成三组，每组三枚.第二步,先将其中的两组放在天平的两边，如果天平不平衡，那么假金币就在轻的那一组；如果天平左右平衡，则假金币就在未称量的那一组里.第三步,取出含假币
7、的那一组，从中任取两枚金币放在天平两边进行称量，如果天平不平衡，则假金币在轻的那一边；若平衡，则未称的那一枚就是假币.问题4:有人对歌德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了如下操作步骤：第一步,检验6=3+3.第二步,检验8=3+5.第三步,检验10=5+5.利用计算机无穷地进行下去！请问，利用这种程序能够证明猜想的正确性吗？这是一种算法吗？不能 不是 例1设计一个算法，判断7是否为质数.算法分析：根据质数的定义，可以这样判断：依次用26除7，如果它们中有一个能整除7，则7不是质数，否则7是质数.根据以上分析，可写出如下算法：第一步,用2除7，得到余数1,所以2不能整除7.
8、第二步,用3除7，得到余数1,所以3不能整除7.第三步,用4除7，得到余数3,所以4不能整除7.第四步,用5除7，得到余数2,所以5不能整除7.第五步,用6除7，得到余数1,所以6不能整除7.因此，7是质数.设计一个算法，判断35是否为质数.第一步,用2除35，得到余数1,所以2不能整除35.第二步,用3除35，得到余数2,所以3不能整除35.第三步,用4除35，得到余数3,所以4不能整除35.第四步,用5除35，得到余数0,所以5能整除35.因此，35不是质数.探究2：你能写出“判断整数n(n2)是否为质数”的算法吗？第一步,给定一个大于2的整数n.第二步,令i=2.第三步,用i除n，得到余
9、数r.第四步,判断“r=0”是否成立.若是，则n不是质数,结束算法；否则，将i的值增加1，仍用i表示.第五步,判断“i(n-1)”是否成立.若是，则n是质数,结束算法；否则，返回第三步.想一想：什么是二分法？对于区间a,b 上连续不断且f(a)f(b)0)x 例2.写出用“二分法”求方程 x2-2=0（x0）的近似解的算法.第一步,令f(x)=x2-2，给定精确度d.第二步,确定区间a，b，满足f(a)f(b)0.第三步,取区间中点 第四步,若f(a)f(m)0,则含零点的区间为a,m;否则，含零点的区间为m，b.将新得到的含零点的区间仍记为a,b.第五步,判断|a-b|0),给定d=0.00
10、5.此步骤也是求 的近似值的一个算法.2于是，开区间（1.414 062 5,1.417 968 75）中的实数都是当精度为0.005时的原方程的近似解.任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.第一步,输入任意一个正实数r；第二步,计算圆的面积S=r2;第三步,输出圆的面积S.给出一个问题，设计算法时应注意的问题：(1)认真分析问题，联系解决此问题的一般数学方法;(2)综合考虑此类问题中可能涉及的各种情况;(3)将解决问题的过程划分为若干个步骤;(4)用简练的语言将各个步骤表示出来.总结提升 1.算法的有穷性是指()(A)算法必须包含输出(B)算法中每个步骤都是可执行的(C
11、)算法的步骤必须有限 (D)以上说法均不对【解析】选C.算法通常是指按照一定规则解决某一类问题的明确和有限的步骤.C 2.写出解二元一次方程组 的一个算法.第一步,(2)2(1)得x2.第二步,_.第三步,输出x，y的值.【解析】利用解方程组的步骤可得，将x2代入(2)得 y-4.3x2y14 (1)xy2 (2)-=+=-答案：将x2代入(2)得y-4 3.写出求1+2+3+100的一个算法，可运用公式1+2+3+n=直接计算，第一步_.第二步_.第三步输出计算结果.n n12n n12n n12【解析】第一步,取n=100.第二步,计算 的值.答案:取n=100 计算 的值 4.你要乘火车
12、去外地办一件急事,请你写出从自己房间出发到坐在车厢内的三步主要算法.第一步,去车站.第二步,买车票.第三步,凭票上车对号入座.5.任意给定一个大于1 的正整数n,设计一个算法求出n的所有因数.第一步,依次以2(n-1)为除数去除n,检查余数是否为0,若是,则是n的因数;若不是,则不是n的因数.第二步,在n的因数中加入1和n.第三步,输出n的所有因数.知识结构 算法的概念 算法的步骤 算法的特点 算法 设计算法的注意事项:(1)认真分析问题,联系解决此问题的一般数学方法;(2)综合考虑此类问题中可能涉及的各种情况;(3)借助有关的变量或参数对算法加以表达;(4)将解决问题的过程划分为若干个步骤;(5)用简练的语言将各个步骤表示出来.成功和失败本是同一片旷野，它是会令你溺水的深潭，也是能为你解渴的甘泉.