34
2013-7-30
算法的描述方法
⑴ 自然语言
优点：容易理解
缺点：冗长、二义性
使用方法：粗线条描述算法思想
注意事项：避免写成自然段
2013-7-30
35
欧几里德算法
① 输入m 和n；
② 求m除以n的余数r；
③ 若r等于0，则n为最大公约数，算法结束；
否则执行第④步；
④ 将n的值放在m中，将r的值放在n中；
ACM程序设计
东北林业大学 陈宇 Lg_chenyu@
第一讲
算法原理和ACM入门
(Introduction to ACM)
2013-7-30
2
我校的ACM在线评测系统

课件下载地址： /kj/suanfa01.ppt
48
2013-7-30

加密文本 ABCDEFGHIJKLMNOPQRS TUVWXYZ 明文文本 VWXYZABCDEFGHIJKLMN OPQRSTU 密文中只有字母被切换了，非字母的字 符应该保持不变，所有的字母都是大写 的。
49
2013-7-30
【输入】

这个问题的输入包括一系列（非空）最多100 个数据。每一个数据的格式会按照以下格式， 并且在不同组数据间不会有空行分隔。所有的 字符都是大写的。 一个单独的测试数据包括三个部分： 1. 开始行：单独的一行“START” 。 2. 加密的信息：单独的一行，由1~200个字符 组成来自Caesar的一行信息。 3. 结束行：单独的一行“END” 。 最后一组测试数据结束会跟着单独的一行 “ENDOFINPUT”。

2013-7-30
24
和算法执行时间相关的因素：
1）问题中数据存储的数据结构 2）算法采用的数学模型 3）算法设计的策略 4）问题的规模 5）实现算法的程序设计语言 6）编译算法产生的机器代码的质量 7）计算机执行指令的速度
2013-7-30 25
算法效率的衡量方法

通常有两种衡量算法效率的方法:
26
2013-7-30

一个算法中所有语句的频度之和构成了该算法的运行时间。 例如：


for(j=1;j<=n;++j)
for(k=1;k<=n;++k) ++x；


语句“++x、k<=n、++k”的频度是n2， 语句“ j=1、k=1”的频度是1， 语句“j<=n;++j”的频度是n。 算法运行时间为：3*n2+2n+2。
33
2013-7-30
【例3】变量计数之二




(1) x=1； (2) for(i=1；i<=n；i++) (3) for(j=1；j<=i；j++) (4) for(k=1；k<=j；k++) (5) x++； 该算法段中频度最大的语句是(5)，从内层循环 向外层分析语句(5)的执行次数： 复杂度：O(n3)

Temp=i；i=j；j=temp；

以上三条单个语句的频度均为1，该算法段的执行 时间是一个与问题规模n无关的常数。算法的时间复杂 度为常数阶，记作T(n)=Ο(1)。
如果算法的执行时间不随着问题规模n的增加而增 长，即使算法中有上千条语句,其执行时间也不过是一 个较大的常数。此类算法的时间复杂度是Ο(1)。

2013-7-30
32
【例2】变量计数之一。

(1) (2) (3) (4) (5) (6)
x=0；=0； for(k-1；<=n；++) x++； for(i=1；<=n；++) for(j=1；j<=n；++) y++；


