算法设计语言的课件 第6章

理网络、明结构
填要点、记疑点
主目录
探题型、提能力
ห้องสมุดไป่ตู้
探题型、提能力
章末复习课
题型三：算法语句的设计
解 (1)①i>30？ ②P＝P＋i
(2)程序如下： P＝1 S＝0 i＝1 DO S＝S＋P P＝P＋i i＝i＋1 LOOP UNTIL i>30 PRINT S END
理网络、明结构
填要点、记疑点
主目录
章末复习课
题型二：程序框图及设计
算法的设计是画程序框图的基础，我们通过对问题的分析，写出相应的算法步骤．画 程序框图之前应先对算法问题设计的合法性和合理性进行探讨，然后分析算法的逻辑 结构和各步骤的功能(输入、输出、判断、赋值和计算)，画出相应的程序框图．
理网络、明结构
填要点、记疑点
主目录
探题型、提能力
探题型、提能力
章末复习课
题型三：算法语句的设计
基本算法语句有输入语句、输出语句、赋值语句、条件语句、循环语句五种，它们对 应于算法的三种逻辑结构：顺序结构、条件结构、循环结构．用基本语句编写程序时 要注意各种语句的格式要求，特别是条件语句和循环语句，应注意这两类语句中条件 的表达以及循环语句中有关变量的取值范围．
填要点、记疑点
章末复习课
1．算法的概念 算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或看成 按要求设计好的有限的、确切的计算序列，并且这样的步骤或序列能够解决一类 问题．
理网络、明结构
填要点、记疑点
主目录
探题型、提能力
填要点、记疑点
2．程序框图
章末复习课
(1)程序框图又称流程图，是一种用规定的图形、流程线及文字说明来准确、直 观地表示算法的图形． (2)程序框图由程序框和流程线组成．一个或几个程序框的组合表示算法中的一个 步骤：流程线是带方向箭头的指向线，按照算法进行的顺序将程序框连接起来． (3)在利用循环结构画程序框图前，常确定三件事：一是确定循环变量的初始条 件；二是确定算法中的循环体；三是循环终止的条件． 3．程序设计 自然语言表述的算法和程序框图是程序设计的基础，程序框图侧重于直观性，而 程序则倾向于计算机执行的实用性．

