算法的引入想想你每天从起床到去学校中,必不可少要有三个环节,分别是起床、穿衣服、出门,比如说起床,甭管你是爬起来,跳起来,还是嗖的钻起来,总之你得起床,除非你希望你爸妈抬着你家的床到学校,然后你再穿衣服……考虑其中的两项,可以调换顺序么?比如说穿衣服和出门互换,先出门后穿衣服可不可以?当然可以,只要你不介意裸奔嘛,只是随后可爱的警察叔叔就会带你去一个美丽的地方。
那么,像这样的处理一类问题的步骤我们称之为算法。
事实上,算法的迅速发展是在1945年之后,1945年发生一件什么大事?除了日本投降之外,计算机诞生了.那么计算机的诞生就导致人们发现,如果一件事情,你能够规定出一个计算方法来,那么计算机就会比你执行的快.这个年头,大家都用计算机,而且用得非常遛了!但是,你知道有些事情计算机能替你做,有些事情计算机替你做不了.所以,这时我们就希望,越来越多的东西可以用计算机来替我们算,所以,我们需要给计算机提供一个算法.换句话说,一件事情该怎么计算的方法,要由我们来提供,然后由计算机去执行.提到算法这个概念,大家会觉得比较抽象,其实在数学里,有一些比较经典的东西,你要是仔细来说的话都是算法.比如说《九章算术》里介绍的“合分”就是一个很好的算法案例,所谓的合分就是两个分数相加,书中说的是:母互乘子,并以为实.母相乘为法.也就是两个分母相乘作为新的分母,分子分母互乘之后加起来得到分子.具体的如21?32+=,我们很快就可以得到答案,但它运算的实际过知识切片4.1算法基本概念与算法特性知识点睛看到这些算法,都惊呆了!程是先通分再加减,为什么这么算,小学的时候我们就学过,老师说以后看到这个式子你就这样算就行了,只不过,现在我们越来越熟悉,在脑海中这个过程唰一闪就出来了,式子都不用列,结果就出来了,那实际上这个过程就是算法.就是一个东西该怎么运算,你给规定了一个方法,你按照这个方法执行就行了.从这个角度来说,很多东西就都是算法了,比如说1324⨯,这个计算过程也是一个算法.那么稍微高级一点的东西,比如说中国古代劳动人民一个智慧的结晶:辗转相除法—求最大公约数,这个也是算法.还比如说“韩信点兵”,这都是算法.下面我们来看一下算法的概念.1.算法的概念:由基本运算及规定的运算顺序所构成的完整的解题步骤,或者看成按照一定规则解决某一类问题的明确的和有限的步骤,称为算法().2.算法的特性:⑴明确性:算法的每一个步骤必须有确定的含义;⑵有限性: 算法必须在有限的时间内执行完,即算法必须在执行有限个步骤之后终止⑶可执行性:①算法的每个步骤必须是能实现的;②算法的执行结果要达到预期的目的.【教师备案】因为各个参考书对算法的特性总结的都不一样,所以我们重点总结了三条,其它的老师可以根据班里学生的情况进行补充,下面是算法特性的一种讲解方法,老师可以借鉴.计算机执行算法不是无休止的,也不是没有结果的,设想一个计算机等输入了东西然后运行直到地球毁灭宇宙重生都没有而且永远都不会有结果的将是不可行的算法.根据计算机处理问题的特点,算法需要具备以下特性:⑴明确性(Definiteness)指下的指令必须是清晰明确的,比如:你跟计算机说,小计啊!一会你会收到一个数,不管你收到什么数,你遇见它以后,你就平方显示出来,那么计算机收到明确的指令,收到2给你返回4,收到3给你返回9,收到5-给你返回25,很明确的指令.或者你跟它说,不管一会你收到一个什么数,你把它减3给我显示出来,那现在收到一个4,显示一个43-就OK了.这叫明确性,你给算法的指令必须-,收到一个5,显示一个53是清晰明确的,你不能跟它商量,算法很晕的.你跟它商量说,一会你收到一个数,你愿意减3你就减3,你愿意平方你就平方,然后显示出来,那计算机拿到以后啪就晕了,它不会有思想,它只是执行,所以你必须给它明确的指令.⑵有限性(Finiteness)因为我们最终要解决一类问题,问题的解决要有限才可以,叫做解决.比如说,你告诉计算机,你把10万以下的质数给我输出来,当然根据你程序的快慢,早晚有那么一天,如果你程序编的好,一分钟就出来了;如果你程序编的不好,有可能下礼拜就出来了,但是,早晚有那么一天,你还可以算出来.如果你给计算机下这么一条指令,你听说过“哥德巴赫猜想”吗?计算机点点头说听说过,你要干嘛啊!我这慎得慌呢!你把“哥德巴赫猜想”给我证一下吧,从6开始,挨个往上你给我拆一遍.什么时候这个问题能够解决,不可能解决.所以,我们说有限性,要让计算机在有限的步骤内解决.当然了,对于计算机实用的角度来说,我们还希望有限步越少越好.有同学说,是有限步,100年以后就算出来了,这就太不切实际了,所以一般来讲,有限性如果说数字忒大,大到这个计算机虽然能算,但是要几年,几百年之后才能结束,那么往往也不认为是一个很好的算法.⑶可执行性(Effectiveness)执行性在计算机里有些事情是做不到的.比如说,数码相机、摄像头、计算机里的数码相片,都有一个概念叫像素,像素越高画面越清晰,像素代表什么意思呢,计算机里面对于图象所识别的最小单位每一个点是什么颜色,然后很多密密麻麻的点摆在一起,一个点是绿的,一个点是黄的,一个点在稍微黄点,这么多有颜色的点摆在一起,看起来可能就是一个从绿到黄的草坪,实际上它只是每一个点是一个单一的颜色.那么,对于计算机来说,有没有可能做出纯我们视觉看到的那种自然色,这不可能,它可以像素非常非常的细密,比如说iPhone像素很高就看不见点了,但仍然是数字化处理一格一格的,不是自然的.你返回1.732,但是反过来你告诉它小数,你问它这是根号几?注意,无限不循环小数,它会认不出来,因为它处理不了,他只能处理到你看起来好像已经几乎没有差别了而已,就是说计算机永远在做模拟,在很多程度上,计算机的工作不具有可执行性.【教师备案】算法虽然没有一个明确的定义,但其特点是鲜明的,不仅要注意算法的有限性、可执行性、明确性的特点,还应该充分理解算法问题的指向性,即算法往往指向解决某一类问题,泛泛地谈算法是没有意义的.以下是三个导入的题.【备选】写出下列算法1.12个小球,其中有一个小球超重,找出一个算法:只用天平称三次找出这个超重的小球【解析】S1:将12个小球分为2堆,一堆6个,用天平称重S2:将S1中重的那6个小球分成2堆,每堆3个,用天平称重S3:取S2中重的那3个小球中任意2个小球称重,若相等,则剩下的那个小球是重的,不等,则重的那个小球是超重的.【教师备案】本题在ICS中有具体演示的视频,老师可以放给学生看。
2.人鬼过河:河的一边有三个人和三个鬼,河中有一小船,每次最多能乘坐2个人或鬼,而且至少要有一个人或鬼船才能行驶。
请设计一种算法,把人和鬼都送到对岸。
注:不论是在河边、船上,如果人鬼数量相同,则鬼和人能和谐相处,鬼不吃人,否则,鬼吃掉人。
要求算法能给出整个运送过程,包括每次船行驶的方向(是驶向对岸还是返回),船上的人和鬼数量。
【解析】S1:鬼1人一过河S2:人一回S3:鬼2,3过河(这样三个鬼过河了,三个人在一起还没过河)S4:鬼1带船回到人的那一边S5:人一,人二,过河S6:人一,鬼2同时带船过河S7:人一,人三同时过河(这时,人全部过河了,和人一起的只有一个鬼3)S8:鬼3带船回(这时,三个人全过了河,而三个鬼和船在一边)S9:鬼1,2过河S10:人一回S11:人一,鬼3过河(完成)【教师备案】本题在ICS中有具体演示的视频,老师可以放给学生看。
经典精讲【铺垫】下列关于算法的说法正确的有( )①求解某一类问题的算法是唯一的;②算法必须在有限步操作之后停止;③算法的每一步操作必须是明确的,不能有歧义或模糊;④算法执行后产生确定的结果;A.1个B.2个C.3个D.4个【解析】C对于①,解决某一类问题的算法可以有很多个.②③④都正确.故选C.【例1】算法的概念⑴下列结论正确的是()A.一个程序的算法步骤是可逆的B.一个算法可以无止境地运算下去C.完成一件事情的算法有且只有一种D.设计算法要本着简单方便的原则⑵算法的有限性是指()A.算法中每个操作步骤都是可执行的B.算法的步骤必须有限C.算法必须有确定的结果D.以上说法均不正确【解析】⑴D⑵ B【拓展】有一堆形状、大小相同的珠子,其中只有一粒重量比其它的轻,某同学经过思考,他说根据科学的算法,利用天平,三次肯定能找到这粒最轻的珠子,则这堆珠子最多有几粒( )A .21B . 24C . 27D . 30【解析】 C将27个9,9,9分堆找出有轻球的那9个,再将这9个3,3,3分堆,再称3个球中的任意两个即可找出最轻的球.30个球分成10,10,10;当10个球3,3,4分组的时候,若有3个球的2组平衡时,这时有轻球在4球的一堆中,但只有一次称量机会,故无法找出. 答案为C【例2】 体会算法【教师备案】让学生做一个感受算法的小例子,在真正的如何去找算法和描述算法之前,计算机上有一个经典的小问题.在讲这个问题之前先讲一个概念,计算机里数字是怎么处理存储的,比如3,计算机里一定要把3放到一个位置存储,你可以把计算机硬盘看成一个很大的空间,分成很多小格,每一个小格是计算机的一个存储单位,在每一个存储单位下存一个数时,它一定要放在一个位置上.现在你把3放在某一个位置上了,下次你想用的时候,你得把它调出来,因为你除了知道3以外,还要知道3被放在哪,这个“哪”在计算机里叫地址.所以每一个数对应一个存储地址,也叫存储空间.比如(如图):m 就是3所在的地址,我们可以写成“3m = ”,这里的“=”是“赋值号”,“赋值号”是将式子右边的数放在左边的空间.所以,我们不能将式子写成“3m =”,即不能一个数放到另一数里.但我们可以写成“n m =”(如图),即把一个数放到另一个空间里.那下面我们来看一下下面的题. 有实数a 、b ,试设计一个算法,将a 、b 的值互换.【解析】 法一: 法二:【教师备案】老师在讲这道题时,可以给学生提示,假如现在有两个杯子,一个杯子里装有半杯的红豆,另外一个杯子里装有半杯的绿豆,现在要求把红豆倒在装绿豆的杯子里,把绿豆倒在装红豆的杯子里,应该怎么弄?很多同学的第一反应就是再找一个空杯子,然后把红豆倒在空杯子里,把绿豆倒在装红豆的杯子里,最后将红豆再倒在装绿豆的杯子里,这样就可以将红豆和绿豆互换了.老师在讲完这时就可以讲例2中的法一了.讲完法一,老师可以接着再提问,说刚才很宽厚,给了你们一个空杯子,现在要求不用空杯子,那应该怎么将红豆和绿豆进行互换.这时候同学就会想到将半杯的红豆倒入半杯的绿豆里,然后再将绿豆数出来放在装红豆的杯子里.这时我们会发现,空间省了但会费好多的时间,这时老师就可以讲法二了.【点评】 可以以此题来讲计算机里空间与时间互换.解法一中采用了三次赋值操作,占用,,a b c 三个地址空间,而解法二采用了三次加减法,和三次赋值操作,而只用了二个地址空间,在本题中,法一的c 的一个地址空间相当于法二的三次加减法,所以我们设计算法的时候,要尽量降低 算法的时间和空间复杂度.n 33m ③ b=c ② a=b x x y x y y x y x ① c=a c b y x a ③ a=a b ② b=a b xy xy x+y x+y ① a=a+b b y x a1、算法的描述:⑴用自然语言; ⑵用数学语言;⑶用算法语言(程序设计语言); ⑷用程序框图(流程图). 【教师备案】算法可以用自然和数学语言来描述,比如,“x 的平方大于4”就是自然语言的描述,数学语言的描述则是“24x ”。