ACM程序设计算法原理和ACM入门.ppt

1、ACM程序设计,东北林业大学 陈宇,2020/8/7,2,第一讲,算法原理和ACM入门 (Introduction to ACM),2020/8/7,3,我校的ACM在线评测系统, 课件下载地址： ,2020/8/7,4,开课目的,为林大ACM代表队培养后备人才 提高分析问题和应用计算机编程解决问题的能力 培养必要的自学能力 培养学生的协调和沟通能力 体会学习的快乐,2020/8/7,5,ACM/ICPC in China,中国大陆高校从1996年开始参加ACM/ICPC 前六届中国赛区设在上海，由上海大学承办； 2002年：清华和西安交大； 2003年：清华和中山； 2004年：北大和上海交

2、大； 2005年：川大、北大和浙大； 2006年：上海大学、清华和西电； 2007年：北航、南航、吉大、西华； 2008年：哈工程、北交、中科大、杭电、西南民大； 2009年：哈工大、中科大、NIT、武大、东华； 2010年：天大、福大、川大、哈工程、浙江理工；,2020/8/7,6,ACM in NEFU,2006年9月，第一次参加此类比赛（黑龙江省赛） 20062010，每年5月 黑龙江省第15届大学生程序设计竞赛 20072010，每年6月 东北地区第14届大学生程序设计竞赛 20062010，每年9月11月 第2934届ACM国际大学生程序设计竞赛亚洲区预选赛,2020/8/7,7,预

3、期赛事（今后每年）,34月，举行校内大赛（暨选拔赛） 4月， ACM全国邀请赛 5月，参加黑龙江省大学生程序设计大赛 6月，参加东北4省大学生程序设计大赛 1011月，参加ACM/ICPC亚洲区比赛（至少参加45个赛区的比赛） 另外，每学期至少有三次月赛以及适当的练习赛,2020/8/7,8,2010年的风采,2020/8/7,9,2020/8/7,10,2020/8/7,11,2020/8/7,12,2020/8/7,13,2020/8/7,14,2020/8/7,15,2020/8/7,16,2020/8/7,17,2020/8/7,18,2020/8/7,19,2020/8/7,20,2

4、020/8/7,21,2020/8/7,22,2020/8/7,23,第一部分 算法概述,算法分析的目的： 设计算法设计出复杂性尽可能低的算法 选择算法在多种算法中选择其中复杂性最低者,算法分析（Algorithm Analysis）：对算法所需要的两种计算机资源时间和空间进行估算 时间复杂性（Time Complexity） 空间复杂性（Space Complexity）,2020/8/7,24,评价算法,评价算法的三条主要标准是： (1) 算法实现所耗费的时间； (2) 算法实现所所耗费的存储空间，其中 主要考虑辅助存储空间； (3) 算法应易于理解，易于编码，易于调 试等等。,2020/

5、8/7,25,和算法执行时间相关的因素：,1）问题中数据存储的数据结构 2）算法采用的数学模型 3）算法设计的策略4）问题的规模 5）实现算法的程序设计语言 6）编译算法产生的机器代码的质量 7）计算机执行指令的速度,2020/8/7,26,算法效率的衡量方法,通常有两种衡量算法效率的方法: 1）事后统计法（有缺点，较少使用） 2）事前分析估算法 算法的时间效率是问题规模的函数。假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作:T(n)=(f(n),称T(n)为算法的渐近时间复杂度(Asymptotic Time Complexity),简称时间复杂度。是数量级

6、的符号。,2020/8/7,27,一个算法中所有语句的频度之和构成了该算法的运行时间。 例如： 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。,2020/8/7,28,再看看这个代码：,对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基本(或者说是主要) 的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作,多数情况下是最深层次循环体内的语句中的原操作。 例如：

7、for(i=1;i=n;+i) for(j=1;j=n;+j) ci,j=0; for(k=0;k=n;+k) ci,j= ci,j+ai,k*bk,j; ,2020/8/7,29,当一个算法的算法运行时间为n2+n+1，由于n2+n+1与n2的数量级相等(该表达式当n足够大时约等于n2), 我们说这个算法的渐进时间复杂度(简称算法的时间复杂度)为：T(n)=O(n2)。,2020/8/7,30,算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)：,(1)称为常数级 (logn)称为对数级 (n)称为线性级 (nc)称为多项式级 (cn)称为指数级 (n!)

