C++基础知识.doc

精品文档ACM入门进阶 程序设计语言是学习数据结构的一个重要组成部分，任何算法只有通过程序设计语言实现之后才能真正解决问题。C+语言凭借其高度的灵活性和强大的功能在大学生竞赛中被非常广泛地使用，在中学生竞赛中的使用也越来越广泛。本文旨在给初学者一个窗口，通过例题了解什么是ACM，希望能够对刚入门的读者有所帮助（题目是英文的，不用担心，很简单得英文，不懂可以查金山词霸）ACM一般要求在一定的时间内，理解并分析题意，设计符合给定时间和空间复杂度要求的算法，并在计算机上使用一定的程序设计语言正确地实现算法。由于整个竞赛存在时间限制（特别是ACM/ICPC类竞赛，在解决问题数目相等的情况下以做题累计时间的多少来决定名次），因此所使用的程序设计语言能否正确、快速地实现算法对竞赛的成绩影响颇大。 一般信息学竞赛比较常用的程序设计语言有以下几种：BASIC、Pascal、C/C+、Java，它们的特点如下表所示：BASICPascalC+Java学习难度容易一般较难较难语言特点简单严谨灵活高度面向对象程序运行速度慢较快快慢库函数功能弱一般很强强在目前的ACM竞赛中，C+和C语言使用较为广泛。但是C+语言凭借其本身所具有的高度的灵活性，以及它所带的库的强大功能，被越来越多的选手所使用。本文几乎所有内容都是例子，详细的见一些相关的参考书。一 C+基础知识1.1 Hello,world!C+对于大小写是敏感的。首先，让我们通过一个非常简单的C+程序，来初步地了解C+语言。#includeusingnamespacestd;/ 注意如果不使用.h将要增加本行intmain()coutHello,world!endl; return 0;/:这个程序的作用就是在屏幕上输出“Hello, world!”的字样。以“#”开始的内容被称为预处理指令，这一行的作用是把一个叫做iostream的头文件包含到我们的程序中来。C+默认是不包含任何头文件的。另外，C语言中的头文件都是以.h结尾的，而标准的C+提倡使用没有扩展名的头文件。第四行让我们可以在程序中直接使用std名字空间内的标识符。std名字空间包含了所有标准C+提供的类和函数，为了简便起见，一般总在包含头文件的预处理命令后写上这一行。如果是C语言的话，程序将变成：#includeintmain()printf(“%sn”,Hello,world!); return 0;/:1.2 类型C+提供了基本类型以及程序员可以自定义的类型：名称C+类型范围大小布尔型booltrue / false1字符型char所有单字节字符18位有符号整型char-128 . 12718位无符号整型unsigned char0 . 255116位有符号整型short-32768 . 32767216位无符号整型unsigned short0 . 65535232位有符号整型int-2147483648 . 2147483647432位无符号整型unsigned int0 . 4294967295464位有符号整型long long-263 . 263-1864位无符号整型unsigned long long0 . 264-18单精度浮点型float1.17e-38 . 3.40e384双精度浮点型double2.22e-308 . 1.79e3088扩展浮点型long double3.36e-4932 . 1.18e493210/12在C+中，很多其他类型的量都可以隐式地转化为布尔型，这时，非零的值都被转化成true，而零被转化成false。其中VC中没有long long类型，可用_int64代替，sizeof的作用就是返回括号里的类型的大小（也可以是变量或者常量）。单个字符的常数要用单引号括起来，一些不能显示的字符可以通过转义符来表示（参见下表）。另外，从上表中可以看出，在C+中，字符型和单字节的整型实际上是等价的。举例来说，A的数值就是65。名称ASCII名称C+名称换行NL(LF)n水平制表符HTt竖直制表符VTv退格BSb回车CRr复位FFf铃声BELa反斜杠问号?1.3 操作符首先，我们来看下表：操作符名称C+操作符加法+减法-乘法*整数除法/实数除法/取余数%小于小于等于大于等于=相等=不等!=位非逻辑非!位与&逻辑与&位或|逻辑或|位异或位左移从中可以看出，C+语言最大的特点就是几乎所有的操作符都是由符号字符构成的。注意：1、C+中，整数除法和实数除法都是由“/”来完成的，当两个操作数都是整数时进行整数除法，当至少有一个是实数时进行实数除法；2、C+中，位运算与逻辑运算的操作符是不同的。1.4 常用的库函数和格式输出标准C+提供了十分强大的库。在这一节，我们只介绍一些和Pascal所提供的标准过程和函数功能相似的库函数。函数定义头文件作用备注void* memset(void* p, int b, size_t n);cstring把p所指向的连续n个字节的值都设置成b与FillChar类似，但要注意参数的顺序void* memmove(void* p, const* q, size_t n);cstring把q所指向的连续n个字节的值复制到p所指向的位置与Move类似，p、q所指向的内存区域可以部分重叠double atof(const char* p);int atoi(const char* p);long atol(const char* p);cstdlib把字符串p转化成所表示的数与Val类似double fabs(double);cmath绝对值函数与Abs类似double ceil(double);double floor(double);cmath取整函数，前者为上取整，后者为下取整double sqrt(double);cmath平方根函数与Sqrt类似double pow(double d, double e);cmath幂函数，返回d的e次方double sin(double);double cos(double);double tan(double);cmath三角函数double asin(double);double acos(double);double atan(double);cmath反三角函数double atan2(double y, double x);cmath增强型反正切函数，返回点(x, y)的辐角很有用，会根据点所在的象限调整弧度值double sinh(double);double cosh(double);double tanh(double);cmath双曲函数double exp(double);cmath指数函数，以e为底与Exp类似double log(double);double log10(double);cmath对数函数，前者以e为底，后者以10为底与Ln类似另外，标准C+中并没有提供函数Pi，要获得Pi的值一般这样做：const double pi = acos(0.) * 2;格式化输出具体参考C语言等相关书籍C+的流可以完成控制格式的操作。指定场宽由成员函数width()来完成，而指定小数部分的位数则稍微麻烦一些，要先把浮点数的输出方式设置为定点输出方式，然后再设置小数部分的位数。例如：cout.setf(ios:fixed, ios:floatfield);cout.precision(2);cout 1.2345 endl;以上程序段中第一个语句的作用就是把浮点数的输出方式设置为定点输出方式，第二个语句的作用是把小数部分的位数设置为2。和Pascal一样，小数部分的最后一位也会进行四舍五入的处理。需要注意的是，width()只对接下来的一个格式化输出有效，如果有多个输出需要指定场宽，那么就要写多个width()函数。而precision()则对之后所有的浮点数输出都有效。例如：cout.width(3);cout 1 2; / 1的场宽为3，而2采用实际宽度cout.width(4);cout 2;如果你觉得这样写太麻烦，你也可以把它写成：cout setw(3) 1 2 setw(4) 2;不过这时不要忘了在程序的最前面加上#include ，因为setw是在iomanip中被定义的。这样，我们就可以完成一般的格式化输出了。C+中流的格式化输出还有很多内容，如果有兴趣可以参考有关资料。1.5 例子要求：每个程序在全部弄懂的前提下，自己编写一次（可以上网AC的都要尽量通过）例1：http:/acm.timus.ru/problem.aspx?space=1&num=1000 A+B ProblemCalculate a + b 输入： a and b输出： a+bSample Input1 5Sample Output6程序：C+：#include using namespace std;int main() int a,b; while(cin a b) cout a+b endl; /cin和cout是iostream里面的东西C：#include int main() int a,b; while(scanf(%d %d,&a, &b) != EOF) printf(%dn,a+b); 注意一般程序要求你多次输入的！ printf和scanf是stdio.h里面的东西，注意C语言里面没有类的存在，只有函数。这两个函数要熟练使用的，慢慢来也行，具体见C和C帮助例2：1到n求和输入：n 代表一个非负整数 1=n=10000输出：1到n求和Sample Input100Sample Output5050程序：C：#includeint n,sum;int main()while (scanf(%d,&n)!=EOF)sum=n*(n+1)/2;printf(%d,sum);return 0;C：#includeusing namespace std;int n,sum;int main()while (cinn)sum=n*(n+1)/2;coutsumendl;return 0;例3：判断一个数是不是素数 1N=50000Sample Input10031Sample OutputNOYES程序：#include#includeusing namespace std;bool tf(int n)int i;for(i=2;in)if(tf(n) coutYESendl;else coutNOendl;return 0;例4 求两个数的最大公约数和最小公倍数Sample Input12 18Sample Output6 36程序：#include#includeusing namespace std;int gcd(int n,int m) /求最大公约数的递归函数if(m=0) return n;else return gcd(m,n%m);int main()int n,m,g;while (cinnm)g=gcd(n,m); coutg m*n/gendl;return 0;例5 排序输入：n个整数的序列 1=n=10000 第一行输入n，第二行输入n个整数输出：排好序的序列Sample Input51 5 3 2 4Sample Output1 2 3 4 5程序一（顺序排序）：#includeusing namespace std;int n,a10001;void sxpx(int *a)/顺序排序函数 int i,j,temp; for(i=1;i=n;i+) for(j=i+1;jaj) temp=ai; ai=aj; aj=temp; int main()while (cinn) int i;for(i=1;iai;sxpx(a);couta1; for(i=2;i=n;i+) cout ai; coutendl;return 0;程序二（快速排序）：必懂算法#includeint a10000;int n;void quicksort(int s,int t)/总的思想就是第s个节点派到它最后应该排的位置；int i,j,x,t1;i=s;j=t;x=ai;while (i=x)&(ji) j=j-1;if (ji) t1=ai; ai=aj;aj=t1;while (ai=x)&(ij) i=i+1;if (ij) t1=aj;aj=ai;ai=t1;ai=x;i=i+1;j=j-1;if (sj) quicksort(s,j);if (i while (EOF!=0) for (int p=0;pn;p+) scanf(%d,&n);scanf(%d,&ap); for (int p=0;pn;p+)quicksort(0,n-1); scanf(%d,&ap); for (p=0;pn;p+) quicksort(0,n-1);printf(%d ,ap); for (p=0;pn;p+) printf(%d ,ap);return 0; 比较以上两种排序的方法，哪个比较快呢？ 快速排序比较难理解，可以分两步理解：1 ：开数据结构的书，看懂手工是怎么操作的2 ： 自己写一组数据，单步跟踪一下，看看数据怎么变化的。初学时，单步跟踪很重要！如果上面蓝色的字体你都做到了，好了，恭喜！你已经具有自学的能力了，加油加油，以后很多算法只要做这两个工作就行了，再加上一些相关的习题训练就可以灵活运用算法了，再进一步就是成为大牛说远了，加油这里插入STL的使用，可以使用系统的排序函数（具体参考相关STL的资料）：#include#include#includeusing namespace std;int n;int main()while (cinn) int i,x; vector a;/a是一个容器for(i=1;ix; a.push_back(x);/往容器中塞东西sort(a.begin(),a.end();couta0; for(i=1;in;i+) cout ai; coutendl;return 0; 例6：/cgi-bin/problem_cn?id=3020 级数求和问题描述:已知：Sn= 112131n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。现给出一个整数K（1=k=15），要求计算出一个最小的n；使得SnK。输入文件输入有多组测试数据，每组一行，一个数 k输出文件输出有多组数据，每组一行，一个数n。输入样例1输出样例2程序：#includeusing namespace std;int main()int k;while (cink) double s=1.0;int n=1; while(s=k) n+; s+=1.0/n; coutnendl;return 0;建议C和C语言两个版本都自己编写提交例7：/show_problem.php?pid=2482 IP Address简单的说就是8个0或1为一个数，要你转化为十进制数（但是要注意格式）Suppose you are reading byte streams from any device, representing IP addresses. Your task is to convert a 32 characters long sequence of 1s and 0s (bits) to a dotted decimal format. A dotted decimal format for an IP address is form by grouping 8 bits at a time and converting the binary representation to decimal representation. Any 8 bits is a valid part of an IP address. To convert binary numbers to decimal numbers remember that both are positional numerical systems, where the first 8 positions of the binary systems are:27262524232221201286432168421InputThe input will have a number N (1 = N = 9) in its first line representing the number of streams to convert. N lines will follow.OutputThe output must have N lines with a doted decimal IP address. A dotted decimal IP address is formed by grouping 8 bit at the time and converting the binary representation to decimal representation.Sample Input400000000000000000000000000000000000000111000000011111111111111111100101110000100111001011000000001010000000100000000000000000001Sample Output5528算法解释：简单说就是考两个点：1：字符串的操作 2：数制转化#include#includeconst int d8=128,64,32,16,8,4,2,1;int main()int n,i,j,k,x;int a4;char s33;while (scanf(%d,&n)!=EOF)for (i=1;i=n;i+) scanf(%s,&s); memset(a,0,sizeof(a);/a中所有元素都为0 for (j=0;j4;j+) for(k=0;k8;k+) if (sj*8+k=1) aj+=dk; for (j=0;j3;j+) printf(%d.,aj); printf(%dn,a3);return 0;例8： /cgi-bin/problem_cn?id=4026 What is LeftMy lovely sister QingQing has many books. One day she numbers her books with integer. Of cause same books are marked by the same number. When all the books are marked, it is easy to find how many are the same JNow QingQing has a list of books( given by numbers they are marked). In order to buy a gift for her dear brother, she plans to sell some books. But she wants to keep one copy for each kind. After selling, what books will be left ? Please write a program to tell QingQing the answer.InputFirst line is an number N(1=N=50000), meaning the books that QingQing has before selling.Next line will contain N numbers, the marks of the books, separated by a single space.(the marks are between 0 and 999, inclusively)OutputA line for each test case contains the marks of the books after selling. (sorted in non-descending order).Two numbers are separated by a single space.Sample Input51 2 5 4 521 2Sample Output1 2 4 51 2算法分析：sample第一组数据的解释是：5本书，它们的编号分别是1 2 5 4 5 ，问有多少种书，明显是四种，要你列出来而且要编号从小到大列出来。#include#includeusing namespace std;int main()int n,i,x;bool a1000,k;char s33;while (cinn)memset(a,0,sizeof(a);for (i=1;ix;ax=true; k=true;for(i=0;i999;i+)if (ai)if(k) couti;k=false;else cout i;coutendl;return 0;例9：/cgi-bin/problem_cn?id=1059 Points In Line(集训题III-几何)问题描述： 给出平面上的n(3=n=100)个点的坐标，(x1,y1),(x2,y2),.,(xn,yn)，请编写程序判断这n个点，是否都在同一条直线上。所有坐标的取值范围-100,100。 输入格式： 每行分别有2n+1个整数，第一个表示：n,后面连续2n个分别表示：x1,y1,x2,y2,.xn,yn。有多个测试数据。 输出格式： 如果输入中给出的n个点共线，则输出YES，否则输出NO，每行一个输出。 输入样例： 3 1 1 2 2 -1 -1 4 0 1 0 0 -5 5 7 1 输出样例： YESNO算法分析：斜率一样就YES，但是注意计算机可能表示的精度有限，所以判断斜率一样要这样：这是公式： 的转化程序：#includeusing namespace std;struct nodeint x;int y;list100;int main()int n,i;bool k;while(cinn)k=false;for(i=0;ilisti.xlisti.y;for(i=2;in;i+) if (list1.x-list0.x)*(listi.y-list0.y)!=(listi.x-list0.x)*(list1.y-list0.y) k=true; break; if (k) coutNOendl; else coutYESendl;return 0;例10/cgi-bin/problem_cn?id=3002 赋值问题问题描述在很多程序设计语言中，忘记给变量赋初值的错误常令人头疼。 在下面的问题中，最开始仅有变量a中有确定的值。变量为单个小写字母， 每行恰好有三个字符，中间一个是赋值运算符=。 请编程求出含N行的程序段运行以后有哪些变量中有确定的值。 输入： 第一行:N (0N=106) 以下N行，每行3个字符，为一条语句有多组测试数据，直到输入结束为止。输出： 如果没有，输出 none 否则在一行中按字母表顺序给出所有有确定值的变量名。每输出一组数据要换行。输入：4b=ac=dd=be=f2a=cd=b输出：a b dnone程序（from prinse）：C+的#include using namespace std;const int N = 1000000;const int M = 26;char aM = 1 , bM;int main() int i, k, n; char ch1, ch2, ch3; while (cinn) for (i=0; ich1ch2ch3; ach1-a = ach3-a; for (i=k=0; iM; i+) if (ai) bk+ = i; ai = 0; a0 = 1; if (!k) coutnone; else for (i=0; ik-1; i+) coutchar(bi+a) ; coutchar(bk-1+a); coutendl; return 0; C语言：#include #include const