算法初步课件_11_算法的概念

1、X20 世纪最伟大的科学技术发明世纪最伟大的科学技术发明-计算机计算机计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；没有软件的支持，超级计算机只是一堆废铁而已；没有软件的支持，超级计算机只是一堆废铁而已；什么是算法呢什么是算法呢？ 简单地说，算法就是解决问题的程序或步骤。简单地说，算法就是解决问题的程序或步骤。二元一次方程组二元一次方程组 12 12yxyx的求解过程的求解过程.归纳它的步骤归纳它的步骤:第一步第一步: 2+，得，得 5x=1 第三步第三步:第二步第二步: 解得解得 x= 第二步第二步: 解解得得 53y51代入将51x,得得 一般地一

2、般地, 按照一定规则解决某一类问题的明确和有按照一定规则解决某一类问题的明确和有限的步骤称为限的步骤称为算法算法(algorithm)。 所谓所谓 “ “算法算法”就是解题方法的精确描述就是解题方法的精确描述. .从更广义从更广义的角度来看的角度来看, ,并不是只有并不是只有“计算计算”的问题才有算法的问题才有算法, ,日常日常生活中处处都有生活中处处都有. .如如乐谱乐谱是乐队演奏的算法是乐队演奏的算法, ,菜谱菜谱是做菜是做菜肴的算法肴的算法, ,珠算口诀珠算口诀是使用算盘的算法是使用算盘的算法. .它是解决某一类问题的程序或步骤它是解决某一类问题的程序或步骤. .：3.算法的基本思想与特

3、征算法的基本思想与特征:2.算法的表示方法：算法的表示方法：自然语言、程序框图、程序自然语言、程序框图、程序(1)解决某一类问题解决某一类问题(2)在在有限步有限步之内完成之内完成(3)每一步的明确性和有效性每一步的明确性和有效性(4)每一步具有顺序性每一步具有顺序性(一般性一般性)(有限性有限性)(确定与可行性确定与可行性)(顺序性顺序性)例例1 1 在给定素数表的条件下，设计算法，将在给定素数表的条件下，设计算法，将936936分解分解成素因数的乘积成素因数的乘积.(4000.(4000以内的素数表见课本附录以内的素数表见课本附录1)1)解解: :算法步骤如下：算法步骤如下：1.1.判断判

4、断936936是否为素数：否是否为素数：否. .2.2.确定确定936936的最小素因数：的最小素因数：2. 936=22. 936=24684683.3.判断判断468468是否为素数：否是否为素数：否. .4.4.确定确定468468的最小素因数：的最小素因数：2. 936=22. 936=22 22342345.5.判断判断234234是否为素数：否是否为素数：否. .6.6.确定确定234234的最小素因数：的最小素因数：2. 936=22. 936=22 22 21171177.7.判断判断117117是否为素数：否是否为素数：否. .8.8.确定确定117117的最小素因数：的最小

5、素因数：3. 936=23. 936=22 22 23 339399.9.判断判断3939是否为素数：否是否为素数：否. .10.10.确定确定3939的最小素因数：的最小素因数：3. 936=23. 936=22 22 23 33 31313判断判断1313是否为素数：是否为素数：1313是素数，所以分解结束是素数，所以分解结束. .分解结果是：分解结果是： 936=2936=22 22 23 33 31313例例2 2、写出以下问题的算法：、写出以下问题的算法：一位商人有一位商人有9 9枚银元，其中有枚银元，其中有1 1枚略轻的是假银元枚略轻的是假银元. .你能你能用天平（不用砝码）将假银元找出来吗？用天平（不用砝码）将假银元找出来吗？一个人带一只狼和一只羚羊还有一堆白菜过河，只有一一个人带一只狼和一只羚羊还有一堆白菜过河，只有一条船，船可以容纳一个人和一个动物（或菜）没有人在条船，船可以容纳一个人和一个动物（或菜）没有人在的时候，狼就会吃掉羚羊，羚羊会吃掉白菜请设计过河的