计算机基础06设计基础3学时.ppt

《计算机基础06设计基础3学时.ppt》由会员分享，可在线阅读，更多相关《计算机基础06设计基础3学时.ppt（105页珍藏版）》请在装配图网上搜索。

1、1,大学计算机基础,第一章 计算机与计算思维 第二章 数字计算基础 第三章 计算原理与计算机硬件系统 第四章 问题求解与软件系统 第五章 多媒体技术基础 第六章 程序设计基础 第七章信息管理与数据库 第八章计算机网络基础知识 第九章计算机安全,大学计算机基础,相传古代印度布拉玛神庙中有一个僧人，他每天不分白天黑夜，不停地移动那些圆盘，据说，当所有64个圆盘全部从一根杆上移到另一根杆上的那一天就是世界的末日。故汉诺塔问题又被称为“世界末日问题”。 玩汉诺塔游戏 看视频：,第六章 程序设计基础,可执行的程序,int i=0; /* 移动圆盘数量计数器 */ main( ) unsigned n;

2、scanf (%d, 看程序演示,几个问题：,如何使问题变成程序? 程序和软件有何不同? 什么是好 程序?,第六章 程序设计基础,用计算机解题,6.1 程序与程序语言 6.2 算法与算法设计 6.3 程序设计风格,第六章 程序设计基础,计算机软件与程序 程序设计语言 程序设计全过程,第五模块 计算机程序设计基础 第一节 程序与程序语言 1.程序 2.程序设计与程序设计语言 3.程序设计语言的发展史及其分类 第二节 算法与算法设计 1.算法基本特征 2.算法表示 3.算法设计 第三节 结构化程序设计 第四节 基本算法,一、计算机软件与程序,10 R=5 20 L=2*3.14*R 30 S=3.

3、14*R*R 40 PRINT R,L,S 50 END,软件,程序,语言,语言规则,计算机语言是 编写程序、制 作软件的工具,6.1 程序与程序语言,6.1 程序与程序语言,二、程序设计语言,面向过程语言 面向对象语言,FORTRAN BASIC C PASCAL COBOL LISP,C+ C# Visual C+ Visual BASIC Visual J+,程序设计语言是规则和符号的集合,用于编写计算机程序的语言，包含语法、语义和语用三个方面。 程序设计语言的基本成分有： 数据成分，用于描述程序所涉及的数据； 运算成分，用以描述程序中所包含的运算； 控制成分，用以描述程序中所包含的控制

4、； 传输成分，用以表达程序中数据的传输,6.1 程序与程序语言,6.1 程序与程序语言,计算机语言：是规则和符号的集合，是与计算机交流的工具 程序：求解问题的指令序列 软件：程序的集合,学习语言 设计程序 制作软件,概念：,00000000 10111000 00000000 00100101 00000000 00000101 00000000 01010100,A = 37 + 84,第一代：机器语言 二进制机器指令，机器能直接执行。,送数到AX寄存器 被加数 37 加法 加数 84,程序设计语言的发展,6.1 程序与程序语言,MOV AX，37 送数37到AX寄存器 ADD AX，84

5、AX寄存器内容+84送到寄存器AX,第二代：汇编语言 用符号代替机器语言，需要翻译。,6.1 程序与程序语言,A=37+84,第三代：高级语言 英语和数学语言代替机器语言，需要翻译。,A=37+84,第三代：高级语言 英语和数学语言代替机器语言，需要翻译。,6.1 程序与程序语言,计算机语言分类,BASIC 语言 为初级编程者设计，1964年问世。大多数版本是解释执行，易学易用。如GWBASIC、QBASIC、Visual Basic等。其中Visual Basic功能强大。,面向过程语言 面向过程程序设计需要明确规定每个操作步骤和细节。,6.1 程序与程序语言,FORTRAN 语言 适合于数

6、值计算，早期版本主要考虑高精度数字计算，不太关注对计算结果的表达形式。新的FORTRAN版本增强了字符处理和图形功能。,Pascal 语言 其简洁明了结构化，具有丰富的数据结构和控制结构，为程序员提供了极大的方便性与灵活性，同时它特别适合微计算机系统。,第五模块 计算机程序设计基础,第一节 概述,6.1 程序与程序语言,COBOL 语言 通用商务对象处理语言，美国海军上将Grace Hopper于上世纪60年代设计，主要用于开发大型商务程序， COBOL程序通常很长，但可读性好，便于调试和维护。,LISP 语言 开发于1960年，一般用于人工智能专家系统的开发，擅长对字符数据进行复杂的逻辑处理

7、。,第五模块 计算机程序设计基础,第一节 概述,6.1 程序与程序语言,C语言 1970年美国Bell实验室的KThompson发明B语言，用于开发UNIX操作系统。1972年，他的同事DRitchie改进B语言，使之不仅适用于系统软件的开发，也与其他高级语言一样适宜开发应用软件，命名为C语言。 其主要特点是能进行系统软件的开发，可以直接寻址，故被称为高级汇编语言，开发的程序具有较高的效率。,第五模块 计算机程序设计基础,第一节 概述,6.1 程序与程序语言,面向对象语言 面向过程的程序中，数据与对数据的加工是分离的，与现实世界事物的特性不符。 面向对象技术直接描述客观世界的对象及其相互关系。

8、对象是封装了数据和操作的程序块。面向对象程序设计就是设计对象（数据和操作）和安排对象完成所需任务，同一对象可以用在不同的程序中。,第五模块 计算机程序设计基础,第一节 概述,6.1 程序与程序语言,Simula 67被认为是最早的面向对象程序设计语言，它引入了所有后来面向对象程序设计语言所遵循的基础概念：对象、类、继承。 C+ JAVA C+ Visual BASIC （可视化） Visual J+ Visual FoxPro,第五模块 计算机程序设计基础,第一节 概述,6.1 程序与程序语言,6.1 程序与程序语言,三、程序设计全过程,分析问题，建立数学模型 确定数据结构 确定算法，描述算法

9、 编制程序，调试程序 运行结果,6.1 程序与程序语言,1. 程序设计过程：,语言 处理系统,程序实例：,#include graphics.h #include bios.h #include “stdio.h“ /* 预处理 */ main( ) /* 函数体 函数名 */ int n,x=100,y=100,k=1,m=1,driver,mode; long i; /* 定义变量 */ detectgraph( ,6.1 程序与程序语言,计算机执行的指令,6.1 程序与程序语言,高级语言的源程序,目标程序 (机器语言),机器语言的可执行指令,其他程序 (机器语言),6.1 程序与程序语言

10、,2.程序的开发过程,6.1 程序与程序语言,6.1 程序与程序语言,计算机的别名：数据处理机 数据元素：数据的最小单位 数据结构：数据元素的组织形式,程序设计数据结构算法方法工具,数据结构的优劣决定了 软件或程序的复杂程度和面貌,一个程序应包括两个方面的内容:,对数据的描述：数据结构 对操作的描述：算法,完整的程序设计应该是:,3. 程序语言的基本构成,字符集,变量、常量,运算符、运算规则,流程控制,程序结构,6.1 程序与程序语言,数 字：0 1 2 3 4 5 6 7 8 9 字 母：a b c z A B C Z 运算符：+ - * / % = = != = 特殊符号：_(下划线) 回

11、车(r) 换行(n) 制表符(t) 其它转义字符,6.1 程序与程序语言,字符集,6.1 程序与程序语言,数据描述,算术运算符 2. 关系运算符 3. 逻辑运算符 4. 位运算符 5. 赋值与赋值组合运算符 6. 自增自减运算符 7.其它运算符,6.1 程序与程序语言,运算,switch (表达式) case 常量1: 语句序列1 case 常量2: 语句序列2 default: 语句序列n+1 ,if(表达式) 语句1； else 语句2；,while 语句 for 语句 do - while 语句 break 语句 continue 语句 goto 语句,6.1 程序与程序语言,流程,6.

12、1 程序与程序语言 6.2 算法与算法设计 6.3 程序设计风格,第六章 程序设计基础,算法基本特征 算法表示 算法设计,一、什么是算法,算法是为解决问题而采取的方法和步骤。,决定了算法的执行顺序,算术运算、逻辑运算、比较运算和数据传送,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,举例：插入排序法问题，有一个从小到大的数值序列，将一个新数插入到序列中。,24,？,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,12,19,26,37,48,5,9,24,24,举例：插入排序法问题，有一个从小到大的数值序列，将一个新数插入到序列中。,24,24,24,

13、24,24,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,算法： 开始 i=1 新数与序列第i个元素比较 如果（新数比第i个元素大） i 加 1 如果（i大于m）执行步骤 否则 执行步骤 否则 执行步骤 从第i到第m个元素后移一个位置 将新数置于序列第i个位置 结束,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,二、算法的基本特征,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,算法设计的原则,1、正确性：对于一切合法的输入数据都能得出满足要求的结果。,2、可读性：算法应该易理解，便于交流,3、健壮性：当输入非法数据时，算法应恰当

14、地作出反应或进行相应处理。,4、高效率与低存储量需求：算法执行时间较少，算法执行所需存储空间较小。,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,三、算法的表示,流程图 N-S流程图 伪代码 PAD码,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,1. 流程图,用规定的一系列图形、流程线和文字说明算法中的基本操作和控制流程。 流程图的基本元素包括： 表示相应操作的框； 带箭头的流程线； 框内外必要的文字说明。,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,（1）图形符号,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与

15、算法设计,（2）用流程图表示算法,例：求给定半径R的圆面积和圆周长。,这是一个数学问题。 算法： 圆面积 S=* R2 圆周长 L=2*R 这是顺序程序结构。,顺序,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,例：求给定数R的绝对值。,选择,这是分支程序结构,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,T里保存： 1+2+3+K的连加和。 重复进行某种运算，运算对象有规律地变化。采用循环结构。,例: 给定K值，求1到 K连加和。 T=1+2+3+K。 1 I 0 T T+I T(I=1,2,3,K),循环,6.2 算法与算法设计,2. NS图,由

16、于流程图中的流程线可以任意转向，所以传统流程图无法保证程序的结构化，造成了程序设计中的一系列问题。 两位美国学者Nassi 和Shneiderman于1973年提出了表示程序结构的N-S图。,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,（1）图形符号,第五模块 计算机程序设计基础,第二节 算法,顺序结构,6.2 算法与算法设计,第五模块 计算机程序设计基础,第二节 算法,选择结构,6.2 算法与算法设计,第五模块 计算机程序设计基础,第二节 算法,循环结构:while循环,6.2 算法与算法设计,第五模块 计算机程序设计基础,第二节 算法,循环结构:do-while循环

17、,6.2 算法与算法设计,（2）用N-S流程图表示算法,例：求给定半径R的圆面积和圆周长。,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,选择,例：求给定数R的绝对值。,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,例: 给定K值，求T=1+2+3+K。,循环,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,3.伪代码,伪代码是描述算法常用的工具之一； 类似英语的表示形式； 部分英语和部分结构化代码的组合。,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,伪代码描述算法的一般组成：,算法头：算法的名字。 目的、

18、条件和返回值： 目的： 有关算法要做什么的简短说明 前置条件：列出算法所有前驱条件 后置条件：指出算法产生的影响 返回值： 算法返回的结果或无返回值 语句序号：表示语句之间的附属关系。,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,例：用伪代码描述在一数列中找最小值的算法。,Algorithm （算法）：Finding Smallest Purpose（目的）：在一数列中找最小值 Pre（前置条件）：List of numbers（数列） Post（后置条件）：None Return（返回值）：The smallest,3,2,4,1,6,a:,S,3,2,1,算法：设数

19、列中第一个数为最小值S，然后用后续数依次与S比较，若比S小，则用该数替换原S的值，全部比较完成后S即最小值。,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,1.Set smallest to the first number 2.Loop(not end of list) 2.1 if(next number smallest) 2.2.1 set smallest to next number 2.2 end if 3.end loop 4.return smallest End Finding Smallest,第五模块 计算机程序设计基础,第二节 算法,6.2 算法

20、与算法设计,1. 数列ai ( i=1,5 ) 2. a1 S, 2 i 3. while( i5 ) 3.1 if( aiS ) then ai S endif 3.2 i+1 i end while 4. return S,伪代码不一定按上述严格的格式，且可以使用汉字，只要把算法表达清楚即可。,第五模块 计算机程序设计基础,第二节 算法,6.2 算法与算法设计,好程序标准：可读性好、可靠性好、可维护性 程序设计=算法+数据结构+程序设计方法+语言工具 结构化程序设计方法主要包括： 1.采用三种基本结构编制程序( 结构化程序 )； 2.采用模块化结构 (自顶向下，逐步求精)； 3.尽量不使用

21、无条件转向语句。 4.控制结构只有一个入口和一个出口，控制结构之间接口简单，逻辑清晰。 5.采用结构化程序设计语言编程，注意程序设计风格,一、结构化程序设计方法,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.3 程序设计风格,6.2 算法与算法设计,求: ax2+bx+c=0 的根,二、自顶向下，逐步求精的设计方法,求解的问题可以分成三个小问题（模块）： 模块M1（输入原始数据）； 模块M2（求根）； 模块M3（输出结果）。,1、从顶层考虑模块划分,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.3 程序设计风格,6.2 算法与算法设计,2.模块细化,M1模块、M3模块较

22、简单不必细化； M2模块求根，当a=0时，求解一元一次方程，a0时求解一元二次方程。 故M2再细化为M21和M22模块。,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,M2模块细化,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,3.模块集成,a=0,Y,N,X1=-c/b,输出结果,开始,输入数据,结束,M1,M2,M3,d=b2-4ac,d=0,x2=sqrt(d)/(2a),x2=sqrt(-d)/(2a),x1=-b/(2a),Y,N,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,Bohm和J

23、acopini证明：任何算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合来实现。,三、三种基本结构,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,选择结构,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,循环结构,三种基本结构的特点： 一个入口，一个出口，不出现死循环和死语句,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,死循环,死语句,第五模块 计算机程序设计基础,第三节 结构化程序设计,例如：,6.2 算法与算法设计,用顺序结构描述将华氏温度F转换成摄氏温度C的流程。 算法： C=5/9

24、*（F-32）。,1、顺序结构设计,顺序结构中，按语句的自然顺序依次执行。,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,已知三角形的3条边边长，求三角形面积。用顺序结构描述求三角形面积的流程。,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,用顺序结构描述两个值（a=1, b=2）交换的流程。,1,2,b,a,1,2,1,c,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,选择结构，又称为分支结构。根据选择结构中判断的结果，选择执行相应的语句。,2、选择结构及其程序设计,用选择结构描述求两个数中的最大

25、值的流程,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,用选择结构描述检查某年是否闰年的流程。 N年为闰年满足下列条件之一： 1.N能被400整除 2.N能被4整除，但不能被100整除,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,循环结构，当循环控制条件为真时反复执行循环体中的语句，直到循环控制条件为假时为止。,累加器,计数器,用循环结构描述求10个学生成绩之和的流程。,3、循环结构及其程序设计,用T累计10个学生的成绩（K），用I记录累加的次数（I=1，2，10）,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2

26、算法与算法设计,用循环结构描述求10到100之间所有不能被3整除的整数的流程,对10到100之间所有数逐一验证，凡满足“不能被3整除”的整数即可输出。,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,从键盘输入n值，输出n行用*号组成等腰三角形。 例：输入 n=4，输出的图形如下： * * * * * * * * * * * * * * * *,* k=1,n-1=3个空，2*1-1=1个* * * * k=2,n-2=2个空，2*2-1=3个* * * * * * k=3,n-3=1个空，2*3-1=5个* * * * * * * * k=4,n-4=0个空，2

27、*4-1=7个*,共n行，其中第K行由n-k个空格和2k-1个*组成, ,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,分析： 1、输出 n 行。 2、图形的第 k 行(1=k=n)由 n-k个空格和 2k-1个 * 组成。 算法设计： 1.输入 n; 2.外层循环n行。 内层循环，每行先输出n-k个空格 再输出2k-1个* 换行 内层循环结束 外层循环结束,第五模块 计算机程序设计基础,第三节 结构化程序设计,6.2 算法与算法设计,6.2 算法与算法设计,基本思想 首先根据问题的部分条件预估计出答案的范围 在预估计的答案范围内，对所有可能的情况逐一验证。 若

28、某个情况使验证符合题目的全部条件，则该情况是本题目的一个答案。,一、穷举法,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,分析： 假设a、b分别代表父亲和儿子的年龄，x年后a=2b。根据人的寿命，x取值为：1,2,150,问题：今年父亲30岁、儿子6岁，在父亲有生之年中，多少年后父亲的年龄是儿子的2倍？,算法： 1. 考察x可能的范围：x=1，2，150； 2. 30+xa, 6+xb 3. 若a=2b，则输出x。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,X年后，父亲和儿子的年龄,第五模块 计算机程序设计基础,第四节 基本算法,6.2

29、算法与算法设计,例：抓交通肇事犯 一辆卡车违犯交通规则，撞人后逃跑。现场有三人目击事件，但都没有记住车号，只记下车号的一些特征: 甲说：牌照的前两位数字是相同的； 乙说：牌照的后两位数字是相同的，但与前两位不同； 丙是位数学家，说：四位的车号刚好是一个整数的平方。 请根据以上线索求出车号。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,问题分析与算法设计： 按照题目的要求造出一个前两位数(i)相同、后两位数(j)相同且相互间又不同的整数。 得到： （1）0 =31） 使用穷举法,尝试i、j的所有可能。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法

30、设计,循环I取值从1到9 循环J取值从0到9 如果I不等于J 求车牌后四位： I*1000+I*100+J*10+J 如果后四位开方是整数 输出后四位 结束 结束 循环J结束 循环I结束,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,二、迭代法,迭代法是用计算机解决问题的一种基本方法,对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。 迭代法是用于求方程或方程组近似根的一种常用的算法。,第五模块 计算机程序设计基础,第四节 基本算法,6.2

31、算法与算法设计,利用迭代算法解决问题，需要做好以下三个方面的工作： 一、确定迭代变量 迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 二、建立迭代关系式 从变量的前一个值推出其下一个值的公式。 三、对迭代过程进行控制 迭代过程的控制分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来;另一种是所需的迭代次数无法确定, 需要确定结束迭代过程的条件。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,a,b,x1=(a+)/2,x2,x*,x3,x,用二分法方程的根,第五模块 计算机程序设计基础,第四节 基本算法,6.

32、2 算法与算法设计,例1 用二分法求 x3+4x-10=0 在(1,2)内的根，要求绝对误差不超过0.005。 解： f(1)=-50 -(1,2)+ x1 =1.5 f(1.25)0 (1.25,1.375) x3 =1.375 f(1.313)0 (1.360,1.368) x71.368 x8 =1.364,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计, 输入区间初值:a、b 如果f(a)*f(b)0，则执行 循环 求中点:（a+b)/2 y 如果f(y)*f(a)0, 则y a 如果f(y)*f(b)0， 则y b 如果|a-b|0.005,执行 循环结束 输

