1、3.2 算法及其描述 例:设计一个算法,求两个正整数为M和N的最大公约数?在确定了解决问题的方法之后,如何把解题方法转换成计算机能完成的操作步骤呢?辗转相除法求最大公约数设计算法:1、输入正整数M和N的值2、R=M%N3、如果R=0,则继续步骤4,否则M=N、N=R,转步骤24、输出N的值5、结束算法的基本概念 算法:解题方法的精确描述。其要求是有有限个步骤组成的,并且每一步骤的含义都是明确的,而且是能行的。简单的说,算法就是解决问题的方法和步骤。例如乐谱是乐队指挥和演奏的算法;菜谱是厨师做菜的算法等等。算法的特征 输入:有0个或多个输入 确定性 有穷性 输出:有1个或多个输出 能行性算法的表
2、示方法 算法可以用多种不同的方法来描述,主要有:自然语言、流程图、伪代码 流程图是一种比较直观易用的、用图形来描述算法的方法。用伪代码描述算法就是用介于自然语言与计算机语言之间的文字和符号来描述算法。伪代码不用图形符号,书写方便,格式紧凑,易于理解,便于向计算机程序过度。自然语言 是人们日常所用的语言,如汉语、英语等。使用自然语言不用专门训练,所描述的算法也通俗易懂 例:一个笼子里有鸡和兔,现在只知道里面一共有A个头,B只脚,求鸡和兔各有多少只?设计一个求解的算法,并用自然语言描述出来。分析问题:设所求的鸡数是X,兔数是Y,已知笼子里的头数是A,脚数是B,依题意,得到如下的议程组:X+Y=A2
3、X+4Y=B解方程组得:X=2A-B/2 ,Y=B/2-A设计算法:1、输入A和B的值2、求X=2A-B/2 3、求Y=B/2-A4、输出X,Y的值5、结束流程图中的符号的用途流程图开始输出N的值M=N,N=RR=0R=M除以N的余数输入正整数M和N结束开始Y=B/2-A输出X,Y的值结束X=2A-B/2输入A和B的值是否问题:求6x+5y+4z=50正整数解的个数及显示所有解?t=0 x=1y=1z=1如果6x+5y+4z=50,t=t+1,print x,y,zz=z+1如果z=12,则转步骤,否则继续步骤y=y+1如果y=10,则转步骤,否则继续步骤x=x+1如果x=8,则转步骤,否则继
4、续步骤print tt=0 x=1y=1z=16x+5y+4z=50,t=t+1,print x,y,zz=z+1z=12,转,否转y=y+1y=10,转,否转x=x+1x=8,转,否转print t开始结束t=0,x=1,y=1,z=16x+5y+4z=50是否t=t+1输出x,y,z的值z=z+1z=12是否y=y+1y=10是否z=1y=y+1y=b,则x=a,否则x=b如果c=x,则x=c输出x结束开始输入正整数a,b,ca=bx=ax=bc=xx=b输出正整数x结束伪代码输入正整数a,b,cif a=b:x=aelse:x=bif a=b:x=aelse:x=b输出解的个数t和三个整数x,y,z作业:设计一个算法:求出100以内能被3整除的所有正整数算法的常用描述方法程序的三种基本结构