必修三算法的概念省公共课一等奖全国赛课获奖课件.pptx

1.1.1 算法概念算法概念第1页章头图说明 章头图后景是元代朱世杰所著四元玉鉴，前景前部是一台计算机，后部是盛行一时计算工具算筹和算盘。第2页 中国古代数学在世界数学史上一度居于领先地们，它重视实际问题处理，以算法为中心，寓理于算，其中蕴涵了丰富算法思想，算筹是中国古代计算工具，在春秋时期已经很普遍；算盘在明代开始盛行，即使在计算机普及今天，许多人依然在使用算盘。中国古代涌现了许多著名数学家，如三国及两晋时期赵爽、刘徽，南北朝祖冲之、宋、元时期秦九韶、杨辉、朱世杰，等。古时著名数学专著如九章算术周髀算经数书九章四元玉鉴等。全部这些成就，都使中国数学曾经处于世界巅峰。数学史介绍第3页计算机问世可谓是计算机问世可谓是20世纪最伟大科学技术世纪最伟大科学技术创造。它把人类社会带进了信息技术时代。创造。它把人类社会带进了信息技术时代。计算机是对人脑模拟，它强化了人思维智能；计算机是对人脑模拟，它强化了人思维智能；二十一世纪信息社会两个主要特征：“计算机无处不在”“数学无处不在”二十一世纪信息社会对科技人才要求：-会“用数学”解决实际问题-会用计算机进行科学计算第4页算法研究和应用正是本课程主题算法研究和应用正是本课程主题算法研究和应用正是本课程主题算法研究和应用正是本课程主题 ！当代科学研究三大支柱理论研究科学试验科学计算第5页而算法是计算机科学主要基础。就像使用算而算法是计算机科学主要基础。就像使用算盘一样，人们需要给计算机编制盘一样，人们需要给计算机编制“口决口决”算法，算法，才能让它工作，不然超级计算机只是一堆废铁而才能让它工作，不然超级计算机只是一堆废铁而已。已。要想了解计算机工作原理，算法学习是一个要想了解计算机工作原理，算法学习是一个要想了解计算机工作原理，算法学习是一个要想了解计算机工作原理，算法学习是一个开始开始开始开始第6页问题提出问题提出 有一个农夫带一条狼狗、一只羊和有一个农夫带一条狼狗、一只羊和一筐白菜过河。假如没有农夫看管，则一筐白菜过河。假如没有农夫看管，则狼狗要吃羊，羊要吃白菜。不过船很小，狼狗要吃羊，羊要吃白菜。不过船很小，只够农夫带一样东西过河。问农夫该怎只够农夫带一样东西过河。问农夫该怎样解此难题？样解此难题？第7页问题提出问题提出 有一个农夫带一条狼狗、一只羊和有一个农夫带一条狼狗、一只羊和一筐白菜过河。假如没有农夫看管，则一筐白菜过河。假如没有农夫看管，则狼狗要吃羊，羊要吃白菜。不过船很小，狼狗要吃羊，羊要吃白菜。不过船很小，只够农夫带一样东西过河。问农夫该怎只够农夫带一样东西过河。问农夫该怎样解此难题？样解此难题？方法和过程方法和过程：1、带羊到对岸，返回；带羊到对岸，返回；2、带菜到对岸，并把羊带回；带菜到对岸，并把羊带回；3、带狼狗到对岸，返回；带狼狗到对岸，返回；4、带羊到对岸。带羊到对岸。第8页2、回顾、回顾 二元一次方程组二元一次方程组求解过程求解过程.我们能够归纳它步骤我们能够归纳它步骤:第一步第一步:-2，得，得 5y=3 第三步第三步:第二步第二步:解解得得 y=第二步第二步:解解得得 y=第四步：得到方程组解为：第四步：得到方程组解为：x=1/5,y=3/5第9页第二步：解第二步：解，得，得第一步：第一步：-，得，得 第三步：将第三步：将 代入代入，得，得第四步：得到方程组解第四步：得到方程组解.第10页1 1、算法含义、算法含义 算法（algorithm)古代指是用阿拉伯数字进行算术运算过程。在数学中，通常是指按照一定规则处理某一类问题明确和有限步骤。现在，算法通常能够编成计算机程序，让计算机执行并处理问题。注意：处理某一类问题，明确而且有效，有限性，程序性，不唯一注意：处理某一类问题，明确而且有效，有限性，程序性，不唯一第11页【例】写出你在家中烧开水过程一个算法。总结：“第1”其实大部分事情都是按照一定程序执行，所以要理清事情每一步。“第2”判断水是否烧开与是否继续烧火过程是一个反馈与判断过程，所以有必要不停重复过程“3”解:1、往壶内注水；2、点火加热；3观察：假如水开，则停顿烧火，不然继续烧火；4、假如水未开，重复“3”直至水开。第12页请写出下面一个算法：写出已知直角三角形两边a,b，求斜边一个算法 解：输入直角三角形两边a,b值；计算=输出斜边长L值。第13页请试写出一个算法：请试写出一个算法：写出求一个数绝对值一个算法 解：请输入要求绝对值数a.若a=0,则b=0(b为a绝对值)。若a0，则b=a；若a0，则b=-a.输出a 绝对值b。第14页新课讲解新课讲解算法算法基本基本特点特点1、有限性、有限性 一个算法应包含有限操作步骤，能一个算法应包含有限操作步骤，能在执行有穷操作步骤之后结束。在执行有穷操作步骤之后结束。2、确定性、确定性 一个算法计算规则及对应计算步骤一个算法计算规则及对应计算步骤必须是唯一确定，既不能含糊其词，必须是唯一确定，既不能含糊其词，也不能有二义性。也不能有二义性。3、有效性、有效性 算法中每一个步骤都是能够在算法中每一个步骤都是能够在有限时间内有效地完成基本操作，有限时间内有效地完成基本操作，并能得到确定结果并能得到确定结果。第15页广播操图解是广播操算法；广播操图解是广播操算法；菜谱是做菜算法；菜谱是做菜算法；歌谱是一首歌曲算法；歌谱是一首歌曲算法；空调说明书是空调使用算法等空调说明书是空调使用算法等第16页例例1 1、（1 1）设计一个算法，判断）设计一个算法，判断7 7是否为质数。是否为质数。（2 2）设计一个算法，判断）设计一个算法，判断3535是否为质数。是否为质数。算法（算法（1 1）第一步，用第一步，用2 2除除7 7，得到余数，得到余数1 1。因为余数不为。因为余数不为0 0，所以，所以2 2不能整除不能整除7 7。第二步，用第二步，用3 3除除7 7，得到余数，得到余数1 1。因为余数不。因为余数不为为0 0，所以，所以3 3不能整除不能整除7 7。第三步，用第三步，用4 4除除7 7，得到余数，得到余数3 3。因为余数不。因为余数不为为0 0，所以，所以4 4不能整除不能整除7 7。第四步，用第四步，用5 5除除7 7，得到余数，得到余数2 2。因为余数。因为余数不为不为0 0，所以，所以5 5不能整除不能整除7 7。第五步，用第五步，用6 6除除7 7，得到余数，得到余数1 1。因为余数不。因为余数不为为0 0，所以，所以6 6不能整除不能整除7 7。所以，。所以，7 7是质数。是质数。第17页例例1 1、（1 1）设计一个算法，判断）设计一个算法，判断7 7是否为质数。是否为质数。（2 2）设计一个算法，判断）设计一个算法，判断3535是否为质数。是否为质数。算法（算法（2 2）第一步，用第一步，用2 2除除3535，得到余数，得到余数1 1。因为余数。因为余数不为不为0 0，所以，所以2 2不能整除不能整除3535。第二步，用第二步，用3 3除除3535，得到余数，得到余数2 2。因为余数。因为余数不为不为0 0，所以，所以3 3不能整除不能整除3535。第三步，用第三步，用4 4除除3535，得到余数，得到余数3 3。因为余数。因为余数不为不为0 0，所以，所以4 4不能整除不能整除3535。第四步，用第四步，用5 5除除3535，得到余数，得到余数0 0。因为余数。因为余数为为0 0，所以，所以5 5能整除能整除3535。所以，。所以，3535不是质数。不是质数。第18页你能写出你能写出“判断整数判断整数n(nn(n2)2)是否为质数是否为质数”算法吗？算法吗？第一步，给定大于第一步，给定大于2 2整数整数n n。第二步，令第二步，令i=2.i=2.第三步，用第三步，用i i除除n n，得到余数，得到余数r r。第四步：判断余数第四步：判断余数r r是否为是否为0 0，若是则，若是则n n不是质数，不是质数，结束算法；不然，将结束算法；不然，将i i值增加值增加1 1，仍用，仍用i i表示。表示。第五步，判断第五步，判断i i是否大于是否大于(n-1)(n-1)，若是，则，若是，则n n是是质数，结束算法；不然，返回第三步。质数，结束算法；不然，返回第三步。算法分析：对于任意整数n(n2),若用i表示2（n-1)中任意整数，则“判断n是否为质数“算法包含下面重复操作：用i除n，得到余数r，判断余数r是否为0，若是，则n不是质数；不然，将i值增加1，再执行一样操作这个操作一直要进行到i值等于(n-1)为止。所以，”判断i是否为质数“算法能够写成：第19页例例2用二分法设计一个求方程用二分法设计一个求方程 近似正根算法，准确度近似正根算法，准确度0.05。算法分析：算法分析：令令f(x)=x2-2=0(x0)，则方程，则方程x2-2=0解就是函数解就是函数f(x)零点。零点。“二分法二分法”基本思想是：把函数基本思想是：把函数f(x)零点所在区零点所在区间间a,b(满足满足f(a)f(b)0)“一分为二一分为二”。得到。得到a,m和和m,b。依据。依据“f(a)f(m)0”是否成立，取出零是否成立，取出零点所在区间点所在区间a,m或或m,b，仍记为，仍记为a,b，对所得区，对所得区间间a,b重复上述步骤，直到包含零点区间重复上述步骤，直到包含零点区间a,b“足够足够小小“，则，则a,b内数能够作为方程近似解。内数能够作为方程近似解。第20页例例2用二分法设计一个求方程用二分法设计一个求方程 近似正根算法近似正根算法解：解：等。第21页1 1、算法含义、算法含义：2、算法特点、算法特点：有限性、确定性、有效性。：有限性、确定性、有效性。3、算法思想、算法思想：程序化思想：程序化思想第22页作业：作业：1.书本第书本第5页练习页练习1、22.写出用二分法求方程写出用二分法求方程x2-5=0近似解一个算法近似解一个算法（准确到（准确到0.01）3.练习册：练习册：P13第23页