清华大学ACM集训队培训资料.docx

清华大学ACM集训队培训资料
一、C++基础
差不多知识
所有的C++程序差不多上有函数组成的，函数又叫做子程序，且每个C++程序必须包含一个main函数，编译器(能够把源代码转换成目标代码的程序)把翻译后的目标代码和一些启动代码组合le=simon(3);
有返回值的函数如下
//--convertsstonetopounds
#include<iostream>
intstonetolb(int);//functionprototype
intmain()
(
usingnamespacestd:
intstone;
cout«"Entertheweightinstone:"；
cin»stone;
intpounds=stonetolb(stone);
cout«stone«Hstone="；
cout«pounds«”«endl;
return0:
)
intstonetolb(intsts)
(
return14*sts;
)
下面是运行情形：
Entertheweightinsone:14
14stone=196pounds.
程序通过cin语句给stone提供一个值，然后在main函数中，把那个值传递给stonetolb()函数，那个植被赋给sts之后，stone⑹b()用return将14*sts返回给main。©函数头中的int说明stonetolb。将返回一个整数。
除了int类型之外,C++的内置数据类型还有:unsignedlong>long>unsignedintunsignedshort、shortxchar、unsignedchar^signedchar^bookfloat、double、longdoubleo
关于数据的输入和输出有几道练****题
://?pid=1089
至
://?pid=1096
二、算法基础

裁法是完成特定任务的有限指令集。所有的算法必须满足下面的标准：
。由外部题共零个或多个输入量。
。至少产生一个输出量。
。每条指令必须清晰，不具模糊性。
。假如跟踪算法的指令，那么关于所有的情形，算法通过有限步以后终止。
。每条指令必须专门基础，原则上使用笔和纸就能够实现
例选择排序
voidSelectionSort(Typea[]9intn)
//Sortthearrata[l:n]intonondecreasingorder.
(
for(inti=l;i<=n;i++)
(
intj=l;
for(intk=i+l;k<=n:k-H-)
if(a[k]<aUJ)
j=k;
Typet=a[i];
a[i]=a[j];
a(j]=t；
)
)
使用该函数时，应将Type替换为C++中的数据类型
.性能分析
程序P所用时刻定义为T(P),T(P)是编译时刻和运行时刻之和。
下面我们运算一下选择排序运行时所要花费的时刻
SelectionSort
cost
times
for(inti=l;i<=n;i++)(
Cl
n
intj=l;
C2
n
for(intk=i+l;k<=n:k-H-)
C3
£(，一)
if(a[k]<aU])
C4
j=k；
C5
Typet=a[i];a[i]=a[j];a[j]=t;
那么该算法运行的时刻nn
T(n)=c［n+c2n+C3Z(〃-')+%Z(〃-')+，5乙+加』r-l
那么，在最坏的条件下，4的值应该是£(，?-，)
i-1
因此，算法的运行时刻为
T/\/111\1.、2
+C2+Cb--^34--C4~~c5),1+—(c3+。4+C5)n
.渐进符号
定义：［大O］函数/(/?)=O(g("))，念做/(〃)是g(〃)的大“Oh”，当且仅当存在正常数c和
“0，使得关于所有的〃(〃之明)，有/(")<CXg(〃)。
例
关于所有2有3〃+2<4〃，因此3〃+2=O(n)。
关于所有〃26有100〃+64101〃，因此100〃+6=0(〃)
关于所有〃N100有1000〃2+100〃-641001”2,因此1000/+100〃-6=。(〃2)
因此关于所有n>2有100〃2+4〃+2410/74,因此10//+4?+2=O(n4)
定义：［0］函数/(")=Q(g(〃))，念做/(〃)是g(〃)的“omega”，当且仅当存在