该算法段的时间复杂度为T(n)=Ο(n2)。 当有若干个循环语句时，算法的时间复杂度是由嵌 套层数最多的循环语句中最内层语句的频度f(n)决定的。
2013-7-30
27
再看看这个代码：
对较复杂的算法计算算法的运行时间,经常从算法中选取 一种对于所研究的问题来说是基本(或者说是主要) 的原操作, 以该基本操作在算法中重复执行的次数作为算法运行时间的衡 量准则。这个原操作,多数情况下是最深层次循环体内的语句 中的原操作。 例如： for(i=1;i<=n;++i) for(j=1;j<=n;++j) { c[i,j]=0; for(k=0;k<=n;++k) c[i,j]= c[i,j]+a[i,k]*b[k,j]; }
40
伪代码——算法语言
伪代码（Pseudocode）：介于自然语言和 程序设计语言之间的方法，它采用某一程序 设计语言的基本语法，操作指令可以结合自 然语言来设计。 优点：表达能力强，抽象性强，容易理解
2013-7-30
41
欧几里德算法 1. r = m % n; 2. 循环直到 r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n ;
2013-7-30
42
递归算法的分析
关键：根据递归过程建立递推关系式，然 后求解这个递推关系式。 1. 猜测技术:对递推关系式估计一个上限， 然后（用数学归纳法）证明它正确。
2013-7-30
43
扩展递归技术
设n=2k
7 n =1 T ( n) = 2T ( n 2 ) + 5 n2 n >1 T (n) = 2T ( n 2) + 5n2 = 2( 2T ( n 4) + 5( n 2)2 ) + 5n2 = 2( 2( 2T ( n 8) + 5( n 4)2 ) + 5( n 2)2 ) + 5n2 n = 2k T (1) + 2k -1 5( k -1 )2 + L + 2×´( n)2 + 5n2 5 2 2
2013-7-30
47
【问题描述】

Julius Caesar生活在一个危险而又充斥着阴谋 的时代。Caesar面对的最难的情况关系着他的 存亡。为了让自己生存，他决心去创造第一种 加密方法之一。这个加密方法听起来是这样的 令人难以置信，没有一个人可以指出它（的原 文）除非知道它怎样工作。 你是Caesar军队的一个分队长。你的工作是破 译Caesar送来的信息并汇报给你的上级。 密码很简单，每一个字母对应着一个明文，你 将明文向右五步来得到安全的信息。（比如， 假如那个字母是‘A’，密文就是‘F’）
k -1
n2 1 = 7 n + 5 i = 7 n + 5 n 2 ( 2 - k -1 ) = 10 n 2 - 3 n 10 n 2 = O ( n 2 T ( n) 2 i= 2013-7-30 0 2 44
通用分治递推式
大小为n的原问题分成若干个大小为n/b的子问题， 其中a个子问题需要求解，而cnk是合并各个子问题 的解需要的工作量。 c n =1 T ( n) = aT ( n b ) + cn k n>1
设计算法——设计出复杂性尽可能低的算法 选择算法——在多种算法中选择其中复杂性最低者
2013-7-30 23
评价算法

评价算法的三条主要标准是：
(1) 算法实现所耗费的时间； (2) 算法实现所所耗费的存储空间，其中 主要考虑辅助存储空间； (3) 算法应易于理解，易于编码，易于调 试等等。
2013-7-30 28

当一个算法的算法运行时间为n2+n+1， 由于n2+n+1与n2的数量级相等(该表达式 当n足够大时约等于n2), 我们说这个算法 的渐进时间复杂度(简称算法的时间复杂 度)为：T(n)=O(n2)。
2013-7-30
29
算法(渐进)时间复杂度,一般均表示为以下几种数量级的 形式(n为问题的规模,c为一常量)：
O ( nlog a ) = O ( n k log b n) T ( n) k O ( n )
b
> bk a = bk a < bk a
45
2013-7-30
第二部分
编程基本知识
2013-7-30 46
先看这道题

The Hardest Problem Ever hdu1048 .cm 第60题
19
2013-7-30
20
2013-7-30
21
2013-7-30
22
第一部分 算法概述
算法分析（Algorithm Analysis）：对算法所需 要的两种计算机资源——时间和空间进行估算
时间复杂性（Time Complexity） 空间复杂性（Space Complexity）
算法分析的目的：
50
2013-7-30
【输出】

对每一个测试数据只会有一行输出。它 是Caesar的原文。

2013-7-30
7
2010年的风采
2013-7-30
8
2013-7-30
9
2013-7-30
10
2013-7-30
11
2013-7-30
12
2013-7-30
13
2013-7-30
14
2013-7-30
15
2013-7-30
16
2013-7-30