没有合适的资源？快使用搜索试试~ 我知道了~

文库首页考试认证其它ACM考试题 ACM程序设计

ACM考试题 ACM程序设计

0 下载量 32 浏览量 2024-04-07 21:31:59 上传评论收藏 9.27MB PDF 举报

温馨提示

试读

66页

ACM考试题 ACM程序设计

资源推荐

资源详情

资源评论

ACM程序设计

东北林业大学陈宇

Lg_chenyu@yahoo.com.cn

第一讲

算法原理和ACM入门

(Introduction to ACM)

我校的ACM在线评测系统

* acm.nefu.edu.cn

* 课件下载地址：

* acm.nefu.edu.cn/kj/suanfaO1 .ppt

预期赛事(今后每年)

* 3~4月，举行校内大赛(暨选拔赛)

* 4月， ACM全国邀请赛

* 5月，参加黑龙江省大学生程序设计大赛

* 6月，参加东北4省大学生程序设计大赛

* 10~11月，参加ACM/ICPC亚洲区比赛(至少参加4〜 5个赛区的比赛)

* 另外，每学期至少有三次月赛以及适当的练习赛

第一部分算法概述

算法分析 (Algorithm A nalysis)：对算法所需要的两种计算机资源—— 时间

和空间进行估算；

> 时间复杂性(Time Complexity)

> 空间复杂性(Space Complexity)

算法分析的目的：

> 设计算法—— 设计出复杂性尽可能低的算法

> 选择算法一在多种算法中选择其中复杂性最低者

算法的描述语言：

⑴ 自然语言

优点：容易理解

缺点：冗长、二义性

使用方法：粗线条描述算法思想

注意事项：避免写成自然段

( 2 ) 流程图

优点：流程直观

缺点：缺少严密性、灵活性

使用方法：描述简单算法

注意事项：注意抽象层次

⑶程序设计语言

优点：能由计算机执行

缺点：抽象性差，对语言要求高

使用方法：算法需要验证

注意事项：将算法写成子函数

( 4 ) 伪代码—— 算法语言

伪代码 (Pseudocode)：介于自然语言和程序设计语言之间的方法，它

采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设

计。

优点：表达能力强，抽象性强，容易理解

评价算法

* 评价算法的三条主要标准是：

* ( 1 ) 算法实现所耗费的时间；

* ( 2 ) 豫'法实现所所耗费的存储空间，其中

* 主要考虑辅助存储空间；

* ( 3 ) 算法应易于理解，易于编码，易于调

H 试等7

和算法执行时间相关的因素：

1) 问题中数据存储的数据结构

2 ) 算法采用的数学模型

3 ) 算法设计的策略

4 ) 问题的规模

5 ) 实现算法的程序设计语言

6 ) 编译算法产生的机器代码的质量

7 ) 计算机执行指令的速度

算法效率的衡量方法

* 通常有两种衡量算法效率的方法：

* 1) 事后统计法(有缺点，较少使用)

* 2 ) 事前分析估算法

算法的时间效率是问题规模的函数。假如,随着问题规模n的增

长，算法执行时间的增长率和f(n)的增长率相同，则可记作:T(n)= 0

(f(n )),称T(n)为算法的渐近时间复杂度(Asymptotic Time

Complexity),简称时间复杂度。。是数量级的符号。

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

* 例如： for(j=1;j< = n;++j)

* for(k=1 ;k< = n;+ + k)

* + +x；

* 语句"+ + x、k< = n、+ + k"的频度是n?,

* 语句“ j=1、1<=1”的频度是1,

* 语句"j< = n;++j”的频度是n。

* 算法运行时间为：3 */+ 2 皿 2。

再看看这个代码：

* 当一个算法的算法运行时间为V + n + l,由于N + n + l与产的

数量级相等(该表达式当n足够大时约等于V ) , 我们说这个算

法的渐进时间复杂度(简称算法的时间复杂度)为：

T(n)=O(n

算法(渐进)时间复杂度，一般均表示为以下几种数量级的形式(n为问题的规模,c为一

常量)：

* 。(1)称为常数级

* O(logn)称为对数级

* o (n)称为线性级

* 0 ( 鹏)称为多项式级

* 。(d ) 称为指数级

* 0 (n !)称为阶乘级

* Temp=i； i= j； j=tem p；

* 以上三条单个语句的频度均为1 , 该算法段的执行时间是一个与问题规模n无

)

