算法案例

算法案例（精选5篇）

算法案例 篇1

1 引言

随着信息化的进展,计算机已经逐渐成为人们日常生活和工作不可缺少的工具。计算机科学将从前沿高新技术学科变成各专业、各行业均需要普及的基础学科。算法是计算机科学基础内容,也是计算思维培养的核心内容之一。计算机算法的学习,不仅可以让学生体会到计算机的计算能力的强大性,还能够增加学生的解决问题的技能。例如现今新闻、金融、语言等,几乎每个领域都有很多的大数据,挖掘大数据的工作不仅仅属于计算机专业的人员,相关专业的人员也要参与进来,因此掌握计算机算法,对解决类似大数据这类的大规模的、或者很复杂的问题有很大的帮助。

然而算法的学习需要有编程语言、数据结构等课程的学习基础,算法内容生涩难懂,枯燥乏味,非计算机类的专业,特别是文科类专业的计算机教学都避开它。这导致学生无法接触到算法的学习。本文将以生活案例的形式,避开编程语言、数据结构等专业知识,生动形象的介绍算法和算法的思维,以提高学生的学习兴趣,增强学生的计算思维能力。

2 算法的含义

什么是算法呢?简单来说,算法就是解决问题方法。算法处理的内容必然是问题所涉及的数据,算法和数据是程序设计中的核心内容。因此有这一说法:程序=算法+数据结构。

我们生活中也存在许多“算法”。举一例来说,煎一个蛋,厨师首先锅里滴上几滴油,鸡蛋磕破直接把蛋液倒入锅内,用勺子稍稍往鸡蛋上分散撒些食盐,小火等蛋清蛋黄凝固,然后,翻面再煎另一面,这样就做好了煎蛋。这个事例中,鸡蛋、食盐等食材是“数据结构”的话,厨师的烹饪过程便是“算法”。

针对同一问题,很有可能有多种不同的算法。例如,著名的数学家高斯在他小学的时候发生了一件很有名的故事,就是小学老师出于惩罚目的,出了一道算术难题:“计算1+2+3…+100=?”。作为初学算术的学生,高斯的同学都是被难住了,因为他们的解题思路是把这100个数做99次加法运算,需要大量的计算。但是高斯却在几秒后将答案解了出来,他所使用的方法是:对50对构造成和101的数列求和(1+100,2+99,3+98…),同时得到结果:5050。

高斯在小小年纪便能运用巧妙的解题方法,使得他的故事广为流传。人对解决问题与计算机在思维方法上的差异。那么,同样针对这个问题,用计算机程序算法来完成,又应该如何实现呢?

设1~100的累加和放在变量s中,那么让程序重复累加执行:s=s+i,让加数项从1逐步增加到100。这在计算机程序很容易实现。算法的流程和图1所示。

3 排序的应用

排序在生活中是很常见的。比如人员列队时按高矮排列;电影中的票房排行榜;字典或词典里的字词条排序;网上购物时多个推荐商品的前后排序等。

排序对于数据操作来说非常重要。例如:表1中有两组1~10的数字,A组数字是无序的,而B组是有序的。那么随机查找A组中的一个数字,查找方法是从头到尾依次查找,平均要查找5.5次。如果是查找1~10以外的数字,例如-5,则需要查找10次后才能确认它不在表中。而针对B组中有序的数字,我们可以采用折半查找法进行查找,即不是从头到尾依次查找,而是从中间开始查找。中点m=(s+e)/2,s和e分别为数组序号的上限和下限。例如,要查找数字4,一开始,s为1,e为10,m为5,B组中第5个数是5,没有找到4,但是这一次查找,我们可以确定的是,中点的数字是5,我们要找的数字4小于5,所示,它不可能会在数组的后半部分,那么我们可以排队第5~10的数字,只要在前4个数字中查找就可以了。于是第二步,在前4个数中,再次从中间找,s,e,m的值分别为1,4,2。中间的数字是2,也是没有找到,但可以排队第1、2个数字;接着第三步,在剩下的第3、4个数中找,s,e,m的值分别为3,4,3,查到的数字是3,也没找到,剩下只有第4个数了;最后一步,比较第4个数,当然,就找到了我们要查找的数字4。如果要查找1~10以外的数字,则最多4次便可以确定查找失败。因此可以确定,B组有序的数字查找快于A组。

上例中,有序的数所查找快于无序的数据,但是快速的优势并不明显,原因是数据量太小。如果我们把数据记录扩大为1万条。那么无序的查找次数平均为5000次,数据范围之外的数据要查找10000次。那么,对有序的数据,采用折半查找法进行查找,查找次数为,即13.3次。

