1、1.1.1 算法的概念算法的概念 问题的提出问题的提出 有一个农夫带一条狼狗、一只羊和有一个农夫带一条狼狗、一只羊和一筐白菜过河。如果没有农夫看管，则一筐白菜过河。如果没有农夫看管，则狼狗要吃羊，羊要吃白菜。但是船很小，狼狗要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如只够农夫带一样东西过河。问农夫该如何解此难题？何解此难题？方法和过程方法和过程：1、带羊到对岸，返回；带羊到对岸，返回；2、带菜到对岸，并把羊带回；带菜到对岸，并把羊带回；3、带狼狗到对岸，返回；带狼狗到对岸，返回；4、带羊到对岸。带羊到对岸。问题问题:用加减消元法解二元一次方程组用加减消元法解二元一次方程组
2、 的具体步骤是什么？的具体步骤是什么？1212yxyx +2 2，得得 5 5x=1.=1.解解，得得 .15x -2 2，得得 5 5y3 3.解解，得得 .35y 第一步：第一步：第二步：第二步：第三步：第三步：第四步：第四步：第五步：第五步：1212yxyx 得到方程组的解为得到方程组的解为 .15x 35y 问题问题:参照上述思路参照上述思路,一般地一般地,解方程组解方程组 的基本步骤是什么？的基本步骤是什么？111a xb yc222a xb yc1 22 10aba b（）第一步：第一步：解解，得得2 11 21 22 1b cbcxaba b -，得得1a2a1 22 11 22
3、 1()aba b ya ca c解解，得得12211221a ca cya ba b得到方程组的解为得到方程组的解为 2112122112211221b cb cxa ba ba ca cya ba b2b1b -，得得 1 22 12 11 2()aba b xb cbc第二步：第二步：第三步：第三步：第四步：第四步：第五步：第五步：根据上述分析，用加减消元法解二元根据上述分析，用加减消元法解二元一次方程组，可以分为五个步骤进行，一次方程组，可以分为五个步骤进行，这五个步骤就构成了解二元一次方程组这五个步骤就构成了解二元一次方程组的一个的一个“算法算法”.我们再根据这一算法编我们再根据这一
4、算法编制计算机程序，就可以让计算机来解二制计算机程序，就可以让计算机来解二元一次方程组元一次方程组.广义地说：为了解决某一问题而采取广义地说：为了解决某一问题而采取的方法和步骤，就称之为算法。的方法和步骤，就称之为算法。在数在数学中，按照一定规则解决某一类问题学中，按照一定规则解决某一类问题的明确和有限的步骤，的明确和有限的步骤，称为算法称为算法,现现在，算法通常可以编成计算机程序，在，算法通常可以编成计算机程序，让计算机执行并解决问题。让计算机执行并解决问题。1 1、算法的概念、算法的概念:2 2、算法的特征、算法的特征（1）有限性：）有限性：一个算法的步骤是有限的，它应在一个算法的步骤是有
5、限的，它应在有限步操作之后停止，而不能是无限的。有限步操作之后停止，而不能是无限的。（2）明确性：）明确性：算法中的每一步都应该是确定的，算法中的每一步都应该是确定的，并且能有效地执行且得到确定的结果，而不应当是并且能有效地执行且得到确定的结果，而不应当是模棱两可的。模棱两可的。（3）可行性：）可行性：算法中的每一步操作都必须是可执算法中的每一步操作都必须是可执行的，也就是说算法中的每一步都能通过手工或机行的，也就是说算法中的每一步都能通过手工或机器在有限时间内完成。器在有限时间内完成。（4）通用性：）通用性：可解决某一类问题，并且能重复使可解决某一类问题，并且能重复使用。用。（5）不唯一性：
6、）不唯一性：求解某一个问题时的方法不一定求解某一个问题时的方法不一定只有一种，但这些算法有繁简、优劣之分。只有一种，但这些算法有繁简、优劣之分。自然语言：自然语言：用日常语言和数学语用日常语言和数学语言或借助于形式语言；言或借助于形式语言；框图语言框图语言（流程图）（流程图）程序设计语言。程序设计语言。3.3.算法的表述形式算法的表述形式:例例1 1.(1).(1)设计一个算法判断设计一个算法判断7 7是否为质数是否为质数.第一步第一步,用用2除除7,得到余数得到余数1.因为余数不为因为余数不为0，所以所以2不能整除不能整除7.第二步第二步,用用3除除7,得到余数得到余数1.因为余数不为因为余
7、数不为0，所以所以3不能整除不能整除7第三步第三步,用用4除除7,得到余数得到余数3.因为余数不为因为余数不为0，所以所以4不能整除不能整除7.第四步第四步,用用5除除7,得到余数得到余数2.因为余数不为因为余数不为0，所以所以5不能整除不能整除7.第五步第五步,用用6除除7,得到余数得到余数1.因为余数不为因为余数不为0，所以所以6不能整除不能整除7.因此，因此，7是质数是质数.例例1 1.(2).(2)设计一个算法判断设计一个算法判断3535是否为质是否为质数数.第一步第一步,用用2除除35,得到余数得到余数1.因为余数不为因为余数不为0，所以所以2不能整除不能整除35.第二步第二步,用用
8、3除除35,得到余数得到余数2.因为余数不为因为余数不为0，所以所以3不能整除不能整除35.第三步第三步,用用4除除35,得到余数得到余数3.因为余数不为因为余数不为0，所以所以4不能整除不能整除7.第四步第四步,用用5除除35,得到余数得到余数0.因为余数为因为余数为0，所以所以5能整除能整除35.因此，因此，35不是质数不是质数.探究：探究：你能写出你能写出“判断整数判断整数n（n2）是否为质数是否为质数”的算法吗？的算法吗？第一步：给定大于第一步：给定大于2 2的整数的整数n.第二步：令第二步：令i=2.=2.第三步：用第三步：用i除除n，得到余数，得到余数r.第四步：判断第四步：判断“
9、r=0”=0”是否成立是否成立.若是，则若是，则n不是不是质数，结束算法；否则，将质数，结束算法；否则，将i的值增加的值增加1 1，仍用，仍用i表示表示.第五步：判断第五步：判断“i（n-1）”是否成立是否成立.若是，若是，则则n是质数，结束算法；否则，返回第三步是质数，结束算法；否则，返回第三步.例例2.用二分法设计一个求方程用二分法设计一个求方程220 x 的近似根的算法的近似根的算法.(0)x 对于区间对于区间a,b 上连续不断、且上连续不断、且f(a)f(b)0的函数的函数y=f(x),通过不断地通过不断地把函数把函数f(x)的零点所在的区间一分的零点所在的区间一分为二，使区间的两个端
10、点逐步逼近为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法零点，进而得到零点近似值的方法叫做叫做二分法二分法.22(0)yxx第四步第四步,若若f(a)f(m)c,a+cb,b+ca是否同时成立是否同时成立,若是若是,则能组成三角形则能组成三角形;若否若否,则组不成三角形则组不成三角形.程序框图程序框图:a+bc,a+cb,b+ca是否是否同时成立同时成立?结束结束开始开始输入输入a,b,c是是存在这样的存在这样的三角形三角形不存在这样的不存在这样的三角形三角形否否开开 始始输入输入x值值x1结结 束束是是否否y=x+2y=-1输出输出y输出输出y例例5：请画出框图表示输入自变量：
11、请画出框图表示输入自变量x的一个的一个值，求分段函数值，求分段函数 的值。的值。1,11,2)(xxxxf开始开始输入输入xX3?否否是是结束结束y=5+1.2(x-3)输出输出yy=55,(3)51.2(3).(3)xyxx 【1】卫生费卫生费:计费方计费方法法:3人和人和3人以下人以下,每每户收户收5元元;超过超过3人的住人的住户户,每超过每超过1人加收人加收1.2元元,设计一个算法设计一个算法,根据根据输入的人数输入的人数,计算应收计算应收的卫生费的卫生费,并画出程序并画出程序框图框图.课堂练习结束结束开始开始y=1输入输入xX100?否否是是X5000?X100000?y=x1%y=5
12、0是是是是否否否否【2】观察所给程序框图】观察所给程序框图,说出它所表示的函数说出它所表示的函数.)100000 x5000(,50)5000 x100(,01.0 x)100 x(,1y 【3 3】已知函数已知函数 ，请画出输入请画出输入x的值，输出的值，输出 y的值的程序框图。的值的程序框图。1111101)(xxxxf开始开始结束结束是是否否xa?是是t=aa=b否否ca?是是t=a否否cb?t=c是是否否交换交换a,ba,b的值的值(3)循环结构循环结构-在一些算法中在一些算法中,也经常会出也经常会出现从某处开始现从某处开始,按照一定条件按照一定条件,反复执行某反复执行某一步骤的情况一
13、步骤的情况,这就是循环结构这就是循环结构.反复执行的步骤称为循环体反复执行的步骤称为循环体.注意注意:循环结构不能是永无终止的循环结构不能是永无终止的“死循死循环环”,一定要在某个条件下终止循环一定要在某个条件下终止循环,这这就需要条件结构来作出判断就需要条件结构来作出判断,因此因此,循环循环结构中一定包含条件结构结构中一定包含条件结构.直直到到型型循循环环结结构构 满足条件？满足条件？循环体循环体是是 直到型直到型循环循环执行了一次循环体执行了一次循环体之后之后,对控对控制循环条件进行判断制循环条件进行判断,当条件不满足时执行循当条件不满足时执行循环体环体,直到条件直到条件满足时终止循环满足
14、时终止循环.框图表示框图表示否否当当型型循循环环结结构构满足条件满足条件?循环体循环体是是否否 当型循环结构在每次执行循环体前对控制当型循环结构在每次执行循环体前对控制循环条件进行判断循环条件进行判断,当条件满足时执行循环体当条件满足时执行循环体,不满足则停止不满足则停止.是是否否开始开始i=1S=0S=S+ii=i+1i9?输出输出S结束结束直到直到型循型循环结环结构构是是否否开始开始i=1S=0S=S+ii=i+1i9?输出输出S结束结束开始开始i=1S=0i9?是是S=S+ii=i+1否否输出输出S结束结束当当型型循循环环结结构构开始开始i=1S=0i9?是是S=S+ii=i+1否否输出
15、输出S结束结束 循环结构中都有一个循环结构中都有一个计数变量和累加变量计数变量和累加变量：计计数变量数变量用以记录循环次数，同时它的取值还用于用以记录循环次数，同时它的取值还用于判断循环是否终止；判断循环是否终止；累加变量累加变量用于输出结果，累加变量和计数变量一用于输出结果，累加变量和计数变量一般是般是同步执行同步执行的，累加一次，计数一次的，累加一次，计数一次.例例6:6:设计一个计算设计一个计算1+2+3+1+2+3+100+100的值的算法的值的算法,并画出程序框图并画出程序框图.程序框图程序框图:是是否否开始开始i=1S=0S=S+ii=i+1i100?输出输出S结束结束直到直到型循
16、型循环结环结构构开始开始i=1S=0i100?是是S=S+ii=i+1否否输出输出S结束结束当型循环当型循环结构结构改进后的程序框图改进后的程序框图是是否否开始开始i=1S=0S=S+ii=i+1in?输出输出S结束结束输入输入nns131211 的值,并画出程序框图.设计一个算法求开始输入一个正整数n输出S的值结束S=0i=1S=S+1/ii=i+1inNY课堂练习结束结束输出输出SS 开始开始S S+ii i+YNi 0结束结束输出输出SS 开始开始i i+S S+i YNi 开始开始S 结束结束输出输出Si SSiii NY开始开始S 结束结束输出输出Si ii SSi NY当型当型 后
17、计数后计数直到型直到型 后计数后计数99531 S直到型直到型 先计数先计数当型当型 先计数先计数01112222111i99i=101i=99i97i101i99i99i97课堂练习开始开始n100？n=1S=0n是偶数是偶数?S=S-nnS=S+nnn=n+1输出输出S结束结束是是是是否否否否【1 1】该程序框图反映的实际问题是什么？】该程序框图反映的实际问题是什么？答：求答：求1 12 2-2-22 2+3+32 2-4-42 2+99+992 2-100-1002 2的值的值.课堂练习【2】设计一个算法框图，输出】设计一个算法框图，输出1000以以内能被内能被7整除的所有正整数整除的所
18、有正整数.开始开始输出输出n是是n1000否否k=1n=7kk=k+1结束结束开始开始输出输出x是是x1000否否x=0 x=x+7结束结束例例6：为了求满足：为了求满足1+2+n22?否是结束输出i-1i=1，s=0开始s=s+ii=i+1s22?否是课堂练习结束S=S+ii=i+1s22?输出i-1否是i=1，S=0开始结束i=i+1S=S+is 22?输出i否是i=0，S=0开始【2】设计一个算法框图：】设计一个算法框图：求使求使12n300”300”时终止循时终止循 环；环；（2 2）循环体：）循环体：s=s+0.05ss=s+0.05s，n=n+1n=n+1；设设s为某年的年生产总值
19、，为某年的年生产总值，n为年份为年份（1）输入初始值）输入初始值n=2005n=2005，s=200s=200；算法分析：算法分析：开始开始n=2005 s=200s=s+0.05s n=n+1s300？结束结束输出输出n是是否否程序框图程序框图：结束开始输处na=200t=0.05aa=a+tn=n+1a300Yn=2005N直到型直到型结束t0.05aaa+tnn+1开始输出na=200a300Nn=2005Y当型当型例：运行右边的程序框图，例：运行右边的程序框图，输出的是数列输出的是数列2n-1的前的前7项，若要使输出项，若要使输出的结果是数列的结果是数列3n-1的的前前7项，则须将处理
20、框项，则须将处理框A内的关系式变更为内的关系式变更为 。3 aa【1】根据如图所示的程序框图，将输出的】根据如图所示的程序框图，将输出的x、y值依次分别记为值依次分别记为x1，x2，xn，x2012；y1，y2，yn，y2012;x=1，y=2，n=1x=x+2YN结束n=n+1 n2012？开始输出x，yy=3y+2（）求数列）求数列xn的通项公式；的通项公式；（）求数列）求数列yn的通项公式；的通项公式；（）求数列）求数列xn+yn的前的前n项项和和(xN*，n2012)。解析：(1)由题意和框图知，数列xn中，x1=1，xn+1=xn+2xn=1+2(n1)=2n1(nN*，n2012)
21、(2)由框图知，数列yn中，yn+1=3yn+2yn+1+1=3(yn+1)，y1+1=3数列yn+1是以首项为3，公比为3的等比数列。yn+1=33n1=3nyn=3n1(nN*，n2012)A执行下面的程序框图，若执行下面的程序框图，若p4，则输出的，则输出的S等于等于()程序框图中，若输出程序框图中，若输出s的值为的值为7，则判断框内可填写，则判断框内可填写()Ai3?Bi4?Ci5?Di6?（2010浙江）（浙江）（1）某程序框图如图所示，）某程序框图如图所示，若输出的若输出的S=57，则判断框内，则判断框内为：为：（A）k4?（B）k5?（C）k6?（D）k7?A0101614121 下图给出的是计算的值的一个程序框图，其中判断框内应填入的条件是（）ABC DA开始结束输入SI=2S=0S=S+1/II=I+2100I 100I 50I 50I 100I 100I B直到型当型100I 是否
