第一篇:高中数学必修2教学设计: 1.1.1算法的概念
文字资料] 1.1.1算法的概念
算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据,经过计算机程序的有限次运算,能够得出所要求或期望的终止状态或输出数据。
算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。〖算法的历史〗
“算法”(algorithm)来自于9世纪波斯数学家比阿勒·霍瓦里松的名字al-Khwarizmi,比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为“algorism”,意思是阿拉伯数字的运算法则,在18世纪演变为“algorithm”。第一次编写算法是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利方程的程序,因此Ada Byron被大多数人认为是世界上第一位程序员。因为巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。因为“well-defined procedure”缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要的作用。
一个算法应该具有以下五个重要的特征:
有穷性: 一个算法必须保证执行有限步之后结束;
确切性: 算法的每一步骤必须有确切的定义;
输入:一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定除了初始条件;
输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。
〖形式化算法〗
算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。〖算法的实现〗
算法不单单可以用计算机程序来实现,也可以在神经网络、电路或者机械设备上实现。·例子
这是算法的一个简单的例子。
如果将数列中的每一个数字看成是一颗豆子的大小,可以将下面的算法形象地称为“捡豆子”: 首先将第一颗豆子放入口袋中。
从第二颗豆子开始检查,直到最后一颗豆子。如果正在检查的豆子比口袋中的还大,则将它捡起放入口袋中,同时丢掉原先口袋中的豆子。
最后口袋中的豆子就是所有的豆子中最大的一颗。下面是一个形式算法,用近似于编程语言的伪代码表示
给定:一个数列“list“,以及数列的长度”length(list)" largest = list[1] for counter = 2 to length(list): if list[counter] > largest: largest = list[counter] print largest 符号说明: = 用于表示赋值。即:右边的值被赋予给左边的变量。List[counter]用于表示数列中的第counter项。例如:如果counter的值是5,那么List[counter]表示数列中的第5项。<= 用于表示“小于或等于”。
==例子==
设两个变量 M 和 N 1.如果 M < N,则交换 M 和 N 2.以 N 除以 M,得到余数 R 3.判断 R=0,正确则 N 即为“最大公约数”,否则下一步 4.将 N 赋值给 M,将 R 赋值给 N,重做第一步。用“Basic 代码”表示--
If M < N Then Swap M,N Do While R <> 0 R = M Mod N M = N N = R Loop Print R
〖算法设计和分析的基本方法〗
分治法:字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题„„直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)„„
动态规划:动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个
因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。
贪心法(亦作饕餮法):就是一种在每一步选择中都采取在当前状态下最好/优的选择,从而希望导致结果是最好/优的算法。贪心法可以解决一些最优性问题,如:求图中的最小生成树、求哈夫曼编码„„对于其他问题,贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决,那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果,贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。〖算法的分类〗
·基本算法 〔枚举 搜索(深度优先搜索 广度优先搜索 启发式搜索 遗传算法)〕 ·数据结构的算法 ·数论与代数算法
·计算几何的算法(凸包算法)
·图论的算法(哈夫曼编码 树的遍历 最短路径算法 最小生成树算法 最小树形图 网络流算法 匹配算法)· 动态规划
·其他(数值分析 加密算法 排序算法 检索算法 随机化算)
还可以分成串行算法、并行算法。
〖算法的复杂性〗
算法的复杂性是算法效率的度量,在评价算法性能时,复杂性是一个重要的依据。算法的复杂性的程度与运行该算法所需要的计算机资源的多少有关,所需要的资源越多,表明该算法的复杂性越高;所需要的资源越少,表明该算法的复杂性越低。
计算机的资源,最重要的是运算所需的时间和存储程序和数据所需的空间资源,算法的复杂性有时间复杂性和空间复杂性之分。
算法在计算机上执行运算,需要一定的存储空间存放描述算法的程序和算法所需的数据,计算机完成运算任务需要一定的时间。根据不同的算法写出的程序放在计算机上运算时,所需要的时间和空间是不同的,算法的复杂性是对算法运算所需时间和空间的一种度量。不同的计算机其运算速度相差很大,在衡量一个算法的复杂性要注意到这一点。
对于任意给定的问题,设计出复杂性尽可能低的算法是在设计算法时考虑的一个重要目标。另外,当给定的问题已有多种算法时,选择其中复杂性最低者,是在选用算法时应遵循的一个重要准则。因此,算法的复杂性分析对算法的设计或选用有着
在讨论算法的复杂性时,有两个问题要弄清楚:
(1)一个算法的复杂性用怎样的一个量来表达;
(2)怎样计算一个给定算法的复杂性。
找到求解一个问题的算法后,接着就是该算法的实现,至于是否可以找到实现的方法,取决于算法的可计算性和计算的复杂性,该问题是否存在求解算法,能否提供算法所需要的时间资源和空间资源。
筛选法求质数
质数亦叫作素数,是大于1的自然数,并且除了该数本身和1以外没有其它的数能整除它,如2,3,5,7,11,13,„,质数有无穷多个。
(1)判断143是否为质数。解:
Step1:143÷2不为整数; Step2:143÷3不为整数; Step3:143÷4不为整数; Step4:143÷5不为整数; Step5:143÷6不为整数; Step6:143÷7不为整数; Step7:143÷8不为整数; Step8:143÷9不为整数;
:143÷10不为整数;
Step10:143÷11=13,143能被11整除; Step11:结论:143不是质数。(2)判断17是否为质数。解:
Step1:17÷2不为整数; Step2:17÷3不为整数; Step3:17÷4不为整数; Step4:17÷5不为整数; Step5:17÷6不为整数; Step6:17÷7不为整数; Step7:17÷8不为整数; Step8:17÷9不为整数; Step9:17÷10不为整数; Step10:17÷11不为整数; Step11:17÷12不为整数; Step12:17÷13不为整数; Step13:17÷14不为整数; Step14:17÷15不为整数; Step15:17÷16不为整数; Step16:结论:17是质数。
3)判断216091是不是质数
该题的计算量非常大,我们可以把算法编为程序,由计算机帮我们计算。
(4)设计一个算法,输入大于2的整数n,由计算机判断它是不是质数。
解:Step1:输入整数n;
Step2:依次检验2~(n-1)是不是n的因数,若有这样的数,则n不是质数,否则,n为质数。Step3:输出结果。
说明:其中第3步在计算机中可以通过一个循环来实现,今后会学到
第二篇:高中数学必修2教学设计:1.1.1算法的概念教案
[教案]
1.1.1算法的概念 教学目标:
(1)了解算法的含义,体会算法的思想。(2)能够用自然语言叙述算法。(3)掌握正确的算法应满足的要求。(4)会写出解线性方程(组)的算法。教学重点和难点
重点:算法的含义、解二元一次方程组和判断一个数为质数的算法设计。难点:把自然语言转化为算法语言。.教学基本流程
(1)由生活实例发邮件和猜价格,体会算法思想。(2)转到数学问题,体会算法思想,设计自然语言算法。(3)总结概括算法的概念和特征。(4)两个例子巩固提高。(5)反馈练习,课堂小结。教学情景设计
一、新课引入
算筹、算盘、计算机等从古到今计算工具的变化,现了中国古代数学与现代计算机科学的联系,它们的基础都是“算法”。
算法这个名词虽然听起来很陌生,但它确是一个古老的概念。我们却从小学就开始接触算法,如,做四则运算要先乘除后加减,从里往外脱括弧,竖式笔算等都是算法,至于乘法口诀、珠算口诀更是算法的具体体现。广
科学计算、科学实验、理论研究。算法的研究和应用正是本课程的主题!
二、问题设计
1、假如你的朋友不会发邮件,你能教他吗?,请你写出步骤。
(设计意图:让S从生活中的实例体会算法就是做某一件事的步骤或程序)第一步:打开电子信箱;第二步:点击“写邮件”;第三步:输入发送地址;第四步:输入主题;第五步:输入信件内容;第六步;点击“发送邮件”
2、电视节目中,有一种有趣的“猜数”游戏:?现有一商品,价格在0到8000元之间,釆取怎样的策略才能在较短的时间内说出正确的答案呢? 第一步:报“4000”;第二步:若答“高了”,就报“2000”;否则报“6000”;第三步:重复第二步的报数方法,直至得到正确结果。
T点评:我们做任何一件事,都是在一定的条件下按某种顺序执行的一系列操作。解决数学问题也常常如此。例如:用加减消元法解二元一次方程组时,就可以按照某一程序进行操作;将上述程序换成计算机能识别的语言后,就能借助计算机极大地提高解决问题的速度。因此探索解决问题的统一程序的思想是十分重要的,对一类问题的机械的、统一的求解程序就是算法。
3、面对一个需要解决的问题?如何设计解决问题的操作步骤??怎样用数学语言描述这些操作序列?(设计意图:让S体会数学问题的步骤或程序就是算法)
例1 给出求1+2+3+4+5的一个算法.算法1:连续加和求得,第一步 : 计算1+2,得到3;
第二步:将第一步中的运算结果3与3相加,得到6;
第三步:将第二步中的运算结果6与4相加,得到10;
第四步:将第三步中的运算结果10与5相加,得到15.算法2:可以运用公式1+2+3+……+n=n(n+1)/2直接计算.第一步:
取n=5;
第二步:计算n(n+1)/2;
第三步:输出运算结果.T点评:比较上二种算法,算法2更简单,步骤少,所以利用公式解决问题是最理想、合算的算法.因此在寻求算法的过程中,首先是利用公式.例2.给出解二元一次方程组
2xy7(1)(2)4x5y11我们用消元法求解这个方程组,步骤是: 第一步:将方程(2)中x的系数4除以方程(1)中x的系数2, 得到乘数m=2.第二步:方程(2)减去方程(1)乘以m,消去方程(1)中的x项,得到:3y=-
3y=-1;第三步:将y=-1代入方程(1),得到x=4.写出求下方程组的解的算法.a1xb1yc1a2xb2yc2①②a1b2a2b10
第一步:②×a1-①×a2,得:a1b2a2b1ya1c2a2c1③
a1c2a2c1 第二步:解③得 y; a1b2a2b1
a1c2a2c1b2c1b1c2 第三步:将y代入①,得x.a1b2a2b1a1b2a2b1
三、归纳总结 算法的概念和特点
概念:通常指按照一定规则解决某一类问题的明确的和有限的步骤。(现在,算法通常可以编成程序,让计算机执行并解决问题。)
特征:(1)有限性:一个算法的步骤序列是有限的,必须在有限操作之后停止,.(2)确定性:算法中的每一步应该是确定的并且能有效地执行且得到确定的结果,而不应当是模棱两可.(3)逻辑性:算法从初始步骤开始,分为若干明确的步骤,每一个步骤只能有一个确定的后继步骤,前一步是后一步的前提,只有执行完前一步才能进行下一步,并且每一步都准确无误,才能完成问题.(4)不唯一性:求解某一个问题的解法不一定是唯一的,对于一个问题可以有不同的算法.(5)普遍性:很多具体的问题,都可以设计合理的算法去解决。
四、巩固提高
例
3、任意给定一个大于1的整数n,试设计一个程序或步骤对n是否为质数做出判断.分析:(1)质数是只能被1和自身整除的大于1的整数.(2)要判断一个大于1的整数n是否为质数,只要根据质数的定义,用比这个整数小的数去除n,如果它只能被1和本身整除,而不能被其它整数整除,则这个数便是质数.解:算法:
第一步:判断n是否等于2.若n=2,则n是质数;若n>2,则执行第二步.第二步:依次从2~(n-1)检验是不是n的因数,即整除n的数.若有这样的数,则n不是质数;若没有这样的数,则n是质数.T点评:本算法是用自然语言的形式描述的.设计算法一定要做到以下要求:(1)写出的算法必须能解决一类问题,并且能够重复使用.(2)要使算法尽量简单、步骤尽量少.(3)要保证算法正确,且计算机能够执行.例
4、.用二分法设计一个求方程 的近似根的算法.分析:该算法实质是求 的近似值的一个最基本的方法.解:设所求近似根与精确解的差的绝对值不超过0.005,算法: 第一步:令.因为,所以设x1=1,x2=2.第二步:令,判断f(m)是否为0.若是,则m为所求;若否,则继续判断 大于0还是小于0.第三步:若,则x1=m;否则,令x2=m.第四步:判断 是否成立?若是,则x1、x2之间的任意值均为满足条件的近似根;若否,则返回第二步.说明:按以上步骤,我们将依次得到课本第4页的表1-1和图1.1-1.于是,开区间(1.4140625,1.41796875)中的实数都满足假设条件的原方程是近似根.运行结果:
五、练习反馈
1、任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.2、有蓝和黑两个墨水瓶,但现在却错把蓝墨水装在了黑墨水瓶中,黑墨水错装在了蓝墨水瓶中,要求将其互换,请你设计算法解决这一问题。
六、小结作业:
1、算法概念和算法的基本思想
(1)算法与一般意义上具体问题的解法的联系与区别;(2)算法的五个特征。
2、利用算法的思想和方法解决实际问题,能写出一此简单问题的算法。
第三篇:高中数学 1.1.1 算法的概念教案2 新人教A版必修3
算法的概念
教学目的:理解并掌握算法的概念与意义,会用“算法”的思想编制数学问题的算法。教学重点:算法的设计与算法意识的的培养 教学过程:
一、问题情景:
请大家研究解决下面的一个问题
1.两个大人和两个小孩一起渡河,渡口只有一条小船,每次只能渡1 个大人或两个小孩,他们四人都会划船,但都不会游泳。试问他们怎样渡过河去?请写出一个渡河方案。
(通过学生讨论得出渡河方案与步骤如下)
S1 两个小孩同船过河去; S2 一个小孩划船回来; S3 一个大人划船过河去; S4 对岸的小孩划船回来; S5 两个小孩同船渡过河去; S6 一个小孩划船回来;
S7 余下的一个大人独自划船渡过河去;对岸的小孩划船回来; S8 两个小孩再同时划船渡过河去。
2.一群小兔一群鸡,两群合到一群里,要数腿共48,要数脑袋整17,多少小兔多少鸡?
先列方程组解题,得鸡10只,兔7只; 再归纳一般二元一次方程组的通用方法,即用高斯消去法解一般的二元一次a11x1a12x2b1方程组。
axaxb2222211令Da11a22a21a12,若D0,方程组无解或有无数多解。若D0,则x1b1a22b2a12bab1a21,x2211。
DD由此可得解二元一次方程组的算法。
S1 计算Da11a22a21a12;
S2 如果D0,则原方程组无解或有无穷多组解;否则(D0),x1b1a22b2a12bab1a21,x2211
DDS3 输出计算结果x1、x2或者无法求解的信息。
二、数学构建:
算法的概念:由基本运算及规定的运算顺序所构成的完整的解题步骤,或者是按照要求设计好的有限的计算序列,并且这样的步骤或序列能解决一类问题。
算法的五个重要特征:
(1)有穷性:一个算法必须保证执行有限步后结束;(2)确切性:算法的每一步必须有确切的定义;
(3)可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次即可完成;
(4)输入:一个算法有0个或多个输入,以刻划运算对象的初始条件。所谓0个输入是指算法本身定出了初始条件。
(5)输出:一个算法有1个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
三、知识运用:
例1.一个人带三只狼和三只羚羊过河,只有一条船,同船可以容纳一个人和两只动物。没有人在的时候,如果狼的数量不少于羚羊的数量,狼就会吃掉羚羊。(1)设计过河的算法;(2)思考每一步算法所遵循的相同之处原则是什么。
解:算法或步骤如下: S1 人带两只狼过河 S2 人自己返回
S3 人带一只羚羊过河 S4 人带两只狼返回 S5 人带两只羚羊过河 S6 人自己返回 S7 人带两只狼过河
S8 人自己返回带一只狼过河
例2.写出一个求有限整数序列中的最大值的算法。解:为了便于理解,算法步骤用自然语言叙述:
S1 先将序列中的第一个整数设为最大值;
S
2将序列中的下一个整数值与“最大值”比较,如果它大于此“最大值”,这时就假定“最大值”就是这个整数;
S3 如果序列中还有其它整数,重复S2;
S4 在序列中一直进行到没有可比的数为止,这时假定的“最大值”就是这个序列中的最大值。
试用数学语言写出对任意3个整数a、b、c中最大值的求法
S1 max=a S2 如果b>max,则max=b S3 如果c>max,则max=c, S4 max就是a、b、c中的最大值。
四、学力发展:
1.给出求100!123100的一个算法。
2.给出求点P(x0,y0)关于直线AxByC0的对称点的一个算法。
五、课堂小结:
算法的概念:由基本运算及规定的运算顺序所构成的完整的解题步骤,或者是按照要求设计好的有限的计算序列,并且这样的步骤或序列能解决一类问题。
算法的五个重要特征:
(1)有穷性:一个算法必须保证执行有限步后结束;(2)确切性:算法的每一步必须有确切的定义;
(3)可行性:算法原则上能够精确地运行,而且人们用笔和纸做有限次即可完成;
(4)输入:一个算法有0个或多个输入,以刻划运算对象的初始条件。所谓0个输入是指算法本身定出了初始条件。
(5)输出:一个算法有1个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
六、课外作业:
1.优化设计P3-4:变式练习1-10题。2.课本P6:练习1-4题
第四篇:《1.1.1算法的概念》教案
1.1.1 算法的概念(第1课时)
【课程标准】通过对解决具体问题过程与步骤的分析(如二元一次方程
组求解等问题),体会算法的思想,了解算法的含义.【教学目标】1.理解算法的概念与特点;
2.学会用自然语言描述算法,体会算法思想; 3.培养学生逻辑思维能力与表达能力.【教学重点】算法概念以及用自然语言描述算法
【教学难点】用自然语言描述算法
【教学过程】
一、游戏引入
1.汉诺塔游戏;(详见课件演示)2.鸡兔同笼问题。
鸡兔同笼问题:鸡和兔共有若干只,数腿共有94条,数头共35只,请问各有鸡兔多少只?能不能说出解决这个问题的步骤(过程)!
二、新课探究
a1xb1yc1,1、对于一般的二元一次方程组a2xb2yc2,其中a1b2a2b10,能否找到一个程序化的求解步骤:
2、算法的概念
通过对以上几个问题的分析,我们对算法有了一个初步的了解.在解决某些问题时,需要设计出一系列可操作或可计算的步骤,通过实施这些步骤来解决问题,通常把这些在数学中叫做算法。现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成.三、知识应用
1.说说你在家里烧开水过程的一个算法.第一步:把水注入电锅; 第二步:打开电源把水烧开; 第三步:把烧开的水注入热水瓶.(以上算法是解决某一问题的程序或步骤)2.例1(1)设计一个算法,判断7是否为质数.(2)设计一个算法,判断35是否是质数.3.探究:设计一个算法,判断整数n(n>2)是否为质数.四、课堂练习
1、(课本第5页练习1)任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.解:第一步:输入任意正实数r 第二步:计算Sr2; 第三步:输出圆的面积S.2、(课本第5页练习2)任意给定一个大于1的正整数n,设计一个算法求出n的所有因数.解:根据因数的定义,可设计出下面的一个算法: 第一步:输入大于1的正整数n.第二步:判断n是否等于2,若n2,则n的因数为1,n;若n2,则执行第三步.第三步:依次从2到n1检验是不是整除n,若整除n,则是n的因数;若不整除n,则不是n的因数.五、课堂小结 1.算法的特性:
①有限性:一个算法的步骤序列是有限的,它应在有限步操作之后停止,而不能是无限的.②确定性:算法中的每一步应该是确定的并且能有效地执行且得到确定的结果,而不应当是模棱两可.③可行性:算法中的每一步操作都必须是可执行的,也就是说算法中的每一步都能通过手工和机器在有限时间内完成.2.描述算法的一般步骤:
①输入数据.②数据处理.③输出结果.六、作业
1、求1×3 × 5 × 7 × 9 × 11的值,写出其算法。
2、写出解不等式 x22x30的一个算法。
七、课后反思:
第五篇:§1.1.1 算法的概念教案
§1.1.1 算法的概念
【教学目标】:
(1)了解算法的含义,体会算法的思想。(2)能够用自然语言叙述算法。(3)掌握正确的算法应满足的要求。
【过程与方法】:通过求解二元一次方程组,体会解方程的一般性步骤,从而得到一个解二元一次方程组的步骤,这些步骤就是算法,不同的问题有不同的算法。由于思考问题的角度不同,同一个问题也可能有多个算法,能模仿求解二元一次方程组的步骤,写出一个求一个一元二次方程解的算法。
【情感态度与价值观】:通过本节的学习,使我们对计算机的算法语言有一个基本的了解,明确算法的要求,认识到计算机是人类征服自然的一各有力工具,进一步提高探索、认识世界的能力。
【教学重点】算法的含义和判断一个数为质数的算法设计。.【教学难点】把自然语言转化为算法语言。.【教法】:采用“问题探究与学案相结合”教学法,以多媒体为辅助手段,让学生主动发现问题、分析问题、解决问题,培养学生的探究论证、逻辑思维能力。
【教学过程】
一、本章章头图说明
章头图为我们展示的是古代与近代的计算工具:算筹与算盘.以及20世纪最伟大的发明——计算机,体现了中国古代数学与现代计算机科学的联系,它们的基础都是“算法”。计算机是强大的实现各种算法的工具。那么,计算机是怎样工作的呢?算法的学习是一个开始。
二、引入新课
1、怎样理解算法?
x2y1引例1:解二元一次方程组:
2xy1① ②分析:解二元一次方程组的主要思想是消元的思想,有代入消元和加减消元两种消元的方法,下面用加减消元法写出它的求解过程.解:第一步:②①×a2,得:a1b2a2b1ya1c2a2c③
第二步:解③得 ya1c2a2c1;
a1b2a2b1
第三步:将ya1c2a2c1bcb1c2代入①,得x21
a1b2a2b1a1b2a2b1评注:1.以上求解的步骤就是解二元一次方程组的算法.2本题的算法是由加减消元法求解的,同样利用代入消元也可达到解方程组的目的,解决一个问题不一定只有一种算法
算法概念: 算法通常是指可以用计算机来解决的某一类问题的程序或步骤,这些程序或步骤必须是明确的和有效的,而且能够在有限步之内完成。
例如:描述太极拳动作的图解,就是“太极拳的算法”;一首歌的乐谱,可以称之为该歌曲的算法。从小学到高中遇到的算法绝大多数都与“计算”有关的问题。
2.算法的特点: ①有穷性:一个算法的步骤序列是有限的,它应在有限步操作之后停止,而不能是无限地执行下去。
②确定性:算法中的每一步应该是确定的并且能有效地执行且得到确定的结果,而不应当是模棱两可的。
③逻辑性:算法从初始步骤开始,分为若干个明确的步骤,前一步是后一步的前提,只有执行完前一步才能进行下一步,并且每一步都准确无误,才能完成问题。
④不唯一性:求解某一个问题的算法不一定只有唯一的一个,可以有不同的算法。⑤普遍性:很多具体的问题,都可以设计合理的算法去解决。
2、例题讲评:
例
1、设计算法判断任意一个大于2的正整数n是否是质数。
分析:首先考虑判断一个具体的数是否是质数的方法,以7为例。
根据质数的定义,可以这样判断:依次用2~6去除7如果它们中有一个数能整除7,则7不是质数,否则7是质数。
第一步 用2除7,得到余数1,所以2不能整除7
第二步 用3除7,得到余数1,所以3不能整除7
第三步 用4除7,得到余数3,所以4不能整除7
第四步 用5除7,得到余数2,所以5不能整除7
第五步 用6除7,得到余数1,所以6不能整除7,因此,7是质数。
根据以上分析,对于任意大于2的正整数n,判断它是否为质数的算法如下:
第一步:给出大于2的正整数
第二步:令i=2
第三步:用i 除n,得到余数r
第四步: 判断“r=0”是否成立。若是则n 不是质数,结束算法;否则将 i 的值增加1,仍用 i表示
第五步:判断
“i >(n-1)” 是否成立。若是,则n是质数,结束算法;否则,返回第三步。
(设计意图:通过这个例子从特殊到一般的过程,使学生进一步体会到算法概括性,逻辑性,有限性,练习把自然语言转化成规范的算法语言)
例
2、.用二分法设计一个求方程x220的近似根的算法.分析:该算法实质是求2的近似值的一个最基本的方法.解:设精确度为d,初始区间【a,b】且fafb0
2fxx2;
第二步:令m=(a+b)/2 算法:第一步:令
第三步:若fafm0,则b=m;否则,令a=m.第四步:判断|a-b| 三、小结 1、算法概念和算法的基本思想 (1)算法与一般意义上具体问题的解法的联系与区别;(2)算法的五个特征。 2、两类算法问题 (1)数值性计算问题,如:解方程(或方程组),解不等式(或不等式组),套用公式判断性的问题,累加,累乘等一类问题的算法描述,可通过相应的数学模型借助一般数学计算方法,分解成清晰的步骤,使之条理化即可。 (2)非数值性计算问题,如:排序、查找、变量变换、文字处理等需先建立过程模型,通过模型进行算法设计与描述。 四、作业: 完成学案作业 六 五、板书设计 1.1.1 算法的概念 一问题1 二 概念 例2 问题2 三例1 小结