由上述可知,数据的有序对操作的重要性。那么如何对数据进行排序呢?排序的算法有很多,如选择排序法、冒泡法、直接插入排序法、归并排序法、快速排序法、希尔排序法等。

4 穷举法

穷举法也称为枚举算法,其基本思想是根据题目的部分条件确定答案的大致范围,并在此范围内对所有可能情况逐一验证,直到全部情况验证完毕。若全部情况验证后都不符合题目的全部条件,则本题无解[1]。

生活中也存在许多穷举法的案例。例如,小明是新来的机房管理员,他要管理的是n间机房,有n把钥匙,但他不清楚哪条钥匙对应哪间机房,那么他便每扇门逐条钥匙的去试,直到确认每把钥匙对应的机房。

用穷举法来破解密码,也称暴力破解法,是密码破解技术中最基本的方法。简单来说就是将密码进行逐个推算直到找出真正的密码为止。比如一个四位并且全部由数字组成其密码共有10000种组合,也就是说最多我们会尝试9999次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算,也就是说用我们破解任何一个密码也都只是一个时间问题。破解过程可以用网上免费的暴力破解软件演示给学生看。

穷举法在求解一个较小规模的问题时,可以根据问题中的约束条件把可能的情况一一列举出来,然后注意尝试从中找到满足约束条件的解。若该问题规模较大,比如破译一个有位数很长,且有多种符号可能的密码,其组合方法可能有万亿种组合。用普通的电脑可能会用掉几年甚至更多的时间去计算,这样长的时间显然是不能接受的。因此规模太大的求解问题穷举法并不适合,应考虑用其他效率更高的算法。

5 动态规划

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。所有已解的子问题的答案将会记录在一个表中。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这样,当需要已求得的子问题的答案,只要在表中查找就可以了,这样就可以避免大量的重复计算,节省时间[2]。

简单地说,动态规划就是采用分治的策略,把求最优解问题分解为求若干子问题的最优解,记录子问题的解,化繁为简。

例:一个楼梯有x级(本例中x=5),每次可以走1级或2级,请问走完楼梯一共有多少种走法?

动态规划的关键是发现子问题和怎么记录子问题。此例中,分解为2个问题:(1)走1级,楼梯就还剩x-1级,这种情况下剩下的楼梯共有f(x-1)种走法。(2)走2级,变成x-2级,这种情况下剩下的楼梯共有f(x-2)种走法。

直到最后,如果只有1级楼梯的话,只有一种方法可以走完,那就是直接走1级;只有2级的话,可以走两步1极,或者走一步2级,共2种走法。显然f(1)=1,f(2)=2。

于是就得到了一个递推公式:

式(1)中设x=5,那么:

可以得出5级楼梯有8种走法。本例的程序算法,可采用递归函数的方法来实现。

6 并行计算

为了更好理解并行计算,我们先来看看2个并行思想的案例。

近年来澳洲的各个河流湖泊遭遇到了生态不平衡,河水里头的鲤鱼异常泛滥造成了当地的生态被坏。由于数量太多了,民众也没有动力去捕捉。单靠一个人或机构去捕捉是不现实的。为此,2015年底,澳大利亚政府想出了一个办法:在某河展开了一项活动,将芯片植入到一条鲤鱼,然后将它放回河里并且鼓励人们到河边钓鱼,如果钓到这条拥有芯片的鲤鱼则可获得100万澳元的奖金。试图吸引全国的钓鱼好手来钓鱼,以消灭成群的鲤鱼[3]。

另一个案例是美国纽约时报利用图形验证码的人工识别来输入的大量历史资料。纽约时报有大量的历史资料,这些早期纸质的资料由于印刷模糊等多种原因,机器无法准确识别。单靠人工录入不仅工作量巨大,准确度也难以保证。于是想到靠亿万网民来帮忙。先把资料扫描为图形,按单词切割成小块并编号,然后将这些单词图块放在验证码后面,网民输入验证码的同时也义务完成了资料的录入工作。为了保证正确率,同一单词图块在2次录入相同时,录入结果才被采纳。

并行计算是指同时使用多种计算资源解决计算问题的过程,是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题,即将被求解的问题分解成若干个部分,各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机,也可以是以某种方式互连的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理,再将处理的结果返回给用户[4]。

并行操作能让问题解决的速度更快,关键是如何分解成若干个尽量相互独立的了问题,即问题分解方案,从而使计算机能够运用并行的方法高效的解决。云计算的核心原理就是实现在不同服务器之间的负载均衡,也就是说,让不同的服务器参与同一个计算,这就涉及并行计算的问题。

7 总结