33、出y,6.2 算法与算法设计,三、递推法,由初始的已知条件，先计算出第(N1)步的结果，再利用前面已知的(N1)项结果，按照递推公式（或遵照递推规则），推出第N步结果。 递推法是程序设计中最常用的方法之一，使用递推法必须有明确的递推初始值和递推公式。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,例：求菲波那奇数列第N项的值。 数列递推通项公式为： 1 2 n n-1 n-2（n=3） 即：1、1、2、3、5、8、13、21、 根据递推通项公式，可用递推法编写程序，计算第N项的值。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,输入N,1 U

34、1，1 U2,3 I,U1 + U2 U U2 U1 U U2 I+1 I,输出U,N 2,I = N,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,递推算法求10的阶乘。 求解过程：0！= 1 1！= 1*0！ 2！= 2*1！= 2 3！= 3*2！= 6 4！= 4*3！ = 24 5！= 5*4! = 120 6！= 6*5! = 720 7！= 7*6! = 5040 8！= 8*7! = 40320 9！= 9*8! = 367880 10！= 10*9! = 3628800,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,四、递归

35、法,为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题； 再从这些更小问题的解构造出规模较大问题的解。 特别地，当规模N=1时，能直接得解。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,1.递归调用时程序的执行过程。 2.为什么要用递归？ 对一些问题本身蕴涵了递归关系且结构复杂，用非递归算法实现可能使程序结构非常复杂，而用递归算法实现，可使程序简洁，提高程序的可读性。 3.递归调用会增加存储空间和执行时间上的开销。 4.所有的递归问题一定可以用非递归

