计算机程序设计与算法.ppt

第1章 计算机程序设计与算法 C/C+程序设计教程 主要内容有 l 程序设计语言 l 程序设计过程 l 程序设计算法 l 自然语言描述计算机算法 l 程序流程图描述计算机算法 l N-S图描述计算机算法 l 用程序设计语言描述计算机算法 1.1程序设计 学习程序设计并不是简单地学习计算机 语法规范或程序设计语言的本身，而是要学 会怎么用计算机程序设计语言解决实际问题 、提高工作效率和工作质量。计算机技术应 用领域博大而广泛，谁也不可能完全学会计 算机技术的方方面面，这是因为计算机涉及 到的领域太广了，计算机技术的发展日新月 异，即使学上很久我们也不可能完全学到头 ，可以说学无止境。 1.1.1程序设计语言 （1）科学计算语言。用于科学计算，基础是数学模型，过程描述的是数值 计算，如FORTRAN语言； （2）系统开发语言。用于编写编译程序、操作系统、数据库管理系统 DBMS等，如C语言； （3）实时处理语言。及时响应环境信息，可以根据外部信号对不同的程序 段进行并发控制执行；如汇编语言 （4）商用语言。主要用于商业处理、经济管理, 基础为自然语言模型；如 COBOL语言 （5）人工智能描述语言。模拟人的思维推理过程，实现智能化控制等； （6）模拟建模语言。用于模拟实现客观事物的发展与变化过程，以提前预 测未来发展的结果； （7）网络编程语言，在网络技术基础上进入深层次的应用研究与开发的语 言, 如Dephi适于网络化环境的编程，而JAVA是一种 新型跨平台分布式程 序设计语言，语义规范与C语言相同等等，不再列举。 1.1.2 程序设计过设计过 程 1.程序实现过程 程序设计是指我们使用一种计算机语言为实 现解决实际问题的算法去设计编写计算机程序的 过程。 计算机语言是人与计算机进行交流的媒介，通 过语言编写的程序，计算机就会准确地按程序步 骤执行操作，计算机解决实际问题的一般过程如 图1.1所示： 2. 程序设计的过程 程序设计大致包含以下几个步骤 (1) 分析问题 程序设计首先要进行对问题的分析，明白我们要作什么，确定要使用 的数学模型。 (2) 确定算法 确定算法即确定解决问题时要执行的一系列步骤。 (3) 算法描述 算法描述就是使用计算机语言对算法予以描述。 (4) 确定程序设计语言 由于不同的计算机程序设计语言有不同的特点，根据实际情况与需要 选定好程序设计语言后，就可以用该语言编程实现以算法。 (5) 调试和运行程序 1.2 程序设计算法 计算机程序可以这样表示 程序=算法+数据结构 其中 数据结构: 对数据的描述,包括对数据类型的描述核对数据组织形式描述定义. 算法: 对操作过程的描述, 即操作步骤的描述。 如果考虑现代编程的工程化与多样性，可以这样表示： 程序=数据结构+算法+（程序设计方法+编程工具+语言环境） 其中算法是关键，是实现程序设计的依据和基础，算法分析作的 完整，作的精细，才能有完整的程序设计，才可能对程序进行优化， 所以掌握算法至关重要。 1.3计算机算法的表示 1.3.1 自然语言描述 期末数学成绩高于90分，英语成 绩高于95分，有很好的团队协作精 神的同学，可以报名参加国际数学 建模比赛。 （有很多种理解） 1.3计算机算法的表示 1.3.2 程序流程图描述 顺序结构 条件判断分支结构 循环控制结构 图1.4 表示复杂的算法看似乱麻 1.3计算机算法的表示 1.3.3 N-S图描述 图1.6 N-S图表示三种基本结构 1.4 用程序设计语言描述 1.机器语言(Machine language) 例如，计算表达式 mn-z的值，并把结果值存到10010000 号内存单元。假设已知某计算机的取数操作码为1000，除法操作 码为1010，减法操作码为1001，传送操作码为0100，另外也知m 、n、z中的三个数已分别存放在11110110、10101101、01010110 号内存单元。用机器语言可描述编写如下程序： 1000 11110110 取出放在11110110内存单元的值 1010 10101101 除法操作放在10101101内存单元的值 1001 01010110 把结果值减去放在10101101内存单元的值 0100 10010000 把最后结果值存到10010000号内存单元 2.汇编语言(Assembler language) 例如计算表达式mn-z值的程序可以写成： LDA M DIV N SUB Z MOV Y 使用这种语言计算机CPU不能直接识别，必须 用事先存放在存储器中的“翻译程序”，把汇编 语言翻译成机器语言,计算机指令系统才能识别和 执行，这个翻译程序称为编译汇编程序, 翻译成机 器语言描述的程序叫目标程序。 3.高级语言(High-level language) 不管使用机器语言还是使用汇编语言描述算 法和编写程序，都没有摆脱计算机指令系统的束 缚。到了1954年，出现了一种与具体计算机指令 系统无关的语言，即高级语言。它与人们习惯使 用的自然语言与数学语言非常接近，例如： y=2x2-x+1 这样一个数学式子用高级语言来写，就写成 y=2*x*x-x+1 基本上是原样表达，这样描述程序算法显然就 得心应手的多。 高级语言的解释过程如图1.10所示。 高级语言的编译过程如图1.11所示。 1.5 算法举例 算法步骤分析： S1: 累加器变量sum 赋初值0 ，即sum=0 S2: 计数器变量i 赋初值1 ，即i=1 S3: 使累加器变量值sum加计数器变量值i, 结果仍放在sum中, 即sum=sum+i, 此时sum值为 sum=sum+i=0+1=1 S4: 使计数器变量i加1,结果仍放在i中, 即 i=i+1, 此时i值为 i=i+1=1+1=2 S5: 使累加器变量值sum加计数器变量值i,结果仍放在sum中, 即sum=sum+i, 此时sum值为 sum=sum+i=1+2=3 S6: 使i加1,结果仍放在i中, 即i=i+1, 此时i值为 i=i+1=2+1=3 S7: 使sum加i,结果仍放在sum中, 可表示为sum=sum+i, 此时sum值为 sum=sum+i=3+3=6 S8: 使i加1,结果仍放在i中, 可表示为i=i+1, 此时i值为 i=i+1=3+1=4 S9: 使sum加i,结果仍放在sum中., 可表示为sum=sum+i, 此时sum值为 sum=sum+i=6+4=10 程序流程图如图1.12所示，N-S图如图1.13 所示。 图1.12 累加运算程序流程图 图1.13 累加运算N-S图 开 始 sum=0 i=0 sum=sum+i i=i+1 i=100 打 印 N Y C语言程序算法如下： main() int i=1,sum=0; /*定义变量及其数据类型*/ while(i=100) /*循环控制结构*/ sum+=i; i=i+1; /*循环体结束*/ printf(“sum=%dn“,sum); /*输出累加结果*/ 程序算法不是唯一的，这个问题还有其它的算法 算法1： main() float sum=0; int i=1; loop: if (i=100) sum=sum+i ; i=i+1; goto loop; printf(“n%f“,sum); 算法2： main() float sum=0; int i=1; while (i=100) sum=sum+i ; i+; printf(“n%f“,sum); 算法3： main() int i=1,sum=0; do sum=sum+i; i=i+1; while(i=100); printf(“the sum is %d“,sum); 以此类推 可以很容易表示出计算 之和的算法，当分母大于100时程序结束， 输出计算结果。程序算法如下。 算法3的N-S图如图1.14所示。 图1.14累加运算N-S图 本章是计算机程序设计的基础，介绍了计算 机程序设计语言的应用特点和发展演变，特别介 绍了程序设计过程以及程序设计算法，学要重点 理解和掌握的是计算机算法的表示方法，列举了 用自然语言描述结局问题过程的特点与不足。作 为一个程序设计人员，应该熟悉并掌握比较常用 的程序流程图描述方法，以及N-S图描述算法的基 本技能，最终需要使用计算机语言，即程序设计 语言描述并实现。本章通过算法举例以训练引导 读者用计算机的思维表达解决问题的过程，以最 终实现算法，这就是程序设计算法的根本。 本章小结 1.6