《算法的概念__行》由会员分享，可在线阅读，更多相关《算法的概念__行（53页珍藏版）》请在金锄头文库上搜索。
1、1.1.1算法的概念算法的概念 问题情境问题情境问题情境问题情境 【1】一一个个农农夫夫带带着着一一只只狼狼、一一头头山山羊羊和和一一篮篮蔬蔬菜菜要要过过河河,但但只只有有一一条条小小船船.乘乘船船时时,农农夫夫只只能能带带一一样样东东西西.当当农农夫夫在在场场的的时时候候,这这三三样样东东西西相相安安无无事事.一一旦旦农农夫夫不不在在,狼狼会会吃吃羊羊,羊羊会会吃吃菜菜.请请设设计计一一个个方方案案,使使农农夫夫能安全地将这三样东西带过河能安全地将这三样东西带过河.人鬼过河人鬼过河现在河的岸边有三个人和三个鬼，河上只有一条小船，现在河的岸边有三个人和三个鬼，河上只有一条小船，船上最多能坐两个
2、船上最多能坐两个“人人”，在河的任何一边，当鬼的个，在河的任何一边，当鬼的个数比人多时，鬼就会吃掉人。请问如何才能使人和鬼都数比人多时，鬼就会吃掉人。请问如何才能使人和鬼都平安的到达对岸。平安的到达对岸。 在在中中央央电电视视台台幸幸运运5252节节目目中中, ,有有一一个个猜猜商商品品价价格格的的环环节节, ,竟竟猜猜者者如如在在规规定定的的时时间间内内大大体体猜猜出出某某种种商商品品的的价价格格, ,就就可可获获得得该该件件商商品品. .现现有有一一商商品品, ,价价格格在在0-0-80008000元元之之间间, ,采采取取怎怎样样的的策策略略才才能能在在短短的时间内说出正确的时间内说出正
3、确( (大体上大体上) )的答案呢的答案呢? ?第一步第一步:报报“4000”；第二步第二步:若主持人说高了若主持人说高了第三步第三步:重复第二步的报数方法取中间重复第二步的报数方法取中间数数,直至得到正确结果直至得到正确结果.(说明答案在说明答案在04000之间之间),就就报报“2000”,否则否则:(答数在答数在40008000之间之间)报报“6000”；例例.写出交换两个大小相同的杯子中写出交换两个大小相同的杯子中 的液体的液体 (A 水、水、 B 酒酒) 的一个过程的一个过程例例.写出交换两个大小相同的杯子中写出交换两个大小相同的杯子中 的液体的液体 (A 水、水、 B 酒酒) 的一个
4、过程的一个过程第一步第一步, ,找一个大小与找一个大小与A A相同的空杯子相同的空杯子C.C.第二步第二步, ,将将A A 中的水倒入中的水倒入C C中中. .第三步第三步, ,将将B B中的酒精倒入中的酒精倒入A A中中. .第四步第四步, ,将将C C中的水倒入中的水倒入B B中中, ,结束结束. . 问题情境问题情境问题情境问题情境 【2】“鸡兔同笼鸡兔同笼”是我国隋朝时期的数是我国隋朝时期的数学著作学著作孙子算经孙子算经中的一个有趣而具中的一个有趣而具有深远影响的题目：有深远影响的题目： “今有鸡兔同笼，今有鸡兔同笼，上有三十五头，下有九十四足，问：鸡上有三十五头，下有九十四足，问：鸡
5、兔各几何？兔各几何？” 解决问题解决问题解决问题解决问题【2】“鸡兔同笼鸡兔同笼”是我国隋朝时期的数学著作是我国隋朝时期的数学著作孙子算经孙子算经中的一个有趣而具有深远影响的题中的一个有趣而具有深远影响的题目：目： “今有鸡兔同笼，上有三十五头，下有九十今有鸡兔同笼，上有三十五头，下有九十四足，问：鸡兔各几何？四足，问：鸡兔各几何？” 解：解： 设设 笼子里有鸡笼子里有鸡 只，兔子只，兔子 只只. .列列得得解解得得答：答： 笼子中有鸡笼子中有鸡2323只，兔只，兔1212只只. .式式设设列列解解答：答： 提出问题提出问题提出问题提出问题 解方程解方程 解决问题解决问题解决问题解决问题 解方
6、程解方程第一步第一步, ,由（由（1）得）得第二步第二步, ,将（将（3）代入（）代入（2）得）得第三步第三步, , 解（解（4）得）得第四步第四步, , 将（将（5）代入（）代入（3）得）得第五步第五步, , 得到方程组的解得得到方程组的解得 解决问题解决问题解决问题解决问题解方程解方程第一步第一步, ,第二步第二步, ,第三步第三步, ,第四步第四步, ,第五步第五步, , 得到方程组的解得得到方程组的解得步骤：步骤： S1 设未知数；设未知数；S2 根据题意列方程组；根据题意列方程组；S3 解方程组；解方程组；S4 还原实际问题，得到实际问题的答案。还原实际问题，得到实际问题的答案。 提
7、出问题提出问题提出问题提出问题【3】写出一般二元一次方程组的解法步骤写出一般二元一次方程组的解法步骤. . 第一步第一步, 第二步第二步,解（解（3）得）得 解决问题解决问题解决问题解决问题 【3】写出一般二元一次方程组的解法步骤写出一般二元一次方程组的解法步骤. . 第四步第四步,解（解（4）得）得 第三步第三步, 第五步第五步,得到方程得到方程组的解的解为 算法的概念算法的概念算法的概念算法的概念 算法：算法： 在数学中算法通常指在数学中算法通常指按照一按照一定定规则规则 解决某一类问题的解决某一类问题的明确明确和和有限有限的步骤的步骤. . 现在现在,算法通常可以编成计算算法通常可以编成
8、计算机程序机程序,让计算机执行并解决问题让计算机执行并解决问题. 算法的概念算法的概念 理解理解 算法算法(algorithm)一词源于算术一词源于算术(algorism),即算术方法，是指一个即算术方法，是指一个由已知推求未知由已知推求未知的的运算过程。后来，人们把它推广到一般，运算过程。后来，人们把它推广到一般，把把进行某一工作的方法和步骤进行某一工作的方法和步骤称为算法。称为算法。 注意：写在笔记上 算法算法作为一个名词，在中学教科书中作为一个名词，在中学教科书中并没有出现过，我们在基础教育阶段还并没有出现过，我们在基础教育阶段还没有接触算法概念。但是我们却从小学没有接触算法概念。但是我
9、们却从小学就开始接触算法，熟悉许多问题的算法。就开始接触算法，熟悉许多问题的算法。如，做四则运算要如，做四则运算要先乘除后加减先乘除后加减，从里，从里往外脱括弧，竖式笔算等都是算法，至往外脱括弧，竖式笔算等都是算法，至于于乘法口诀乘法口诀、珠算口诀珠算口诀更是算法的具体更是算法的具体体现。体现。 广义地说，广义地说，算法就是做某一件事的步算法就是做某一件事的步骤或程序骤或程序。菜谱是做菜肴的算法，洗衣。菜谱是做菜肴的算法，洗衣机的使用说明书是操作洗衣机的算法，机的使用说明书是操作洗衣机的算法，歌谱是一首歌曲的算法。歌谱是一首歌曲的算法。 在数学中，在数学中，主要研究计算机能实现的主要研究计算机
10、能实现的算法算法，即按照某种机械程序步骤一定可，即按照某种机械程序步骤一定可以得到结果的解决问题的程序。比如解以得到结果的解决问题的程序。比如解方程的算法、函数求值的算法、作图的方程的算法、函数求值的算法、作图的算法，等等。算法，等等。 我们知道我们知道解一元二次方程解一元二次方程的算法，求的算法，求解一元一次不等式、一元二次函数图象解一元一次不等式、一元二次函数图象的画法，解线性方程组的算法，求两个的画法，解线性方程组的算法，求两个数的最大公因数的算法等。因此，数的最大公因数的算法等。因此，算法其实是重要的数学对象算法其实是重要的数学对象。 巩固概念巩固概念巩固概念巩固概念 例例1.写出求一
11、元二次方程写出求一元二次方程 ax2+bx+c=0 的根的算法的根的算法.第一步第一步, ,计算计算=b b2 2-4-4acac. .第二步第二步, ,如果如果0,2) 2) 是否为质数是否为质数. .注意：书上第4页 应用举例应用举例应用举例应用举例 例例3. .用二分法设计一个求方程用二分法设计一个求方程的近似根的算法的近似根的算法. .注意：书上第4页 分析问题分析问题分析问题分析问题 二分法 对于区间对于区间a,b 上连续不断、且上连续不断、且f(a)f(b)0的函数的函数y=f(x),通过不断地通过不断地把函数把函数f(x)的零点所在的区间一分的零点所在的区间一分为二，使区间的两个
12、端点逐步逼近为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法零点，进而得到零点近似值的方法叫做叫做二分法二分法. 探究解决探究解决探究解决探究解决 解决问题解决问题解决问题解决问题 第四步第四步, 若若f(a) f(m) n-1” 是否成立是否成立,若是若是, ,再输出再输出n和和1, 结束算结束算法法,否则返回第三步否则返回第三步.二、算法的特点二、算法的特点 不论在哪一种算法中，它们都是经有限不论在哪一种算法中，它们都是经有限次步骤完成的，因而它们体现了次步骤完成的，因而它们体现了算法的有算法的有穷性穷性。 在算法中，每一步都能明确地执行，在算法中，每一步都能明确地执行，且有确
13、定的结果，因此具有且有确定的结果，因此具有确定性确定性。 在所有算法中，每一步操作都是可以在所有算法中，每一步操作都是可以执行的，也就是具有执行的，也就是具有可行性可行性。2.2.体现算法的什么特点？体现算法的什么特点？思考：思考：你对以下的你对以下的“算法算法”如何理解？如何理解？问：问：要把大象装冰箱，分几步？要把大象装冰箱，分几步？有穷性，明确性，可行性 为了便于计算机运算，它们必须先输入为了便于计算机运算，它们必须先输入已知数据，而计算的目的分别是解方程组已知数据，而计算的目的分别是解方程组和求最大值等，因此必须输出结果，也就和求最大值等，因此必须输出结果，也就是必须有输入和输出。是必
14、须有输入和输出。 算法解决的都是一类问题（分别是解决算法解决的都是一类问题（分别是解决求方程组的解和确定一个有理整数序列中求方程组的解和确定一个有理整数序列中的最大值问题），因此具有的最大值问题），因此具有普适性普适性。体验体验 ：写出解方程：写出解方程x22x3=0的一个算法的一个算法. 配方法：配方法：S1 移项，得移项，得x22x=3 S2 式两边同加式两边同加1并配方得并配方得 (x1)2=4 S3 式两边开方，得式两边开方，得x1=2 S4 解解式得式得x=3或或x=1因式分解法：因式分解法：S1 将方程左边因式分解得将方程左边因式分解得(x3)(x+1)=0 S2 由由得得x3=0
15、或或x+1=0 S3 解解得得x=3或或x1公式法：公式法：S1 计算方程的判别式，判断其符号计算方程的判别式，判断其符号 =(2)24(3)0；S2 将将a=1，b=2，c=3代入求根公式，代入求根公式， 得得x=3或或x=1例例3 写出求写出求1+2+3+4+5+6的一个算法。的一个算法。解：算法解：算法1：S1 计算计算1+2得到得到3；S2 将第一步中的运算结果将第一步中的运算结果3与与3相加得到相加得到6S3 将第二步中的运算结果将第二步中的运算结果6与与4相加得到相加得到10S4 将第三步中的运算结果将第三步中的运算结果10与与5相加得到相加得到15S5 将第四步中的运算结果将第四
16、步中的运算结果15与与6相加得到相加得到21算法算法2：S1：取：取n=6；S2：计算：计算S3：输出运算结果。：输出运算结果。算法算法3：S1 将原式变形为将原式变形为(1+6)+(2+5)+(3+4)=37；S2 计算计算37；S3 输出运算结果。输出运算结果。例例4. 求求1357911的值，写出其算法。的值，写出其算法。算法算法1；第一步，先求第一步，先求13，得到结果，得到结果3；第二步，将第一步所得结果第二步，将第一步所得结果3再乘以再乘以5，得，得到结果到结果15；第三步，再将第三步，再将15乘以乘以7，得到结果，得到结果105；第四步，再将第四步，再将105乘以乘以9，得到，得
17、到945；第五步，再将第五步，再将945乘以乘以11，得到，得到10395，即，即是最后结果。是最后结果。例例8 一位商人有一位商人有9枚银元，其中有枚银元，其中有1枚略轻枚略轻的是假银元，你能用天平（不用砝码）将的是假银元，你能用天平（不用砝码）将假银元找出来吗？假银元找出来吗？ 算法一：算法一：S1 任取任取2枚银元分别放在天平的两边，如枚银元分别放在天平的两边，如果天平左右不平衡，则轻的一边就是假银果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则进行元；如果天平平衡，则进行S2；S2 取下右边的银元放在一边，然后把剩余取下右边的银元放在一边，然后把剩余的的7枚银元依次在右边进行称
18、量，直到天枚银元依次在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元。平不平衡，偏轻的那一枚就是假银元。算法二：算法二： S1 任取任取2枚银元分别放在天平的两边，如枚银元分别放在天平的两边，如果天平左右不平衡，则轻的一边就是假银果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则进行元；如果天平平衡，则进行S2；S2 从余下的从余下的7枚银元中再任取枚银元中再任取2枚分别放枚分别放在天平的两边，如果天平左右不平衡则轻在天平的两边，如果天平左右不平衡则轻的一边就是假银元；如果天平平衡，则进的一边就是假银元；如果天平平衡，则进行行S3；S3 从余下的从余下的5枚银元中再任取枚银元中再任
19、取2枚分别放枚分别放在天平的两边，如果天平左右不平衡，则在天平的两边，如果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则轻的一边就是假银元；如果天平平衡，则进行进行S4；S4 从余下的从余下的3枚银元中再任取枚银元中再任取2枚分别放枚分别放在天平的两边，如果天平左右不平衡，则在天平的两边，如果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则轻的一边就是假银元；如果天平平衡，则最后剩下的还未称的最后剩下的还未称的1枚银元就是假银元。枚银元就是假银元。算法三：算法三：S1 任取任取4枚银元分别放在天平的两边，各枚银元分别放在天平的两边，各2枚，如果天平左右不平衡，则轻的一边中枚，如果
20、天平左右不平衡，则轻的一边中含有假银元，并进行含有假银元，并进行S2；如果天平平衡，；如果天平平衡，则进行则进行S3；S2 将轻的一边的两枚银元分别放在天平将轻的一边的两枚银元分别放在天平的两边，则轻的一边的那枚银元就是假银的两边，则轻的一边的那枚银元就是假银元，称量结束；元，称量结束；S3 从余下的从余下的5枚银元中再任取枚银元中再任取4枚分别放枚分别放在天平的两边，各在天平的两边，各2枚，如果天平左右不平枚，如果天平左右不平衡，则轻的一边就含有假银元，并转向衡，则轻的一边就含有假银元，并转向S2；如果天平平衡，则最后剩下的还未称的；如果天平平衡，则最后剩下的还未称的1枚银元就是假银元，称量
21、结束。枚银元就是假银元，称量结束。算法四：算法四：S1 把银元分成把银元分成3组，每组组，每组3枚；枚；S2 先将两组分别放在天平的两边，如果先将两组分别放在天平的两边，如果天平不平衡，那么假银元就在轻的那一组；天平不平衡，那么假银元就在轻的那一组；如果天平左右平衡，则假银元就在未称的如果天平左右平衡，则假银元就在未称的第第3组里；组里；S3 取出含假银元的那一组，从中任取两取出含假银元的那一组，从中任取两枚银元放在天平的两边，如果左右不平衡，枚银元放在天平的两边，如果左右不平衡，则轻的那一边就是假银元；如果天平两边则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元平衡，则未称
22、的那一枚就是假银元.1下面的四种叙述不能称为算法的是（下面的四种叙述不能称为算法的是（ ）（A）广播的广播操图解）广播的广播操图解 （B）歌曲的歌谱）歌曲的歌谱 （C）做饭用米）做饭用米 （D）做米饭需要刷锅、淘米、添水、加）做米饭需要刷锅、淘米、添水、加热这些步骤热这些步骤练习题练习题C2下列关于算法的说法正确的是（下列关于算法的说法正确的是（ ）（A）某算法可以无止境地运算下去）某算法可以无止境地运算下去 （B）一个问题的算法步骤可以是可逆的）一个问题的算法步骤可以是可逆的 （C）完成一件事情的算法有且只有一种）完成一件事情的算法有且只有一种 （D）设计算法要本着简单、方便、可操）设计算法
23、要本着简单、方便、可操作的原则作的原则 D3下列关于算法的说法中，正确的是（下列关于算法的说法中，正确的是（ ）.A. 算法就是某个问题的解题过程算法就是某个问题的解题过程 B. 算法执行后可以不产生确定的结果算法执行后可以不产生确定的结果C. 解决某类问题的算法不是惟一的解决某类问题的算法不是惟一的 D. 算法可以无限地操作下去不停止算法可以无限地操作下去不停止C4下列运算中不属于我们所讨论算法范下列运算中不属于我们所讨论算法范畴的是（畴的是（ ）.A. 已知圆的半径求圆的面积已知圆的半径求圆的面积 B. 从一副扑克牌随意抽取从一副扑克牌随意抽取3张扑克牌抽到张扑克牌抽到24点的可能性点的可
24、能性C. 已知坐标平面内的两点求直线的方程已知坐标平面内的两点求直线的方程 D. 加减乘除运算法则加减乘除运算法则B5下列语句表达中是算法的有（下列语句表达中是算法的有（ ）. 从济南到巴黎可以先乘火车到北京再坐从济南到巴黎可以先乘火车到北京再坐飞机抵达；飞机抵达；利用公式利用公式 S = ah2 计算底为计算底为1高为高为2的三的三角形的面积；角形的面积； x2x +4；求求M(1，2)与与N(3，5)两点连线的方程可两点连线的方程可先求先求MN的斜率再利用点斜式方程求得的斜率再利用点斜式方程求得A. 1 个个 B. 2 个个 C. 3 个个 D. 4 个个C6写出求写出求123100的一个算法的一个算法.可以运用公式可以运用公式123n直接计算直接计算.第一步第一步；第二步第二步；第三步输出运算结果第三步输出运算结果. 取取n100 计算计算 7已知一个学生的语文成绩为已知一个学生的语文成绩为89，数学成，数学成绩为绩为96，外语成绩为，外语成绩为99，求他的总分和平，求他的总分和平均成绩的一个算法为：均成绩的一个算法为：第一步取第一步取A89，B96，C99;第二步第二步；第三步第三步；第四步输出第四步输出D，E.计算总分计算总分DA+B+C 计算平均成绩计算平均成绩E