36、算法实现。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,10的阶乘的递归过程： 10！= 10 * 9！ 9！= 9 * 8！ 8！= 8 * 7！ 7！= 7 * 6！ 6！= 6 * 5！ 5！= 5 * 4！ 4！= 4 * 3！ 3！= 3 * 2！ 2！= 2 * 1！ 1！= 1 * 0！ 0！= 1,1 = 1,1 = 2,2 = 6,6 = 24,24 = 120,120 = 720,720 = 5040,5040 = 40320,40320 = 362880,362880 = 3628800,递推算法求解过程： 1！= 1 2！= 1*2 = 2

37、3！= 2*3 = 6 4！= 6*4 = 24 5！= 24*5 = 120 6！= 120*6 = 720 7！= 720*7 = 5040 8！= 5040*8 = 40320 9！= 40320*9 = 362880 10！= 362880*10 = 3628800,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,例:汉诺塔问题 汉诺塔（Hanoi）问题是一个著名的问题，其来源据说是在约19世纪末欧洲的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔，游戏的目的是将最左边杆上的圆盘，借助最右边的杆，全部移到

38、中间的杆上，条件是一次仅能移动一个盘，且不允许大盘放在小盘的上面。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,18,446,744,073,709,551,615次,1844亿亿次。每次1微秒，需要60万年,64 片,初始杆,中间杆,目的杆,1 n, ., .,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,18,446,744,073,709,551,615次,1844亿亿次。每次1微秒，需要60万年,先考虑二片的情况：,初始杆,中间杆,目的杆,移动方法： 1. 将上面小片移到中间杆上。 2. 将下面的大片由初始杆移到目的杆上。 3. 将