30
Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 3 from Peg A to Peg B Move Disk 1 from Peg C to Peg A Move Disk 2 from Peg C to Peg B Move Disk 1 from Peg A to Peg B Move Disk 4 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 2 from Peg B to Peg A Move Disk 1 from Peg C to Peg A
" from peg "， fromPeg， " to peg
/*把n-1个圆盘从auxPeg借助fromPeg移至
29
towers(n-1，auxPeg，toPeg，fromPeg); }设计一个测试主函数如下： ＃include <stdio.h> void main(void) {
Towers(4， 'A'， 'C'， 'B'); }程序运to Peg B
26
Move Disk i from Peg X to Peg Y 这样， 汉
诺塔问题的递归算法可设计如下： void towers(int n，
char fromPeg， char toPeg， char auxPeg)
{
if(n＝＝1)
/*递归出口*/
{
printf("%s%c%s%c＼n"， "move disk
并不是每个问题都适宜于用递归算法求解。 适宜于用递归 算法求解的问题的充分必要条件是：

一种类自然语言。结构化语言语法结构包括内外两层。 内部语法则比较灵活，可以使用数据字典中定义过的 词汇、易于理解的一些名词、运算符和关系符；外层 语法具有较固定的格式，设定一组符号如IF、THEN、 ELSE、DO WHILE…ENDWHILE、DO CASE…ENDCASE等，用于描述顺序、选择和重复 的控制结构。
3
6.1详细设计任务
6.1.1 详细设计的基本任务 1．数据结构设计 前面的需求分析、总体设计阶段，确定的 概念性的数据类型，要进行确切的定义。这一 部分的设计内容一般比较多，所以大多数采用 小型数据库辅助的方法。
4
2．物理设计 对数据库进行物理设计，即确定数据库的
物理结构。物理结构主要指数据库的存储记录 格式、存储记录安排和存储方法，这些都依赖 于具体所使用的数据库系统。
要评审。
10
6.1.2 详细设计方法
1．采用自顶向下、逐步求精的程序设计方法 在详细设计中，虽然处于“具体”设计阶段，但
在设计某个复杂的模块内部处理过程时，仍可以采用 逐步求精的方法。可以将其分解为若干个模块来实现， 降低处理细节的复杂度。
11
2．使用三种基本控制结构构造程序 设计时，如果对一个模块处理过程细化中，开始是模 糊的，可以用下面三种方式以模糊过程进行分解：
5
3．算法设计 在总体设计的结构完成后，结构各个环节
的实现是多解的。着就需要用系统设计与分析 的技术来描述。可以用某种图形、表格、语言 等工具将每个模块处理过程的详细算法描述出 来。
6
4．界面设计 用户界面的设计现在显得比较重要，可以
采用字符用户界面设计，图形用户界面和多媒 体人机界面设计。这就要结合具体的系统来处 理。
以上三种逻辑表达工具各有所长和不足，归纳 起来可以得出下列结论：

2.Inputbox（）函数应用
例2：编程求半径为r=6的圆的面积
r=val (inputbox(“r=”,”输入半 ) 径”) s=3.14*r*r print “圆的面积s=”；s
提问：例2与例1相比，好在哪？
四、顺序结构应用
1.已知长方体的长、宽、高，编开始程求 长方体的全面积和体积。 输入长a
该函数返回值的是字符串类型
三、输入函数
2.Inputbox（）函数应用
例1：编程求半径为r=6的圆的面积
r=6 s=3.14*r*r print “圆的面积s=”；s
提问：如果圆的半径为8，15，30分别计算圆的面积， 上述程序段如何修改？ 提问：如果计算任意半径圆的面积，上述程序如何修改？
三、输入函数
→先计算，后输出计算值； 结果为 8 结果为 x=8
二、Print语句
4.输出项的间隔符：
输出内容可以是一个或多个。如果是多个输出内容，
则各输出内容之间可以用逗号或分号分隔
（1）分号：则后面一个输出内容紧跟前一个输出（紧凑格） Print "早安"; "中国" 结果为 早安中国
（2）逗号，则按照分区(14个字符位置)格式输出（分区格）
Y=x3*100+x2*10+x1
计算个位数x3 Y=x3*100+x2*10+x1 输出x的反向数y
结束四、顺序结构应用Fra bibliotek2.从键盘上输入一个三位数，然后将它 反向输出。如输入456，输出应为654。
X=val(inputbox（“x=”，“输入”）) X1=x\100 X2=(x-x1*100)\10 X3=x-x1*100-x2*10 Y=x3*100+x2*10+x1 Print “三位数”；x；“的反向数为”；y

9
1.3 描述算法
2.Java数据类型 2.Java数据类型 Java
基本数据类型：详见下页表1-1
数据类型
非基本数据类型：如 Byte, Integer, Boolean, String等。
Java对两种数据类型的不同处理方式：
对基本数据类型：在声明一个具有基本数据类型的变量时，自 动建立该数据类型的对象（或称实例）。如:int k; 对非基本数据类型：语句 String s; 并不建立具有数据类型 String的对象，而是建立一个类型String的引用对象， 数据类型为String的对象可用下面的new语句建立。 s = new String String(“Welcome”); String(“Welcome”); String s = new String
20
1.4 算法复杂性分析
• 目的：
– 分析算法就是估计算法所需资源（时间，空间， 通信带宽等） ，以便选取有效的算法。
• 计算模型：
– 单 处 理 机 ， 随 机 存 取 机 （ Random-Access Machine，RAM）计算模型，其中指令是顺序执 行的，无并发操作
• 涉及的知识基础：
算法设计与分析
云南大学旅游文化学院信科系
主讲：周华君
1
主要内容介绍
• • • • • • 第1章 第2章 第3章 第4章 第5章 第6章 算法引论 递归与分治策略 动态规划 贪心算法 回溯法 分支限界法
2
主要内容介绍（续）
• • • • 第7章 第8章 第9章 第10章 概率算法 NP完全性理论 近似算法 算法优化策略
– 离散组合数学、概率论、代数等（分析）、程 序设计、数据结构（算法设计）
1.4 算法复杂性分析

Ad d (Ch ro m o so m e )
loop [nt So rtByAcco m m o d a ti o n () Cro ssOve r(Ch ro m o so m e )
m u ta ti o n ()
CanbeEnded(int): Boolean
图6-1 顺序图中常见的对象
6.1.2 生命线（lifeline）
生命线是从对象图标向下出来的延伸的一条直线，也是和对象紧密联系在 一起的一种模型元素，用于表示对象的生存期或生存期内的某个时间片段。
事实上，在顺序图中，对象和生命线是不可分割的同一个元素，生命线是 对象的一个组成部分，代表了对象的整个或部分生命期。顺序图中即不存在 没有生命线的对象，也不存在没有对象的生命线。当然这并不排除生命线分 支的概念。
除了图形符号，UML还使用消息表达式的方式来描述消息。 按照对象间交互的形式，可以把消息分成方法调用、发送信号、创建实例 和销毁对象等多种形式。其中，最常用的形式就是对象间的方法调用。
6.1.4 消息（Message）
描述方法调用或发送信号的消息的语法格式定义如下： [returnvalue=] message_name (arguments) : type_of_return_value return_value：是消息的可选部分，表示存储消息返回值的变量。这个变 量可以是发送者的一个属性、整个交互的全局属性、或者是某个拥有交互的 类的属性。 message_name：表示消息名称，可以是接收者的某个方法名或发送的信号 名等。 arguments：表示消息参数列表，是一个用逗号分隔的若干个参数构成的 列表，其中每个参数都可以是参数名或参数值。 type_of_return_value:返回值类型。

其次，图形引擎中存在一些低效算法。不过 MicroWindows支持中文、日文、韩文等多种语言，而且 也支持Truetype字体，目前可知的MicroWindows版本是 0.91。
Page 13
精选课件ppt
6.2.4 OpenGUI
OpenGUI在 Linux 系统上存在已经很长时间了。最初 的名字叫 FastGL，只支持 256 色的线性显存模式，但目
OpenGUI 采用 LGPL 条款发布。OpenGUI 比较适合 于基于 x86 平台的实时系统，可移植性稍差，目前的发展 也基本停滞。
Page 14
精选课件ppt
6.2.5 GTK+简介
GTK+即GIMP ToolKit，是一套跨平台的图形工具包， 它来源于GIMP（GNU Minipulation Prigram），是使用C 语言作为其开发语言的，它基于LGPL授权，是源代码开 放完全免费的。
Page 23
精选课件ppt
.1MiniGUI程序框架
在 MiniGUI 中，窗口主函数名 字叫MiniGUIMain（），它负责创建 程序的主窗口。在这个过程中， MiniGUI 使 用 MAINWINCREATE 结构把Windows 中的创建窗口类和创 建窗口风格合二为一
Page 22
精选课件ppt
MiniGUI-Lite：MiniGUI-Lite上每个程序是单 独的进程，每个进程可创建多个窗口。 MiniGUI-Lite适合于具有完整UNIX特性的嵌 入式操作系统，如Linux。
MiniGUI-Standalone：MiniGUI-Standalone模 式下可以独立进程方式运行，不需多线程也不 需要多进程的支持。MiniGUI-Standalone模式 适合功能单一的应用场合，可以支持几乎所有 的操作系统。

if((a=b;)>0) cout<<″a>0″<<endl；
因为在if的条件中不能包含赋值语句。C++把赋值 语句和赋值表达式区别开来，增加了表达式的种类， 能实现其他语言中难以实现的功能。
3.4 C++的输入与输出
输入和输出并不是C++语言中的正式组成成分。C 和C++本身都没有为输入和输出提供专门的语句结 构。输入输出不是由C++本身定义的，而是在编译 系统提供的I/O库中定义的。 C++的输出和输入是用“流”(stream)的方式实现 的。图3.2和图3.3表示C++通过流进行输入输出的 过程。
图3.2
图3.3
有关流对象cin、cout和流运算符的定义等信息是存 放在C++的输入输出流库中的，因此如果在程序中 使用cin、cout和流运算符，就必须使用预处理命令 把头文件stream包含到本文件中：
#include <iostream>
尽管cin和cout不是C++本身提供的语句，但是在不 致混淆的情况下，为了叙述方便，常常把由cin和 流提取运算符“>>”实现输入的语句称为输入语句 或cin语句，把由cout和流插入运算符“<<”实现 输出的语句称为输出语句或cout语句。根据C++的 语法，凡是能实现某种操作而且最后以分号结束的 都是语句。
前面已介绍，赋值语句是由赋值表达式加上一个分 号构成。 (1)C++的赋值语句具有其他高级语言的赋值语句的 功能。但不同的是： C++中的赋值号“＝”是一个 运算符，可以写成

首先把明文划分为长度为3的序列，cip her blo ck， 每个序列中的字母分别与密钥序列中的相应字母进行
模26加，得到密文JOI OMK ITH JS。
14
2．置换密码 在置换密码中，明文和密文的字母保
持相同，但顺序被打乱了。在简单的纵 行置换密码中，明文以固定的宽度水平 地写在一张图表纸上，密文按垂直方向 读出；解密就是将密文按相同的宽度垂 直地写在图表纸上，然后水平地读出明 文。例如：
18
数据加密标准 DES
美国IBM公司W. Tuchman 和 C. Meyer 1971-1972年研制 成功。
1967年美国Horst Feistel提出的理论。 美国国家标准局（NBS ） 1973年5月到1974年8月两次
发布通告，公开征求用于电子计算机的加密算法。经 评选从一大批算法中采纳了IBM的LUCIFER方案。 DES算法1975年3月公开发表，1977年1月15日由美国 国家标准局颁布为联邦数据加密标准（Data Encryption Standard），于1977年7月15日生效。
DES算法的过程:是在一个初始置换IP后,明文组被分成
右半部分和左半部分,每部分32位,以L0和R0表示.然后是16 轮迭代的乘积变换,称为函数f,将数据和密钥结合起来.16轮
之后,左右两部分再连接起来,经过一个初始逆置换IP-1,算 法结束.
初始置换与初始逆置换在密码意义上作用不大,他们的
作用在于打乱原来输入x的ASCII码字划分关系,并将原来明
19
数据加密标准 DES
数据加密标准 DES 属于常规密钥密码体制，是 一种分组密码。
在加密前，先对整个明文进行分组。每一个组 长为 64 bit。
然后对每一个 64 bit 二进制数据进行加密处理， 产生一组 64 bit 密文数据。