《算法初步.ppt》由会员分享，可在线阅读，更多相关《算法初步.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机与算法计算机与算法:在现代社会里，计算机已经成为人在现代社会里，计算机已经成为人们日常生活和工作不可缺少的工们日常生活和工作不可缺少的工具听音乐、看电影、玩游戏、画具听音乐、看电影、玩游戏、画卡通画、处理数据卡通画、处理数据计算机几乎可计算机几乎可以是一个全能的助手，你可以用它以是一个全能的助手，你可以用它来做你想做的任何事情那么，计来做你想做的任何事情那么，计算机是怎样工作呢？要想弄清楚这算机是怎样工作呢？要想弄清楚这个问题，就需要学习算法个问题，就需要学习算法什么是算法？什么是算法？ 要把大象装冰箱，分几步？要把大象装冰箱，分几步？第一步：打开冰箱门第一步：打开冰箱门第二步：把大象装
2、第二步：把大象装冰箱冰箱第三步：关上冰箱门第三步：关上冰箱门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 得： 第二步第二步, ,第三步第三步, ,第四步第四步, ,第五步第五步, , 得到方程组的解
3、得得到方程组的解得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
4、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 广义地说，广义地说，算法就是做某算法就是做某一件事的步骤或程序一件事的步骤或程序。菜。菜谱是做菜肴的算法，洗衣谱是做菜肴的算法，洗衣机的使用说明书是操作洗机的使用说明书是操作洗衣机的算法，衣机的算法， 算法：算法： 在数学中算法通常指在数学中算法通常指按照一按照一定规则定规则 解决某一类问题的明确解决某一类问题的明确和
5、有限的步骤和有限的步骤. . 现在现在,算法通常可以编成计算算法通常可以编成计算机程序机程序,让计算机执行并解决问题让计算机执行并解决问题. 写出交换两个大小相同的杯子中写出交换两个大小相同的杯子中 的液体的液体 (A 水、水、 B 酒酒) 的一个算法的一个算法第一步第一步, ,找一个大小与找一个大小与A A相同的空杯子相同的空杯子C.C.第二步第二步, ,将将A A 中的水倒入中的水倒入C C中中. .第三步第三步, ,将将B B中的酒精倒入中的酒精倒入A A中中. .第四步第四步, ,将将C C中的水倒入中的水倒入B B中中, ,结束结束. .例例1.(1).(1)设计一个算法判断设计一个
6、算法判断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、，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不是质数不是质数.设计一个算法设
8、计一个算法,判断整数判断整数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.
9、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,2x +4；求求M(1，2)与
10、与N(3，5)两点连线的方程可两点连线的方程可先求先求MN的斜率再利用点斜式方程求得的斜率再利用点斜式方程求得A. 1 个个 B. 2 个个 C. 3 个个 D. 4 个个21C9写出求写出求123100的一个算法的一个算法.可以运用公式可以运用公式123n直接计算直接计算.第一步第一步；第二步第二步；第三步输出运算结果第三步输出运算结果. (1)2n n取取n100 计算计算 (1)2n n1已知一个学生的语文成绩为已知一个学生的语文成绩为89，数学，数学成绩为成绩为96，外语成绩为，外语成绩为99，求他的总分和，求他的总分和平均成绩的一个算法为：平均成绩的一个算法为：第一步取第一步取A89
11、，B96，C99;第二步第二步；第三步第三步；第四步输出第四步输出D，E.计算总分计算总分DA+B+C 计算平均成绩计算平均成绩E 3D一、算法的概念一、算法的概念 算法算法(algorithm)一词源于算术一词源于算术(algorism),即算术方法，是指一个即算术方法，是指一个由已知推求未知由已知推求未知的的运算过程。后来，人们把它推广到一般，运算过程。后来，人们把它推广到一般，把把进行某一工作的方法和步骤进行某一工作的方法和步骤称为算法。称为算法。 2.2.算法的特点算法的特点: :明确性明确性: :算法中的每一个步骤都是确切的算法中的每一个步骤都是确切的, ,能有效的能有效的执行且得到
12、确定的结果执行且得到确定的结果, ,不能模棱两可。不能模棱两可。有限性有限性: :算法应由有限步组成算法应由有限步组成, ,必须在有限操作之后必须在有限操作之后停止停止, ,并给出计算结果。并给出计算结果。思考：思考：有人对歌德巴赫猜想有人对歌德巴赫猜想“任何大于任何大于4的偶的偶数都能写成两个奇质数之和数都能写成两个奇质数之和”设计了设计了如下操作步骤：如下操作步骤：第一步：检验第一步：检验6=3+3 6=3+3 第二步：检验第二步：检验8=3+5第三步：检验第三步：检验10=5+5 . . . . . . 利用计算机无穷地进行下去！利用计算机无穷地进行下去！请问，利用这种程序能够证明猜想的
13、正确性吗？请问，利用这种程序能够证明猜想的正确性吗？ 这是一种算法吗？这是一种算法吗？2.2.算法的特点算法的特点: :明确性明确性: :算法中的每一个步骤都是确切的算法中的每一个步骤都是确切的, ,能有效的能有效的执行且得到确定的结果执行且得到确定的结果, ,不能模棱两可。不能模棱两可。有序性有序性: :算法从初始步骤开始算法从初始步骤开始, ,分为若干明确的步骤分为若干明确的步骤, ,每一步都只能有一个确定的继任者每一步都只能有一个确定的继任者, ,只有执行完前一步只有执行完前一步才能进入到后一步才能进入到后一步, ,并且每一步都确定无误后并且每一步都确定无误后, ,才能解才能解决问题。决
14、问题。不唯一性不唯一性: :求解某一个问题的解法不一定是唯一的求解某一个问题的解法不一定是唯一的, ,对对于同一个问题可以有不同的解法于同一个问题可以有不同的解法, ,但算法有优劣之分但算法有优劣之分, ,好的算法是我们追求的目标好的算法是我们追求的目标. .普适性普适性: :写出的算法必须能解决一类问题写出的算法必须能解决一类问题, ,并且能重复并且能重复使用使用, ,这是设计算法的一条基本原则这是设计算法的一条基本原则, ,这样才能使算法这样才能使算法更有价值更有价值. .有限性有限性: :算法应由有限步组成算法应由有限步组成, ,必须在有限操作之后必须在有限操作之后停止停止, ,并给出计算结果。并给出计算结果。