39、中间杆上的小片移到目的杆上。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计,初始杆,中间杆,目的杆,以移动二片的思路，考虑 N 片的情况：,移动方法： 1. 将上面（N-1）片移到中间杆上。 2. 将下面的第 N 片由A杆移到目的杆上。 3. 将中间杆上的（N-1）片移到目的杆上。,第五模块 计算机程序设计基础,第四节 基本算法,6.2 算法与算法设计, 开始 将绿柱上的N片利用蓝柱搬到红柱 如果N1 将绿柱上的N-1片利用红柱搬到蓝柱 将绿上的最后1片搬到红柱 将蓝柱上的N-1片利用绿柱搬到红柱 否则 将绿柱上的最后1片搬到红柱 结束, 开始 将 ？柱上的N片利用

40、？柱搬到 ？柱 如果N1 将 ？柱上的N-1片利用 ？柱搬到 ？柱 将 ？上的最后1片搬到 ？柱 将 ？柱上的N-1片利用 ？柱搬到？柱 否则 将 ？柱上的最后1片搬到 ？柱 结束,N-1片移动方法,6.1 程序与程序语言 6.2 算法与算法设计 6.3 程序设计风格,第六章 程序设计基础, 源程序文档化 有意义的符号名：FindRoot、JSJKeXue、 写好注释：序言性注释、注解性注释 采用缩进格式 数据说明标准化 数据说明的顺序 同类数据排序 对重要数据进行注释,四、编程风格,源程序文档化 数据说明标准化 语句规范化 输入输出格式化,6.3 程序设计风格, 语句规范化 编程思路不要追求技巧，要直截了当 避免使用临时变量 尽量使用库函数、公共函数 使用括号避免二义性 对不好的程序要重新写，避免反复修改 输入输出格式化 输入格式要简单、自由 对输入数据要进行检验 对输入数据给出必要的提示 输入风格要一致 输出数据要进行注释。,6.3 程序设计风格,