1.3-1.4算法与结构化程序设计

1.3问题求解与算法1.3.1问题求解1.3.2算法的概念与特点1.3.3算法优劣的标准1.3.4算法的描述上页下页节末页结束1.3.1问题求解问题：输入n,求1+2+…+n理解问题特征：“输入”n,“输出”1到n间所有正整数和设想解决方案：(1)输入n；初始化变量s为0,逐个将1到n的正整数累加到s中；输出s的值(2)输入n；根据等差数列求和公式计算n*(1+n)/2赋值给s；输出s的值优化解决方案:比较确定最优解决方案解决方案表示:图形化方法或自然语言描述编程实现解决方案:选择适合的语言与开发环境编程测试分析解决方案开始s←n*(1+n)/2输出s结束输入n开始输出s的值s←0,i←1s←s+ii←i+1FT结束i=n输入n上页下页节末页结束1.3.2算法及其特点算法:问题求解的具体步骤和方法特点：确定性可行性0或多个输入1或多个输出有穷性开始s←n*(1+n)/2输出s结束输入n开始输出s的值s←0,i←1s←s+ii←i+1FT结束i=n输入n上页下页节末页结束开始输出s的值s←0,i←1s←s+ii←i+1FT结束i=n输入n渐近时间复杂度指基本操作执行次数函数的关键项,反映算法运行所需时间随问题规模增长的增长率,如算法1基本操作执行次数函数为f(n)=3+2*n+1,时间复杂度T(n)=O(n);算法2中频度函数f(n)=3，时间复杂度为T(n)=O(1).关键看循环次数空间复杂度指所需存储空间函数的关键项,反映算法运行所需存储空间随问题规模增长的增长率，如算法1需3个变量i、s、n，f(n)=3,S(n)=O(1);算法2需2个变量n与s，f(n)=2,S(n)=O(1)，两者时间复杂度相同，均为常数阶1.3.3算法优劣标准◆正确性◆时间复杂度◆空间复杂度◆健壮性◆可读性开始s←n*(1+n)/2输出s结束输入n上页下页节末页结束1.3.4算法描述程序流程图N-S图(盒图)PAD图伪码判定表和判定树上页下页节末页结束程序流程图开始i←1score[i]=80输出score[i]i←i+1i50结束TFF常用符号：起止框控制流处理框选择框输入输出框注释框连接点等简单易懂,但箭头可随意转移控制流，导致复杂算法难以阅读和维护。改进:限制箭头的滥用，不允许流程的随意转向，为此提出了三种基本结构，他们各自只有一个入口和出口(比如不允许随意跳转到循环内)i计数器S累加器T开始输出s的值s←0,i←1s←s+ii←i+1FT结束i=n输入n上页下页节末页结束改进的流程图S1S2ab条件语句1语句2TF循环体F条件T条件TF循环体开始输出s的值0s,1is+isi+1iFT结束i=n输入n上页下页节末页结束N-S图(盒图)条件YNS1S2casei=？i1……ini1……inS1S2循环体当满足条件时循环体当条件满足上页下页节末页结束改进流程图与盒图举例：开始输出s的值s←0,i←1s←s+ii←i+1FT结束i=n输入ns=0i=1while(i=n)s←s+ii←i+1输出s的值输入n优点：使用Ｎ-Ｓ图设计出的算法必然是结构化算法，较流程图清晰直观易懂，容易表现嵌套关系和模块的层次结构缺点：当程序内嵌层数增多时，内层方框会越来越小，增加画图难度，影响清晰度上页下页节末页结束PAD图上页下页节末页结束PAD图举例s=0i=1while(i=n)s←s+ii←i+1输出s的值输入n输入ns=0i=1while(i=n)s←s+ii←i+1输出s的值开始输出s的值s←0,i←1s←s+ii←i+1FT结束i=n输入n相比NS图，PAD图是一个开放的结构，支持自顶向下、逐步求精的算法设计方法，已被ISO认可为算法图形描述的标准上页下页节末页结束伪码s=0i=1while(i=n)s←s+ii←i+1输出s的值输入n输入ns=0i=1while(i=n)s←s+ii←i+1输出s的值输入n;s0i1while(i=n){ss+iii+1}输出s#includestdio.hvoidmain(){scanf(“%d”,&n);s=0;i=1;while(i=n){s=s+ii=i+1}Printf(“%d”,s);}上页下页节末页结束判定表与判定树[自学]判定树(DecisionTree)是用来表示逻辑判断问题的一种图形工具。它用“树”来表达不同条件下的不同处理，比语言、表格的方式更为直观。判定树的左侧(称为树根)为加工名，中间是各种条件，所有的行动都列于最右侧判定表采用表格形式来表达逻辑判断问题，表格分成四个部分：左上角为条件说明；左下角为行动说明；右上角为各种条件的组合说明；右下角为各条件组合下相应的行动。。上页下页节末页结束回顾：理解计算机求解问题的步骤掌握算法的概念、特性及优劣指标，尤其注意渐近时间复杂度的概念和计算掌握算法的N-S图和PAD图表示,了解流程图和决策树、决策表作业：1.4(1)(3)(4)课下：务必预习第2章各节，周二实验用上页下页节末页结束上机常见问题说明：常见error:丢分号、括号和引号,标点或大小写错,变量未定义,缺头文件常见warning:变量使用前未赋初值,赋值类型不匹配,变量定义后未用常见运行错:越界访问(丢&)除0溢出常见逻辑错:算法错,尤其是特殊情况的处理,类型不匹配,格式控制符错常见连接错：工程(项目)模板选择错误，一个工程中有多个main函数说明1：输入输出整数时用格式控制符%d，单精度浮点数用%f，双精度浮点数%lf，且输入多个数据时，通过键盘输入时的分隔符要与两个%d或%f、%lf之间的分隔符一致.如语句scanf(“%f,%f”,&a,&b);printf(“%f\n”,a);输入时必须用英文状态下的逗号将两个数据分开，但对下句则必须用空格或Tab隔开scanf(“%f%f”,&a,&b);printf(“%f\n”,a);。注意scanf语句双引号内最好只有格式控制符，不要有汉字及\n说明2：判断相等与否用==，判断多个条件是否同时成立用&&，如不能用0x10，应用x0&&x10.再如if(x==0&&y!=0)printf(ok)说明3：花括号的使用，将多条语句看作一个整体if(...)while(...)do{{{...;...;...;...;...;...;}}}while(m%n!=0)else{...;}上页下页节末页结束上机实验：实验一实验报告填写说明实验名称：熟悉C语言的上机环境实验日期：2009.9.22正文：◆一、实验目的1.了解并初步掌握编写简单C程序的方法。2.熟悉C语言上机环境VisualC++6.0。3.初步了解C语言的调试工具。◆二、实验内容说明：加下划线者为需要写入实验报告的内容上页下页节末页结束1.打开VC6，观察其环境，记录下VC6的主要菜单及其功能，如：File、View、Build等。2.利用VC6创建一个工程，命名为FirstProject，然后在此工程中新建一个C源程序，命名为：FirstProg.c。记录操作步骤，之后输入如下程序：#includestdio.h/*Thisisademoprogram*/voidmain(){printf(“Iamverygladtoseeyou,myfirstprogram!\n”);}3.编译并运行这个程序，输出结果是什么？4.如下修改上面的程序，简述修改情况#includestdio.h/*Thisisademoprogram*/voidmain(){printf(“Iamverygladtoseeyou,myfirstprogram!\n”);printf(“Now,Itrytocomputethesumoftwonumbers,pleaseinputtwonumbers:”);scanf(“%d%d”,&a,&b);c=a+b;}5.编译这个程序，出现什么错误？把错误提示记录下来并加以解释。注意：这里的错误信息是英文的，所以大家一定要熟悉一些常见的错误提示，并会据错误信息修改源程序。上页下页节末页结束6.再次修改，简述修改情况#includestdio.h/*Thisisademoprogram*/voidmain(){inta,b,c;printf(“Iamverygladtoseeyou,myfirstprogram!\n”);printf(“Now,Itrytocomputethesumoftwonumbers,pleaseinputtwonumbers:”);scanf(“%d%d”,&a,&b);c=a+b;}7.编译它，还有错误么？回想一下，刚才的错误提示是什么含义？8.执行这个程序，输入两个数，注意用空格或者tab键隔开。屏幕上显示计算结果了吗？为什么？应该如何修改程序？9.再修改如下，简述修改情况：#includestdio.h/*Thisisademoprogram*/voidmain(){inta,b,c;printf(“Iamverygladtoseeyou,myfirstprogram!\n”);printf(“Now,Itrytocomputethesumoftwonumbers,pleaseinputtwonumbers:”);scanf(“%d%d”,&a,&b);c=a+b;printf(“%d\n”,c);}编译执行它，有结果显示吗？是什么？记录下来。上页下页节末页结束10.调试下面的程序，使其能够实现求阶乘的功能。注意记录调试和测试过程#includestdio.hintgetFactorial(intn)/*返回n的阶乘*/{inti;intresult;result=n;i==0;while(in){result=result*I;i=i+1;}returnresult;}voidmain(){printf(“inputanintegerplease:);scanf(%d,&n);printf(%ld,getFactorial(n));}提示1：C程序是由一个或多个函数组成的，每个函数完成一定的功能，且通常返回一定的处理结果，函数间可以相互调用。如上例中程序由两个函数组成，一个是main函数，该函数是程序执行的入口，函数的作用是输入一个整数n，之后调用getFactorial函数计算n的阶乘并输出计算结果；getFactorial函数用以求一个整数的阶乘，被调用执行时接受一个整数参数，并计算其阶乘，之后返回计算结果。提示2：赋值运算符是=，如i=1含义是为变量i赋值1；而==是用以判断左右两侧的值是否相等，如i==1用以判断i是否等于1上页下页节末页结束作业说明：补充：正负0、正负32767各种编码与2字节补码表示范围1.3：0.125-33×225或-110729625695×225或231876710401.4：两变量互换三变量排序求阶乘上页下页节末页结束两变量互换（答案略有问题）：说明：变量存储空间相当于盒子，定义变量即开辟存储空间问题1：通常每个语句单独占一个处理框问题2：通常要有输出,此处输入实际可略注意：PAD图右侧各框是分开的上页下页节末页结束三变量排序（答案略有问题）问题：Y/N统一用T/F;注意画法美观PAD图默认上T下F经典排序算法：选择法冒泡法…上页下页节末页结束求阶乘（与作业略有差别，此处求n！）p=1i=1while(i=n)p←p*ii←i+1输出p的值输入n输入np=1i=1while(i=n)p←p*ii←i+1输出p的值开始输出p的值p←1,i←1p←p*ii←i+1FT结束i=n输入n注:循环与分支区别；循环画法；当型/直到型上页下页节末页结束回顾：计算机解题的步骤算法的概念和特点算法的描述：流程图N-S图PAD图C程序的运行步骤与VC6.0的使用1.4程序设计与程序设计语言1.