算法的概念ppt课件.ppt

计算机与算法计算机与算法:在现代社会里，计算机已经成为人在现代社会里，计算机已经成为人们日常生活和工作不可缺少的工们日常生活和工作不可缺少的工具听音乐、看电影、玩游戏、画具听音乐、看电影、玩游戏、画卡通画、处理数据卡通画、处理数据计算机几乎可计算机几乎可以是一个全能的助手，你可以用它以是一个全能的助手，你可以用它来做你想做的任何事情那么，计来做你想做的任何事情那么，计算机是怎样工作呢？要想弄清楚这算机是怎样工作呢？要想弄清楚这个问题，就需要学习算法个问题，就需要学习算法什么是算法？什么是算法？ 算法的概念算法的概念任课教师：张艳梅任课教师：张艳梅 问题2：要把大象装冰箱，要把大象装冰箱， 分几步？分几步？第一步：打开冰箱门第一步：打开冰箱门第二步：把大象装冰箱第二步：把大象装冰箱第三步：关上冰箱门第三步：关上冰箱门创设情境 给出定义创设情境 给出定义问题2：有一个农夫带一条狼、一只羊和一筐白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？ 解决步骤：1、带羊到对岸，返回；2、带菜到对岸，并把羊带回；3、带狼到对岸，返回；4、带羊到对岸。35(1)2494(2)xyxy你能写出解方程组你能写出解方程组 的步骤吗？的步骤吗？第一步第一步, ,由（由（1）得）得35(3)xy第二步第二步, ,将（将（3）代入（）代入（2）得）得2(35)494(4)yy第三步第三步, , 解（解（4）得）得12(5)y 第四步第四步, , 将（将（5）代入（）代入（3）得）得23x 第五步第五步, , 得到方程组的解得得到方程组的解得2312xy35(1)2494(2)xyxy你能写出解方程组你能写出解方程组 的步骤吗？的步骤吗？第一步第一步, ,(1)2(2)224(3)y 得： 第二步第二步, ,第三步第三步, ,第四步第四步, ,第五步第五步, , 得到方程组的解得得到方程组的解得2312xy(3)12y 解得：(1)4(2)246(4)x得：(4)23x 解得：写出一般二元一次方程组的解法步骤写出一般二元一次方程组的解法步骤. .1111 22 1222(1)0(2)a xb ycaba ba xb yc 第一步第一步,21(1)(2)bb得 ：12211221a ba bxc bc b（ 3） 第二步第二步,解（解（3）得）得 12211221c bc bxa ba b写出一般二元一次方程组的解法步骤写出一般二元一次方程组的解法步骤. .1111 22 1222(1)0(2)a xb ycaba ba xb yc 2 11 22 11 2a ca cya bab 第四步第四步,解（解（4）得）得 21(1)(2)aa得：第三步第三步,2 11 22 11 2a ba bya ca c（4） 第五步第五步,得到方程组的解为得到方程组的解为 1221122121122112c bc bxa ba ba ca cya ba b写出一般二元一次方程组的解法步骤写出一般二元一次方程组的解法步骤. .1111 22 1222(1)0(2)a xb ycaba ba xb yc第一步第一步,21(1)(2 )bb得 ：12211221a ba bxc bc b（ 3） 第二步第二步,解（解（3）得）得 12211221c bc bxa ba b2 11 22 11 2a ca cya bab 第四步第四步,解（解（4）得）得 21(1)(2)aa得 ：第三步第三步,21122112a ba bya ca c（ 4） 第五步第五步,得到方程组的解为得到方程组的解为 1221122121122112c bc bxa ba ba ca cya ba b 广义地说，广义地说，算法就是做某算法就是做某一件事的步骤或程序一件事的步骤或程序。菜。菜谱是做菜肴的算法，洗衣谱是做菜肴的算法，洗衣机的使用说明书是操作洗机的使用说明书是操作洗衣机的算法，衣机的算法， 算法的概念算法的概念 算法：算法： 在数学中算法通常指在数学中算法通常指按照一按照一定规则定规则 解决某一类问题的明确解决某一类问题的明确和有限的步骤和有限的步骤. . 现在现在,算法通常可以编成计算算法通常可以编成计算机程序机程序,让计算机执行并解决问题让计算机执行并解决问题. 程序性程序性明确性明确性有限性有限性不唯一性不唯一性普适性普适性 巩固概念巩固概念 写出交换两个大小相同的杯子中写出交换两个大小相同的杯子中 的液体的液体 (A 水、水、 B 酒酒) 的一个算法的一个算法第一步第一步, ,找一个大小与找一个大小与A A相同的空杯子相同的空杯子C.C.第二步第二步, ,将将A A 中的水倒入中的水倒入C C中中. .第三步第三步, ,将将B B中的酒精倒入中的酒精倒入A A中中. .第四步第四步, ,将将C C中的水倒入中的水倒入B B中中, ,结束结束. . 应用举例应用举例 例例1.(1).(1)设计一个算法判断设计一个算法判断7 7是否为质数是否为质数. .第一步第一步, 用用2除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以2不能整除不能整除7.第二步第二步, 用用3除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以3不能整除不能整除7.第三步第三步, 用用4除除7,得到余数得到余数3.因为余数不为因为余数不为0， 所以所以4不能整除不能整除7.第四步第四步, 用用5除除7,得到余数得到余数2.因为余数不为因为余数不为0， 所以所以5不能整除不能整除7.第五步第五步, 用用6除除7,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以6不能整除不能整除7.因此，因此，7是质数是质数. 应用举例应用举例 例例1.(2).(2)设计一个算法判断设计一个算法判断3535是否为质是否为质数数. .第一步第一步, 用用2除除35,得到余数得到余数1.因为余数不为因为余数不为0， 所以所以2不能整除不能整除35.第二步第二步, 用用3除除35,得到余数得到余数2.因为余数不为因为余数不为0， 所以所以3不能整除不能整除35.第三步第三步, 用用4除除35,得到余数得到余数3.因为余数不为因为余数不为0， 所以所以4不能整除不能整除7.第四步第四步, 用用5除除35,得到余数得到余数0.因为余数为因为余数为0， 所以所以5能整除能整除35.因此，因此，35不是质数不是质数.判断53是否为质数。第一步，用2除53，得到余数1。因为余数不为0，所以2不能整除53。第二步，用3除53，得到余数2。因为余数不为0，所以3不能整除53。第三步，用4除53，得到余数1。因为余数不为0，所以4不能整除53。第五十一步，用52除53，得到余数1。因为余数不为0，所以52不能整除53。因此，53是质数。不是算法以下是算法吗？第二步：用i除53，得到余数是r；第三步：判断r是否为0，若是，则53不是质数，结束算法；否则，将i的值增加1，仍用i表示； 第四步：判断i52是否成立。若是，则53是质数，结束算法；否则，返回第三步。探究：设计一个算法探究：设计一个算法,判断整数判断整数n(n2)是否为质数是否为质数?第一步，给定大于第一步，给定大于2的整数的整数n。第二步，令第二步，令i=2第三步，用第三步，用i除除n，得到余数，得到余数r。第四步，判断第四步，判断“r=0”是否成立。是否成立。第五步，判断第五步，判断“i(n-1)”是否成立。是否成立。 若是，则若是，则n不是质不是质数，结束算法数，结束算法;否则，将否则，将i的值增加的值增加1，仍用，仍用i表示。表示。 若是，则若是，则n不是不是质数，结束算法质数，结束算法;否则，返回第三步。否则，返回第三步。11.521.251.3752+2+1.5+1-a ab ba-ba-b11211.50.51.50.251.251.50.1251.37512+1.5+1.251.375-2+1.5+1.251-22 xy1- -例例2 用二分法设计一个求方程用二分法设计一个求方程 x2 2 = 0 的近似根的算法。的近似根的算法。旧知识回顾：旧知识回顾：用二分法求函数的零点用二分法求函数的零点 解决问题解决问题 第四步第四步, 若若f(a) f(m) n”是否成立，若是，则结束算法；否则是否成立，若是，则结束算法；否则返回第三步返回第三步. 巩固概念巩固概念 3、写出求一元二次方程、写出求一元二次方程 ax2+bx+c=0 的根的算法的根的算法.第一步第一步, ,计算计算=b b2 2-4-4acac. .第二步第二步, ,如果如果0,0,则原方程无实数解则原方程无实数解 ; ;否则否则(0(0时时)，,a2bx1 .a2bx2 第三步第三步: :输出输出x x1 1, , x x2 2或无实数解的信息或无实数解的信息. .4下面的四种叙述不能称为算法的是下面的四种叙述不能称为算法的是（ ）（A）广播的广播操图解）广播的广播操图解 （B）歌曲的歌谱）歌曲的歌谱 （C）做饭用米）做饭用米 （D）做米饭需要刷锅、淘米、添水、加）做米饭需要刷锅、淘米、添水、加热这些步骤热这些步骤练习题练习题C5下列关于算法的说法正确的是（下列关于算法的说法正确的是（ ）（A）某算法可以无止境地运算下去）某算法可以无止境地运算下去 （B）一个问题的算法步骤可以是可逆的）一个问题的算法步骤可以是可逆的 （C）完成一件事情的算法有且只有一种）完成一件事情的算法有且只有一种 （D）设计算法要本着简单、方便、可操）设计算法要本着简单、方便、可操作的原则作的原则 D6下列关于算法的说法中，正确的是下列关于算法的说法中，正确的是（ ）.A. 算法就是某个问题的解题过程算法就是某个问题的解题过程 B. 算法执行后可以不产生确定的结果算法执行后可以不产生确定的结果C. 解决某类问题的算法不是惟一的解决某类问题的算法不是惟一的 D. 算法可以无限地操作下去不停止算法可以无限地操作下去不停止C7下列运算中不属于我们所讨论算法范下列运算中不属于我们所讨论算法范畴的是（畴的是（ ）.A. 已知圆的半径求圆的面积已知圆的半径求圆的面积 B. 从一副扑克牌随意抽取从一副扑克牌随意抽取3张扑克牌抽到张扑克牌抽到24点的可能性点的可能性C. 已知坐标平面内的两点求直线的方程已知坐标平面内的两点求直线的方程 D. 加减乘除运算法则加减乘除运算法则B8写出求写出求123100的一个算法的一个算法.可以运用公式可以运用公式123n直接计算直接计算.第一步第一步；第二步第二步；第三步输出运算结果第三步输出运算结果. (1)2n n取取n100 计算计算 (1)2n n9已知一个学生的语文成绩为已知一个学生的语文成绩为89，数学，数学成绩为成绩为96，外语成绩为，外语成绩为99，求他的总分和，求他的总分和平均成绩的一个算法为：平均成绩的一个算法为：第一步取第一步取A89，B96，C99;第二步第二步；第三步第三步；第四步输出第四步输出D，E.计算总分计算总分DA+B+C 计算平均成绩计算平均成绩E 3D一、算法的概念一、算法的概念 算法算法(algorithm)一词源于算术一词源于算术(algorism),即算术方法，是指一个即算术方法，是指一个由已知推求未知由已知推求未知的运算过程。后来，的运算过程。后来，人们把它推广到一般，把人们把它推广到一般，把进行某一进行某一工作的方法和步骤工作的方法和步骤称为算法。称为算法。 在数学中算法通常指在数学中算法通常指按按照一定规则照一定规则 解决某一类问题解决某一类问题的明确和有限的步骤的明确和有限的步骤. . 归纳小结归纳小结2.2.算法的特点算法的特点: :明确性明确性: :算法中的每一个步骤都是确切的算法中的每一个步骤都是确切的, ,能有效的能有效的执行且得到确定的结果执行且得到确定的结果, ,不能模棱两可。不能模棱两可。有限性有限性: :算法应由有限步组成算法应由有限步组成, ,必须在有限操作之后必须在有限操作之后停止停止, ,并给出计算结果。并给出计算结果。思考：思考：有人对歌德巴赫猜想有人对歌德巴赫猜想“任何大于任何大于4的偶的偶数都能写成两个奇质数之和数都能写成两个奇质数之和”设计了设计了如下操作步骤：如下操作步骤：第一步：检验第一步：检验6=3+3 6=3+3 第二步：检验第二步：检验8=3+5第三步：检验第三步：检验10=5+5 . . . . . . 利用计算机无穷地进行下去！利用计算机无穷地进行下去！请问，利用这种程序能够证明猜想的正确性吗？请问，利用这种程序能够证明猜想的正确性吗？ 这是一种算法吗？这是一种算法吗？2.2.算法的特点算法的特点: :明确性明确性: :算法中的每一个步骤都是确切的算法中的每一个步骤都是确切的, ,能有效的能有效的执行且得到确定的结果执行且得到确定的结果, ,不能模棱两可。不能模棱两可。程序性程序性: :算法从初始步骤开始算法从初始步骤开始, ,分为若干明确的步骤分为若干明确的步骤, ,每一步都只能有一个确定的继任者每一步都只能有一个确定的继任者, ,只有执行完前一步只有执行完前一步才能进入到后一步才能进入到后一步, ,并且每一步都确定无误后并且每一步都确定无误后, ,才能解才能解决问题。决问题。不唯一性不唯一性: :求解某一个问题的解法不一定是唯一的求解某一个问题的解法不一定是唯一的, ,对对于同一个问题可以有不同的解法于同一个问题可以有不同的解法, ,但算法有优劣之分但算法有优劣之分, ,好的算法是我们追求的目标好的算法是我们追求的目标. .普适性普适性: :写出的算法必须能解决一类问题写出的算法必须能解决一类问题, ,并且能重复并且能重复使用使用, ,这是设计算法的一条基本原则这是设计算法的一条基本原则, ,这样才能使算法这样才能使算法更有价值更有价值. .有限性有限性: :算法应由有限步组成算法应由有限步组成, ,必须在有限操作之后必须在有限操作之后停止停止, ,并给出计算结果。并给出计算结果。