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

1 大学计算机基础大学计算机基础 第一章 计算机与计算思维 第二章 数字计算基础 第三章 计算原理与计算机硬件系统 第四章 问题求解与软件系统 第五章 多媒体技术基础 第六章 程序设计基础 第七章信息管理与数据库 第八章计算机网络基础知识 第九章计算机安全 大学计算机基础大学计算机基础 相传古代印度布拉玛神庙中有一个僧 人，他每天不分白天黑夜，不停地移 动那些圆盘，据说，当所有64个圆盘 全部从一根杆上移到另一根杆上的那 一天就是世界的末日。故汉诺塔问题 又被称为“世界末日问题”。 玩汉诺塔游戏 /flash/293_1.htm 看视频： /v_show/id_XMjU0MzU0ND Q0.html 第六章 程序设计基础 可执行的程序 int i=0; /* 移动圆盘数量计数器 */ main( ) unsigned n; scanf (“%d“, movedisc ( n,a,b,c); /* 将A上的N个圆盘借助C将移动到B上 */ printf( “t Total: %dn“, i ); movedisc ( n, fromneedle, toneedle, usingneedle ) unsigned n; char fromneedle, toneedle, usingneedle; if ( n = 1 ) printf(“%2d-(%2d): %c = %cn“, +i, n, fromneedle, toneedle); else movedisc ( n-1, fromneedle, usingneedle, toneedle ); printf(“%2d-(%2d): %c = %cn“, +i, n, fromneedle, toneedle); movedisc ( n-1, usingneedle, toneedle, fromneedle ); 看程序演示 几个问题： 如何使问题变成程序? 程序和软件有何不同? 什么是好 程序? 第六章 程序设计基础 用计算机解题 程序程序 题 工具 6.1 程序与程序语言 6.2 算法与算法设计 6.3 程序设计风格 第六章 程序设计基础 计计算机软软件与程序 程序设计语设计语 言 程序设计设计 全过过程 第五模块第五模块 计算机程序设计基础计算机程序设计基础 第一节第一节 程序与程序语言程序与程序语言 1.1.程序程序 2.2.程序设计与程序设计语言程序设计与程序设计语言 3.3.程序设计语言的发展史及其分类程序设计语言的发展史及其分类 第二节第二节 算法与算法设计算法与算法设计 1.1.算法基本特征算法基本特征 2.2.算法表示算法表示 3.3.算法设计算法设计 第三节第三节 结构化程序设计结构化程序设计 第四节第四节 基本算法基本算法 一、计计算机软软件与程序 10 R=5 20 L=2*3.14*R 30 S=3.14*R*R 40 PRINT R,L,S 50 END 计算机语言是 编写程序、制 作软件的工具 6.1 程序与程序语言 6.1 程序与程序语言 二、程序设计语言 l面向过程语言 l面向对象语言 FORTRAN BASIC C PASCAL COBOL LISP C+ C# Visual C+ Visual BASIC Visual J+ 系统软件设计 具有图形功能 科学计算 商用 人工智能 程序设计语言是规则和符号的集合程序设计语言是规则和符号的集合, ,用于编用于编 写计算机程序的语言，包含语法、语义和语用三写计算机程序的语言，包含语法、语义和语用三 个方面。个方面。 程序设计语言的基本成分有：程序设计语言的基本成分有： 数据成分，用于描述程序所涉及的数据；数据成分，用于描述程序所涉及的数据； 运算成分，用以描述程序中所包含的运算运算成分，用以描述程序中所包含的运算 ； 控制成分，用以描述程序中所包含的控制控制成分，用以描述程序中所包含的控制 ； 传输成分，用以表达程序中数据的传输传输成分，用以表达程序中数据的传输 6.1 程序与程序语言 6.1 程序与程序语言 计算机语言：是规则和符号的集合，是 与计算机交流的工具 程序：求解问题的指令序列 软件：程序的集合 学习语言 设计程序 制作软件 概念： 00000000 1011100000000000 10111000 00000000 0010010100000000 00100101 00000000 0000010100000000 00000101 00000000 0101010000000000 01010100 A = 37 + 84A = 37 + 84 第一代：机器语言第一代：机器语言 二进制机器指令，机器能直接执行。二进制机器指令，机器能直接执行。 送数到送数到AXAX寄存器寄存器 被加数被加数 3737 加法加法 加数加数 8484 程序设计语言的发展 6.1 程序与程序语言 MOV AX，37 送数37到AX寄存器 ADD AX，84 AX寄存器内容+84送到寄存器AX 第二代：汇编语言第二代：汇编语言 用符号代替机器语言，需要翻译。用符号代替机器语言，需要翻译。 6.1 程序与程序语言 A=37+84A=37+84 第三代：高级语言第三代：高级语言 英语和数学语言代替机器语言，需要翻译。英语和数学语言代替机器语言，需要翻译。 A=37+84A=37+84 第三代：高级语言第三代：高级语言 英语和数学语言代替机器语言，需要翻译。英语和数学语言代替机器语言，需要翻译。 6.1 程序与程序语言 计算机语言分类计算机语言分类 BASIC BASIC 语言语言 为初级编程者设计，为初级编程者设计，19641964年问世。大多数版本年问世。大多数版本 是解释执行，易学易用。如是解释执行，易学易用。如GWBASICGWBASIC、QBASICQBASIC、 Visual BasicVisual Basic等。其中等。其中Visual BasicVisual Basic功能强大。功能强大。 面向过程语言面向过程语言 面向过程程序设计需要明确规定每个操作步面向过程程序设计需要明确规定每个操作步 骤和细节。骤和细节。 6.1 程序与程序语言 FORTRAN FORTRAN 语言语言 适合于数值计算，早期版本主要考虑高精度适合于数值计算，早期版本主要考虑高精度 数字计算，不太关注对计算结果的表达形式。新数字计算，不太关注对计算结果的表达形式。新 的的FORTRANFORTRAN版本增强了字符处理和图形功能。版本增强了字符处理和图形功能。 Pascal Pascal 语言语言 其简洁明了结构化，具有丰富的数据结构和控其简洁明了结构化，具有丰富的数据结构和控 制结构，为程序员提供了极大的方便性与灵活性，制结构，为程序员提供了极大的方便性与灵活性， 同时它特别适合微计算机系统。同时它特别适合微计算机系统。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第一节 第一节 概述概述 6.1 程序与程序语言 COBOL COBOL 语言语言 通用商务对象处理语言，美国海军上将通用商务对象处理语言，美国海军上将Grace Grace HopperHopper于上世纪于上世纪6060年代设计，主要用于开发大型商年代设计，主要用于开发大型商 务程序，务程序， COBOLCOBOL程序通常很长，但可读性好，便于程序通常很长，但可读性好，便于 调试和维护。调试和维护。 LISP LISP 语言语言 开发于开发于19601960年，一般用于人工智能专家系统的年，一般用于人工智能专家系统的 开发，擅长对字符数据进行复杂的逻辑处理。开发，擅长对字符数据进行复杂的逻辑处理。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第一节第一节 概述概述 6.1 程序与程序语言 C C语言语言 19701970年美国年美国BellBell实验室的实验室的K K ThompsonThompson发发 明明B B语言，用于开发语言，用于开发UNIXUNIX操作系统。操作系统。19721972年，年， 他的同事他的同事D D RitchieRitchie改进改进B B语言，使之不仅适语言，使之不仅适 用于系统软件的开发，也与其他高级语言一用于系统软件的开发，也与其他高级语言一 样适宜开发应用软件，命名为样适宜开发应用软件，命名为C C语言。语言。 其主要特点是能进行系统软件的开发，其主要特点是能进行系统软件的开发， 可以直接寻址，故被称为高级汇编语言，开可以直接寻址，故被称为高级汇编语言，开 发的程序具有较高的效率。发的程序具有较高的效率。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第一节第一节 概述概述 6.1 程序与程序语言 面向对象语言面向对象语言 面向过程的程序中，数据与对数据的加工 面向过程的程序中，数据与对数据的加工 是分离的，与现实世界事物的特性不符。是分离的，与现实世界事物的特性不符。 面向对象技术直接描述客观世界的对象及面向对象技术直接描述客观世界的对象及 其相互关系。对象是封装了数据和操作的程序其相互关系。对象是封装了数据和操作的程序 块。面向对象程序设计就是设计对象（数据和块。面向对象程序设计就是设计对象（数据和 操作）和安排对象完成所需任务，同一对象可操作）和安排对象完成所需任务，同一对象可 以用在不同的程序中。以用在不同的程序中。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第一节第一节 概述概述 6.1 程序与程序语言 SimulaSimula 67 67被被认为认为认为认为 是最早的面向是最早的面向对对对对象程序象程序设计设计设计设计 语语语语言，它引入了所有后来面向言，它引入了所有后来面向对对对对象程序象程序设计语设计语设计语设计语 言言 所遵循的基所遵循的基础础础础概念：概念：对对对对象、象、类类类类、继继继继承。承。 C+C+ JAVA JAVA C+ C+ Visual BASIC Visual BASIC （可（可视视视视化）化） Visual J+Visual J+ Visual FoxPro Visual FoxPro 第五模块第五模块 计算机程序设计基础计算机程序设计基础第一节第一节 概述概述 6.1 程序与程序语言 6.1 程序与程序语言 三、程序设计全过程 l分析问题，建立数学模型 l确定数据结构 l确定算法，描述算法 l编制程序，调试程序 l运行结果 6.1 程序与程序语言 分 析 问 题 建 立 数 学 模 型 确 定 数 据 结 构 和 算 法 编 写 程 序 调 试 运 行 分 析 整 理 结 果 1. 程序设计过程： 依赖于你的头脑 依赖于你的 头脑和机器 语言 处理系统 程序实例：#include “#include “graphics.hgraphics.h“ “ #include “#include “bios.hbios.h“ “ #include #include “ “stdio.hstdio.h“ “ /* /* 预处理预处理 * */ / main( ) main( ) /* /* 函数体函数体 函数名函数名 * */ / intint n,xn,x=100,y=100,k=1,m=1,driver,mode; =100,y=100,k=1,m=1,driver,mode; long i; long i; /* /* 定义变量定义变量 * */ / detectgraph(); initgraph(“); setcolor(0); setbkcolor(9); bar(40,40,300,440); setcolor(0); setbkcolor(9); bar(40,40,300,440); while(1) while(1) n=bioskey(1); n=bioskey(1); if(nif(n=283) break;=283) break; setcolor(15); setcolor(15); circle(x,y,30); circle(x,y,30); setcolor(4); setcolor(4); if(x+k+30300 | x+k-30300 | x+k-30440 | y+m-30440 | y+m-30 = != = = != = ( ) - . ? : , ; 特殊符号：特殊符号：_(_(下划线下划线) ) 回车回车(r) r) 换行换行(n) (n) 制表符制表符(t)(t) 其它转义字符其它转义字符 6.1 程序与程序语言 字符集 数据类型数据类型 基本类型基本类型 构造类型构造类型 整型整型 intint 字符型字符型 charchar 实型（浮点型）实型（浮点型） 枚举类型枚举类型 enumenum 指针类型指针类型 空类型（无值类型）空类型（无值类型） voidvoid 数组类型数组类型 结构类型结构类型 structstruct 联合类型联合类型 unionunion 单精度实型单精度实型 floatfloat 双精度实型双精度实型 doubledouble 6.1 程序与程序语言 数据描述 1.1. 算术运算符算术运算符 2. 2. 关系运算符关系运算符 3. 3. 逻辑运算符逻辑运算符 4. 4. 位运算符位运算符 5. 5. 赋值与赋值组合运算符赋值与赋值组合运算符 6. 6. 自增自减运算符自增自减运算符 7.7.其它运算符其它运算符 6.1 程序与程序语言 运算 switch (switch (表达式表达式) ) case case 常量常量1: 1: 语句序列语句序列1 1 case case 常量常量2: 2: 语句序列语句序列2 2 default: default: 语句序列语句序列n+1 n+1 i if(f(表达式表达式) ) 语句语句1 1； elseelse 语句语句2 2； while while 语句语句 for for 语句语句 do - while do - while 语句语句 break break 语句语句 continue continue 语句语句 gotogoto 语句语句 6.1 程序与程序语言 流程 6.1 程序与程序语言 6.2 算法与算法设计 6.3 程序设计风格 第六章 程序设计基础 算法基本特征 算法表示 算法设计设计 一、什么是算法 算法是为解决问题而采取的方法和步骤。算法是为解决问题而采取的方法和步骤。 决定了算法的执决定了算法的执 行顺序行顺序 算术运算、逻辑算术运算、逻辑 运算、比较运算运算、比较运算 和数据传送和数据传送 1. 1. 基本操作基本操作 2. 2. 控制结构控制结构 算法的算法的 基本要素基本要素 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 举例：插入排序法问题，有一个从小到大的数值序举例：插入排序法问题，有一个从小到大的数值序 列，将一个新数插入到序列中。列，将一个新数插入到序列中。 12121919262637374848 5 5 9 9 2424 ？ 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 12121919262637374848 5 5 9 9 2424 2424 举例：插入排序法问题，有一个从小到大的数值序举例：插入排序法问题，有一个从小到大的数值序 列，将一个新数插入到序列中。列，将一个新数插入到序列中。 2424 2424 2424 2424 2424 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 算法： 开始 i=1 新数与序列第i个元素比较 如果（新数比第i个元素大） i 加 1 如果（i大于m）执行步骤 否则 执行步骤 否则 执行步骤 从第i到第m个元素后移一个位置 将新数置于序列第i个位置 结束 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 二、算法的基本特征 有穷性有穷性: : 一个算法必须在执行有限个操作步骤后终止一个算法必须在执行有限个操作步骤后终止 确定性确定性: :算法中每一步是确切的算法中每一步是确切的, ,不可出现任何二义性不可出现任何二义性 可行性可行性: :算法中每一步操作都能有效执行算法中每一步操作都能有效执行 （如：一个数被（如：一个数被0 0 除的操作就是无效的）除的操作就是无效的） 有零个或多个输入有零个或多个输入: : 输入是指算法开始之前所需要的原始数据输入是指算法开始之前所需要的原始数据 输出是指与输入有某种特定关系的量，是算输出是指与输入有某种特定关系的量，是算 法进行信息加工后得到的结果法进行信息加工后得到的结果 有一个或多个输出有一个或多个输出: : 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 算法设计算法设计的原则的原则 1 1、正确性：对于一切合法的输入数据都能得出、正确性：对于一切合法的输入数据都能得出 满足要求的结果。满足要求的结果。 2 2、可读性：算法应该易理解，便于交流、可读性：算法应该易理解，便于交流 3 3、健壮性：当输入非法数据时，算法应恰当地、健壮性：当输入非法数据时，算法应恰当地 作出反应或进行相应处理。作出反应或进行相应处理。 4 4、高效率与低存储量需求：算法执行时间较少、高效率与低存储量需求：算法执行时间较少 ，算法执行所需存储空间较小。，算法执行所需存储空间较小。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 三、算法的表示 流程图流程图 N-SN-S流程图流程图 伪代码伪代码 PADPAD码码 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 1. 1. 流程图流程图 用规定的一系列图形、流程线和文字说明算用规定的一系列图形、流程线和文字说明算 法中的基本操作和控制流程。法中的基本操作和控制流程。 流程图的基本元素包括：流程图的基本元素包括： 表示相应操作的框；表示相应操作的框； 带箭头的流程线；带箭头的流程线； 框内外必要的文字说明。框内外必要的文字说明。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 （1 1）图形符号）图形符号 起止框判断框处理框输入/输出框 注释框流向线 连接点 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 （2 2）用流程图表示算法）用流程图表示算法 例：求给定半径例：求给定半径R R的圆的圆 面积和圆周长。面积和圆周长。 这是一个数学问题。这是一个数学问题。 算法：算法： 圆面积圆面积 S=S=* R* R 2 2 圆周长圆周长 L=2*L=2*R*R 这是顺序程序结构。这是顺序程序结构。 开始开始 输出输出 S S、L L的值的值 结束结束 输入半径输入半径R R *R*R *R*R S S 2*2*R*R L L 顺序顺序 第五模块第五模块 计算机程序设计基础计算机程序设计基础第二节第二节 算法算法 6.2 算法与算法设计 例：求给定数R 的绝对值。 算法： R R0 |R|= -R R=0d=0 x2=sqrt(d)/(2a)x2=sqrt(d)/(2a)x2=sqrt(-d)/(2a)x2=sqrt(-d)/(2a) x1=-b/(2a)x1=-b/(2a) Y Y N N M22M22 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 3.3.模块集成模块集成 a=0a=0 Y Y N N X1=-X1=-c/bc/b 输出结果输出结果 开始开始 输入数据输入数据 结束结束 M1M1 M2M2 M3M3 d=bd=b 2 2 -4ac-4ac d=0d=0 x2=sqrt(d)/(2a)x2=sqrt(d)/(2a)x2=sqrt(-d)/(2a)x2=sqrt(-d)/(2a) x1=-b/(2a)x1=-b/(2a) Y Y N N 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 BohmBohm和和JacopiniJacopini证明：任何算法都可以由证明：任何算法都可以由 顺序结构、选择结构和循环结构这三种基本结顺序结构、选择结构和循环结构这三种基本结 构组合来实现。构组合来实现。 三、三种基本结构 三种三种 顺序结构顺序结构 基本基本 选择结构选择结构 结构结构 循环结构循环结构 S1S1 S2S2 顺顺 序序 结结 构构 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 选择结构选择结构 N N 条条 件件 S1S1S2S2 Y Y 双选择结双选择结 构构 N N 条件条件 S1S1 Y Y 单选择结构单选择结构 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 条件条件 A A 块块 Y Y N N 直到型循环结构直到型循环结构 循环结构循环结构 三种基本结构的特点：三种基本结构的特点： 一个入口，一个出口，不出现死循环和死语句一个入口，一个出口，不出现死循环和死语句 条件条件 A A 块块 Y Y N N 当型循环结构当型循环结构 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 T+I T+I T T I10I10 Y Y N N 1 1I I，0 0K, 0K, 0T T K10K10 Y Y N N T+K T+K T T 死循环死循环 死语句死语句 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 例如：例如： 6.2 算法与算法设计 用顺序结构描述将华氏用顺序结构描述将华氏 温度温度F F转换成摄氏温度转换成摄氏温度C C 的流程。的流程。 算法：算法： C=5/9*C=5/9*（F-32F-32）。）。 1 1、顺序结构设计、顺序结构设计 顺序结构中，按语句的自顺序结构中，按语句的自 然顺序依次执行。然顺序依次执行。 开始开始 5/9 5/9 b b b*(F-32)b*(F-32)C C 输出输出F F，C C 结束结束 输入输入F F 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 已知三角形的已知三角形的3 3条条 边边长，求三角形面边边长，求三角形面 积。用顺序结构描述积。用顺序结构描述 求三角形面积的流程求三角形面积的流程 。 三角形面积公式：三角形面积公式： 其中：其中：s=(a+b+c)/2s=(a+b+c)/2 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 开始开始 (a+b+c)/2 (a+b+c)/2 s s s*(s-a)*(s*(s-a)*(s-bs-b)*()*(s-c)s-c)t t 输出输出areaarea 结束结束 输入输入a,b,ca,b,c 6.2 算法与算法设计 用顺序结构描述两用顺序结构描述两 个值（个值（a=1, b=2a=1, b=2）交换）交换 的流程。的流程。 1 1 2 2 b b a a 1 1 2 2 1 1 开始开始 1 1a a，2 2b b a a c c b b a a 输出输出a a，b b 结束结束 c c b b c 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 选择结构，选择结构， 又称为分支结构又称为分支结构 。根据选择结构。根据选择结构 中判断的结果，中判断的结果， 选择执行相应的选择执行相应的 语句。语句。 2 2、选择结构及其程序设计、选择结构及其程序设计 开始开始 输出输出 MAXMAX 结束结束 输入输入R,HR,H R R MAXMAXH H MAXMAX RHRH Y Y N N 用选择结构用选择结构 描述求两个数中描述求两个数中 的最大值的流程的最大值的流程 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 用选择结构用选择结构 描述检查某年是描述检查某年是 否闰年的流程。否闰年的流程。 N N年为闰年满年为闰年满 足下列条件之一足下列条件之一 ： 1.N1.N能被能被400400整除整除 2.N2.N能被能被4 4整除，整除， 但不能被但不能被100100整除整除 开始开始 输出输出 YESYES 结束结束 输入输入N N N N被被400400整除整除 Y Y N N N N被被4 4整除整除 Y Y N N N N被被100100整除整除 Y Y N N 输出输出 NONO 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 循环结构，当循环控循环结构，当循环控 制条件为真时反复执行循制条件为真时反复执行循 环体中的语句，直到循环环体中的语句，直到循环 控制条件为假时为止。控制条件为假时为止。 开始开始 输出输出 T T 的值的值 结束结束 输入输入K K T+K T+K T T I+1 I+1 I I I10I10 Y Y N N 1 1I I，0 0 T T 累加器累加器 计数器计数器 用循环结构描述求用循环结构描述求1010 个学生成绩之和的流程。个学生成绩之和的流程。 3 3、循环结构及其程序设计、循环结构及其程序设计 用用T T累计累计1010个学生的个学生的 成绩（成绩（K K），用），用I I记录累加记录累加 的次数（的次数（I=1I=1，2 2，1010 ） 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 用循环结构描用循环结构描 述求述求1010到到100100之间所之间所 有不能被有不能被3 3整除的整整除的整 数的流程数的流程 开始开始 结束结束 I+1 I+1 I I I100I100 Y Y N N 1010I I I I不能被不能被3 3整除整除 输出输出 I I Y Y N N 对对1010到到100100之间之间 所有数逐一验证，所有数逐一验证， 凡满足凡满足“ “不能被不能被3 3整整 除除” ”的整数即可输出的整数即可输出 。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 从键盘输入从键盘输入n n值，输出值，输出n n行用行用* *号组成等腰三角形号组成等腰三角形 。 例：输入例：输入 n=4n=4，输出的图形如下：，输出的图形如下： * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * k=1,n-1=3* k=1,n-1=3个空，个空，2*1-1=12*1-1=1个个* * * * * * * * k=2,n-2=2k=2,n-2=2个空，个空，2*2-1=32*2-1=3个个* * * * * * * * * * * * k=3,n-3=1k=3,n-3=1个空，个空，2*3-1=52*3-1=5个个* * * * * * * * * * * * * * * * k=4,n-4=0k=4,n-4=0个空，个空，2*4-1=72*4-1=7个个* * 共共n n行，其中第行，其中第K K 行由行由n-kn-k个空格和个空格和 2k-12k-1个个* *组成组成 第五模块第五模块 计算机程序设计基础计算机程序设计基础第三节第三节 结构化程序设计结构化程序设计 6.2 算法与算法设计 分析：分析： 1 1、输出、输出 n n 行。行。 2 2、图形的第、图形的第 k k 行行(1=31=31） 使用穷举法使用穷举法, ,尝试尝试i i、j j的所有可能。的所有可能。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第四节第四节 基本算法基本算法 6.2 算法与算法设计 循环循环I I取值从取值从1 1到到9 9 循环循环J J取值从取值从0 0到到9 9 如果如果I I不等于不等于J J 求车牌后四位：求车牌后四位： I*1000+I*100+J*10+JI*1000+I*100+J*10+J 如果后四位开方是整数如果后四位开方是整数 输出后四位输出后四位 结束结束 结束结束 循环循环J J结束结束 循环循环I I结束结束 第五模块第五模块 计算机程序设计基础计算机程序设计基础第四节第四节 基本算法基本算法 6.2 算法与算法设计 I+1 I+1 I I I9I9 Y Y N N 1 1 I I 输出车号输出车号 J+1 J+1 b b J9J9 Y Y N N 0 0 J J I I J J Y Y N N i*1000+i*100+j*10+ji*1000+i*100+j*10+jk k 开始开始 结束结束 k k Q Q Q=INT(Q)Q=INT(Q) Y Y N N 第五模块第五模块 计算机程序设计基础计算机程序设计基础第四节第四节 基本算法基本算法 6.2 算法与算法设计 二、迭代法 迭代法是用计算机解决问题的一种迭代法是用计算机解决问题的一种 基本方法基本方法, ,对一组指令对一组指令( (或一定步骤或一定步骤) )进行进行 重复执行，在每次执行这组指令重复执行，在每次执行这组指令( (或这些或这些 步骤步骤) )时，都从变量的原值推出它的一个时，都从变量的原值推出它的一个 新值。新值。 迭代法是用于求方程或方程组近似 迭代法是用于求方程或方程组近似 根的一种常用的算法。根的一种常用的算法。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第四节第四节 基本算法基本算法 6.2 算法与算法设计 利用迭代算法解决问题，需要做好以下三个方面的 利用迭代算法解决问题，需要做好以下三个方面的 工作：工作： 一、确定迭代变量一、确定迭代变量 迭代算法解决的问题中，至少存在一个直接或间接迭代算法解决的问题中，至少存在一个直接或间接 地不断由旧值递推出新值的变量，这个变量就是迭代变地不断由旧值递推出新值的变量，这个变量就是迭代变 量。量。 二、建立迭代关系式二、建立迭代关系式 从变量的前一个值推出其下一个值的公式。从变量的前一个值推出其下一个值的公式。 三、对迭代过程进行控制三、对迭代过程进行控制 迭代过程的控制分为两种情况：一种是所需的迭代迭代过程的控制分为两种情况：一种是所需的迭代 次数是个确定的值，可以计算出来次数是个确定的值，可以计算出来; ;另一种是所需的迭另一种是所需的迭 代次数无法确定代次数无法确定, , 需要确定结束迭代过程的条件。需要确定结束迭代过程的条件。 第五模块第五模块 计算机程序设计基础计算机程序设计基础第四节第四节 基本算法基本算法 6.2 算法与算法设计 a b b x1=(a+)/2 x x2 2 x* x3 x x 用二分法方程的根用二分法方程的根 第五模块第五模块 计算机程序设计基础计算机程序设计基础第四节第四节 基本算法基本算法 6.2 算法与算法设计 例例1 1 用二分法求用二分法求 x x 3 3 +4x-10=0 +4x-10=0 在在(1,2)(1,2)内的根，要求绝内的根，要求绝 对误差不超过对误差不超过0.0050.005。 解：解： f(1)=-50 -(1,2)+ xf(2)=140 -(1,2)+ x1 1 =1.5 =1.5 f(1.25)0 (1.25,1.375) x f(1.375)0 (1.25,1.375) x3 3 =1.375 =1.375 f(1.313)0 (1.360