8、称为阶乘级,以上时间复杂度级别是由低到高排列的,其随规模n的增长率见下图。,2020/8/7,31,图 T(n)与规模n的函数关系,2020/8/7,32,Temp=i；i=j；j=temp； 以上三条单个语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=(1)。 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是(1)。,【例1】交换i和j的内容。,2020/8/7,33,【例2】变量计数之一。,(1) x=0；=0； (2) for(k-1；=n；+) (3

9、) x+； (4) for(i=1；=n；+) (5) for(j=1；j=n；+) (6) y+； 该算法段的时间复杂度为T(n)=(n2)。 当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。,2020/8/7,34,【例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),2020/8/7,35,算法的描述方法, 自然语言 优点

10、：容易理解 缺点：冗长、二义性 使用方法：粗线条描述算法思想 注意事项：避免写成自然段,2020/8/7,36, 输入m 和n； 求m除以n的余数r； 若r等于0，则n为最大公约数，算法结束； 否则执行第步； 将n的值放在m中，将r的值放在n中； 重新执行第步。,欧几里德算法,2020/8/7,37, 流程图 优点：流程直观 缺点：缺少严密性、灵活性 使用方法：描述简单算法 注意事项：注意抽象层次,2020/8/7,38,欧几里德算法,2020/8/7,39, 程序设计语言 优点：能由计算机执行 缺点：抽象性差，对语言要求高 使用方法：算法需要验证 注意事项：将算法写成子函数,2020/8/7

11、,40,#include int CommonFactor(int m, int n) int r=m % n; while (r!=0) m=n; n=r; r=m % n; return n; void main( ) coutCommonFactor(63, 54)endl; ,欧几里德算法,2020/8/7,41,伪代码算法语言 伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。 优点：表达能力强，抽象性强，容易理解,2020/8/7,42,1. r = m % n; 2. 循环直到 r 等于0 2.

12、1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出 n ;,欧几里德算法,2020/8/7,43,递归算法的分析,1. 猜测技术:对递推关系式估计一个上限，然后（用数学归纳法）证明它正确。,关键：根据递归过程建立递推关系式，然后求解这个递推关系式。,2020/8/7,44,扩展递归技术 设n=2k,2020/8/7,45,通用分治递推式,大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。,2020/8/7,46,第二部分,编程基本知识,2020/8/7,47,先看这道题,The Hardest Pro

13、blem Ever hdu1048 A.cm 第60题,2020/8/7,48,【问题描述】,Julius Caesar生活在一个危险而又充斥着阴谋的时代。Caesar面对的最难的情况关系着他的存亡。为了让自己生存，他决心去创造第一种加密方法之一。这个加密方法听起来是这样的令人难以置信，没有一个人可以指出它（的原文）除非知道它怎样工作。你是Caesar军队的一个分队长。你的工作是破译Caesar送来的信息并汇报给你的上级。密码很简单，每一个字母对应着一个明文，你将明文向右五步来得到安全的信息。（比如，假如那个字母是A，密文就是F）,2020/8/7,49,加密文本A B

14、C D E F G H I J 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 I J K L M N O P Q R S T U 密文中只有字母被切换了，非字母的字符应该保持不变，所有的字母都是大写的。,2020/8/7,50,【输入】,这个问题的输入包括一系列（非空）最多100个数据。每一个数据的格式会按照以下格式，并且在不同组数据间不会有空行分隔。所有的字符都是大写的。一个单独的测试数据包括三个部分：1. 开始行：单独的一行“START” 。2. 加密的信息：单独的一行，由1200个字符组成来自Caesar的一

