课题:算法的概念
教学目标1、知识目标:了解算法。分析算法。2、能力目标:体验程序的独特魅力,了解编程加工的内在机制,培养学生的创新能力。3、情感目标:通过编程实现信息的加工,激发学生的兴趣,增加学生的成就感。
重点:如何分析算法,算法的概念,算法的表示
难点:如何写算法。理解用算法描述实际问题,理解人的思维在计算机工作中发挥的作用。
教学方法:讲授法,演示法,归纳法
教学反思:
教学过程
一、导入
在学习程序设计时,既要掌握所使用的某种计算机计算机语言如PASCAL语言,更好掌握解题的方法和步骤,这是程序设计中的关键。语言只是一个工具,只懂得语言的规则并不能编制出有效的高质量的程序,下面所讲座的算法,就是研究解题的步骤和方法,这是编程的基础,同时也是我们解数理化题的基础。
著名计算机科学家沃思提出一个公式:
??数据结构+算法=程序
二新授
什么是算法:广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。
或者说:算法是解题方法的精确描述。解决一个问题的过程,就是实现一个算法的过程。
1.做任何事情都有一定的步骤。例如要计算
的值,无论手算,心算,或用算盘,计算器计算,都要经过有限的事先设计好的步骤。
2、对同一个问题,往往有不同的解题方法和步骤
如
方法1:顺序计算1-1/2+1/3-1/4+1/5……+1/99-1/100,一直加到100加99次
方法2:先计算+,再计算减,即1+1/3+1/5……+1/99,1/2+1/4+1/6……+1/100当然各种方法有优劣之分。
3、不仅数值计算的问题要研究算法,实际上,做任何事情。都需要事先设想好的步骤和方法,这就是算法。
计算机算法可分为两大类别:
数值运算
非数值运算
数值运算举例:求数值解,例如求方程的根、求函数的定积分等。
非数值运算举例:人名排序,图书资料检索等.
三、简单算法举例
为了理解如何设计算法,下面举几个算法的简单例子。
[例1]有两个杯子A和B,分别盛有果汁和酒,要求将这两个杯子进行互换。
(请学生回答,并要求说清楚明确的步骤)
学生所回答的步骤就是算法的描述:
根据常识,必须增加一个空杯C作为过渡。
其算法表示
步骤1:先将A杯中的果汁倒在C杯中;
步骤2:再讲B杯中的酒倒在A杯中;
步骤3:最后将C杯中的果汁倒在B杯中。
此问题可以抽象为数值运算中的交换两个变量的值,简化为:
①A→C
②B→A
③C→B
[例2]从十个数中挑选出最大的数。
创设情景:这个问题的思路可以用“打描台”来比喻。第一个同学先上讲台,然后第二个同学上去比试,胜者(个子高的)留在讲台上,依次轮流,一直到第十个人比完为止()一共九次)最后留在讲台上的同学就是胜者(个子最高的同学)。
算法描述:
1.先任选一个数放在变量A中;
2.将第二个数与变量A中的数进行比较,大者放在变量A中;
3.再将第三个数与变量A中的数进行比较,大者放在变量A中;
:
:
:
10.最后将第十个数与变量A中的数进行比较,大者放在变量A中。
这样写算法虽然正确,但是太烦琐了,可以简化为如下:
1.数X→A,计数器0→N;
2.下一个数Y与A比较,大者→A;
3.N+1→N;(增加一次比较次数)
4.若N﹤9,执行第2步,否则停止循环,此时A中的数最大。
显然,用“循环”表示的算法比较简练。
如果题目要求改为“从1000个数中挑选最大者”,只许需要将算法里面的第4步中的“9”改为“999”即可。
[例3]求两个正整数m和n的最大公约数。
解题之前介绍“辗转相除法”求最大公约数的方法。“辗转”就字面意思来讲是翻来覆去的意思,因此“辗转相除法”的格式可以形象地表示为:
将m和n赋具体值,m=60,n=14,板书具体求解方法。
用m作被除数,n作除数,r做余数。
具体方法(算法)为:
①求m/n的余数r;
②若r=0,则n为最大公约数,若r≠0,执行第③步;
③将n→m,将r→n中;
④返回重新执行第①步。
注意:如果事先不知道M,N两个数谁大谁小,应(可)在第一步之前增加一个步骤,比较一下两个数的大小,大数在m中,小数在n中。
四、算法的特性
1、有穷性:一个算法应该包含有限个操作步骤,而不能是无限的。
2、确定性:算法的每个步骤都应该是明确无误的,不能含义模糊,使执行者无所适从。
3、有零个或者多个输入
4、有一个或者多个输出
5、有效性:算法中的每一步都应该能有效地执行,执行算法最后应该能得到确定的结果。
五、归纳总结
算法的概念;
算法的描述;
算法的特性:
有穷性:包含有限的操作步骤
确定性:算法中的每一个步骤都应当是确定的
有零个或多个输入:输入是指在执行算法时需要从外界取得必要的信息
有一个或多个输出:算法的目的是为了求解,“解”就是输出
有效性:算法中的每一个步骤都应当能有效地执行,并得到确定的结果。
对于程序设计人员来说,我们不仅要会使用现成的算法,还要会设计算法,即要设计出算法中的每一个步骤。
六、练习
①用辗转相除法求324和180的最大公约数。
七、板书设计
八、课后记
§1.1.1算法的概念
【教学目标】:
(1)了解算法的含义,体会算法的思想。
(2)能够用自然语言叙述算法。
(3)掌握正确的算法应满足的要求。
(4)会写出解线性方程(组)的算法。
(5)会写出一个求有限整数序列中的最大值的算法。
【教学重点】算法的含义、解二元一次方程组和判断一个数为质数的算法设计。.
【教学难点】把自然语言转化为算法语言。.
【学法与教学用具】:
学法:
1、写出的算法,必须能解决一类问题(如:判断一个整数n(n1)是否为质数;求任意一个方程的近似解;……),并且能够重复使用。
2、要使算法尽量简单、步骤尽量少。
3、要保证算法正确,且计算机能够执行,如:让计算机计算1×2×3×4×5是可以做到的,但让计算机去执行“倒一杯水”“替我理发”等则是做不到的。
教学用具:计算机,TI-voyage200图形计算器
【教学过程】
一、本章章头图说明
章头图体现了中国古代数学与现代计算机科学的联系,它们的基础都是“算法”。
算法作为一个名词,在中学教科书中并没有出现过,我们在基础教育阶段还没有接触算法概念。但是我们却从小学就开始接触算法,熟悉许多问题的算法。如,做四则运算要先乘除后加减,从里往外脱括弧,竖式笔算等都是算法,至于乘法口诀、珠算口诀更是算法的具体体现。广义地说,算法就是做某一件事的步骤或程序。菜谱是做菜肴的算法,洗衣机的使用说明书是操作洗衣机的算法,歌谱是一首歌曲的算法。在数学中,主要研究计算机能实现的算法,即按照某种机械程序步骤一定可以得到结果的解决问题的程序。
古代的计算工具:算筹与算盘.
20世纪最伟大的发明:计算机,计算机是强大的实现各种算法的工具。
例1:解二元一次方程组:
分析:解二元一次方程组的主要思想是消元的思想,有代入消元和加减消元两种消元的方法,下面用加减消元法写出它的求解过程.
解:第一步:②-①×2,得:5y=3;③
第二步:解③得;
第三步:将代入①,得.
学生探究:对于一般的二元一次方程组来说,上述步骤应该怎样进一步完善?
老师评析:本题的算法是由加减消元法求解的,这个算法也适合一般的二元一次方程组的解法。下面写出求方程组的解的算法:
例2:写出求方程组的解的算法.
解:第一步:②×a1-①×a2,得:③
第二步:解③得;
第三步:将代入①,得
利用TI-voyage200图形计算器演示:(吸引学生的注意力)
运行结果:
(其中输入a1=1,b1=-2,m1=-1,a2=2
b2=1,m2=1,当然可输入其它数值)
算法概念:
在数学上,现代意义上的“算法”通常是指可以用计算机来解决的某一类问题是程序或步骤,这些程序或步骤必须是明确和有效的,而且能够在有限步之内完成.
说明:
1.“算法”没有一个精确化的定义,教科书只对它作了描述性的说明.
2.算法的特点:
(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是质数.
说明:本算法是用自然语言的形式描述的.设计算法一定要做到以下要求:
(1)写出的算法必须能解决一类问题,并且能够重复使用.
(2)要使算法尽量简单、步骤尽量少.
(3)要保证算法正确,且计算机能够执行.
利用TI-voyage200图形计算器演示:(学生已经被吸引住了)
运行例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:
写出解方程x2-2x-3=0的一个算法。
解:算法1:
第一步:移项,得x2-2x-3=0;①
第二步:①式两边同加1并配方,得(x-1)2=4;②
第三步:②式两边开方,得x-1=±2;③
第四步:解③得x=3或x=-1。
算法2:
第一步:计算方程的判别式判断其符号△=22+4×3=16>0;
第二步:将a=1,b=-2,c=-3代入求根公式x=,
得x1=3,x2=-1
评析:比较两种算法,算法2更简单,步骤少,所以利用公式解决问题是最理想、合算的算法。因此在寻求算法的过程中,首先是利用公式。
下面设计一个求一般的一元二次方程ax2+bx+c=0的根的算法如下:
第一步:计算△=b2+4ac;
第二步:若△<0;
第三步:输出方程无实根;
第四步:若△≥0;
第五步:计算并输出方程根x1,2=。
练习2、求1×3×5×7×9×11的值,写出其算法。
第一步,先求1×3,得到结果3;
第二步,将第一步所得结果3再乘以5,得到结果15;
第三步,再将15乘以7,得到结果105;
第四步,再将105乘以9,得到945;
第五步,再将945乘以11,得到10395,即是最后结果。
评析:求解某个问题的算法不同于求解一个具体问题的方法,算法必须能够解决一类问题,并且能够重复使用;算法过程要能一步一步地执行,每一步操作必须确切,能在有限步后得出结果。
练习3、有蓝和黑两个墨水瓶,但现在却错把蓝墨水装在了黑墨水瓶中,黑墨水错装在了蓝墨水瓶中,要求将其互换,请你设计算法解决这一问题。
分析:由于两个墨水瓶中的墨水不能直接交换,故可以考虑通过引入第三个空墨水瓶的办法进行交换。
解:算法步骤如下:
第一步:取一只空的墨水瓶,设其为白色;
第二步:将黑墨水瓶中的蓝墨水装入白瓶中;
第三步:将蓝墨水瓶中的黑墨水装入黑瓶中;
第四步:将白瓶中的蓝墨水装入蓝瓶中;
第五步:交换结束。
评析:对于这种非数值性问题的算法设计问题,应当首先建立过程模型,根据过程设计步骤,完成算法。
小结
1、算法概念和算法的基本思想
(1)算法与一般意义上具体问题的解法的联系与区别;
(2)算法的五个特征。
2、利用算法的思想和方法解决实际问题,能写出一此简单问题的算法
3、两类算法问题
(1)数值性计算问题,如:解方程(或方程组),解不等式(或不等式组),套用公式判断性的问题,累加,累乘等一类问题的算法描述,可通过相应的数学模型借助一般数学计算方法,分解成清晰的步骤,使之条理化即可。
(2)非数值性计算问题,如:排序、查找、变量变换、文字处理等需先建立过程模型,通过模型进行算法设计与描述。
4、利用TI-voyage200图形计算器演示时,开始学生看,想,探究,然后模范、创新。图形计算器为学生创建一个自我发挥的平台。
作业:(课本第4页练习)
1、任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.
解:算法步骤:
第一步:输入任意一个正实数r;
第二步:计算以r为半径的圆的面积:;
第三步:输出圆的面积S.
2、任意给定一个大于1的正整数n,设计一个算法求出n的所有因数.
解:算法步骤:
第一步:依次以2~(n-1)为除数去除n,检查余数是否为0.若是,则是n的因数;若不是,则不是n的因数;
第二步:在n的因数中加入1和n;
第三步:输出n的所有因数.
运行结果:
(即32的公因数为1,2,4,8,16,32)
高二数学上册《算法案例》教学设计
一、教学目标:
1、知识与技能
⑴理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析;
⑵基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.
2、过程与方法
在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法,比较它们在算法上的区别,并从程序的学习中体会数学的严谨,领会数学算法与计算机处理的结合方式,初步掌握把数学算法转化成计算机语言的一般步骤.
3、情感与价值观
⑴通过阅读中国古代数学中的算法案例,体会中国古代数学对世界数学发展的贡献.
⑵在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力,在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力.
二、教学重点、难点:
重点:理解辗转相除法与更相减损术求最大公约数的方法.
难点:把辗转相除法与更相减损术的方法转换成程序框图与程序语言.
三、教学过程:
(一)创设情景、导入课题
1.研究一个实际问题的算法,主要从哪几方面展开?
算法步骤、程序框图和编写程序三方面展开.
2.在程序框图中算法的基本逻辑结构有哪几种?
顺序结构、条件结构、循环结构
3.在程序设计中基本的算法语句有哪几种?
输入语句、输出语句、赋值语句、条件语句、循环语句
4.思考1:18与30的最大公约数是多少?你是怎样得到的?
5.思考2:对于8251与6105这两个数,它们的最大公约数是多少?你是怎样得到的?
由于它们公有的质因数较大,利用上述方法求最大公约数就比较困难.有没有其它的方法可以较简单的找出它们的最大公约数呢?
(板书课题)
(二)师生互动、探究新知
1.辗转相除法
思考3:注意到8251=6105×1+2146,那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系?
我们发现6105=2146×2+1813,同理,6105与2146的公约数和2146与1813的公约数相等.
思考4:重复上述操作,你能得到8251与6105这两个数的最大公约数吗?
6105=2146×2+1813
2146=1813×1+333
1813=333×5+148
333=148×2+37
148=37×4+0
以上我们求最大公约数的方法就是辗转相除法,也叫欧几里德算法,它是由欧几里德在公元前300年左右首先提出的.
利用辗转相除法求最大公约数的步骤如下:
第一步:用较大的数m除以较小的数n得到一个商和一个余数;
第二步:若=0,则n为m,n的最大公约数;若≠0,则用除数n除以余数得到一个商和一个余数;
第三步:若=0,则为m,n的最大公约数;若≠0,则用除数除以余数得到一个商和一个余数;
……
依次计算直至=0,此时所得到的即为所求的最大公约数.
思考5:你能把辗转相除法编成一个计算机程序吗?
第一步,给定两个正整数m,n(mn).
第二步,计算m除以n所得的余数r.
第三步,m=n,n=r.
第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步.
INPUTm,n
DO
r=mMODn
m=n
n=r
LOOPUNTILr=0
PRINTm
END
思考6:如果用当型循环结构构造算法,则用辗转相除法求两个正整数m,n的最大公约数的程序框图和程序分别如何表示?
INPUTm,n
WHILEn0
r=mMODn
m=n
n=r
WEND
PRINTm
END
2.更相减损术
《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数
更相减损术求最大公约数的步骤如下:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之.”
翻译出来为:
第一步:任意给出两个正整数;判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.
第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
例1(课本P36例1)用更相减损术求98与63的最大公约数.
解:由于63不是偶数,把98和63以大数减小数,并辗转相减,即:98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以,98与63的最大公约数是7。
练习:用更相减损术求两个正数84与72的最大公约数。(答案:12)
(三)讲练结合,巩固提高
例2:分别用辗转相除法和更相减损术求168与93的最大公约数.
辗转相除法:
168=93×1+75,
93=75×1+18,
75=18×4+3,
18=3×6.
更相减损术:
168-93=75,
93-75=18,
75-18=57,
57-18=39,
39-18=21,
21-18=3,
18-3=15,
15-3=12,
12-3=9,
9-3=6,
6-3=3.
例3:求325,130,270三个数的最大公约数.
因为325=130×2+65,130=65×2,所以325与130的最大公约数是65.
因为270=65×4+10,65=10×6+5,10=5×2,所以65与270最大公约数是5.
故325,130,270三个数的最大公约数是5.
练习:用更相减损术求两个正整数m,n的最大公约数,可以用什么逻辑结构来构造算法?其算法步骤如何设计?
第一步,给定两个正整数m,n(mn).
第二步,计算m-n所得的差k.
第三步,比较n与k的大小,其中大者用m表示,小者用n表示.
第四步,若m=n,则m,n的最大公约数等于m;否则,返回第二步.
讨论:该算法的程序框图如何表示?
讨论:该程序框图对应的程序如何表述?
(四)小结
1、辗转相除法,就是对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽为止,这时的较小的数即为原来两个数的最大公约数.
2、更相减损术,就是对于给定的两个正整数,用较大的数减去较小的数,然后将差和较小的数构成新的一对数,继续上面的减法,直到差和较小的数相等,此时相等的两数即为原来两个数的最大公约数.
(五)布置作业
P45练习:1题.
P48习题1.3A组:1题
一位优秀的教师不打无准备之仗,会提前做好准备,作为教师就要早早地准备好适合的教案课件。教案可以让上课时的教学氛围非常活跃,帮助教师提前熟悉所教学的内容。那么如何写好我们的教案呢?小编收集并整理了“高二数学集合的概念教案3”,希望对您的工作和生活有所帮助。
第1课时集合的概念
一、集合
1.集合是一个不能定义的原始概念,描述性定义为:某些指定的对象就成为一个集合,简称.集合中的每一个对象叫做这个集合的.
2.集合中的元素属性具有:
(1)确定性;(2);(3).
3.集合的表示法常用的有、和韦恩图法三种,有限集常用,无限集常用,图示法常用于表示集合之间的相互关系.
二、元素与集合的关系
4.元素与集合是属于和的从属关系,若a是集合A的元素,记作,若a不是集合B的元素,记作.但是要注意元素与集合是相对而言的.
三、集合与集合的关系
5.集合与集合的关系用符号表示.
6.子集:若集合A中都是集合B的元素,就说集合A包含于集合B(或集合B包含集合A),记作.
7.相等:若集合A中都是集合B的元素,同时集合B中都是集合A的元素,就说集合A等于集合B,记作.
8.真子集:如果就说集合A是集合B的真子集,记作.
9.若集合A含有n个元素,则A的子集有个,真子集有个,非空真子集有个.
10.空集是一个特殊而又重要的集合,它不含任何元素,是任何集合的,是任何非空集合的,解题时不可忽视.
例1.已知集合,试求集合的所有子集.
例2.
例2.设集合,,,求实数a的值.
例3.已知集合A={x|mx2-2x+3=0,m∈R}.?(1)若A是空集,求m的取值范围;?(2)若A中只有一个元素,求m的值;?(3)若A中至多只有一个元素,求m的取值范围.?
例4.若集合A={2,4,},B={1,a+1,,、},且A∩B={2,5},试求实数的值.
变式训练1.若a,bR,集合求b-a的值.
变式训练2:(1)P={x|x2-2x-3=0},S={x|ax+2=0},SP,求a取值?
(2)A={-2≤x≤5},B={x|m+1≤x≤2m-1},BA,求m。
变式训练3.(1)已知A={a+2,(a+1)2,a2+3a+3}且1∈A,求实数a的值;?
(2)已知M={2,a,b},N={2a,2,b2}且M=N,求a,b的值.?
变式训练4.已知集合A={a,a+d,a+2d},B={a,aq,},其中a≠0,若A=B,求q的值
1.本节的重点是集合的基本概念和表示方法,对集合的认识,关键在于化简给定的集合,确定集合的元素,并真正认识集合中元素的属性,特别要注意代表元素的形式,不要将点集和数集混淆.
2.利用相等集合的定义解题时,特别要注意集合中元素的互异性,对计算的结果要加以检验.
3.注意空集φ的特殊性,在解题时,若未指明集合非空,则要考虑到集合为空集的可能性.
4.要注意数学思想方法在解题中的运用,如化归与转化、分类讨论、数形结合的思想方法在解题中的应用.
文章来源:http://m.jab88.com/j/111683.html
更多