第1部分语言篇
第1章程序设计入门
【教学内容相关章节】
1.1算术表达式 1.2变量及其输入 1.3顺序结构程序设计
1.4分支结构程序设计 1.5C/C++编码规范 1.6小结与习题
【教学目标】
（1）熟悉C语言程序的编译和运行；
（2）学会编程计算并输出常见的算术表达式的结果；
（3）掌握整数和浮点数的含义和输出方法；
（4）掌握数学函数的使用方法；
（5）初步了解变量的含义；
（6）掌握整数和浮点数变量的声明方法；
（7）掌握整数和浮点数变量的读入方法；
（8）掌握变量交换的三变量法；
（9）理解算法竞赛中的程序三步曲：输入、计算、输出；
（10）记住算法竞赛的目标及其对程序的要求。
【教学要求】
掌握算术表达式的书写格式、整数和浮点数的声明、输入和输出方法，C语言中scanf 的输入格式和printf的输出格式。
【教学内容提要】
计算机速度快，很适合做计算和逻辑判断工作。本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若个步骤，然后依次让计算机执行。这部分的重点是计算，所以要求掌握算述表达式的书写格式，整数和浮点数的输入和输出方法。由于是竞赛，所以还要掌握C语言中scanf的输入格式和printf的输出格式中的一些特殊的格式。
接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。
【教学重点、难点】
教学重点：
（1）掌握算术表达式的书写格式；
（2）整数和浮点数的声明、输入和输出方法；
（3）C语言中scanf的输入格式和printf的输出格式。
教学难点：
整数和浮点数的声明、输入和输出方法，scanf的输入格式和printf的输出格式。【课时安排（共2学时）】
1.1算术表达式（0.25学时） 1.2变量及其输入（0.25学时）
1.3顺序结构程序设计（0.5学时） 1.4分支结构程序设计（0.5学时）
1.5C/C++编码规范（自学） 1.6小结与习题（0.5学时）
1.1 算术表达式
计算机的“本职”工作是计算，从算术表达式入手，分析计算机是如何进行复杂的计算。下面来看一个完整的程序1-1。
程序1-1 计算并输出1+2的值
#include
int main(){
printf("%d\n", 1+2);
return 0;
}
程序1-1的功能是计算1+2的值，并把结果3输出到屏幕。
下面做4个实验：
（1）实验1：修改程序1-1，输出3-4的结果
解答：用3-4代替程序1-1的背景为灰色的部分，输出结果为-1。
（2）实验2：修改程序1-1，输出5×6的结果
解答：用5*6代替程序1-1的背景为灰色的部分，输出结果为30。
（3）实验3：修改程序1-1，输出8÷4的结果
解答：用8/4代替程序1-1的背景为灰色的部分，输出结果为2。
（4）实验4：修改程序1-1，输出8÷5的结果
解答：用8/5代替程序1-1的背景为灰色的部分，输出结果为1。
注意：在C语言中，8/5的确切的含义是8除以5所得的商值的整数部分。
下面来看一个完整的程序1-2。
程序1-2 计算并输出8/5的值，并保留小数点后1位
#include
int main(){
printf("%.1lf\n", 8.0/5.0);
return 0;
}
程序1-2的功能是计算8.0/5.0的值，并把结果1.6输出到屏幕。
注意：在程序1-2的背景为灰色部分中,百分号后面是小数点，然后是数字1，再然后是小写字母l，最后是小写它f。
下面再来做3个实验：
（5）实验5：把%.1lf中的数字1改为2，结果如何？能猜想出“1”的确切意思吗？如果把小数点和1都删除，%1lf的含义是什么？
解答：%lf表示输出double浮点数，如果程序1-2中的printf语句改为printf("%lf\n", 8.0/5.0);,则输出结果为1.600000。
%.llf表示输出double浮点数，并且小数点后面保留一位数字，所以程序1-2的输出结果为1.6。%.2lf表示输出double浮点数，并且小数点后面保留二位数字。
（6）实验6：字符串%.llf不变，把8.0/5.0改成原来的8/5，结果如何？
解答：在VC中调试的输出结果为0.000000。在TC中调试，会出现一个提示“printf: floating point formats not linked。Abnormal program termination”。
（7）实验7：字符串%.1lf改为原来的%d，8.0/5.0不变，结果如何？
解答：在VC中调试的输出结果为-1717986918。在TC中调试的输出结果为-26214。
对于上面的实验6和实验7的答案很难简单的解释，真正的原因是涉及整数和浮点编码。
提示1-1：整数值用%d，实数用%lf输出。
提示1-2：整数/整数=整数，浮点数/浮点数=浮点数。
算术表达式可以和数学表达式一样复杂，例如计算数学表达式1的值：
程序1-3 复杂的表达式计算
#include
#include
int main(){
printf("%.8lf\n", 1+2*sqrt(3)/(5-0.1));
return 0;
}
说明：（1）整数-浮点数是整数先“变”成浮点数，然点浮点数-浮点数=浮点数。
（2）在程序1-3中用到数学函数sqrt。数学函数sqrt(x)的作用是计算x的算术平方根。一般来说，只要在程序中用到了数学函数，就需要在程序最开始的地方包含文件math.h
1.2 变量及其输入
在程序中可以通过键盘输入，然后根据输入内容来计算结果。程序如下：
程序1-4 A+B问题
#include
int main(){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a+b);
return 0;
}
说明：（1）变量用来存储可变的数据，它像一个筐，什么都往里面装。它只能用来存储事先指定的数据结构。
（2）在scanf语句中，变量a和b前面的&（取地址）符号，不能丢掉。
提示1-3：scanf中的占位符和变量的数据类型应一一对应，且每个变量前需要&符号。
下面来看一个复杂一点的例子。
例1-1 圆柱体的表面积。
输入底面积半径r和高h，输出圆柱体的表面积，保留3位小数，格式见样例。
样例输入：3.5 9
样例输出：Area=274.889
【分析】
圆柱体的表面积=底面积×2+侧面积。根据平面几何知识，底面积=πr2，侧面积=2πrh。完整的程序如下：
程序1-5 圆柱体的表面积
#include
#include
int main(){
const double pi=4.0*atan(1.0);
double r,h,s1,s2,s;
scanf("%lf%lf",&r,&h);
s1=pi*r*r;
s2=2*pi*r*h;
s=s1*2.0+s2;
printf("Area =%.3lf\n",s);
return 0;
}
说明：（1）在程序1-5的语句“const double pi=4.0*atan(1.0);”中，const类型限定修饰符表示把一个对象转换成一个常量（constant），在程序中任何改变这个值的企图都导致编译错误，因此它被称为是只读的（read-only）。由于常量在定义后就不能修改，所以它必须初始化，未初始化的常量定义将导致编译错误。
函数atan()计算数的反正切值，返回角度以弧度表示,也就是就是数学中的反正切函数arctg，由于tg(arctg(1))=1，即arctg(1)=π/4，所以atan(1.0)=0.785398（弧度）≈π/4。
语句“const double pi=4.0*atan(1.0);”就是将常量pi赋值为4.0*0.785398=3.141
593（π的近似值）。
（2）const与#define的比较。
在C/C++语言中，存在两种符号常量：用#define定义的宏常量和用const定义的常量。但后者比前者具有更多的优点：
①#define是预编译伪指令，它定义的宏常量在进入编译阶段前就已经替换为所代表的字面常量，因此宏常量在本质上是字面常量。
const常量有数据类型，而宏常量没有数据类型。编译器可以对它进静态类型安全检查；而对#define常量只进行字符替换，没有类型安全检查，并且在字符替换时可能会产生意料不到的错误（边际效应）。
所以在C++程序中应尽量使用const来定义符号常量，包括字符串常量。
②有些集成化的调试工具可以const常量进行调试，但是不能对宏常量进行调试。
（3）在正规比赛中，题目包含着输入输出格式规定，还有样例数据。
（4）在比赛时，选手程序的执行是自动完成的，没有人工干预。不要在用户输入之前打印提示信息，否则会让程序丢掉大量的分数，因为这些提示信息会被当作输出的数据的一部分。
（5）不会让程序“按任意键退出”（例如在Dev C++中调用system(“pause”)，或者加一个多余的getchar()）。所以千万不要在算法竞赛中这样做。
提示1-4：在算法竞赛中，输入前不要打印提示信息。输出完毕后应立即终止程序，不要等待用户按键，因为输入输出过程都是自动的，没有人工干预。
提示1-5：在算法竞赛中不要使用头文件conio.h，包括getch()，clrscr()。
提示1-6：在算法竞赛中，每行输出均应以回车符结束，包括最后一行。除非特别说明，每行的行首不应空格，但行末通常可以有多余空格。另外，输出的每两个数或者字符串之间应以单个空格隔开。
提示1-7：尽量用const关键字声明常数。
提示1-8：赋值是个动作，先计算右边的值，再赋给左边的变量，覆盖它原来的值。
提示1-9：printf的格式字符串中可以包含其他可打印符号，打印时原样输出。
1.3 顺序结构程序设计
例1-2 三位数反转。
输入一个三位数，分离出它的百位、十位和个位，反转后输出。
样例输入：127
样例输出：721
【分析】
首先将三位数读入变量n，然后进行分离。百位等于n/100（注意这里取的是商的整数部分），十位数等于n/10%10（这里的%是取余数操作），个位数等于n%10。完整的程序如下：
程序1-6 三位数反转（1）
#include
int main(){
int n;
scanf("%d", &n);
printf("%d%d%d\n", n%10, n/10%10, n/100);
return 0;
}
注意：程序1-6的输出结果是025。如果一个数的个位是0，例如输入是520，输出结果是025，还是25，在算法竞赛中如果遇到这个问题，可向监考老师询问。
提示1-10：算法竞赛的题目应当严密的，各种情况下的输出均应有严格规定。如果在比赛中发现题目有漏洞，应当向相关人员询问，而尽量不要自己随意假定。
对程序1-6，如果要输出25，解决办法是在输出结果前把结果存在变量m中，直接用%d 格式输出m，这样可以输出25；如果要输出025，把输出格式变为%03d即可。
程序1-7 三位数反转（2）
#include
int main(){
int n, m;
scanf("%d", &n);
m = (n%10)*100 + (n/10%10)*10 + (n/100);
printf("%03d\n", m);
return 0;
}
例1-3 交换变量。
输入两个整数a和b，交换二者的值，然后输出。
样例输入：824 16
样例输出：16 824
【分析】
按题目的所说，先把变量存入变量a和b，然后交换。最经典的方法是三变量法：
程序1-8 变量交换（1）
#include
int main(){
int a, b, t;
scanf("%d%d", &a, &b);
t = a;
a = b;
b = t;
printf("%d %d\n", a, b);
return 0;
}
提示1-11：赋值a=b之后，变量a原来的值被覆盖，而b的值不变。
另一个方法没有借助任何变量，但较难理解：
程序1-9 变量交换（2）
#include
int main(){
int a, b;
scanf("%d%d", &a, &b);
a = a + b;
b = a - b;
a = a - b;
printf("%d %d\n", a, b);
return 0;
}
说明：程序1-9的功能也是交换两个变量的值（少用了一个中间变量来实现），但实际上很少使用，因为它的适用范围很窄：只有定义了加减法的数据类型才能这么做。
提示1-12：交换两个变量的三变量法适用范围广，推荐使用。
多数算法竞赛采用黑盒测试，即只考查程序解决问题的能力，而不关心它采用的方法，所以三变量法不是解决变量交换的最佳途径，对于本题而言，最合适程序如下：
程序1-10 变量交换（3）
#include
int main(){
int a, b;
scanf("%d%d", &a, &b);
printf("%d %d\n", b, a);
return 0;
}
换句话说，我们的目标是解决问题，而不是为了写程序而写程序，同时应保持简单（Keep It Simple and Stupid，KISS），而不是自己创造条件去展示编程序技巧。
提示1-13：算法竞赛是在比谁更好地解决问题，而不是在比谁写的程序看上去更高级。
1.4 分支结构程序设计
例1-4 鸡兔同笼。
已知鸡和兔的总数量为n，总腿数为m。输入m和n，依次输出鸡的数目和兔的数目。如果无解，则输出“No answer”（不要引号）。
样例输入：14 32
样例输入：12 2
样例输出：10 6
样例输出：No answer
【分析】
设鸡有a只，兔有b只，则a+b=n，2a+4b=m，联立解得a=(4n-m)/2，b=n-a。在本题中，首先，a和b都是整数；其次，a和b必须是非负的。可以通过下面的程序判断：
程序1-11 鸡兔同笼
#include
int main(){
int a, b, n, m;
scanf("%d%d", &n, &m);
a = (4*n-m)/2;
b = n-a;
if(m % 2 == 1 || a < 0 || b < 0)
printf("No answer\n");
else
printf("%d %d\n", a, b);
return 0;
}
在本程序中，用到if语句，其基本格式如提示1-14所示。
提示1-14：if语句的基本格式为：if(条件) 语句1; else 语句2。
在程序1-11中，m%2==1||a<0||b<0是一个逻辑表达式。和算术表达式类似，逻辑表达式也由运符符和值构成，例如“||”运算符称为“逻辑或”，a||b表示a和b只要有一个为真，a||b就为真；如果a和b都为真，则a||b也为真。
提示1-15：if语句的条件是一个逻辑表达式，它的值可能为真，也可能为假。
在逻辑表达式a||b中，只要a为真，无论b的取值为真或假，a||b均为真。换句话说，只要a真，不必计算b的值。C语言正是采取了这样的策略，称为短路（short-circuit）。类似地，逻辑表达式a&&b，也存在这种短路现象，只要a为假，不必计算b的值，结果必为假。
提示1-16：C语言中的逻辑运算符都是短路运算符。一旦能够确定整个表达式的值，就在再继续计算。
课堂小练习1写出下列各逻辑表达式的值（真为 1，假为 0），设 a=3, b=4, c=5。
（1）a+b>c && b==c
答案：由于b==c为假，所以剩下的就不用计算了。
（2）a || b+c && b-c
答案：1，由于a为真，所以剩下的就不用计算了。
（3）!(a>b) && !c || 1
答案：1，由于1为真，所以剩下的就不用计算了。
（4）!(x=a) && (y=b) && 0
答案：0，由于0为假，所以剩下的就不用计算了。
（5）!(a+b)+c-1 && b+c/2
答案：0，!(a+b)+c-1为假，所以剩下的就不用计算了。
例1-5 三整数排序。
输入3个整数，从小到大排序后输出。
样例输入：20 7 33
样例输入：7 20 33
【分析】
a、b、c3个数一共只有6种可能的顺序：a b c、a c b、b a c、b c a、c a b、c b a，所以最简单的思路是使用6条if语句。
程序1-12 三整数排序（1）（错误）
#include
int main(){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(a < b && b < c) printf("%d %d %d\n", a, b, c);
if(a < c && c < b) printf("%d %d %d\n", a, c, b);
if(b < a && a < c) printf("%d %d %d\n", b, a, c);
if(b < c && c < a) printf("%d %d %d\n", b, c, a);
if(c < a && a < b) printf("%d %d %d\n", c, a, b);
if(c < b && b < a) printf("%d %d %d\n", c, b, a);
return 0;
}
注意：在程序1-12中，如果输入1 1 1将得不到任何输出。所以编写出来的程序，即使通过了题目中给出的样例，程序仍然可能存在问题。
提示1-17：算法竞赛的目标是编程对任意输入均得到正确的结果，而不仅是样例数据。
对于上面出现的错误，它的解决方案是人为地让6种情况没有交叉：把所有的if改成else if。
程序1-13 三整数排序（2）
#include
int main(){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(a <= b && b <= c) printf("%d %d %d\n", a, b, c);
else if(a <= c && c <= b) printf("%d %d %d\n", a, c, b);
else if(b <= a && a <= c) printf("%d %d %d\n", b, a, c);
else if(b <= c && c <= a) printf("%d %d %d\n", b, c, a);
else if(c <= a && a <= b) printf("%d %d %d\n", c, a, b);
else if(c <= b && b <= a) printf("%d %d %d\n", c, b, a);
return 0;
}
提示1-18：如果有多个并列、情况不交叉的条件需要一一处理，可以用else if语句。
另一种思路是把a、b、c这3个变量本身改成a≤b≤c的形式。首先检查a和b的值，如果a>b，则交换a和b（利用前面进过的三变量交换法）；接下来检果a和c，最后检查b 和c，程序如下：
程序1-14 三整数排序（3）
#include
int main(){
int a, b, c, t;
scanf("%d%d%d", &a, &b, &c);
if(a > b) { t = a; a = b; b = t; }
if(a > c) { t = a; a = c; c = t; }
if(b > c) { t = b; b = c; c = t; }
printf("%d %d %d\n", a, b, c);
return 0;
}
注意：程序1-14的检查顺序不可颠倒。例如，先判断a>b，然后b>c，最后a>c是不可以的。假如输入3 2 1，则结果为2 1 3。
提示1-19：可以用花括号把若干条语句组成一个整体（复合语句）。这些语句仍然按顺序执行。
最后一种思路再次利用了“问题求解”这一目标——它实际上并没有真的进行排序：求出了最小值和最大值，中间值是可以计算出来的。
程序1-15 三整数排序（4）
#include
int main(){
int a, b, c, x, y, z;
scanf("%d%d%d", &a, &b, &c);
x = a
x = a; if(b < x) x = b; if(c < x) x = c;
z = a; if(b > z) z = b; if(c > z) z = c;
y = a + b + c - x - z;
printf("%d %d %d\n", x, y, z);
return 0;
}
注意：程序1-15中包含了的“当前最小值”x和“当前最大值”z。它们初始化为a，但是随着“比较”操作的进行而慢慢更新，最后变成真正的最小值和最大值。这个技巧极为实用。
提示1-20：在难以一次性求出最后结果时，可以用变量储存“临时结果”，从而逐步更新。
1.5 C/C++编码规范
一个好的程序，不仅要算法正确，效率高，而且还应该可读性好。所谓程序的可读性，就是程序是否能让人容易读懂。在开发实践中，许多情况下可读性与代码效率同等重要。
软件开发是团队工作，接手别人编码的程序并在此基础上进行改进是必不可少的，因此可读性在工程实践中非常重要。即使是自己编写的程序，如果可读性不好，过一段时间需要改进时自己再看，也常会看不懂。
如何提高程序的可读性呢？在标识符、书写格式、注释三个方面加以培养，再养成一些好的习惯，就能够有效增强程序的可读性。
1.5.1 标识符命名注意事项
应该对变量、常量以及函数等标识进行适当的命名。好的命名方法使标识符易于记忆且使程序可读性大大提高。
对标识符命名的基本要求是，看到标识符就能想起或猜出它是做什么用的。如果名字能体现变量的类型或作用域等性质，当然更好。标识符命名应注意以下几点：（1）标识符号应能提供足够信息以说明其用途。一定不要怕麻烦而懒得起足够长的变量名，少按几个键省下的时间，和日后自己读程序或别人读你的程序揣摩该变量的作用所花的时间相比，实在微不足道。在没有国标合作的项目中编写程序，如果英语实在不好，可以使用拼音，但不要使用拼音缩写。
（2）为全局变理取长的、描述信息多的名字，为局部变量限稍短的名字。
（3）名字太长时可以适当采用单词的缩写。但要注意缩写方式一致，要缩写就全部缩写。比如单词Number，如果在某个变量里缩写成了：
int nDoorNum;
那么最好包含Number单词的变量都缩写成Num。
（4）注意使用单词的复数形式。如
int nTotalStudents,nStudents;
nStudents容易让人理解成代表学生数目，而nStudent含义就不十分明显。
（5）对于返回值为真或假的函数，加“IS”前缀如：
int IsCanceled();
int isalpha(); //C语言标准库函数
BOOL IsButtonPushed();
1.5.2 程序的书写格式
书写格式好的程序，看起来才有好心情，谁也不愿意看下面这样的程序：
void main()
{
int t, x, y;
cin>>t;
while (t>0)
{
min=60000;
cin>>N>>x>>y>>max; plat[0].x1=x;
plat[0].x2=x; plat[0].h=y;
for (int i=1;i<=N;i++)
{
cin>>plat[i].x1>>plat[i].x2>>plat[i].h;
plat[i].t1=-1;
plat[i].t2=-1;
if (plat[i].h>y) {i--; N--; }
}
plat[0].t1=0;plat[0].t2=0;
qsort((void*)(&plat[1]), N, sizeof(plat[0]), compare);
tryway(0);
t--;
cout< } } 因此，如果想要让你的程序看起来赏心悦目，应该注意以下几点： （1）正确使用缩进 首先，一定要有缩进，否则代码的层次不明显。缩进应为4 个空格较好。需要缩进时一律按Tab 键，或一律按空格键，不要有时用Tab 键缩进，有时用空格键缩进。一般开发环境都能设置一个Tab 键相当于多少个空格，此时就都用Tab 键。 （2）行宽与折行 一行不要太长，不能超过显示区域，以免阅读不便。太长则应折行，折行最好发生在运算符前面，不要发生在运算符后面。如 if(Condition1() && Condition2() && Condition3()) { } 3)‘{’, ‘}’位置不可随意放置。 建议将‘{’放在一行的右边，而将‘}’单独放置一行。如： if(condition1()) { DoSomething(); } 比较 if(condition1()) { DoSomething(); } 这种写法，前者既不影响可读性，又能节省一行。 但是对于函数体或结构定义的的第一个‘{’，还是单独一行更为清晰。 （4）变量和运算符之间最好加1个空格，如： int nAge = 5; nAge = 4; if(nAge >= 4) printf(“%d”, nAge); for(i = 0; i < 100; i++); 1.5.3 注释的写法 在工程实践中，文件开头，全局变量定义处，函数开头，都应该有注释。 文件开头的注释模板如下： /****************************************************************** ** 文件名: ** Copyright (c) 1998-1999 *********公司技术开发部 ** 创建人: ** 日期: ** 修改人: ** 日期: ** 描述: ** ** 版本: **--------------------------------------------------------------------------- ******************************************************************/ 函数开头的注释模板如下： /***************************************************************** ** 函数名: ** 输入: a,b,c ** a--- ** b--- ** c--- ** 输出: x--- ** x为1, 表示... ** x为0, 表示... ** 功能描述: ** 用到的全局变量: ** 调用模块: ** 作者: ** 日期: ** 修改: ** 日期: ** 版本 ****************************************************************/ 本书由于篇幅所限，书中程序略去了文件开始处和函数开始处的注释。 1.5.4 一些好的编程习惯 （1）尽量不要用立即数，而用#define 定义成常量，以便以后修改。例如： #define MAX_STUDENTS 20 struct SStudent aStudents [MAX_STUDENTS]; 比 struct SStudent aStudents [20]; 好。 再例如： #define TOTAL_ELEMENTS 100 for(i = 0; i < TOTAL_ELEMENTS; i++) { } （2）使用sizeof()，不直接使用变量所占字节数的数值。如应该写成： int nAge; for(j = 0; j < 100; j++ ) fwrite(fpFile, & nAge, 1, sizeof(int)); 不应该写： for( j = 0; j < 100; j++ ) fwrite( fpFile, & nAge, 1, 4); （3）稍复杂的表达式中要积极使用括号，以免优先级理解上的混乱以及二义性。 n = k++ + j; //不好 n = (k++) + j; //好一点 （4）不很容易理解的表达式应分几行写： n = (k++) + j;应该写成： n = k + j; k++; （5）嵌套的if else 语句要多使用 { } if(Condition1()) if(condition2()) DoSomething(); else NoCondition2(); 不够好，应该： if(Condition1()) { if(condition2()) DoSomething(); else NoCondition2(); } （6）单个函数的程序行数最好不要超过100 行（两个屏幕高）。 （7）尽量使用标准库函数。 （8）不要随意定义全局变量，尽量使用局部变量。 （9）保持注释与代码完全一致，改了代码别忘改注释。 （10）循环、分支层次最好不要超过5层。 （11）注释可以与语句在同一行，也可以在上行。 （12）一目了然的语句不加注释。 1.6 小结与习题 通过前几个小节的学习，对顺序结构程序设计和分支程序设计的核心概念和方法，然而对这些进行知识进行总结，并且完成适当的练习是很有必要的。 1.6.1 数据类型实验 实验A1：表达式11111*11111的值是多少？把5个1改为6个1呢？9个1呢？ 解答：（1）计算表达式11111*11111的值 #include int main(){ printf("11111*11111=%ld",11111*11111); return 0; } 程序的运行结果为11111*11111=123454321。 （2）计算表达式111111*111111的值 只须将（1）中的printf语句改为printf("111111*111111=%ld",111111*111111);，程序的运行结果为111111*111111=-539247567。正确的结果应为12345654321，由于这个数比较大，所以产生了溢出。 （3）计算表达式111111111*111111111的值 只须将（1）中的printf改为printf("111111111*111111111=%ld ",111111111*1111111 11);，程序的运行结果为111111111*111111111=1653732529。正确的结果应为12345678987 654321，由于这个数比较大，所以产生了溢出。 实验A2：把实验A1中的所有数换成浮点数，结果如何？ 解答：（1）计算表达式11111.0*11111.0的值 #include int main(){ printf("11111.0*11111.0=%lf",11111.0*11111.0); return 0; } 程序的运行结果为11111*11111=123454321.000000。 （2）计算表达式111111.0*111111.0的值 只须将（1）中的printf语句改为printf("11111*11111=%lf",11111*11111);，程序的运行结果为111111.0*111111.0=12345654321.000000。 （3）计算表达式111111111.0*111111111.0的值 只须将（1）中的printf改为printf("111111111.0*111111111.0=%lf ",111111111.0 *111111111.0);，程序的运行结果为111111111.0*111111111.0=12345678987654320.00000 0。 实验A3：表达式sqrt(-10)的值是多少？尝试用种方法输出。在计算过程中系统会报错吗？ 解答： #include #include int main(){ printf("sqrt(-10)=%lf",sqrt(-10)); return 0; } 程序的运行结果为sqrt(-10)=-1.#IND，没有报错，但结果异常。 实验A4：表达式1.0/0.0、0.0/0.0的值是多少？尝试用种方法输出。在计算过程中系统会报错吗？ 解答： #include int main(){ printf("1.0/0.0=%lf 0.0/0.0=%lf",1.0/0.0,0.0/0.0); return 0; } 输出结果为1.0/0.0=1.#INF 0.0/0.0=-1.#IND。在计算过程中系统会报错，提示信息为“divdide or mod by zero”。 实验A5：表达式1/0的值是多少？在计算过程中系统会报错吗？ 解答：表达式1/0的值无结果。在计算过程中系统会报错，提示信息为“divdide or mod by zero”。 1.6.2 scanf输入格式实验 scanf("%d%",&a,%b);语句用来输入两个数，可用Tab、空格、回车，作为分隔符。 实验B1：在同一行中输入12和2，并以空格分隔，是否得到了预期的效果？ 解答： #include void main() { int a,b; scanf("%d%d",&a,&b); printf("%d, %d\n",a,b); return; } 从键盘上输入：12 2↙，可以达到输入两个数给变量a和b的效果。 实验B2：在不同的两行中输入12和2，是否得到了预期的效果？ 解答： 从键盘上输入：12↙ 2↙，也可以达到输入两个数给变量a和b的效果。。 实验B3：在实验B1和B2中，在12和2的前面和后面加入大量的空格或水平制表符（TAB），甚至插入一些空行。 解答：从键盘上输入的12和2，也可以前面和后面加入大量的空格或水平制表符（TAB），甚至插入一些空行，达到输入两个数给变量a和b的效果。 实验B4：把2换成字符s，重复实验B1～B3。 解答：从键盘上输入：12 2↙，而输出的结果为12 -85899360。 1.6.3 printf语句输出实验 在printf语句中的格式字符串，决定了数据的输入/输出格式。 实验C1：仅用一条printf语句，打印1+2和3+4，用两个空行隔开。 解答： #include void main() { printf("%d\n\n%d",1+2,3+4); return; } 实验C2：试着把%d中的两个字符（百分号和小写字）。 解答： #include void main() { printf("%%d\n"); return; } 实验C3：试着把\n中的两个字符（反斜线和小写字母n）输出到屏幕。 解答： #include void main() { printf("\\n"); return; } 实验C4：像C2、C3那样也需要“特殊方法”才能输出的东西还有哪些？哪些是printf 函数引起的问题，哪些不是？ 解答：输出单引号和双引号需要用\’和\"。 1.6.4 测试你的实践能力 问题1：int型整数的最小值和最大值是多少？（需要精确度）。 解答：（1）方法一 #include #include int main() { int a,b; a=-pow(2,31); b=pow(2,31)-1; printf("%d %d\n",a,b); return 0; } 注意：在TC中int型整数（2字节）的最小值和最大值分别为-32768和32767；在VC6.0中int型整数（4字节）的最小值和最大值分别为-2147483648和2147483647，所以不同的编译系统为整型数据分配的字节数是不相同的。本题程序是在VC6.0中调试的。 （2）方法二 #include #include int main() { int a,b; a=INT_MAX; b=INT_MIN; printf("%d %d\n",a,b); return 0; } 说明：头文件limits.h中定义了用于表示整数类型大小的常量（宏定义）。 （1）如果在C：盘上有TC，就可以在“c:\TC”用记事本打开头文件limits.h，可以找到“#define INT_MAX 0x7FFF”和“#define INT_MIN ((int)0x8000)”。INT_MAX表示在TC中表示最大整数，0x7FFF就是32767；INT_MIN表示在TC中表示最小整数，(int)0x8000就是-32768。 （2）如果在C：盘装有VC6.0，就可以在“C:\Program Files\Microsoft Visual Studio\VC98\Include”用记事本打开头文件limits.h，可以找到“#define INT_MIN (-2147483647-1) /* minimum (signed) int value */”和“#define INT_MAX 2147483647 /* maximum (signed) int value */”。INT_MAX表示在VC6.0中表示最大整数是2147483647；INT_MIN表示在TC中表示最小整数是-2147483648。 问题2：double型浮点数能精确到多少位小数？或者，这个问本身值得商榷？ 解答： #include int main() { double a; a=123.0; printf("%lf\n",a); return 0; } double型浮点数隐含输出小数位数为6位，不过还可以通printf("%.20lf\n",a);来重新设置，.20中的20也可以换成其它的数值。 问题3：double型浮点数最大正数值和最小正数值分别是多少？ 解答： #include int main() { int y = 1030; for (double x = 0.999999999; y-- ; x *= 2) cout << x << '\t'; cout << endl; y = 1030; for (x = 0.000000001; y-- ; x /= 2) cout << x << '\t'; cout << endl; return 0; } 由程序可得，double型浮点数最大正数值和最小正数值分别是1.79769e+308、1.73832e -319。 问题4：逻辑运算符号&&、||和!（它表示逻辑非）的相对优先级是怎样的？也就是说，a&&b||c应理解成(a&&b)||c还是a&&(b||c)，或者随便怎么理解都可以？ 解答：逻辑运算符号&&、||和!（它表示逻辑非）的相对优先级（由高到低）是!→ &&→||。a&&b||c应理解为(a&&b)||c。 问题5：if(a) if(b) x++; else y++;的确切含义是什么？这个else应和哪个if配套？有没有办法明确表达出配套方法，以避免初学者之困惑？ 解答： if(a) if(b) x++; else y++; 可以换成以下的形式： if(a) if(b) x++; else y++; else与if的配对的原则是else一般与最近没有配对的if进行配对。实际上，如果else 与第一个if进行配对，可以采取加{}的方式进行： if(a) { if(b) x++;} else y++; 如果else与第二个if进行配对，可以采取加{}的方式进行： if(a){ if(b) x++; else y++; } 以上这种加{}的方式，就不会引起歧义。 1.6.5 小结 （1）本章介绍了常见的各种数据类型，以及他们所能表达的范围； （2）本章介绍了scanf和printf语句的使用； （3）本章介绍了逻辑判断的使用，理解并描述复杂的逻辑判断。 （4）程序设计是一门实践性很强学科，所以在学习时，给出两点建议：重视实验、学会模仿。 1.6.6 上机练习 程序设计是一门实践性很强的学科，所以给出下面的练习。 习题1-1 平均数（average） 输入3个整数，输出它们的平均值，保留3位小数。 解答： #include int main() { int a,b,c; double d; scanf("%d%d%d",&a,&b,&c); d=(double)(a+b+c); printf("%.3lf\n",d/3.0); return 0; } 习题1-2 温度（temperature） 输入华式温度f，输出对应的摄氏温度c，保留3位小数。提示：c=5(f-32)/9。 解答： #include int main() { int f; double c; scanf("%d",&f); c=5*(f-32)/9; printf("%.3lf\n",c); return 0; } 习题1-3 连续和（sum） 输入正整数n，输出1+2+…+n的值。提示：目标是解决问题，而不是练习编程。 解答： #include int main() { int n; scanf("%d",&n); printf("%d\n",(1+n)*n/2); return 0; } 注意：本题利用了等差数列的公式，而不是像平常编程时，用循环来实现。 习题1-4 余弦和正弦（sincos） 输入正整数（n<360），输出n度的正弦、余弦函数值。提示：使用数学函数。 解答： #include #include int main() { const double pi = 3.1415926; int n; /* n是角度 */ scanf("%d",&n); printf("sin(n)=%lf\n",sin((n/180.0)*pi)); printf("cos(n)=%lf\n",cos((n/180.0)*pi)); return 0; } 习题1-5 距离（distance） 输入4个浮点数x1，y1，x2，y2，输出平面坐标系中点(x1，y1)和点(x2，y2)的距离。 解答： #include #include int main() { double x1,x2,y1,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); printf("%lf\n",sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); return 0; } 习题1-6 偶数（odd） 输入一个整数，判断它是否为偶数。如果是，则输出“yes”，否则输出“no”。提示：可以用多种方法判断。 解答： #include int main(){ int n; scanf("%d",&n); if(n%2==0){ printf("YES\n"); } else{ printf("NO\n"); } return 0; } 习题1-7 打折（discount） 一件衣服95元，若消费满300元，可打八五折。输入购买衣服件数，输出需要支付的金额（单位：元），保留两位小数。 解答： #include int main() { int n; double a; scanf("%d",&n); a=n*95.0; if(a<300){ printf("%.2lf\n",a); } else{ printf("%.2lf\n",a*0.85); } return 0; } 习题1-8 绝对值（abs） 输入一个浮点数，输出它的绝对值，保留两位小数。 解答： #include #include int main() { double n; scanf("%lf",&n); printf("%.2lf",fabs(n)); return 0; } 习题1-9 三角形（triangle） 输入三角形三边长度值（均无正整数），判断它是否能为直角三角形的三个边长。如果可以，则输出“yes”，如果不能，则输出“no”。如果根本无法构成三角形，则输出“not a triangle”。 解答： #include int main() { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(a==b&&b==c) { printf("no\n"); } if((a*a+b*b==c*c)||(a*a+c*c==b*b)||(b*b+c*c==a*a)) { printf("yes\n"); } else { printf("no\n"); } return 0; } 习题1-10 年份（year） 输入年份，判断是否为闰年。如果是，则输出“yes”，否则输出“no”。提示：简单地判断除以4的余数的是不够的。 解答： #include int main() { int n; scanf("%d",&n); if(n%4==0) { if(n%100!=0) { printf("no\n"); } else { if(n%400==0) { printf("yes\n"); } else{ printf("no\n"); } } } else { printf("no\n"); } return 0; } 布置作业 上机练习习题1-7、1-8、1-9、1-10 #《算法竞赛入门经典》勘误 关于勘误?下面的勘误很多来自于热心读者，再次向他们表示衷心的感谢！我并不清楚这些错误实际是在哪个版本中改正过来的，所以麻烦大家都看一下。 有发现新错误的欢迎大家在留言中指出，谢谢！ 一些一般性的问题?运算符?已经被废弃，请用min、max代替（代码仓库中的代码已更新，g++ 4.6.2下编译通过） 重大错误?p24. 最后一行，“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而min=INF”。 (感谢imxivid） p43. 最后，判断s[i..j]是否为回文串的方法也不难写出：int ok = 1; for(k = i; i<=j; i++)应该为for(k = i; k<=j; k++) (感谢imxivid） p45. 第七行和第九行i-j+1应为i+j+1。修改后： 1. { 2. for (j = 0; i - j >= 0 && i + j < m; j++) 3. { 4. if (s[i - j] != s[i + j]) break; 5. if (j*2+1 > max) { max = j*2+1; x = p[i - j]; y = p[i + j];} 6. } 7. for (j = 0; i - j >= 0 && i + j + 1 < m; j++) 8. { 9. if (s[i - j] != s[i + j + 1]) break; 10. if (j*2+2 > max) 11. {max = j*2+2; x = p[i - j]; y = p[i + j + 1]; } 12. } 13. }p53. 例题4-1. 组合数. 输入非负整数n和m，这里的n和m写反了。应是“输入非负整数m和n”。 p54. 举例中的m和n也写反了（真是个悲剧），且C(20,1)=20。 p71. 《周期串》代码的第8行，j++应为i++。 p72. 代码的第7行，“return”改为“break”以和其他地方一致。 p81. k为奇数和偶数的时候，分子和分母的顺序是不一样的。正确代码为： #include 第一章习题1-1 #include 习题1-3 #include 习题1-5 #include 大师兄教你如何过华为机试 宝典1—内功心法 大华为这个大数据时代土豪金海量式的招聘又要开始了！！！ 近期听说大华为的校招机试马上就要开始了，由于华为软件岗位的招聘只有技术面跟机试是与技术有关的内容，所以机试的地位非常重要。对于机试，除了长期积累的软件基本功以外，还有很多可以短期训练的东西，类似于考试之前的突击，可以迅速提高机试成绩，就像在我西电大杨老师考前最后一堂课一定要去，那个重点就是考点阿。 这篇机试葵花宝典的内容是针对华为软件类上机准备的，如果你认真看了本宝典,如果你是真正通过自己能力考上西电的话,想不过都难。同样想拿高级题的同学，请移步 https://www.doczj.com/doc/ef18816436.html,/land/或者https://www.doczj.com/doc/ef18816436.html,，刷上200道题，机试不想拿满分都难。 对于机试，首先应该调整好自己的心态，不要觉得写程序很难，机试题很难，也不要去考虑，万一机试考到自己不会的内容怎么办，要相信，机试题永远是考察每个人的基础，基础是不会考的很偏的，会有人恰好做过某个题而做出来那个题，但不会有人恰好没做过一个题而做不出来那个题。 机试之前，应该做的准备有： 1、买一本《算法竞赛入门经典》，这本书不同于普通的算法或者编程语言的书籍，这 本书既讲语言，又讲算法，由浅入深，讲的很好，能看完前几章并且把例题都做 会，想通过机试就很简单了 2、调整好心态，时刻告诉自己，哪些小错误是自己以前经常犯的，最好用笔记本记录 下来，写每道题前再看一遍，如果遇到代码调不出来了，先想想自己是否犯过以 前那些错误。还有就是，看了题目以后，先仔细想清楚细节，在纸上写清楚自己 需要用到的变量，以及代码的基本框架，不要急于动手去写代码 3、不要惧怕任何一道看起来很难的题目，有不会的就去问身边会的人，让别人给自己 讲清楚 4、心中默念10遍C++跟C除了多了两个加号其实没有区别，会C就能上手C++ 5、大量的练习是必要且有效的 6、看完这篇宝典，预过机试、必练此功。 在这里推荐一个帖子，是机试归来的学长写的，写的很不错，里面的例题在后面的攻略 信息学奥赛（NOIP）必看经典书目汇总！ 小编整理汇总了一下大神们极力推荐的复习资料！（欢迎大家查漏补缺） 基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》（推荐指数：4颗星） 曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。语言是pascal的。 2、谭浩强老先生写的《C语言程序设计（第三版）》（推荐指数：5颗星） 针对零基础学C语言的筒子，这本书是必推的。 3、《骗分导论》（推荐指数：5颗星） 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程（一）》（推荐指数：5颗星） 传说中的黄书。吴文虎，王建德著，系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著，传说中的红书。 6、《算法竞赛入门经典》（推荐指数：5颗星） 刘汝佳著，算法必看经典。 7、《算法竞赛入门经典:训练指南》（推荐指数：5颗星） 刘汝佳著，《算法竞赛入门经典》的重要补充 提高篇 1、《算法导论》（推荐指数：5颗星） 这是OI学习的必备教材。 2、《算法艺术与信息学竞赛》（推荐指数：5颗星） 刘汝佳著，传说中的黑书。 3、《学习指导》（推荐指数：5颗星） 刘汝佳著，《算法艺术与信息学竞赛》的辅导书。（PS：仅可在网上搜到，格式为PDF）。 4、《奥赛经典》（推荐指数：5颗星） 有难度，但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星） 历年真题，这是绝对不能遗失的存在。必须要做！ 三、各种在线题库 1、题库方面首推USACO（美国的赛题），usaco写完了一等基本上就没有问题，如果悟性好的话甚至能在NOI取得不错的成绩. 2、除此之外Vijos也是一个不错的题库，有很多中文题. 3、国内广受NOIP级别选手喜欢的国内OJ（Tyvj、CodeVs、洛谷、RQNOJ） 4、BJOZ拥有上千道省选级别及以上的题目资源，但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高，命题人大多为现役集训队选手。 424-Integer Inquiry One of the first users of BIT's new supercomputer was Chip Diller.He extended his exploration of powers of3to go from0 to333and he explored taking various sums of those numbers. ``This supercomputer is great,''remarked Chip.``I only wish Timothy were here to see these results.''(Chip moved to a new apartment,once one became available on the third floor of the Lemon Sky apartments on Third Street.) Input The input will consist of at most100lines of text,each of which contains a single VeryLongInteger.Each VeryLongInteger will be100or fewer characters in length,and will only contain digits(no VeryLongInteger will be negative). The final input line will contain a single zero on a line by itself. Output Your program should output the sum of the VeryLongIntegers given in the input. Sample Input 123456789012345678901234567890 123456789012345678901234567890 123456789012345678901234567890 Sample Output 370370367037037036703703703670 10106–Product The Problem The problem is to multiply two integers X,Y.(0<=X,Y<10250) The Input The input will consist of a set of pairs of lines.Each line in pair contains one multiplyer. The Output For each input pair of lines the output line should consist one integer the product. Sample Input 12 12 2 222222222222222222222222 Sample Output 144 444444444444444444444444 465–Overflow Write a program that reads an expression consisting of two non-negative integer and an operator.Determine if either integer or the result of the expression is too large to be represented as a``normal''signed integer(type integer if you are working Pascal,type int if you are working in C). Input An unspecified number of lines.Each line will contain an integer,one of the two operators+or*,and another integer. Output For each line of input,print the input followed by0-3lines containing as many of these three messages as are appropriate: ``first number too big'',``second number too big'',``result too big''. Sample Input 300+3 9999999999999999999999+11 Sample Output 300+3 9999999999999999999999+11 first number too big 算法工程师成长计划 大学期间必须要学好的课程：C/C++两种语言（或JA V A）、高等数学、线性代数、数据结构、离散数学、数据库原理、操作系统原理、计算机组成原理、人工智能、编译原理、算法设计与分析。 大一上学期： 1.C语言基础语法必须全部学会，提前完成C语言课程设计。 2.简单数学题：求最大公约数、筛法求素数、康托展开、同余定理、次方求模等。 3.计算机课初步：三角形面积，三点顺序等等。 4.学会计算简单程序的时间复杂度和空间复杂度。 5.二分查找、贪心算法经典算法。 6.简单的排序算法：冒泡排序法、插入排序法。 7.高等数学。 8.操作系统应用：DOS命令，学会Windows系统的一些小知识，学会编辑注册表， 学会使用组策略管理器（gpedit.msc）管理组策略等。 大一下学期： 1.掌握C++部分语法，如引用类型、函数重载等，基本明白什么是类。 2.学会使用栈和队列等线性结构。 3.掌握BFS和DFS以及树的前序、中序、后序遍历。 4.学会分治策略。 5.掌握排序算法：选择排序、归并排序、快速排序、计数、基数排序等等。 6.动态规划：最大子串和、最长公共子序列、最长单调递增子序列、01背包、完全背 包等。 7.数论：扩展欧几里德算法、求逆元、同余方程、中国剩余定理。 8.博弈论：博弈问题与SG函数的定义、多个博弈问题SG值的合并。 9.图论：图的存储、欧拉回路的判定、单源最短路Bellman-Ford算法及Dijkstra算法、 最小生成树Kruskal算法及Prim算法。 10.学会使用C语言进行网络编程与多线程编程。 11.高等数学、线性代数：做几道“矩阵运算”分类下的题目。 12.学习matlab，如果想参加数学建模大赛，需要学这个软件。 大一假期： 1.掌握C++语法，并熟练使用STL（重要）。 2.试着实现STL的一些基本容器和函数、使自己基本能看懂STL源码。 3.数据结构：字典树、并查集、树状数组、简单线段树。 4.图论：使用优先队列优化Dijkstra算法及Prim算法，单源最短路径之SPFA，差分 约束系统，多源多点最短路径之FloydWarshall算法，求欧拉回路（圈套圈算法）。 5.拓扑排序：复杂BFS和DFS搜索、复杂模拟题训练。 6.动态规划：多重背包、分组背包、依赖背包等各种背包问题（参见背包九讲）。 7.计算几何：判断点是否在线段上、线段相交、圆与矩形的关系、点是否在多边形内、 点到线段的最近点、多边形面积、求多边形重心、求凸包、点在任意多边形内外的 判定。 8.学习使用C/C++连接数据库、学习一种C++的开发框架来编写一些窗体程序（如 MFC、Qt）。 第7章暴力求解法 【教学内容相关章节】 7.1简单枚举 7.2枚举排列 7.3子集生成 7.4回溯法 7.5隐式图搜索 【教学目标】 （1）掌握整数、子串等简单对象的枚举方法； （2）熟练掌握排列生成的递归方法； （3）熟练掌握用“下一个排列”枚举全排列的方法； （4）理解解答树，并能估算典型解答树的结点数； （5）熟练掌握子集生成的增量法、位向量法和二进制法； （6）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效； （7）熟练掌握解答树的宽度优先搜索和迭代加深搜索； （8）理解倒水问题的状态图与八皇后问题的解答树的本质区别； （9）熟练掌握八数码问题的BFS实现； （10）熟练掌握集合的两种典型实现——hash表和STL集合。 【教学要求】 掌握整数、子串等简单对象的枚举方法；熟练掌握排列生成的递归方法；熟练掌握用“下一个排列”枚举全排列的方法；理解子集树和排列树；熟练掌握回溯法框架；熟练掌握解答树的宽度优先搜索和迭代搜索；熟练掌握集合的两种典型实现——hash表和STL集合。【教学内容提要】 本章主要讨论暴力法（也叫穷举法、蛮力法），它要求调设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。介绍了排列生成的递归方法；在求解的过程中，提出了解答树的概念（如子集树和排列树）；介绍了回溯法的基本框架；介绍了集合的两种典型实现——hash表和STL集合。 【教学重点、难点】 教学重点： （1）熟练掌握排列生成的递归方法； （2）理解解答树，并能估算典型解答树的结点数； （3）熟练掌握子集生成的增量法、位向量法和二进制法； （4）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效； （5）熟练掌握解答树的宽度优先搜索和迭代搜索； （6）熟练掌握集合的两种典型实现——hash表和STL集合。 教学难点： （1）熟练掌握子集生成的增量法、位向量法和二进制法； （2）熟练掌握回溯法框架，并能理解为什么它往往比生成-测试法高效； （3）熟练掌握解答树的宽度优先搜索和迭代搜索； （4）熟练掌握集合的两种典型实现——hash表和STL集合。 【课时安排】 7.1简单枚举 7.2枚举排列 7.3子集生成 7.4回溯法 7.5隐式图搜索 第6章数据结构基础 【教学内容相关章节】 6.1栈和队列 6.2链表 6.3二叉树 6.4图 【教学目标】 （1）熟练掌握栈和队列及其实现； （2）了解双向链表及其实现； （3）掌握对比测试的方法； （4）掌握随机数据生成方法； （5）掌握完全二叉树的数组实现； （6）了解动态内存分配和释放方法及其注意事项； （7）掌握二叉树的链式表示法； （8）掌握二叉树的先序、后序和中序遍历和层次遍历； （9）掌握图的DFS及连通块计数； （10）掌握图的BFS及最短路的输出； （11）掌握拓扑排序算法； （12）掌握欧拉回路算法。 【教学要求】 掌握栈和队列及其实现；掌握对比测试的方法；掌握随机数据生成方法；掌握完全二叉树的数组实现和链式表示法；掌握二叉树的先序、后序和中序遍历和层次遍历；掌握图的DFS和BFS遍历；掌握拓扑排序算法；掌握欧拉回路算法。 【教学内容提要】 本章介绍基础数据结构，包括线性表、二叉树和图。有两种特殊的线性表：栈和队列。对于树型结构主要讨论二叉树，还有二叉树的先序、中序和后序的遍历方式。对于图主要讨论图的DFS和BFS的遍历方法。这些内容是很多高级内容的基础。如果数据基础没有打好，很难设计正确、高效的算法。 【教学重点、难点】 教学重点： （1）掌握栈和队列及其实现； （2）掌握对比测试的方法； （3）掌握随机数据生成方法； （4）掌握完全二叉树的数组实现和链式表示法； （5）掌握二叉树的先序、后序和中序遍历和层次遍历； （6）掌握图的DFS和BFS遍历； （7）掌握拓扑排序算法和欧拉回路算法。 教学难点： （1）掌握完全二叉树的数组实现和链式表示法； （2）掌握二叉树的先序、后序和中序遍历和层次遍历； （3）掌握图的DFS和BFS遍历； （4）掌握拓扑排序算法和欧拉回路算法。 【课时安排（共9学时）】 6.1栈和队列 6.2链表 6.3二叉树 6.4图 求int的上限与下限#include return 0; } 1-3 #include 求int的上限与下限 #include return 0; } 1-3 #include 第一章程序设计入门 1.1算术表达式 ?大小写字母代表的含义不同 ?整数值用%d输出，实数用%lf,小数点位数可以用%.nf中的n来控制 ?整数/整数=整数浮点数/浮点数=浮点数 1.2变量及其输入 ?可以通过scanf来输入数据，但是要注意每个变量前需要&符号。 ?比赛时不需编写提示信息。 ?不要让程序“按任意键退出”，即在程序的最后写入 return0; 尽量用const关键字声明变量 1.3顺序结构程序设计 ?注意数据的分离。准确的使用/和% ?十进制：非0数字打头 ?竞赛目标：解决问题 1.4分支结构程序设计 ?情况考虑周全，不仅仅是样例数据 1.5小结与习题 1.5.1数据类型实验 ?A1A2注意数据范围，数值太大，用double表示时，最好将数据换成浮点型?A3负数不能开方，计算过程中系统不会报错，最后结果是错误结果 ?A4编译报错 ?A5编译报错 1.5.2scanf输入格式实验 ?B1B2可以得到预期结果 ?B3前后插入大量空格或者水平制表符或者空格都可以 ?B4只能正常输出12，字符无法输出 1.5.3printf语句输出实验 ?C1两个空行：\n\n ?C2%%d ?C3\\n ?转义字符 1.5.4测测你的实践能力 问题1： 问题2、3： 问题4：！14级&&5级||4级问题5：if(a) {if(b)x++; else y++; } 1.5.6上机练习 习题1-1平均数 注意将整数换成实数 习题1-2温度 可直接将f定义成float类型 习题1-3连续和 注意求和公式（a1+an）*n/2 习题1-4正弦和余弦 注意将数值转换成角度，n*pa/180 习题1-5距离 距离公式sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))习题1-6偶数 x%2==0 x==(x/2)+(x/2) (x+1)%2==1 算法竞赛入门竞赛 第1章程序设计入门 学习目标 ?熟悉C语言程序的编译和运行 ?学会编程计算并输出常见的算术表达式的结果 ?掌握整数和浮点数的含义和输出方法 ?掌握数学函数的使用方法 ?初步了解变量的含义 ?掌握整数和浮点数变量的声明方法 ?掌握整数和浮点数变量的读入方法 ?掌握变量交换的三变量法 ?理解算法竞赛中的程序三步曲：输入、计算、输出 ?记住算法竞赛的目标及其对程序的要求 计算机速度快，很适合做计算和逻辑判断工作。本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。注意这里的“依次”二字——步骤之间是有先后顺序的。这部分的重点在于计算。 接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。本章内容不复杂，但是不容忽视。 注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。 1.1 算术表达式 计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。 程序1-1 计算并输出1+2的值 #include 算法竞赛入门经典 ·2· { printf("%d\n", 1+2); return 0; } 这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。 即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码——它们看上去工作情况良好。 下面让我们做4个实验： 实验1：修改程序1-1，输出3-4的结果 实验2：修改程序1-1，输出5×6的结果 实验3：修改程序1-1，输出8÷4的结果 实验4：修改程序1-1，输出8÷5的结果 直接把“1+2”替换成“3+4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。解决方法是：用星号“*”代替乘号，而用正斜线“/”代替除号。这样，4个实验都顺利完成了。 等一下！实验4的输出结果居然是1，而不是正确答案1.6。这是怎么回事？计算机出问题了吗？计算机没有出问题，问题出在程序上：这段程序的实际含义并非和我们所想的一致。 在C 语言中，8/5的确切含义是8除以5所得商值的整数部分。同样地，（-8）/5的值是-1，不信可以自己试试。那么如果非要得到8÷5=1.6的结果怎么办？下面是完整的程序。 程序1-2 计算并输出8/5的值，保留小数点后1位 #include ?基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》（推荐指数：4颗星） 曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。语言是pascal的。 2、谭浩强老先生写的《C语言程序设计（第三版）》（推荐指数：5颗星） 针对零基础学C语言的筒子，这本书是必推的。 3、《骗分导论》（推荐指数：5颗星） 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程（一）》（推荐指数：5颗星） 传说中的黄书。吴文虎，王建德著，系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著，传说中的红书。 6、《算法竞赛入门经典》（推荐指数：5颗星） 刘汝佳著，算法必看经典。 7、《算法竞赛入门经典:训练指南》（推荐指数：5颗星） 刘汝佳著，《算法竞赛入门经典》的重要补充 ?提高篇 1、《算法导论》（推荐指数：5颗星） 这是OI学习的必备教材。 2、《算法艺术与信息学竞赛》（推荐指数：5颗星） 刘汝佳著，传说中的黑书。 3、《学习指导》（推荐指数：5颗星） 刘汝佳著，《算法艺术与信息学竞赛》的辅导书。（PS：仅可在网上搜到，格式为PDF）。 4、《奥赛经典》（推荐指数：5颗星） 有难度，但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星） 历年真题，这是绝对不能遗失的存在。必须要做！ 三、各种在线题库 1、题库方面首推USACO（美国的赛题），usaco写完了一等基本上就没有问题，如果悟性好的话甚至能在NOI取得不错的成绩. 2、除此之外Vijos也是一个不错的题库，有很多中文题. 3、国内广受NOIP级别选手喜欢的国内OJ（Tyvj、CodeVs、洛谷、RQNOJ） 4、BJOZ拥有上千道省选级别及以上的题目资源，但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高，命题人大多为现役集训队选手。 算法竞赛-入门经典-作者刘汝佳.doc 第1部分语言篇 第1章程序设计入门 学习目标 ?熟悉C语言程序的编译和运行 ?学会编程计算并输出常见的算术表达式的结果 ?掌握整数和浮点数的含义和输出方法 ?掌握数学函数的使用方法 ?初步了解变量的含义 ?掌握整数和浮点数变量的声明方法 ?掌握整数和浮点数变量的读入方法 ?掌握变量交换的三变量法 ?理解算法竞赛中的程序三步曲：输入、计算、输出 ?记住算法竞赛的目标及其对程序的要求 计算机速度快，很适合做计算和逻辑判断工作。本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。注意这里的“依次”二字——步骤之间是有先后顺序的。这部分的重点在于计算。 接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。本章内容不复杂，但是不容忽视。 注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。 （为帮助没有分值的朋友能下载，特此修改文档，以免上传不了） 1.1 算术表达式 计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。 程序1-1 计算并输出1+2的值 #include 算法竞赛入门经典 这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。 即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码——它们看上去工作情况良好。 下面让我们做4个实验： 实验1：修改程序1-1，输出3-4的结果 实验2：修改程序1-1，输出5×6的结果 实验3：修改程序1-1，输出8÷4的结果 实验4：修改程序1-1，输出8÷5的结果 直接把“1+2”替换成“3+4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。解决方法是：用星号“*”代替乘号，而用正斜线“/”代替除号。这样，4个实验都顺利完成了。 等一下！实验4的输出结果居然是1，而不是正确答案1.6。这是怎么回事？计算机出问题了吗？计算机没有出问题，问题出在程序上：这段程序的实际含义并非和我们所想的一致。 在C语言中，8/5的确切含义是8除以5所得商值的整数部分。同样地，（-8）/5的值是-1，不信可以自己试试。那么如果非要得到8÷5=1.6的结果怎么办？下面是完整的程序。 程序1-2 计算并输出8/5的值，保留小数点后1位 #include 第2章循环结构程序设计 【教学内容相关章节】 2.1 for循环 2.2 循环结构程序设计 2.3文件操作 2.4 小结与习题 【教学目标】 （1）掌握for循环的使用方法； （2）掌握while循环的使用方法； （3）学会使用计算器和累加器； （4）学会用输出中间结果的方法调试； （5）学会用计时函数测试程序效率； （6）学会用重定向的方式读写文件； （7）学会fopen的方式读写文件； （8）了解算法竞赛对文件读写方式和命名的严格性； （9）记住变量在赋值之前的值是不确定的； （10）学会使用条件编译指示构建本地运行环境。 【教学要求】 掌握for循环的使用方法；掌握while循环的使用方法；掌握几个常用的文件操作库函数fopen、fclose、fprintf、fscanf等。 【教学内容提要】 在有些程序中，需要反复执行某些语句。将n条相同的语句简单地复制会使程序变得不合理的冗长，因此高级语言中提供了支持程序重复执行某一段程序的循环控制语句。相关的语句有：for、while、do while、break、continue等。 既可以从文件中读取数据, 也可以向文件中写入数据。读写文件之前，首先要打开文件。读写文件结束后，要关闭文件。C/C++提供了一系列库函数，声明于stdio.h中，用于进行文件操作。这里介绍其中几个常用的文件操作库函数fopen、fclose、fprintf、fscanf等。 【教学重点、难点】 教学重点： （1）掌握for循环的使用方法； （2）掌握while循环的使用方法； （3）掌握文件有关操作； （4）条件编译。 教学难点： （1）掌握for循环的使用方法； （2）掌握while循环的使用方法； 【课时安排（共2学时）】 2.1 for循环 2.2 循环结构程序设计 2.3 文件操作 2.4 小结与习题 number theory 575 - Skew Binary When a number is expressed in decimal, the k-th digit represents a multiple of 10k. (Digits are numbered from right to left, where the least significant digit is number 0.) For example, When a number is expressed in binary, the k-th digit represents a multiple of 2k. For example, In skew binary, the k-th digit represents a multiple of 2k+1 - 1. The only possible digits are 0 and 1, except that the least-significant nonzero digit can be a 2. For example, The first 10 numbers in skew binary are 0, 1, 2, 10, 11, 12, 20, 100, 101, and 102. (Skew binary is useful in some applications because it is possible to add 1 with at most one carry. However, this has nothing to do with the current problem.) Input The input file contains one or more lines, each of which contains an integer n. If n = 0 it signals the end of the input, and otherwise n is a nonnegative integer in skew binary. Output For each number, output the decimal equivalent. The decimal value of n will be at most 231 - 1 = 2147483647. Sample Input 10120 200000000000000000000000000000 10 1000000000000000000000000000000 11 100 11111000001110000101101102000 Sample Output 44 2147483646 3 2147483647 4 7 1041110737 10110 - Light, more light There is man named "mabu" for switching on-off light in our University. He switches on-off the lights in a corridor. Every bulb has its own toggle switch. That is, if it is pressed then the bulb turns on. Another press will turn it off. To save power consumption (or may be he is mad or something else) he does a peculiar thing. If in a corridor there is `n' bulbs, he walks along the corridor back and forth `n' times and in i'th walk he toggles only the switches whose serial is divisable by i. He does not press any switch when coming back to his initial position. A i'th walk is defined as going down the corridor (while doing the peculiar thing) and coming back again. Now you have to determine what is the final condition of the last bulb. Is it on or off? The Input The input will be an integer indicating the n'th bulb in a corridor. Which is less then or equals 2^32-1. A zero indicates the end of input. You should not process this input. The Output Output "yes" if the light is on otherwise "no" , in a single line. Sample Input 3 6241 8191蓝书刘汝佳算法竞赛入门经典勘误
最新算法竞赛入门经典各章(第二版)前4章课后习题答案电子教案
大师兄教你如何过华为机试
(完整)信息学奥赛(NOIP)必看经典书目汇总,推荐文档
BIG NUMBER 算法竞赛入门经典 刘汝佳
算法工程师本科生学习计划
算法竞赛入门经典授课教案第7章 暴力求解法
算法竞赛入门经典授课教案第6章数据结构基础(精心排版,并扩充部分内容)
算法竞赛入门经典第二版习题答案
算法竞赛入门经典第二版习题问题详解
算法竞赛入门经典第一章要点
《算法竞赛入门经典》
信息竞赛推荐书籍
算法竞赛-入门经典-作者刘汝佳
算法竞赛入门经典授课教案第2章_循环结构程序设计(精心排版,并扩充部分内容)
number theory 算法竞赛入门经典 刘汝佳
相关主题
文本预览