算法的表示方法.ppt

1.3算法的表示方法算法的表示方法算法的描述算法的描述l1、自然语言描述、自然语言描述l2、用流程图描述、用流程图描述l3、用伪代码或直接用、用伪代码或直接用计算机程序描述计算机程序描述易理解，但书写烦、易引起歧义易理解，但书写烦、易引起歧义直观、形象直观、形象能被计算机识别和执行能被计算机识别和执行伪代码伪代码l是介于自然语言和计算机程序语言之间的一种算法描述，它也是专业软件开发人员描述算法的一种常用方法。1、自然语言描述算法、自然语言描述算法C引入一个空杯子引入一个空杯子【例【例1】交】交换换两个杯子中的液体。两个杯子中的液体。提问同学，如何处理？提问同学，如何处理？将杯子将杯子A中的液体倒中的液体倒给给杯子杯子C；将杯子将杯子B中的液体倒中的液体倒给给杯子杯子A；将杯子将杯子C中的液体倒中的液体倒给给杯子杯子B。AB2、用流程图描述算法l【例3】将例2用流程图来描述。算法的执行流程算法的执行流程l顺序结构顺序结构l分支结构（选择结构）分支结构（选择结构）l循环结构（重复结构）循环结构（重复结构）算法的执行流程算法的执行流程l顺序结构顺序结构算法的执行流程算法的执行流程l顺序结构顺序结构【例【例1】键盘输入半径键盘输入半径r，求该圆周长及面积并输出。，求该圆周长及面积并输出。1、分析问题：、分析问题：输入数据：输入数据：处理问题：处理问题：输出数据：输出数据：2、设计算法：、设计算法：r开始开始结束结束输入半径输入半径r计算圆周长计算圆周长c=2*3.14*r计算圆面积计算圆面积s=3.14*r*r输出周长输出周长c输出面积输出面积s程序代码：程序代码：Input rC=2*3.14*rS=3.14*r*rPrint cPrint s算法的执行流程算法的执行流程l顺序结构顺序结构【例【例2】交换变量交换变量a，b的值。的值。1、分析问题：、分析问题：输入数据：输入数据：处理问题：处理问题：输出数据：输出数据：2、设计算法：、设计算法：开始开始结束结束输入变量输入变量a、b输出变量输出变量a、b程序代码：程序代码：Input a,bc=aa=bb=cPrint aPrint bc=aa=bb=c算法的执行流程算法的执行流程l顺序结构顺序结构【例【例3】连续输出连续输出5个个*，设计程序并调试。，设计程序并调试。1、分析问题：、分析问题：输入数据：输入数据：处理问题：处理问题：输出数据：输出数据：2、设计算法：、设计算法：开始开始结束结束输出输出“*”程序代码：程序代码：Print“*”Print“*”Print“*”Print“*”Print“*”输出输出“*”输出输出“*”输出输出“*”输出输出“*”算法的执行流程算法的执行流程l顺序结构顺序结构【例【例19】键盘输入一个二位正整数】键盘输入一个二位正整数n，输出它的十位数，输出它的十位数x。1、分析问题：、分析问题：输入数据：输入数据：处理问题：处理问题：输出数据：输出数据：2、设计算法：、设计算法：int（x）取整函数）取整函数【例【例4】输入任意一个二位正整数】输入任意一个二位正整数n，输出，输出n的十位数。如输入的十位数。如输入45，则输出，则输出4.开始开始结束结束输入二位正整数输入二位正整数n输出输出a十位数十位数a=int(n/10)程序代码：程序代码：Input na=int(n/10)Print a算法的执行流程算法的执行流程l顺序结构顺序结构【例【例19】键盘输入一个二位正整数】键盘输入一个二位正整数n，输出它的十位数，输出它的十位数x。int（x）取整函数）取整函数 取余取余 mod【例【例5】输入任意一个三位正整数】输入任意一个三位正整数n，输出这个三位数各位数字之和，输出这个三位数各位数字之和total。例。例如：输入如：输入456，输出结果为，输出结果为15。开始开始结束结束输入三位正整数输入三位正整数n输出输出total百位数百位数a=int(n/100)程序代码：程序代码：Input na=int(n/100)b=int(n-a*100)/10)c=n mod 10total=a+b+cPrint total十位数十位数b=int(n-a*100)/10)个位数个位数c=n mod 10total=a+b+c算法的执行流程算法的执行流程l分支结构分支结构双分支结构双分支结构 单分支结构单分支结构 算法的执行流程算法的执行流程双分支结构双分支结构 单分支结构单分支结构【例【例24】打印出从键盘输入的两个不相等的数中较大的数。】打印出从键盘输入的两个不相等的数中较大的数。（双分支结构）（双分支结构）算法的执行流程算法的执行流程分支结构分支结构 【例【例25】求分段函数值】求分段函数值。y=x2 2x+1 x3 x0)1 (x0)y=0 (x=0)y=0 (x=0)-1 (x0)-1 (x0)算法的执行流程算法的执行流程分支结构分支结构 单分支结构单分支结构 流程流程图图：【例【例29】分段函数问题。（分支嵌套）】分段函数问题。（分支嵌套）算法的执行流程算法的执行流程分支结构分支结构 【例【例30】购买地铁车票：乘】购买地铁车票：乘1-4 站站 3元元/位；位；5-9站站 4元元/位；位；9站以上站以上5元元/位；输位；输入人数入人数person、站数、站数n，输出应付款，输出应付款pay。(分支嵌套）分支嵌套）流程流程图图：分析问题：分析问题：输入什么数据？输入什么数据？处理什么问题？处理什么问题？输出什么数据？输出什么数据？算法的执行流程算法的执行流程分支结构分支结构 【例【例31】某手机话费套餐规定：每月】某手机话费套餐规定：每月60元，可通话元，可通话300分钟，超过分钟，超过300分钟的部分钟的部分，另按每分钟分，另按每分钟0.4元计算。键盘输入当月通话时间（分钟），计算当月实际需元计算。键盘输入当月通话时间（分钟），计算当月实际需付的手机费。如果输入的通话时间小于付的手机费。如果输入的通话时间小于0，则应输出，则应输出“输入数据有误输入数据有误”的提示信的提示信息。息。流程流程图图：分析问题：分析问题：输入什么数据？输入什么数据？处理什么问题？处理什么问题？输出什么数据？输出什么数据？算法的执行流程算法的执行流程循环结构循环结构 1 1 1 1、定义：、定义：、定义：、定义：某些操作进行重复执行的结构。某些操作进行重复执行的结构。某些操作进行重复执行的结构。某些操作进行重复执行的结构。2 2、基本模式：、基本模式：、基本模式：、基本模式：当型循环，直到型循环当型循环，直到型循环当型循环，直到型循环当型循环，直到型循环当型循环当型循环当型循环当型循环直到型循环直到型循环直到型循环直到型循环循环条件循环条件循环体循环体循环体循环体循环条件循环条件3 3、组成：、组成：、组成：、组成：循环体：循环体：循环体：循环体：重复执行的步骤。重复执行的步骤。重复执行的步骤。重复执行的步骤。循环条件：循环条件：循环条件：循环条件：判断是否执行循环体的条件。判断是否执行循环体的条件。判断是否执行循环体的条件。判断是否执行循环体的条件。算法的执行流程算法的执行流程循环结构循环结构 【例【例1 1】过马路问题】过马路问题：如果红灯，则等待，重复前面过程，否则过马路。如果红灯，则等待，重复前面过程，否则过马路。组成：组成：循环体：循环体：等待。等待。循环条件：循环条件：是否红灯。是否红灯。当型循环当型循环当型循环当型循环是是 绿绿 灯灯 吗吗直到型循环直到型循环直到型循环直到型循环算法的执行流程算法的执行流程循环结构循环结构 【例【例2 2】打印输出五个】打印输出五个“你真棒！你真棒！”。组成：组成：循环体：循环体：输出输出“你真棒！你真棒！”循环条件：循环条件：输出输出“你真棒！你真棒！”个数是否满个数是否满5个。个。当型循环当型循环当型循环当型循环 开始开始 i=1i=5打印输出打印输出“你真棒！你真棒！”i=i+1是是否否结束结束循环变量三要素：循环变量三要素：循环变量三要素：循环变量三要素：初值、终值、步长初值、终值、步长初值、终值、步长初值、终值、步长 开始开始 i=0i5打印输出打印输出“你真棒！你真棒！”i=i+1是是否否结束结束算法的执行流程算法的执行流程循环结构循环结构 若需要循环次数为若需要循环次数为n，通常循环变量，通常循环变量i初值初值为为1，终值为，终值为n，步长为，步长为1，判断条件为，判断条件为i=n，计数语句，计数语句i=i+1位于循环体最后。位于循环体最后。算法的执行流程算法的执行流程循环结构循环结构 【例【例3 3】求】求65+90+10+35+75的和的和s s。组成：组成：循环体：循环体：输入一个数据输入一个数据x，加到表示和的变量，加到表示和的变量s中。中。循环条件：循环条件：循环变量循环变量i是否满是否满5次。次。累加器：循环体中，将输入的数据累加器：循环体中，将输入的数据x加到变量加到变量s中去，中去，采用的是采用的是s=s+x的方法，这种方法称为累加，变量的方法，这种方法称为累加，变量s起起到了累加数据的作用，称为累加器。累加器初值一般到了累加数据的作用，称为累加器。累加器初值一般为为0。循环变量：设置变量循环变量：设置变量i作为循环变量，作为循环变量，起计数器的作用，控制循环次数。起计数器的作用，控制循环次数。用用变变量跟踪表量跟踪表体会循体会循环过环过程。程。循环次数循环次数is0（初值）（初值）123451 02 653 65+904 65+90+105 65+90+10+356 65+90+10+35+75算法的执行流程算法的执行流程循环结构循环结构 【例【例4 4】计算计算s=1+2+3+4+5的值。的值。组成：组成：循环体：循环体：输入变量输入变量x，设置变量，设置变量s作为累加器，实现累加。作为累加器，实现累加。循环条件：循环条件：设置循环变量设置循环变量i，作为计数器，循环次数，作为计数器，循环次数5次。次。用用变变量跟踪表量跟踪表体会循体会循环过环过程。程。循环次数循环次数is0（初值）（初值）123451 02 13 1+24 1+2+35 1+2+3+46 1+2+3+4+5算法的执行流程算法的执行流程循环结构循环结构 练习：练习：组成：组成：循环体：循环体：输入变量输入变量x，设置变量，设置变量s作为累乘器，实现累乘。作为累乘器，实现累乘。循环条件：循环条件：设置循环变量设置循环变量i，作为计数器，循环次数，作为计数器，循环次数5次。次。用用变变量跟踪表量跟踪表体会循体会循环过环过程。程。循环次数循环次数is0（初值）（初值）123451 12 13 1*24 1*2*35 1*2*3*46 1*2*3*4*5如果求如果求s=1*2*3*4*5s=1*2*3*4*5的值，流程图该如何调整？的值，流程图该如何调整？1累乘器：循环体中，将循环变量累乘器：循环体中，将循环变量i的值乘到变量的值乘到变量s中去，中去，采用的是采用的是s=s*i 的方法，这种方法称为累乘，变量的方法，这种方法称为累乘，变量s起到了起到了累乘数据的作用，称为累乘器。累加器初值一般为累乘数据的作用，称为累乘器。累加器初值一般为1。算法的执行流程算法的执行流程循环结构循环结构 【例【例5 5】计算计算s=2+4+6+8+10的值。的值。开始开始 S=0i=1i=5i=i+1是是否否结束结束s=s+2*i算法的执行流程算法的执行流程循环结构循环结构 【例【例6 6】求求s=1+2+3+n的值，其中的值，其中n由键盘输入。由键盘输入。n的值通过输入得到，在循环执行过程中是定值，用计数法控制循环。的值通过输入得到，在循环执行过程中是定值，用计数法控制循环。即即i=1,i=n,i=i+1。分清。分清n、i的作用。的作用。若求若求s=123n的值，其的值，其中中n由键盘输入。由键盘输入。