大学计算机基础09

四川大学计算机基础教学中心2012年第9章程序设计基础程序设计概述程序设计的基本方法算法与数据结构大学计算机基础（第9章）29.1程序设计概述9.1.1程序设计概述9.1.2程序设计的方法与风格9.1.3结构化程序设计的原则9.1.4结构化程序设计的基本结构9.1.5程序设计的一般步骤大学计算机基础（第9章）31.程序为完成某一任务的若干条指令的有序集合。2.程序设计用程序设计语言来描述问题的求解过程（算法）,并对参与运算的数据进行合理地组织和安排。程序=算法+数据结构大学计算机基础（第9章）43.软件数据程序文档软件的主要组成部分和表现形式程序处理的对象对软件开发和维护过程的描述与记录软件=程序+数据+文档大学计算机基础（第9章）5程序设计风格1.源程序中的内部文档2.数据说明3.语句的结构4.输入和输出结构化程序设计方法的主要原则自顶向下、逐步细化三种基本结构每个结构只有一个入口和一个出口控制GOTO语句的使用大学计算机基础（第9章）6三种基本结构（顺序、分支、循环）的特点•只有一个入口•只有一个出口•每一个基本结构中的每一部分都有机会执行到,结构内不存在“死循环”。大学计算机基础（第9章）7程序设计的一般步骤需求分析算法设计编写代码调试运行大学计算机基础（第9章）8程序设计的一般步骤1.需求分析计算机解决问题的可行性研究。什么问题能否解决数学模型原始数据的组织输出的项目及格式软硬件环境质量保证及验收标准效益……做什么？大学计算机基础（第9章）9程序与软件•x和y只能是正整数的子集•最大公约数的定义：能整除x、y，且是最大的除数•采用“辗转相除法”•x和y的数值通过键盘录入•在屏幕上显示两数的最大公约数•个人计算机环境•一个人在短时间内即可完成【例】计算x和y两数的最大公约数。大学计算机基础（第9章）10程序与软件用算法表示工具描述求解问题的方法和步骤。步骤1:任意输入两个数，放入x和y中步骤2:求出x/y的余数放入r中步骤3:如果r=0，则执行步骤7,否则执行下一步步骤4:令x=y，y=r步骤5:计算x和y的余数放入r中步骤6:执行步骤3步骤7:y就是所求的结果,输出结果如何做？辗转相除法2.算法设计大学计算机基础（第9章）11程序与软件开始键盘输入x和y显示输出y结束x/y的余数→rr≠0y→xx/y的余数→rTFr→y流程图大学计算机基础（第9章）12程序与软件3.编码开始键盘输入x和y显示输出y结束x/y的余数→rr≠0y→xx/y的余数→rTFr→y#includestdio.hmain(){intx,y,r;scanf(“%d%d”,&x,&y);r=x%y;while(r!=0){x=y;y=r;r=x%y;}printf(“%d\n”,y);}大学计算机基础（第9章）13程序与软件4.程序调试为发现错误而执行程序的过程。输入输出大学计算机基础（第9章）14面向对象的程序设计方法面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统，提倡人们在现实生活中常用的自然思维来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。面向对象方法的主要优点：（1）与人类习惯的思维方法一致；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。软件的重用是指在不同的软件开发过程中重复使用相同或相似软件的过程。大学计算机基础（第9章）15【例】学生对象属性：学号、姓名、性别、籍贯、出生年月等行为：选修某几门课程、参加某项活动等属性值只能由这个对象的行为存取客观世界中的任何一个事物都可看成是对象。对象的行为（用操作表示）对象的属性（用数据表示）对象静态特征动态特征大学计算机基础（第9章）16类类是具有相同对象的集合，它为属于该类的全部对象提供了统一的抽象描述。动物马类白马黑马类是一个独立的程序单位（数据类型），其作用是定义对象。对象实例大学计算机基础（第9章）17封装将有关的数据和操作代码封装在一个对象中，使对象以外的部分不能随意存取对象的内部数据，从而尽可能地避免外部错误对它的“交叉感染”，使软件错误局部化，减少了查错和排错的难度。大学计算机基础（第9章）18继承继承是在已有的类基础上生成新类。这样可以重用已有软件中的一部分甚至大部分，大大节省了编程工作量。由继承而产生的相关的不同类，其对象对同一消息会作出不同的响应。这一特征能增加程序的灵活性。多态性大学计算机基础（第9章）19对象是属性和方法的封装体。属性:对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。方法或服务描述了对象执行功能的操作.操作是对象的动态属性。*：一个对象由对象名、属性和操作三部分组成。面向对象特征:封装性、继承性、多态性、分类性大学计算机基础（第9章）209.3算法9.3.1算法9.3.2算法的特征9.3.3算法设计的基本方法9.3.4算法的基本工具9.3.5简单算法介绍大学计算机基础（第9章）211.算法的概念解决问题的方法和步骤。有穷性确定性有零个或多个输入有输出有效性2.算法的特征大学计算机基础（第9章）22算法设计的基本方法•列举法•归纳法•递推法•递归•减半递推技术大学计算机基础（第9章）234.算法的表示传统流程图N—S图PAD图自然语言流程图伪代码算法大学计算机基础（第9章）24顺序结构N-S图传统流程图ABaABb执行A操作后，顺序的执行B操作。算法工具大学计算机基础（第9章）25选择结构TABFpN-S图（P157图5-12）ATpFbaB双分支TAFp单分支pATFba大学计算机基础（第9章）26循环结构当p成立A先执行后判断A直到p成立当型循环先判断后执行N-S图ApFTba直到型循环abpTFA大学计算机基础（第9章）27简单算法举例9.3.5算法简介【例1】对换a和b两变量中的值。c=a输入a，ba=bb=ca=a+b输入a，bb=a-ba=a-b计算机方法数学方法大学计算机基础（第9章）28算法【例2】求三个数a，b，c中的最大值。设4个变量：a,b,c,max输入a,b,ca→maxTFmax＜bb→max输出maxTFmax＜cc→max大学计算机基础（第9章）29算法【例3】采用累加算法，计算1＋2＋3＋…100。0→S1→NS+N→SN+1→NN≤100打印SN—加数（1、2···100），初值为1S—累加器，初值为0大学计算机基础（第9章）30算法【例4】采用累乘算法，计算5！。1→S，1→NS×N→SN+1→NN≤5打印SN—乘数（1、2···5），初值为1S—累乘器，初值为1大学计算机基础（第9章）31【例5】采用辗转相除法，求两数m和n的最大公约数。x/y的余数→rr→y输入x、y当r≠0输出最大公约数yx/y的余数→ry→x如果r≠0则y→xr→yx/y的余数→r1）计算余数r：x/y的余数→r2）当r＝0y为两数的最大公约数算法大学计算机基础（第9章）32课堂练习•用流程图或N_S盒图完成下列问题的算法描术？•1。求6！•2。求任意数的N！•3。求23•4。求2n大学计算机基础（第9章）33k=1,t=1当k=6t=t*kk=k+1输出t大学计算机基础（第9章）34k=1,t=1当k=nT=t*kK=k+1输出t输入n大学计算机基础（第9章）35k=1,t=1当k=3t=t*2k=k+1输出t大学计算机基础（第9章）36k=1,t=1当k=nT=t*2K=k+1输出t输入n大学计算机基础（第9章）370→Sk=1S+2*k→Sk+1→kk≤50打印SS=1+3+……..+99S=2+4+……..+100偶数:2*K奇数:2*K-12*k+10→Sk=1S+2*k-1→Sk+1→kk≤50打印S大学计算机基础（第9章）380→S,k=1输入NS+1/k→Sk+1→kk≤N打印SS=1+1/2+1/3+……..1/n大学计算机基础（第9章）390→S,k=1,h=1输入NS+h*(1/k)→Sk+1→kk≤N打印Sh=-hS=1-1/2+1/3-1/4……..1/n大学计算机基础（第9章）40k=1,t=1,s=0当k=nt=t*kk=k+1输出s输入ns=s+tS=1！+2！+3！+……..n!大学计算机基础（第9章）41k=1,t=1,s=0当k=nT=t*4K=k+1输出s输入ns=s+tS=41+42+43+……..+4n大学计算机基础（第9章）42计算公式的值。?99507453321k=1,s=0当k=50s=s+k/(2*k-1)k=k+1输出s大学计算机基础（第9章）43课堂练习的值。?246301335572931sk=1,s=0当k=15s=s+2*k/(2*k-1)*（2*k+1)*k=k+1输出s大学计算机基础（第9章）44从键盘上输入20个数,统计偶数的个数.结束是不是开始输入x输出结果i=20？i=1,k=0X是偶数？K=k+1i=i+1是不是大学计算机基础（第9章）45巩固练习1、请用流程图描述计算的算法。100999998989797964332211s2、统计1000以内奇数的个数。（要求采用循环结构）3、用流程图或N-S图表示求解下列问题的算法。要求：用循环完成求以上公式的值，在流程图或N-S图中，用变量S来存放公式的结果。23581321144123581389s4、s=a+aa+aaa+…….+a……..an大学计算机基础（第9章）46k=100,s=1当k1s=s+k*(k-1)k=k-1输出s100999998989797964332211s大学计算机基础（第9章）47k=1000,s=0当k0k=k-1输出s统计1000以内奇数的个数。（要求采用循环结构）K%2!=0Ys=s+1大学计算机基础（第9章）48S=0，a=2，b=0，c=0当a=144S=S+a/bc=a，a=a+b，b=c输出s23581321144123581389s大学计算机基础（第9章）49s=0，t=0,k=1当k=nt=t*10+as=s+tk=k+1输出s4、s=a+aa+aaa+…….+a……..an输入a,n大学计算机基础（第9章）52求Fibonacci数列：1,1,2,3,5,8,……的前20项。即第一、二项都是1，第三项以后的每一项都是前两项的和。大学计算机基础（第9章）53k=1,s=0，f1=1,f2=1当k=10输出f1,f2f1=f1+f2f2=f1+f2k=k+1大学计算机基础（第9章）54将1到100之间能用3或5整除的数打印出来。i赋初值为1i=100?i能被3或5整除？TF打印i用N-S图表示i++用流程图表示开始i赋初值为1i=100?i能被3或5整除？打印i结束NYYNi++巩固练习大学计算机基础（第9章）55如下算法能输出哪种图形？