Dqsscha清华大学ACM集训队企业培训范本.doc

《Dqsscha清华大学ACM集训队企业培训范本.doc》由会员分享，可在线阅读，更多相关《Dqsscha清华大学ACM集训队企业培训范本.doc（11页珍藏版）》请在三一办公上搜索。

1、Time will pierce the surface or youth, will be on the beauty of the ditch dug a shallow groove ; Jane will eat rare!A born beauty, anything to escape his sickle sweep.- Shakespeare清华大学ACM集训队培训资料（内部使用）一、C+基础基本知识所有的C+程序都是有函数组成的， 函数又叫做子程序，且每个C+程序必须包含一个main函数，编译器（能够把源代码转换成目标代码的程序）把翻译后的目标代码和一些启动代码组合起来，生成

2、可执行文件，main函数就是可执行文件的入口，所以，每个C+程序有且只有一个main函数。下面我们看一个最简单C+程序。(程序1.1)程序1.1int main()return 0;在这个程序中，如果缺少任何一个字符，编译器就无法将其翻译成机器代码。此外，C+是对大小写敏感的，这就意味着，如果我将mian()函数拼为Main(),哪么，编译器在编译这段程序的时候就会出错。编辑源文件能够提共管理程序开发的所有步骤，包括编辑的程序成为集成开发环境（integrated development evironments, IDE）。在windows系统下，使用较为广泛的有Microsoft Visua

3、l C+、Dev-Cpp等，在UNIX系统下，有Vim、emacs、eclipes等。这些程序都能提供一个较好的开发平台，使我们能够方便的开发一个程序，接下我们所要了解的都是标准C+，所有源代码都在Dev-cpp下编写，能够编译通过。如果我们修改程序1.1中的main()函数的名称，将其改为Main()，那么，IDE就会给出错误信息，比如“ Linker error undefined reference to WinMainx16”，因为编译器没有找到main函数。接下来，我们来看一个经典的C+例子（程序1.2）程序1.2#includeusing namespace std;int mai

4、n(void)coutHello Wrold!endl;return 0;运行结果Hello World!程序说明第一行“#include”，是一句预处理命令，相当于把“iostream”这个文件的所有内容复制到当前位置，替换该行。因为在输出操作中需要做很多事，C+编译器就提供了很多已经写好的函数(成为C+标准库)，我们做的只是拿来用就可以了。第二行的“using namespace std;”是使用标准命名空间，因为我们在程序中用到了在标准命名空间里的函数和对象。目前可以不了解其具体如何实现，在以后的程序设计中可以再对其进行了解。在明函数中“cout”Hello World!”endl;”是

5、在屏幕上打印“Hello World!eHeH”，“endl”表明打印完这句话之后需要换行。如果我们替换引号内的内容，程序的输出就会相应改变。另外一个C+程序例子/ ourfunc.cpp - defining your own function#include void simon(int); / function prototype for simon()int main() using namespace std; simon(3); / call the simon() function cout count; simon(count); / call it again cout Do

6、ne! endl; return 0;void simon(int n) / define the simon() function using namespace std; cout Simon says touch your toes n times. endl; / void functions dont need return statements下面试运行情况：Simon says touch your toes 3 times.Pick an integer: 512Simon says touch your toes 512 times.Done!程序中包含了cin语句来从键盘上

7、获取数据。该程序中包含了除main函数以外的另一个函数simon()，他和main函数定义的格式相同，函数的统一格式如下：type functionname (argumentlist)statements注意，定义simon()的代码在main()函数的后面，C+中不允许将函数定义在另一个函数内。每个函数的定义都是独立的，所有的函数的创建都是平等的。simon()函数的函数头定义如下：void simon(int n)以void 开头表明simon()没有返回值，因此我们不能类是这样的使用它。simple = simon(3);有返回值的函数如下/ convert.cpp - convert

