算法和算法的特征

《算法和算法的特征》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1-2算法和算法的描述赵圣川1.2.1算法1、算法的概念在数学课程里，我们学习了算法的基本思想和初步认识，知道了是在有限步骤内求解某一问题所使用的一组被定义明确的规则。通俗地说，算法就是用计算机求解某一问题的方法，是能被机械执行的动作或指令的有穷集合。欧几里得阐述了关于求两个最大公约数的过程，这就是著名的欧几里得算法——辗转相除法。设定两个正整数为m和n，求它们的最大公约数的步骤为：（1）以m除以n，令所得的余数为r。（2）若r=0，则输出结果n,算法结束；否则继续步骤（3）。（3）令m=n，n=r，并返回步骤（1）继续进行。实践设给定两个正整数m=1

2、12和n=64，利用辗转相除法，求它们的最大公约数。算法如下：（1）112除以64，余数为＿；（2）＿除以＿，余数为＿；（3）＿除以＿，余数为＿；答案（1）112除以64，余数为（48）；（2）（64）除以（48），余数为（16）；（3）（48）除以（16），余数为（0）；答：112和64的最大公约数为（16）。2.算法的特征(1)输入。一个算法有零个或多个输入。(2)确定性。算法的每一步骤必须要确切定义。(3)有穷性。一个算法在执行有穷步之后必须结束。(4)输出。算法有一个或多个输出。(5)能行性。算法中有待执行的运算和操作必须是相当基本的，换句话说

3、，它们都是能够精确地进行的。1.2.2算法的描述人的思想要用语言来表达。而算法则是人求解问题的思想方法，是对解题过程的精确描述，同样也需要用语言来表示。表示算法的语言，主要有自然语言、流程图、伪代码等。1、用自然语言描述算法前面关于欧几里得算法以及算法实例的描述，使用的都是用自然语言。自然语言是人们日常所用的语言，如汉语、英语、德语等。使用这些语言不用专门训练，所描述的算法也通俗易懂。问题1-2：鸡兔同笼问题。一个笼子里有鸡和兔，现在只知道里面一共有35个头，94只脚，鸡和兔各有多少只？试设计一个求解的算法，并用自然语言描述出来。（1）分析问题设所求的

4、鸡数是x,兔数是y,已知笼子里的头数是a,脚数是b,依题意，得到如下方程组：x+y=a2x+4y=b解方程组得：x=2a-b/2,y=b/2-a(2)设计算法①输入a和b的值；②求x=2a-b/2；③求y=b/2-a；④输出x,y的值；⑤结束。问题1-3:设计一个算法，求出100以内能被3整除的所有正整数。（1）分析问题。设能被3整除的数为I,令I=1，2，3，…，100，如果I是能被3整除的数，则输出I，否则，检查下一个I，直到I=100为止。（2）设计算法。①令I=1；②如果I能被3整除，则输出I；③I=I+1；④如果I≤100，则返回第②步；⑤结

5、束。然而，用自然语言描述算法也存在明显的缺点：（1）由于自然语言的歧义性，容易导致算法执行的不确定性。（2）自然语言的语句一般较长，从而导致了用自然语言描述的算法太长。（3）由于自然语言表示是按照步骤的标号顺序执行的，因此，当一个算法中循环和分支多时就很难清晰地表示出来。（4）自然语言表示的算法不便翻译成计算机设计程序。2、用流程图描述算法在数学课堂里，我们学习了用程序框图来描述算法。在程序框图中流程图是描述算法的常用工具，它由表1-4所列的一组图形符号来表示算法。表1-4流程图的基本图形及其功能图形名称功能开始/结束框表示算法的开始或结束输入/输出框

6、表示算法中变量的输入或输出处理框表示算法中变量的计算与赋值判断框表示算法中的条件判断流程线表示算法中的流向连接点表示算法中的连接1-2的算法流程图输入正整数m和n开始r=m除以n的余数r=0输出n的值结束M=n,n=r1-3的算法流程图输入a和b开始x=2a-b/2输出x,y的值结束y=b/2-a1-2的算法流程图开始I=1I能被3整除结束I=I+1输出I的值I≤100是否是3、用伪代码描述算法伪代码是介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此，书写方便，格式紧凑，易于理解，便于向计算机程序设计语言过渡。伪代码描述算

7、法回避了程序设计语言严格、烦琐的书写格式，它不需要让计算机接收，又吸取了程序设计语言代码表达的精炼，容易转换为程序设计语言。但由于语言的种类繁多，伪代码的语句不容易规范，有时会产生误解。下面给出用辗转相除法去求两个最大公约数的伪代码算法描述。INPUTm,nR=mmodnDOWHILEr≠0m=nn=rLOOPPRINTn1.2.3算法在解决问题中的地位和作用在运用计算机程序解决问题的过程中,算法设计是一个重要环节，不同的算法会产生不同的运行效果。求两个整数的最大公约数，有很多不同的算法。以下是两位同学用不同的算法设计的9147485和5147480的

8、最大公约数的两个程序。同学甲的算法：同学乙的算法PrivateSubCommand1_Clic