算法与结构化程序设计

1、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的值 优化解决方案:比较确定最优解决方案 解决方案表示:图形化方法或自然语言描述 编程实现解决方案:选择适合的语言与开发环境编程 测试分析解决方案,1.3.2 算法及其特点,算法:问题求解的具体步骤和

2、方法 特点： 确定性 可行性 0或多个输入 1或多个输出 有穷性,渐近时间复杂度指基本操作执行次数函数的关键项,反映算法运行所需时间随问题规模增长的增长率,如算法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 算法优劣标准,正确性 时间

3、复杂度 空间复杂度 健壮性 可读性,1.3.4 算法描述,程序流程图 N-S图(盒图) PAD图 伪码 判定表和判定树,程序流程图,常用符号：起止框 控制流 处理框 选择框 输入输出框 注释框 连接点等 简单易懂,但箭头可随意转移控制流，导致复杂算法难以阅读和维护。 改进:限制箭头的滥用，不允许流程的随意转向，为此提出了三种基本结构，他们各自只有一个入口和出口(比如不允许随意跳转到循环内),i计数器 S累加器,T,改进的流程图,N-S图(盒图),改进流程图与盒图举例：,优点：使用-图设计出的算法必然是结构化算法，较流程图清晰直观易懂，容易表现嵌套关系和模块的层次结构 缺点：当程序内嵌层数增多时

4、，内层方框会越来越小，增加画图难度，影响清晰度,PAD图,PAD图举例,相比NS图，PAD图是一个开放的结构，支持自顶向下、逐步求精的算法设计方法，已被ISO认可为算法图形描述的标准,伪码,输入n; s 0 i 1 while(i=n) s s+i i i+1 输出s,#include void main() scanf(“%d”, ,判定表与判定树自学,判定树(Decision Tree)是用来表示逻辑判断问题的一种图形工具。它用“树”来表达不同条件下的不同处理，比语言、表格的方式更为直观。判定树的左侧(称为树根)为加工名，中间是各种条件，所有的行动都列于最右侧 判定表采用表格形式来表达逻辑

5、判断问题，表格分成四个部分：左上角为条件说明；左下角为行动说明；右上角为各种条件的组合说明；右下角为各条件组合下相应的行动。 。,回顾：,理解计算机求解问题的步骤 掌握算法的概念、特性及优劣指标，尤其注意渐近时间复杂度的概念和计算 掌握算法的N-S图和PAD图表示,了解流程图和决策树、决策表 作业：1.4(1)(3)(4) 课下：务必预习第2章各节，周二实验用,上机常见问题说明：,常见error:丢分号、括号和引号,标点或大小写错,变量未定义,缺头文件 常见warning:变量使用前未赋初值,赋值类型不匹配,变量定义后未用 常见运行错:越界访问(丢 ,上机实验：实验一实验报告填写说明,实验名称

6、：熟悉C语言的上机环境 实验日期：2009.9.22 正文： 一、实验目的 1. 了解并初步掌握编写简单C程序的方法。 2. 熟悉C语言上机环境Visual C+ 6.0。 3. 初步了解C语言的调试工具。 二、实验内容 说明：加下划线者为需要写入实验报告的内容,1. 打开VC6，观察其环境，记录下VC6的主要菜单及其功能，如：File、View、Build等。 2. 利用VC6创建一个工程，命名为FirstProject，然后在此工程中新建一个C源程序，命名为：FirstProg.c。记录操作步骤，之后输入如下程序： #include /*This is a demo program*/ v

7、oid main() printf(“I am very glad to see you, my first program!n”); 3. 编译并运行这个程序，输出结果是什么？ 4. 如下修改上面的程序，简述修改情况 #include /*This is a demo program*/ void main() printf(“I am very glad to see you, my first program!n”); printf(“Now, I try to compute the sum of two numbers, please input two numbers:”); sc

8、anf(“%d%d”, 5. 编译这个程序，出现什么错误？把错误提示记录下来并加以解释。注意：这里的错误信息是英文的，所以大家一定要熟悉一些常见的错误提示，并会据错误信息修改源程序。,6. 再次修改，简述修改情况 #include /*This is a demo program*/ void main() int a,b,c; printf(“I am very glad to see you, my first program!n”); printf(“Now, I try to compute the sum of two numbers, please input two number

9、s:”); scanf(“%d%d”, 编译执行它，有结果显示吗？是什么？记录下来。,10. 调试下面的程序，使其能够实现求阶乘的功能。注意记录调试和测试过程 #include int getFactorial(int n) /*返回n的阶乘*/ int i; int result; result = n; i=0; while(in) result=result*I; i=i+1; return result; void main() printf(“input an integer please:); scanf(%d, 提示1：C程序是由一个或多个函数组成的，每个函数完成一定的功能，且通

10、常返回一定的处理结果，函数间可以相互调用。如上例中程序由两个函数组成，一个是main函数，该函数是程序执行的入口，函数的作用是输入一个整数n，之后调用getFactorial函数计算n的阶乘并输出计算结果；getFactorial函数用以求一个整数的阶乘，被调用执行时接受一个整数参数，并计算其阶乘，之后返回计算结果。 提示2：赋值运算符是=，如i=1含义是为变量i赋值1 ；而=是用以判断左右两侧的值是否相等，如i=1用以判断i是否等于1,作业说明：,补充：正负0、正负32767各种编码与2字节补码表示范围 1.3：0.125 -33225或-1107296256 95225或231876710

11、40 1.4：两变量互换 三变量排序 求阶乘,两变量互换（答案略有问题）：,说明：变量存储空间相当于盒子，定义变量即开辟存储空间 问题1：通常每个语句单独占一个处理框 问题2：通常要有输出,此处输入实际可略 注意：PAD图右侧各框是分开的,三变量排序（答案略有问题）,问题：Y/N统一用T/F;注意画法美观 PAD图默认上T下F 经典排序算法：选择法 冒泡法,求阶乘（与作业略有差别，此处求n！）,注:循环与分支区别；循环画法；当型/直到型,回顾：,计算机解题的步骤 算法的概念和特点 算法的描述：流程图 N-S图 PAD图 C程序的运行步骤与VC6.0的使用,1.4 程序设计与程序设计语言,1.4

12、.1程序质量 1.4.2程序设计语言发展史 1.4.3 结构化程序设计方法,2-5 结构化程序设计方法,基本思路:本质是功能分解，从代表目标系统整体功能的单个处理着手，自顶向下不断把复杂的处理分解为子处理，这样一层一层的分解下去，直到仅剩下若干个容易实现的子处理功能为止。,自顶向下,逐步细化 模块化设计,结构化编程,用PAD图表示结构化设计过程：输入n，求1+n,输入n,P:计算1到n间正 整数的和,赋给s,输出s的值,i=1,s = s+i,i= i+1,P,def,s=0,用PAD图表示结构化设计过程-输入n，求n！,用PAD图表示结构化设计过程：输入n，求1!+2!+n!,s=0,输出s的值,while(k=n),k=1,P:计算k!赋给term,s = s+term,输入n,i=1,term=term*i,i= i+1,P,def,term=1,s=0,输出s的值,while(k=n),k=1,s= s+term,输入n,i=1,term=term*i,i= i+1,term=1