算法是计算思维教育的核心内容之一。对于初学者,特别是文科类的初学者来说,算法生涩难懂,枯燥乏味。本文将生活案例引入分类别的算法教学中,将算法的思想生动形象的展现出来,使学生更容易理解和接受,能够很好地达到计算思维培养的目的。

摘要：算法是计算思维培养的核心内容之一,但目前因各种原因并未在非计算机专业的计算机教学中普及。该文将生活案例引入到算法教学中,这些生活案例分别对应动态规划、并行计算等类别的算法问题,生动形象的展示算法的思维,解决了算法教学需要多门课程基础的问题。

关键词：算法,案例,计算思维,教学

参考文献

[1]孙义欣,冯娜穷.举法在程序设计中的应用[J].计算机时代,2012(8):51-53

[2]王晓东.算法设计与分析[M].北京:清华大学出版社,2003:61-63.

[3]网易旅游.澳洲河流生态不平衡悬赏百万澳元捉拿一条鲤鱼[EB/OL].http://travel.163.com/15/1213/12/BANEPSK100063KE8.html,2015-12-13.

[4]钟晴江.大学计算机[M].北京:高等教育出版社,2013:151-152.

算法案例 篇2

唐劲松

一、教材解读

本节内容是在学习了算法的基础知识上，探究古代典型的算法案例——辗转相除法和更相减损术，巩固算法三种描述性语言（算法步骤，程序框图和程序语言），使学生对算法中的迭代思想有一个初步的认识。一方面以辗转相除法及更相减损术为载体，使学生通过模仿，操作，探索经历算法设计的全过程，帮助学生进一步体会算法的基本思想，感受算法在解决实际问题中的重要作用，另一方面让学生体会中国古代数学家对现代数学发展的贡献。

二、教学重难点

重点：辗转相除法与更相减损术的方法和步骤；

难点：辗转相除法的原理及其程序。

三、教学过程

Ⅰ引入新课

简单回顾短除法求两个数的最大公约数，并提出问题：当两个数较大时（如：8251与6105），如何求它们的最大公约数？引出课题——辗转相除法。

Ⅱ知识探究

1、以求8251与6105的最大公约数的过程为例，讲解如何利用辗转相除法求两个数的最大公约数。对于辗转相除法的原理，书本介绍的不是很详细，学生容易产生疑惑，需要教师讲解清楚。

2、通过这个实例，让学生能够模仿求任意两个数的最大公约数，体会这种迭代的思想，并能与前面学习的循环结构联系起来。

3、训练（学生演排），了解学生的掌握情况，及时指出问题。

4、简单介绍欧几里得其人，增强学生人文素养。

5、引导学生根据前面的过程画出辗转相除法的程序框图，并编写出程序。灵活运用直到型循环结构及当型循环结构，并能转化成语句。完成课本P45练习1:用辗转相除法求下列两个数的最大公约数：（1）225,135；（2）98,196；（3）72,168；（4）153,119.并用程序进行演示判断是否正确。

6、巩固提高：

（1）求三个数：324,243,135的最大公约数；（2）求228与1995的最小公倍数。

7、介绍另一种求最大公约数的方法——更相减损术，简单介绍相关数学史的知识，对学生进行数学文化熏陶，增强民族自豪感。

8、通过实例：求98与63的最大公约数 来理解更相减损术的原理和过程。

9、分别用辗转相除法和更相减损术求168与93的最大公约数，来体会和总结辗转相除法和更相减损术的区别。

Ⅲ课堂小结

算法案例学习指导 篇3

例1 用展转相除法编写求63,81的最小公约数的程序．

程序如下：

总结 辗转相除法：辗转相除法就是把给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数，继续上面的除法，直到余数为零，此时的除数就是所求的最大公约数．