15、行信息。3. 结束行：单独的一行“END” 。最后一组测试数据结束会跟着单独的一行“ENDOFINPUT”。,2020/8/7,51,【输出】,对每一个测试数据只会有一行输出。它是Caesar的原文。,2020/8/7,52,【样例输入】,STARTNS BFW, JAJSYX TK NRUTYFSHJ FWJ YMJ WJXZQT TK YWNANFQ HFZXJXENDSTARTN BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJENDSTARTIFSLJW PSTBX KZQQ BJQQ YMFY

16、HFJXFW NX RTWJ IFSLJWTZX YMFS MJENDENDOFINPUT,2020/8/7,53,【样例输出】,IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSESI WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROMEDANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE,2020/8/7,54,分析：,A 的值是65，则Z的值是91 #include #

17、include #include using namespace std; int main(void) char a1000,b1000; int i;,2020/8/7,55,while(gets(a) if(strcmp(a,START)=0) memset(b,0,sizeof(b); else if(strcmp(a,END)=0) printf(%sn,b); else if(strcmp(a,ENDOFINPUT)=0) break; else for(i=0;ai!=0;i+) if(ai=A ,2020/8/7,56,memset()是干什么的？,Memset(a,0,siz

18、eof(a)的最用是把数组a清0，在string.h中定义，很方便！ 代码很规范！,2020/8/7,57,对于字符串输入的处理：,C语法： char buf20; gets(buf); C+语法： 如果用string buf;来保存： getline( cin , buf ); 如果用char buf 255 ; 来保存： cin.getline( buf, 255 );,2020/8/7,58,说明：,scanf(“ %s%s”,str1,str2)，在多个字符串之间用一个或多个空格分隔； 若使用gets函数，应为gets(str1); gets(str2); 字符串之间用回车符作分隔。

19、通常情况下，接受短字符用scanf函数，接受长字符用gets函数。 而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。,2020/8/7,59,说明：cin.getline的用法：,getline 是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下： istream 不用管它的返回类型，来关心它的三个参数： char line： 就是一个字符数组，用户输入的内容将存入在该数组内。 int size : 最多接受几个字符？用户超过size的输入都将不被接受。 char endchar :当用户输入end

20、char指定的字符时，自动结束。默认是回车符。,2020/8/7,60,说明,结合后两个参数，getline可以方便地实现： 用户最多输入指定个数的字符，如果超过，则仅指定个数的前面字符有效，如果没有超过，则用户可以通过回车来结束输入。 char name4; cin.getline(name,4,n); 由于 endchar 默认已经是 n，所以后面那行也可以写成： cin.getline(name,4);,2020/8/7,61,OJ评测原理,Input 1 5 2 6 10 20 111 111 321 123,Output 6 8 30 222 444,2020/8/7,62,Righ

21、tmost Digit（hdu1061）,Problem Description Given a positive integer N, you should output the most right digit of NN. Input The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.Each test case contains a single po

22、sitive integer N(1=N=1,000,000,000).,2020/8/7,63,Output For each test case, you should output the rightmost digit of NN. Sample Input 2 3 4 Sample Output 7 6,2020/8/7,64,Hint In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7. In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost dig

23、it is 6.,2020/8/7,65,直接做,int i,n,tmp,sum; cinn; while(n-) sum=1; cini; tmp=i%10; for(int j=1;j=i;j+) sum=sum*tmp; sum=sum%10; sum=sum%10; coutsumendl; ,2020/8/7,66,Time Limit Exceeded,时间超时了！ 就不是直接做的题！,2020/8/7,67,先找规律,0 1 5 6 这4个数好啊 周期=1 4：4 6 周期=2 9：9 1 2：2 4 8 6 周期=4 3: 3 9 7 1 7: 7 9 3 1 8: 8 4 2

24、 6,2020/8/7,68,int n; int a104 = 0,1,6,2,4,8,1,3,9,7,6,4,5,6,1,7,9,3,6,8,4,2,1,9 ,d,num;,2020/8/7,69,scanf(%d, ,2020/8/7,70,数的长度 (nefu_oj 65),N! (N的阶乘) 是非常大的数，计算公式为：N! = N * (N - 1) * (N - 2) * . * 2 * 1)。现在需要知道N!有多少（十进制）位。,2020/8/7,71,每行输入1个正整数N。0 N 1000000,对于每个N，输出N!的（十进制）位数。,1 3 32000 1000000,202

