下载此文档

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


文档分类:IT计算机 | 页数:约13页 举报非法文档有奖
1/13
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/13 下载此文档
文档列表 文档介绍
清华大学ACM集训队培训资料
一、C++基础
差不多知识
所有的C++程序差不多上有函数组成的,函数又叫做子程序,且每个C++程序必须包含一个main函数,编译器(能够把源代码转换成目标代码的程序)把翻译后的目标代码和一些启动代码组合le=simon(3);
有返回值的函数如下
//convert.cpp--convertsstonetopounds
#include<iostream>
intstonetolb(int);//functionprototype
intmain()
(
usingnamespacestd:
intstone;
cout«"Entertheweightinstone:";
cin»stone;
intpounds=stonetolb(stone);
cout«stone«Hstone=";
cout«pounds«”pounds.H«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
关于数据的输入和输出有几道练****题
://acm.hdu.edu.cii/showproblein.php?pid=1089

://acm.hdu.edu.cn/showproblem.php?pid=1096
二、算法基础
1.什么是算法
裁法是完成特定任务的有限指令集。所有的算法必须满足下面的标准:
a.输入。由外部题共零个或多个输入量。
b.输出。至少产生一个输出量。
c.明确性。每条指令必须清晰,不具模糊性。
d.有限性。假如跟踪算法的指令,那么关于所有的情形,算法通过有限步以后终止。
e.有效性。每条指令必须专门基础,原则上使用笔和纸就能够实现
例选择排序
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”,当且仅

内容来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数13
  • 收藏数0 收藏
  • 顶次数0
  • 上传人cjc201601
  • 文件大小66 KB
  • 时间2022-01-26