8、s stone to pounds#include int stonetolb(int); / function prototypeint main() using namespace std; int stone; cout stone; int pounds = stonetolb(stone); cout stone stone = ; cout pounds pounds. endl; return 0;int stonetolb(int sts) return 14 * sts;下面是运行情况：Enter the weight in sone: 1414 stone = 196 po

9、unds.程序通过cin语句给stone提供一个值，然后在main函数中，把这个值传递给stonetolb()函数，这个植被赋给sts之后，stonetolb()用return将 14*sts返回给main()。函数头中的int表明stonetolb()将返回一个整数。除了int类型之外，C+的内置数据类型还有：unsigned long、long、unsigned int、unsigned short、short、char、unsigned char、signed char、bool、float、double、long double。对于数据的输入和输出有几道练习题xacm.hdu.edux

10、/showproblem.php?pid=1089至xacm.hdu.edux/showproblem.php?pid=1096二、算法基础1. 什么是算法算法是完成特定任务的有限指令集。所有的算法必须满足下面的标准：a. 输入。由外部题共零个或多个输入量。b. 输出。至少产生一个输出量。c. 明确性。每条指令必须清楚，不具模糊性。d. 有限性。如果跟踪算法的指令，那么对于所有的情况，算法经过有限步以后终止。e. 有效性。每条指令必须非常基础，原则上使用笔和纸就可以实现例 选择排序void SelectionSort(Type a, int n)/Sort the arrat a1:n int

11、o nondecreasing order.for (int i=1; i=n; i+)int j=1;for (int k=i+1; k=n; k+)if (ak aj)j = k;Type t = ai;ai = aj;aj = t;使用该函数时，应将Type替换为C+中的数据类型3性能分析程序P所用时间定义为T(P), T(P)是编译时间和运行时间之和。下面我们计算一下选择排序运行时所要花费的时间SelectionSortcosttimesfor (int i=1; i=n; i+)c1int j=1;c2for (int k=i+1; k=n; k+)c3if (ak aj)c4j =

12、 k;c5Type t = ai; ai = aj; aj = t;c6那么该算法运行的时间那么，在最坏的条件下，的值应该是所以，算法的运行时间为4渐进符号定义： 大O函数，念做是的大”oh”，当且仅当存在正常数和，使得对于所有的，有。例对于所有有，所以。对于所有有，所以对于所有有，所以当然对于所有有，所以定义： 函数，念做是的”omega”，当且仅当存在正常数和，使得对于所有的，有。例对于所有有，所以。当然，但是。现然无论是O还是，都不能精确的描述一个函数定义： 函数，念做是的”theta”，当且仅当存在正常数和，使得对于所有的，有。例对于有且，所以记号要比O和都要精确。排列生成器(n!)v

13、oid Perm(Type a, int k, int n)if (k=n) /Output permutation.for (int i-1; in; i+) coutai ;else /ak:n has more than one permutation. / Generate these recursively.for (int i=k; i=n; i+)Type t=ak; ak=ai; ai=t;Perm(a, k+1, n);/All permutations of ak+1:nt=ak; ak=ai; ai=t;对于下面的程序#includeusing namespace std

14、;void Perm(int a, int k, int n)if (kn-1)int i, t;for (i=k; in; i+)t = ak;ak = ai;ai = t;Perm(a, k+1, n);t = ak;ak = ai;ai = t;elseint i;for (i=0; in; i+)coutait;coutendl;int main(void)int a3 = 1, 2, 3;Perm(a, 0, 3);return 0;该程序的运行结果为123132213231321312那么，该函数就完成了对一个数组进行全排列的操作下面，分析该程序，我用圆圈代表每次函数的调用每次函数

15、的调用都用序号表示12853467910k=0k=1k=21. a: 1 2 3 k: 02. a: 1 2 3 k: 13. a: 1 2 3k: 24. a: 1 3 2k: 25. a: 2 1 3k: 16. a: 2 1 3k: 27. a: 2 3 1k: 28. a: 3 2 1k: 19. a: 3 2 1k: 210. a: 3 1 2k: 2排列生成器的另外一个版本他将输出给定n个布尔变量的所有可能的组合void Perm (bool a, int k, int n)if (k = n)/statementelseak = true; Perm(a, k+1, n);ak

