算法定义[1].ppt

。算法是人求解问题的思想方法,是对解题过程的精确描述,同样也需要用语言来表示。表示算法的语言主要有自然语言,流程图,伪代码等。,自然语言是人们日常所用的语言,如汉语,英语,德语。使用这些语言不用专门训练,所描述的算法也通俗易懂1问题1:鸡兔同笼问题。一个笼子里有一些鸡和兔,现在只知道里面一共有35个头,94只脚,问鸡和兔各有多少只?试设计一个求解的算法,并用自然语言描述出来。分析问题设所求的鸡数是x,兔数是y,已知笼子里的头数是a,脚数是b,依题意得到如下的方程组:{x+y=a2x+4y=b解方程组得:x=2a-b/2, y=b/2-a2设计算法:(1)输入a和b的值;(2)求X=2A-B/2;(3)求y=b/2-a;(4)输出x, y的值;(5)结束。3问题2:设计一个算法,求100以内能被3整数的数。分析问题:设能被3整除的数为I,令I=1,2,3,…,100,如果I能被3整数,则输出I,否则,检查下一个,知道I=100为止。设计算法:1)令I=1;(2)如果I能被3整除的数,则输出I;(3)I=I+1;(4)如果I<=100,则返回第(2)步;(5)结束。4然而,用自然语言描述法也存在明显的缺点:(1)由于自然语言的歧义性,容易导致算法执行的不确定性;(2)自然语言的语句一般太长,从而导致了用自然语言描述的算法太长;(3)由于自然语言表示是按照步骤的标号顺序执行的,因此当一个算法中循环和分支较多时就很难清晰地表示出来;(4),我们学习了用程序框图来描述算法。在程序框图中,流程图是描述算法的常用工具,它采用美国国家标准化协会ANSI(American National Standard Institute)规定的一组图形符号来表示算法,如下表所示:6图形名称功能开始/结束表示算法的开始或结束输入/输出表示算法中变量的输入或输出处理表示算法中变量的计算与赋值判断表示算法中的条件判断流程线连接点连接点表示算法中的流向表示算法中的转接7 使用流程图描述算法,让人感到流程的描述清晰简洁,容易表达分支结构;它不依赖于任何具体的计算机和计算机程序设计语言,从而有利于不同环境的程序设计。图2-1给出了用辗转相除发求两个数的最大公约数的算法流程图;图2-2给出了问题1的算法流程图;图2-;8“算法是计算机科学的基础”,计算机完成任何一项任务都需要算法。但是,用自然语言或程序框图描述的算法计算机是无法“理解”的,我们还需要将算法用计算机能够理解的语言表达出来,通常这称为程序设计,所用的语言称为程序设计语言(programming language)。程序设计语言由一些有特定含义的程序语句构成,与算法程序框图的三种基本结构相对应,任何程序设计语言都包含输入输出语句、赋值语句、条件语句和循环语句。不同的程序设计语言有不同的语句形式和语法规则,但基本结构是相同的,正是由于这样的原因,在研究算法的时候,有时并不很关心算法语句是否用的是某种精确的程序语言,而采用基本结构相同的更为简便易懂的语言形式,即所谓伪代码。。它不用图形符号,因此,书写方便,格式紧凑,易于理解,便于向计算机程序设计语言算法(程序)过渡。下面给出用辗转相除法求两个数的最大公约数的伪代码算法描述。INPUT M, N;R=M mod N;DO WHILE R 0M=NN=RR=M mod NLOOP;PRINT N10