—

(

关的常数。算法的时间复杂度为常数阶，记作T(n)=0(1)。

* 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条

语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是0(1)。

【例2 】变量计数之一。

x= 0； = 0；

for(k-1 ； < = n； + + )

x+ + ；

for(i=1； < = n； + + )

for(j= 1 ； j< = n； + + )

y++ ；

* 该算法段的时间复杂度为T(n)=O(n2)。

* 当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中

最内层语句的频度f(n)决定的。

【例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)的

执行次数：

* 复杂度：0( n

)

第二部分

先看这道题

* The Hardest Problem Ever hdu1048

* Acm.nefu.edu.cm 第60题

【问题描述】

* Julius Caesar生活在一个危险而又充斥着阴谋的时代。Caesar面对的

最难的情况关系着他的存亡。为了让自己生存，他决心去创造第一种

加密方法之一。这个加密方法听起来是这样的令人难以置信，没有一

个人可以指出它(的原文)除非知道它怎样工作。

你是Caesar军队的一个分队长。你的工作是破译Caesar送来的信息并

汇报给你的上级。

密码很简单，每一个字母对应着一个明文，你将明文向右五步来得到

安全的信息。（比如，假如那个字母是'A ' , 密文就是F ）

* 加密文本

A B C D E F G H IJ K L M N O P Q R S T U V W X Y Z

明文文本

V W X Y Z A B C D E F G H IJ K L M N O P Q R S T U

密文中只有字母被切换了，非字母的字符应该保持不变，所

有的字母都是大写的。

【输入】

* 这个问题的输入包括一系列（非空）最多100个数据。每一个数据的

格式会按照以下格式，并且在不同组数据间不会有空行分隔。所有的

字符都是大写的。

一个单独的测试数据包括三个部分：

1 . 开始行：单独的一行“START” 。

2 . 加密的信息：单独的一行，由1~200个字符组成来自Caesar的一行

信息。

3 . 结束行：单独的一行“END” 。

最后一组测试数据结束会跟着单独的一行“ENDOFI NPUT”。

【输出】

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

【样例输入】

* START

NS BFW, JAJSYX TK NRUTYFSHJ FWJ YMJ WJXZQT TK YWNANFQ HFZXJX

END

START

N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFU YMFS XJHTSI

NS WTFU

END

START

IFSUW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ

END

ENDOFI NPUT

剩余65页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

fribbler

粉丝: 60
资源: 48

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

ACM考试题 ACM程序设计

ACM

河南省ACM程序设计大赛历年真题

ACM大学生程序设计竞赛在线题库精选题解

历年acm程序设计试题与解答.rar

2018年ACM国际大学生程序设计竞赛真题

ACM程序设计期末考试试题

ACM 国际大学生程序设计竞赛试题与解析

ACM国际大学生程序设计试题

历年acm程序设计试题与解答

ACM程序设计大赛试题及解析

ACM编程竞赛经典而又经典的试题全解析

acm编程比赛入门题目集

ACM题库完整版.pdf

acm程序设计大赛题目

ACM程序设计大赛\ACM试题训练

acm.rar_ACM_ACM PDF_ACM 程序设计_ACM国际大学生程序设计竞赛试题与解析_acm国际大学生程序设计竞赛

acm国际大学生程序设计竞赛试题与解析

ACM国际大学生程序设计大赛试题与解析

ACM国际大学生程序设计竞赛试题与解析

武汉工程大学第一届ACM程序设计竞赛试题.pdf

ACM 国际大学生程序设计竞赛试题与解析 PDG

acm程序设计竞赛试题与解析

浙大杭电ACM程序设计大赛试题

ACM国际大学生程序设计竞赛试题与解析（一）_10110104

ACM国际大学生程序设计竞赛试题与解析（一）PDG格式,影印版

ACM试题_国际程序设计竞赛试题解析.pdf

2006年acm程序设计比赛试题

《科研伦理与学术规范》期末考试及答案2023

计算机组成原理课后习题答案

最新资源