25、0/8/7,72,1 1 130271 5565709,1 3 32000 1000000,2020/8/7,73,如何计算？,所谓N!的（十进制）位数，就是Lg(N!)+1，根据数学公式，有 N!=1*2*N Lg(N!)=lg(2)+lg(N),2020/8/7,74,核心代码：,int main() while(scanf(%ld, ,2020/8/7,75,Leftmost Digit (hdu 1060,nefu_oj 66),Problem Description Given a positive integer N, you should output the leftmost

26、digit of NN.Input The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.Each test case contains a single positive integer N(1=N=1,000,000,000).,2020/8/7,76,OutputFor each test case, you should output the leftmo

27、st digit of NN,Sample Input 2 3 4 Sample Output 2 2,2020/8/7,77,Hint In the first case, 3 * 3 * 3 = 27, so the leftmost digit is 2. In the second case, 4 * 4 * 4 * 4 = 256, so the leftmost digit is 2.,2020/8/7,78,分析问题：,本题目主要是给定一个正整数n，计算nn的结果的最高数位上的数字的值。 如果通过求nn的最后结果再求最高数位的数字，方法简单，但是存在问题，就是n较大时候，nn太大

28、而无法用程序存储，需要设计大数的存储方案，且带来了计算过程中的难度而且消耗大量内存空间和时间。在本题中不可取。,2020/8/7,79,求解：数学知识,另外一种方法，设nn = d.xxx * 10 (k-1) ,其中k表示nn的位数。 那么d.xxx = 10(log10(nn)-(k-1) ,再对d.xxx取整即可获得最终结果。那么k是多少呢？ k = log10(nn)的整数部分+1 = (int)log10(nn)+1;至此，可以获得d的计算公式为 d = (int)(10(log10(nn)-(int)log10(nn);,2020/8/7,80,#include #include

29、int main() int t,n; double x = 0.0; scanf(%d, ,2020/8/7,81,64位的类型,在VC 里有_int64 这个类型，输出时用%I64d来输出，我们使用 long long类型，也是64位的，输出时用%lld就可以了！ 用cout可以避免%的问题！,2020/8/7,82,排序算法,1、 sort 2、 qsort,2020/8/7,83,sort,头文件： algorithm.h 用法：很简单 复杂度：n*log(n) 语句：sort(a,a+10); 默认：升序,2020/8/7,84,Sort 的例子,#include #include

30、#include using namespace std; int main(int argc, char *argv) int data10; for(int i=0;idatai; sort(data,data+5); for(int j=0;j=4;j+) coutdatajendl; system(PAUSE); return EXIT_SUCCESS; ,2020/8/7,85,Sort 降序该怎么办？,STL 已经为我们准备好了！ 升序：sort(begin,end,less();降序：sort(begin,end,greater().,2020/8/7,86,升序： Sort(a

31、,a+20,less(); 降序： Sort(a,a+20,greater(); 头文件没啥变化，就是 algorithm.h,2020/8/7,87,qsort 方法,格式： qsort ( 数组名 ，元素个数，元素占用的空间(sizeof)，比较函数) 说明：要写比较函数 头文件：在 iostream.h,2020/8/7,88,比较函数的写法,int compare(const void *a,const void *b) return *(int*)b-*(int*)a; /降序 int compare(const void *a,const void *b) return *(int

32、*)a-*(int*)b;/升序,2020/8/7,89,qsort的例子,int compare(const void *a,const void *b) return *(int*)b-*(int*)a; int main() int a20=2,4,1,23,5,76,0,43,24,65,i; for(i=0;i20;i+) coutaiendl; qsort(a,20,sizeof(int),compare); for(i=0;i20;i+) coutaiendl; return 0;,2020/8/7,90,简单的练习题目：,林大OJ 30、32题 杭电OJ 2014，2019，2010，2015等 排序是基本知识，必会！,2020/8/7,91,【循环节】 问题,Number Sequence hdu1005,nefu_oj 67 A number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2) mod 7.Given A, B, and n, you are to calculate the val