16、= false;Perm(a, k+1, n);在上次冬季赛上有这么一道题竞赛真理 JUNNY在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是要完全正确地做对一题是要花很多时间（包括调试时间），而竞赛的时间有限。所以开始做题之前最好先认真审题，估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。 当然，如果做完了预先选择的题目之后还有时间，但是这些时间又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一点分数。 根据每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，哪些题目“骗”分，哪些不做），使能在限定

17、的时间内获得最高的得分。 INPUT FORMAT: 从标准输入（cin,scanf等）读入数据。数据有多组，先输入K（K组数据）。每组第一行有两个正整数N和T，表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行个正整数W1i 、T1i 、W2i 、T2i ，分别表示第i题：完全正确做出来的得分，完全正确做出来所花费的时间（单位：秒），“骗”来的分数，“骗”分所花费的时间（单位秒）。其中，3 N 30，2 T 1080000，1 W1i 、W2i 30000，1 T1i 、T2i T。 OUTPUT FORMAT: 直接把所求得的最高得分输出。数据之间需换行。 SAMPLE INPUT:

18、 2 4 10800 一八 3600 3 一八00 22 4000 12 3000 28 6000 0 3000 32 8000 24 6000 3 7200 50 5400 10 900 50 7200 10 900 50 5400 10 900 SAMPLE OUTPUT : 50 70下面我们对问题进行简化。我们只要考虑是做题还是不做题。从标准输入（cin,scanf等）读入数据。数据只有一组，先输入K（K组数据）。每组第一行有两个正整数N和T，表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行个正整数Wi 、Ti，分别表示第i题：做出来的得分和做出来所花费的时间（单位：秒），OU

19、TPUT FORMAT: 直接把所求得的最高得分输出。数据之间需换行。 SAMPLE INPUT: 5 101 205 104 一五3 202 10SAMPLE OUTPUT : 65下面是用全排列生成器完成的代码#includeusing namespace std;int m;int t202;int tSum;void work(bool a, int n);void f(bool a, int k, int n)if (k n)ak = true;f(a, k+1, n);ak = false;f(a, k+1, n);elsework(a, n);void work(bool a,

20、int n)int x;int time=0, score=0;for (x=0; xn; x+)if (ax)score += tx1;time += tx0;if (time m)m = score;int main(void)bool a30;int n, c;cinntSum;m = 0;for (c=0; ctc0;cintc1;f(a, 0, n);coutmendl;return 0;通过一个排列生成器将所有的可能送入work()函数内，然后work函数找到在时间范围内的最高的分数。现在我们将其优化，将work()和f()合并，就能得到更好的程序#includeusing nam

21、espace std;int m;int t202;int tSum;void dfs(int k, int n, int cScore, int cTime)if (k n)dfs(k+1, n, cScore , cTime);dfs(k+1, n, cScore + tk1, cTime + tk0);elseif (cTime m)m = cScore;int main(void)int n, c;cinntSum;m = 0;for (c=0; ctc0;cintc1;dfs(0, n, 0, 0);coutmendl;return 0;这个程序就是深度优先搜索，如果n非常大，递归调

22、用的次数是非常惊人的，达到次。为了减少递归的次数，我们可以采取剪枝的手段，在递归下一次前判断是否可行。如果肯定不能就停止递归，节省时间。#includeusing namespace std;int m;int t202;int tSum;void dfs(int k, int n, int cScore, int cTime)if (k n)dfs(k+1, n, cScore , cTime);if (cTime tSum)dfs(k+1, n, cScore + tk1, cTime + tk0);elseif (cTime m)m = cScore;int main(void)int n, c;cinntSum;m = 0;for (c=0; ctc0;cintc1;dfs(0, n, 0, 0);coutmendl;return 0;为了达到更好的剪枝效果，可以在搜索前对数据进行排序。竞赛真理原题也可用这种思想去解。更复杂的算法将在以后进行讲解.