算法与结构化程序设计

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输入n1.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结束输入n1.3.4算法描述程序流程图N-S图(盒图)PAD图伪码判定表和判定树程序流程图开始i←1score[i]>=80输出score[i]i←i+1i>50结束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,1is+isi+1iFT结束i<=n输入nN-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

0i1while(i<=n){s

s+ii

i+1}

输出s#include<stdio.h>voidmain(){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：判断相等与否用==，判断多个条件是否同时成立用&&，如不能用0<x<10，应用x>0&&x<10.再如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语言的调试工具。二、实验内容说明：加下划线者为需要写入实验报告的内容10.调试下面的程序，使其能够实现求阶乘的功能。注意记录调试和测试过程#include<stdio.h>intgetFactorial(intn)/*返回n的阶乘*/{inti;intresult;result=n;i==0;while(i<n){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或231876710401.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.4.1程序质量1.4.2程序设计语言发展史1.4.3结构化程序设计方法§2-5结构化程序设计方法基本思路:本质是功能分解，从代表目标系统整体功能的单个处理着手，自顶向下不断把复杂的处理分解为子处理，这样一层一层的分解下去，直到仅剩下若干个容易实现的子处理功能为止。输入3个数给a/b/c求a/b/c中最大者给max输出maxmax=amax<bYNmax=bmax<cmax=cYNmax=amax<bYNmax=bmax<cmax=cYN输入a/b/c输出max自顶向下,逐步细化模块化设计,结构化编程用PAD图表示结构化设计过程：输入n，求1+…+n输入nP:计算1到n间正整数的和,赋给s输出s的值输入ns=0i=1while(i<=n)s=s+ii=i+1输出s的值i=1while(i<=n)s=s+ii=i+1Pdefs=0用PAD图表示结构化设计过程--输入n，求n！输入nP:计算1到