从算法思想我们可以看出，辗转相除法的基本步骤是用较大的数（用[a]表示）除以较小的数（用[b]表示），得到：[a=nb+r0≤r

由于这是一个反复执行的步骤，且执行的次数由余数[r]是否等于0决定，所以我们可以把它看作一个循环体，用循环结构就可以实现其算法．

例2 写出利用更相减损术求249与186的最大公约数的程序．

总结 1. 用更相减损术求两数最大公约数时，是当大数减小数恰好等于小数时停止减法，这时的小数就是要求的两数的最大公约数．

2. “更相减损术”与“辗转相除法”的异同点：“更相减损术”与“辗转相除法”这两种算法分别来源于东西方古代数学名著，但二者的算理却是相似的，有异曲同工之妙，主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但实质都是一个不断的递归过程．

案例2 秦九韶算法的应用

秦九韶算法的特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个[n]次多项式，只需做[n]次乘法和[n]次加法即可．秦九韶算法的计算量小，且逻辑简单．

例3 已知[n]次多项式[pn(x)=a0xn+a1xn-1][+⋯+an-1x+an],如果通常算法中，计算[x0k(k=2,3,4,⋯,n)]的值需[k-1]次乘法，计算[p3(x0)]的值是需要9次运算（6次乘法，3次加法），那么计算[pn(x0)]的值需要[12n(n+3)]次运算.

将其改为:

[pn(x)=(a0xn-1+a1xn-2+⋯][+an-1)x+an]

[=(a0xn-2+a1xn-3+⋯+an-2)x+an-1x+an]

[=⋯=(⋯((a0x+a1)x+a2)x+⋯+an-1)x+an]

其算法步骤：

第一步：计算最内层[a0x+a1]的值，将[a0x+a1]的值赋给一个变量[v1]；

第二步：计算[(a0x+a1)x+a2]的值，可以改写为[v1x+a2]，将[v1x+a2]的值赋给一个变量[v2]；

以此类推，即每一步计算之后都赋于一个新值[vn]，即从最内层括号到最外层括号的值依次赋予变量[v1]，[v2]，[v3]，[⋯]，[vk]，[⋯]，[vn]，第[n]步的求值[vn=vn-1x+an]即为所求多项式的值．

秦九韶的算法中：[p0(x)=a,pk+1(x)=xpk(x)][+ak+1(k=0,1,2,⋯,n-1)]．

利用该算法，计算[p3(x0)]的值共需6次运算，计算[pn(x0)]的值共需要[2n]次运算．

案例3 算法在二分法中的应用

例4 设区间[0，1]是方程[fx=0]的有解区间，设计一个用二分法求此方程在区间[0，1]上一个近似解的方法，并画出程序框图，要求精确到[ε]．

算法如下：

第一步，确定有解的区间[[a，b]][fafb<0.]

第二步，取[[a，b]]的中点[a+b2]．

第三步，计算函数[fx]在中点处的函数值[fa+b2]．

第四步，判断函数值[fa+b2]是否为0.

（1）如果为0，[x=a+b2]就是方程的解，问题就得到了解决．

（2）如果函数值[fa+b2]不为0，则分两种情况：

①若[fafa+b2<0]，则确定新的有解区间[a,a+b2]；

②若[fafa+b2>0]，则确定新的有解区间[a+b2,b]．

第五步，判断新的有解区间的长度大于误差[ε]：

（1）如果新的有解区间的长度大于误差[ε]，则在新的有解区间的基础上重复上述步骤；

（2）如果新的有解区间长度小于或等于误差[ε]，则取新的有解区间的中点为方程的近似解．

程序框图如下图：

案例4 算法在分期付款中的应用

例5 张老师购买安居工程集资房92m2，单价为1000元／m2，一次性国家财政补贴28800元，学校补贴14400元，余款由个人负担，房地产开发公司对教师实行分期付款（注①），每期为一年，等额付款，签订购房合同后一年付款一次，再经过一年又付款一次等等，共付10次，10年后付清，如果按年利率7.5%，每年按复利计算（注②），那么每年应付款多少元？画出程序框图，并写出计算所需的程序．（计算结果精确到百元）（注③）

注：①分期付款，各期所付的款以及最后一次付款时所生的利息合计应等于个人负担后购房余款的现价及这个现价到最后一次付款时所生的利息之和．

②每年按复利计算，即本年利息计入次年的本金利息．

③必要时参考下列数据：

[1.0759≈1.917,][1.07510≈2.061,][1.07511≈2.216]

这个问题就是数列中的分期付款问题．解决这个问题用到的是等比数列求和公式，计算量较大，还难以理解．而应用WHILE语句就能较好解决以上问题．先写出程序框图如下图：

[输入公式][结束] [是][否]

程序如下：

总结 循环语句作用主要用来处理算法中的循环结构，在处理一些需要重复计算的问题，如累加求和，累乘求积等问题时，常用到循环语句来编写程序．

【练习】

1．用辗转相除法和更相减损术求48与30的最大公约数，写出具体算法步骤．

2．写出求[m=60]和[n=33]的最大公约数的算法和程序框图．

3．用秦九韶算法计算多项式[f(x)=x6-12x5+60x4-][160x3+240x2-192x+64]当[x=2]时的值．

算法案例 篇4

1 系统构架

案例挖掘系统的架构(图1)包含两个主要模块,特征提取和案例挖掘该系。特征提取器使用模糊测量的方法来选择数据的重要特征,通过评价其相关系数、重叠率和信息增益来发现特征之间的关联,计算案例的相关性。将具有较高相关性的案例选定为重要特征用来挖掘案例,为数据挖掘产生每一个权重。案例挖掘则是利用聚类分析的遗传算法来选择具有代表性的个案。

2 案例特征提取算法设计

特征分析的目的在于确认有意义的特征。R.Caruana和P.Langley发现为特征选择有关的特征都非常重要[3,4],有些系统还可以使用数据挖掘的特征选择。X.Zhu利用特征和作为权重类的相关特征之间的关联来处理错过值[5]。C.Lee和G.G.Lee使用信息增益和不同的特征选择方法来查找相关的特征[6]。G.Qu引入了一个新特征的相关性和子集优点措施来计算特征的相关性和相互关系,提高预测和数据挖掘算法的准确性[7]。本文采用模糊特征提取成分分析(FCA)来评价特征的相关性。

CC、OR和IG分别代表相关系数、重叠率、信息增益。

CC表示计算两个变量的值的变化:

式中,Ai、Ci、分别表示特征值、类值、特征值的平均值和类值的平均值。

OR表示特征值在不同的类之间的重叠度:

式中,Ci和Cj是指i类和j类的特征值的范围。

IG表示根据增益率计算一个特定特征的存在频率[6]:

式中,P、S和Sv分别是概率,特定特征的案例数量,以及类的值是v的个案数量。

特征提取运用模糊理论来计算FCA的隶属度(图2)。

特征提取器利用作为模糊理论的矩阵计算方法来算出每个所选特征的权重。

式中,μ(x)是特征x的隶属度。

新的模糊关联矩阵,见表1;新的模糊集隶属函数,见图3。

3 针对案例的挖掘算法设计

案例挖掘运用遗传算法来选择有代表性的案例,即从原始数据集中选出代表性案例。选择该基因的长度等于案例数目,图4显示了基因的代表性,基因数字用1和0表示案例被选中或没被选中。

在具有代表性案例的范围内,用合适的函数通过计算最接近的案例数量,来评估案例的覆盖范围。

式中,h、Ci、n、cov(Ci)、d(x,y)和Wi分别代表假设,假设的侯选案例,侯选案例的数量,包含侯选案例Ci的案例,权重距离量度和第i个特征的权重。当代表性案例覆盖90%以上的案例时,评估结束。值得注意的是,交叉和变异概率是100%和1%。

最后,通过不断增加具有重要意义特征值的案例,可以在丰富的案例库中进行案例挖掘。显著特征的值不包含在代表性案例的范围内。

4 结论

通过对案例挖掘系统的算法设计,可以构建一个为数据挖掘服务的医学案例库系统。然后在医疗案例库构建中采用了3个标准医疗数据集,包括有大肠直肠癌数据库、甲状腺癌数据库以及乳癌数据库,用这3种医疗数据集作为测试数据来进行数据挖掘。然后以典型案例的涵盖程度以及其使用率作为检视案例库完整性的依据(实验数据量大,就不在本文中描述)。最后对案例库的建设也使用决策规则和神经网络的分类规则进行了评估,研究表明,该系统可以找到正确的典型案例。

参考文献

[1]Y.Li,S.C.K.Shiu and S.K.Pal,Combining Feature Reduction andCase Selection in Building CBR classifiers[J].IEEE Transactionson Knowledge and Data Engineering,2006,18(3):415-429.

[2]N.Arshadi and I.Jurisica.Data Mining for Case-Based Reasoningin High-Dimensional Biological Domains[J].IEEE Transactionson Knowledge and Data Engineering,2005,17(8):1127-1137.

[3]R.Caruana,D.Freitag.Greedy Attribute Selection[A].In Proceedings of International Conference on MachineLearning[C].Morgan Kanfman,1994:28-36.

[4]P.Langley.Selection of Relevant Features in Machine Learning[J].AAAI Fall Symposium on Relevance,1994:97(1-2):1-5.

[5]X.Zhu,X.Wu.Data Acquisition with Active and Impact-SensitiveInstance Selection[A].Proceedings of 16th IEEE InternationalConference on Tools with Artificial Intelligence[C].BocaRaton:IEEE computer Society,2004,721-726.

[6]C.Lee,G.G.Lee.Information Gain and Divergence-Based FeatureSelection for Machine Learning-Based Test Categorization[J].Information Processing and Management,2006,42(1):115-165.

[7]G.Qu,G.Hariri,M.Yousif.A New Dependency and CorrelationAnalysis for Features[J].IEEE Transactions on Knowledge andData Engineering,2005,17(9):1199-1207.

算法的概念教学设计案例 篇5

目标：

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的最大公约数。