《算法竞赛入门经典》
语言篇
第1章程序设计入门
学习目标
?熟悉C语言程序的编译和运行
?学会编程计算并输出常见的算术表达式的结果
?掌握整数和浮点数的含义和输出方法
?掌握数学函数的使用方法
?初步了解变量的含义
?掌握整数和浮点数变量的声明方法
?掌握整数和浮点数变量的读入方法
?掌握变量交换的三变量法
?理解算法竞赛中的程序三步曲：输入、计算、输出
?记住算法竞赛的目标及其对程序的要求
计算机速度快，很适合做计算和逻辑判断工作。本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。注意这里的“依次”二字——步骤之间是有先后顺序的。这部分的重点在于计算。
接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。本章内容不复杂，但是不容忽视。
注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。
1.1 算术表达式
计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。
程序1-1 计算并输出1+2的值
#include
int main()
算法竞赛入门经典
·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
int main()
{
printf("%.1lf\n", 8.0/5.0);
return 0;
}
注意，百分号后面是个小数点，然后是数字1，再然后是小写字母l ，最后是小写字母f ，千万不能打错，包括大小写——在C 语言中，大写和小写字母代表的含义是不同的。
再来做3个实验：
实验5：把%.1lf 中的数字1改成2，结果如何？能猜想出“1”的确切意思吗？如果把小数点和1都删除，%lf 的含义是什么？
实验6：字符串%.1lf 不变，把8.0/5.0改成原来的8/5，结果如何？
实验7：字符串%.1lf 改成原来的%d ，8.0/5.0不变，结果如何？
实验5并不难解决，但实验6和实验7的答案就很难简单解释了——真正原因涉及整数和浮点数编码，相信多数初学者对此都不感兴趣。原因并不重要，重要的是规范：根据规范做事情，则一切尽在掌握中。
第1章
程序设计入门 ·3·
提示1-1：整数值用%d 输出，实数用%lf 输出①。
这里的“整数值”指的是1+2、8/5这样“整数之间的运算”。只要运算符的两边都是整数，则运算结果也会是整数。正因为这样，8/5的值才是1，而不是1.6。 8.0和5.0被看作是“实数”，或者说得更专业一点，叫“浮点数”。浮点数之间的运算结果是浮点数，因此8.0/5.0=1.6也是浮点数。注意，这里的运算符“/”其实是
“多面手”，它既可以拿来做整数除法，又可以拿来做浮点数除法。
提示1-2：整数/整数=整数，浮点数/浮点数=浮点数。
这条规则同样适用于加法、减法和乘法，不过没有除法这么容易出错——毕竟整数乘以整数的结果本来就是整数。
算术表达式可以和数学表达式一样复杂，例如：
程序1-3 复杂的表达式计算
#include
#include
int main()
{
printf("%.8lf\n", 1+2*sqrt(3)/(5-0.1));
return 0;
}
相信读者不难把它翻译成数学表达式：1+惑：5-0.1的值是什么？“整数-浮点数”是整数还是浮点数？另外，多出来的#include
第1个问题相信读者能够“猜到”结果：整数-浮点数=浮点数。但其实这个说法并不准确。确切的说法是：整数先“变”成浮点数，然后浮点数-浮点数=浮点数。
第2个问题的答案是：因为程序1-3中用到了数学函数sqrt 。数学函数sqrt(x )的作用是计算x 的算术平方根（若不信，可输出sqrt(9.0)的值试试）。一般来说，只要在程序中用到了数学函数，就需要在程序最开始的地方包含头文件math.h ，并在编译时连接数学库。如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。
1.2 变量及其输入
1.1节的程序虽好，但有一个遗憾：计算的数据是事先确定的。为了计算1+2和2+3，我们不得不编写两个程序。可不可以让程序读取键盘输入，并根据输入内容计算结果呢？
① 从真正的语言规范来说，这个说法也有一点小问题，不过在算法竞赛中可以完全忽略。
算法竞赛入门经典 ·4·
答案是肯定的。程序如下：程序1-4 A+B 问题
#include
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a+b);
return 0;
}
该程序比1.1节的复杂了许多。简单地说，第一条语句“int a, b ”声明了两个整型（即整数类型）变量a 和b ，然后读取键盘输入，并放到a 和b 中。注意a 和b 前面的&符号——千万不要漏掉，不信可以试试①。
现在，你的程序已经读入了两个整数，可以在表达式中自由使用它们，就好比使用12、597这样的常数。这样，表达式a+b 就不难理解了。
提示1-3：scanf 中的占位符和变量的数据类型应一一对应，且每个变量前需要&符号。
可以暂时把变量理解成“存放值的场所”，或者形象地认为每个变量都是一个盒子、瓶子或箱子。在C 语言中，变量有自己的数据类型，例如int 型变量存放整数值，而double 型变量存放浮点数值（专业的说法是“双精度”浮点数）。如果硬要把浮点数值塞给一个int 型变量，将会丢失部分信息——我们不推荐这样做。
下面来看一个复杂一点的例子。
例题1-1 圆柱体的表面积
输入底面半径r 和高h ，输出圆柱体的表面积，保留3位小数，格式见样例。
样例输入：3.5 9
样例输出：Area = 274.889
【分析】
圆柱体的表面积由3部分组成：上底面积、下底面积和侧面积。由于上下底面积相等，完整的公式可以写成：表面积=底面积×2+侧面积。根据平面几何知识，底面积=2R π，侧面积=2rh π。不难写出完整程序：
程序1-5 圆柱体的表面积
#include
#include
int main()
{
const double pi = 4.0 * atan(1.0);
double r, h, s1, s2, s;
① 在学习编程时，“明知故犯”是有益的：起码你知道了错误时的现象。这样，当你真的不小心犯错时，可以通过现象猜测到可能的原因。
第1章
程序设计入门·5·
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;
}
这是本书中第一个完整的“竞赛题目”，因为和正规比赛一样，题目中包含着输入输出格式规定，还有样例数据。大多数的算法竞赛包含如下一些相同的“游戏规则”。
首先，选手程序的执行是自动完成的，没有人工干预。不要在用户输入之前打印提示信息（例如“Please input n:”），这不仅不会为程序赢得更高的“界面友好分”，反而会让程序丢掉大量的（甚至所有的）分数——这些提示信息会被当作输出数据的一部分。例如刚才的程序如果加上了“友好提示”，输出信息将变成：
Please input n:
Area = 274.889
比标准答案多了整整一行！
其次，不要让程序“按任意键退出”（例如调用system(“pause”)，或者加一个多余的getchar()），因为不会有人来“按任意键”的。不少早期的C语言教材会建议在程序的最后加这样一条语句来“观察输出结果”，但注意千万不要在算法竞赛中这样做。
提示1-4：在算法竞赛中，输入前不要打印提示信息。输出完毕后应立即终止程序，不要等待用户按键，因为输入输出过程都是自动的，没有人工干预。
在一般情况下，你的程序不能直接读取键盘和控制屏幕：不要在算法竞赛中使用getch()、getche()、gotoxy()、clrscr()（早期的教材中可能会介绍这些函数）。
提示1-5：在算法竞赛中不要使用头文件conio.h，包括getch()、clrscr()等函数。
最后，最容易忽略的是输出的格式：在很多情况下，输出格式是非常严格的——多一个或者少一个字符都是不可以的！
提示1-6：在算法竞赛中，每行输出均应以回车符结束，包括最后一行。除非特别说明，每行的行首不应有空格，但行末通常可以有多余空格。另外，输出的每两个数或者字符串之间应以单个空格隔开。
总结一下，算法竞赛的程序应当只做3件事情：读入数据、计算结果、打印输出。不要打印提示信息，不要在打印输出后“暂停程序”，更不要尝试画图、访问网络等与算法无关的任务。
回到刚才的程序，它多了几个新东西。首先是“const double pi = 4.0 * atan(1.0);”。这里也声明了一个叫pi的“符号”，但是const关键字表明它的值是不可以改变的——pi是一
算法竞赛入门经典
·6·
个真正的数学常数①。
提示1-7：尽量用const 关键字声明常数。
接下来是s1 = pi * r * r 。这条语句应该如何理解呢？“s1等于pi*r*r ”吗？并不是这样的。不信，你把它换成“pi * r * r = s1”试试，编译器会给出错误信息：invalid lvalue in assignment 。如果这条语句真的是“二者相等”的意思，为何不允许反着写呢？
事实上，这条语句的学术说法是赋值（assignment ），它不是一个描述，而是一个动作。它的确切含义是：先把“等号”右边的值算出来，然后塞到左边的变量中。注意，变量是“喜新厌旧”的，即新的值将覆盖原来的值，一旦被赋了新的值，变量中原来的值就丢失了。 提示1-8：赋值是个动作，先计算右边的值，再赋给左边的变量，覆盖它原来的值。
最后是那个“Area = %.3lf\n ”，它的用法很容易被猜到：只有以%开头的部分才会被后面的值替换掉，其他部分原样输出。
提示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;
}
此题有一个没有说清楚的细节，即：如果个位是0，反转后应该输出吗？例如输入是520，输出是025还是25？如果在算法竞赛中遇到这样的问题，可向监考人员询问②。但是
①
有的读者可能会用math.h 中定义的常量M_PI ，但其实这个常数不是ANSI C 标准的。不信的话用gcc-ansi 编译试试。 ② 如果是网络竞赛，还可以向组织者发信，在论坛中提问或者拨打热线电话。
第1章
程序设计入门·7·
在这里，两种情况的处理方法都应学会。
提示1-10：算法竞赛的题目应当是严密的，各种情况下的输出均应有严格规定。如果在比赛中发现题目有漏洞，应向相关人员询问，而尽量不要自己随意假定。
上面的程序输出025，但要改成输出25似乎会比较麻烦——我们必须判断n%10是不是0，但目前还没有学到“根据不同情况执行不同指令”（分支结构程序设计是1.4节的主题）。
一个解决方法是在输出前把结果储存在变量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;
}
可以将这种方法形象地比喻成将一瓶酱油和一瓶醋借助一个空瓶子进行交换：先把酱油倒入空瓶，然后将醋倒进原来的酱油瓶中，最后把酱油从辅助的瓶子中倒入原来的醋瓶
算法竞赛入门经典
·8·
子里。这样的比喻虽然形象，但是初学者应当注意它和真正的变量交换的区别。
借助一个空瓶子的目的是：避免把醋直接倒入酱油瓶子——直接倒进去，二者混合以后，将很难分开。在C 语言中，如果直接进行赋值a=b ，则原来a 的值（酱油）将会被新值（醋）覆盖，而不是混合在一起。
当酱油被倒入空瓶以后，原来的酱油瓶就变空了，这样才能装醋。但在C 语言中，进行赋值t = a 后，a 的值不变，它只是把值拷贝（即复制）给了变量t 而已，自身并不会变化。尽管a 的值马上就会被改写，但是从原理上看，t=a 的过程和“倒酱油”的过程有着本质区别。 提示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;
}
这次就不太方便用倒酱油做比喻了：硬着头皮把醋倒在酱油瓶子里，然后分离出酱油倒回醋瓶子？比较理性的方法是手工模拟这段程序，看看每条语句执行后的情况。
在顺序结构程序中，程序一条一条依次执行。为了避免值和变量名混淆，假定用户输入的是a 0和b 0，因此scanf 语句执行完后a = a 0, b = b 0。
执行完a = a+b 后：a = a 0+b 0, b = b 0。
执行完b = a -b 后：a = a 0+b 0, b = a 0。
执行完a = a -b 后：a = b 0, b = a 0。
这样就不难理解两个变量是如何交换的了。这个方法看起来很好（少用一个变量），但实际上很少使用，因为它的适用范围很窄：只有定义了加减法的数据类型才能这么做①。事实上，笔者并不推荐读者采用这样的技巧实现变量交换：三变量法已经足够好了，这个例子只是帮助读者提高程序阅读能力。
提示1-12：交换两个变量的三变量法适用范围广，推荐使用。
那么是不是说，三变量法是解决本题的最佳途径了呢？答案是否定的。多数算法竞赛采用黑盒测试，即只考查程序解决问题的能力，而不关心它采用的什么方法。对于本题而
① 这个思想还有一个“变种”：用异或运算^代替加法和减法，它还可以进一步简写成a^=b^=a^=b 。但不建议使用。
第1章
程序设计入门·9·
言，最合适的程序莫过于：
程序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。输入n和m，依次输出鸡的数目和兔的数目。如果无解，则输出“No answer”（不要引号）。
样例输入：14 32
样例输出：12 2
样例输入：10 16
样例输出：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");
算法竞赛入门经典
·10·
else
printf("%d %d\n", a, b);
return 0;
}
上面的程序用到了if 语句，它的一般格式是：
if(条件)
语句1;
else
语句2;
注意语句1和语句2后面的分号，以及if 后面的括号。“条件”是一个表达式，当该表达式的值为“真”时执行语句1，否则执行语句2。另外，“else 语句2”这个部分是可以省略的。语句1和语句2前面的空行是为了让程序更加美观，并不是必需的，但强烈推荐读者使用。 提示1-14：if 语句的基本格式为：if(条件) 语句1; else 语句2。
换句话说，m%2==1 || a < 0 || b < 0是一个表达式，它的字面意思是“m 是奇数，或者a 小于0，或者b 小于0”。这句话可能正确，也可能错误。因此这个表达式的值可能为真，也可能为假，取决于m 、a 和b 的具体数值。
这样的表达式称为逻辑表达式。和算术表达式类似，逻辑表达式也由运算符和值构成，例如“||”运算符称为“逻辑或”，a || b 表示a 为真，或者b 为真。换句话说，a 和b 只要有一个为真，a || b 就为真；如果a 和b 都为真，则a || b 也为真。
提示1-15：if 语句的条件是一个逻辑表达式，它的值可能为真，也可能为假。
细心的读者也许发现了，如果a 为真，则无论b 的值如何，a || b 均为真。换句话说，一旦发现a 为真，就不必计算b 的值。C 语言正是采取了这样的策略，称为短路（short-circuit ）。也许你会觉得，用短路的方法计算逻辑表达式的唯一优点是速度更快，但其实并不是这样，稍后我们会通过几个例子予以证实。
提示1-16：C 语言中的逻辑运算符都是短路运算符。一旦能够确定整个表达式的值，就不再继续计算。
例题1-5 三整数排序
输入3个整数，从小到大排序后输出。
样例输入：20 7 33
样例输出：7 20 33
【分析】
a 、
b 、
c 3个数一共只有6种可能的顺序：a b c 、a c b 、b a c 、b c a 、c a b 、c b a ，所以最简单的思路是使用6条if 语句。
程序1-12 三整数排序（1）（错误）
第1章
程序设计入门·11·
#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 1 1将得不到任何输出！这个例子告诉我们：即使通过了题目中给出的样例，程序仍然可能存在问题。
提示1-17：算法竞赛的目标是编程对任意输入均得到正确的结果，而不仅是样例数据。
稍微修改一下：把所有的小于符号“<”改成小于等于符号“<=”（在一个小于号后添加一个等号）。这下总可以了吧？很遗憾，还是不行。对于“1 1 1”，6种情况全部符合，程序一共输出了6次1 1 1。
一种解决方案是人为地让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;
}
最后一条语句还可以简化成单独的“else”（想一想，为什么），不过，幸好程序正确了。
提示1-18：如果有多个并列、情况不交叉的条件需要一一处理，可以用else if语句。
另一种思路是把a、b、c这3个变量本身改成a≤b≤c的形式。首先检查a和b的值，
算法竞赛入门经典
·12·
如果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;
}
为什么这样做是对的呢？因为经过第一次检查以后，必然有a ≤b ，而第二次检查以后a ≤c 。由于第二次检查以后a 的值不会变大，所以a ≤b 依然成立。换句话说，a 已经是3个数中的最小值。接下来只需检查b 和c 的顺序即可。
一个很自然的问题产生了：其他检查顺序是否也可以呢？例如先(a,b)，然后(b,c)，最后(a,c)？这个问题留给读者思考。提示：上机实验。
注意上面的程序中唯一的新东西：花括号。前面讲过，if 语句中有一个“语句1”和可选的“语句2”，且都要以分号结尾。有一种特殊的“语句”是由花括号括起来的多条语句。这多条语句可以作为一个整体，充当if 语句中的“语句1”或“语句2”，且后面不需要加分号。当然，当if 语句的条件满足时，这些语句依然会按顺序逐条执行，和普通的顺序结构一样。
提示1-19：可以用花括号把若干条语句组合成一个整体。这些语句仍然按顺序执行。
最后一种思路再次利用了“问题求解”这一目标——它实际上并没有真的进行排序：求出了最小值和最大值，中间值是可以计算出来的。
程序1-15 三整数排序（4）
#include
int main()
{
int a, b, c, x, y, z;
scanf("%d%d%d", &a, &b, &c);
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章 程序设计入门
·13·
}
注意程序中包含的“当前最小值”x 和“当前最大值”z 。它们都初始化为a ，但是随着“比较”操作的进行而慢慢更新，最后变成真正的最小值和最大值。这个技巧极为实用。 提示1-20：在难以一次性求出最后结果时，可以用变量储存“临时结果”，从而逐步更新。
1.5 小结与习题
经过前几个小节的学习，相信读者已经初步了解顺序结构程序设计和分支结构程序设计的核心概念和方法，然而对这些知识进行总结，并且完成适当的练习是很必要的。
首先，我们给出一些实验，旨在加深读者对本章内容的认识。
1.5.1 数据类型实验
实验A1：表达式11111*11111的值是多少？把5个1改成6个1呢？9个1呢？ 实验A2：把实验A1中的所有数换成浮点数，结果如何？
实验A3：表达式sqrt(-10)的值是多少？尝试用各种方式输出。在计算的过程中系统会报错吗？
实验A4：表达式1.0/0.0、0.0/0.0的值是多少？尝试用各种方式输出。在计算的过程中系统会报错吗？
实验A5：表达式1/0的值是多少？在计算的过程中系统会报错吗？
你不必解释背后的原因，但需注意现象。
1.5.2 scanf 输入格式实验
如果用语句scanf(“%d%d ”, &a, &b)来输入两个数，那么这两个数应以怎样的格式输入呢？（提示：可以在输入之后用printf 打印出来，看看打印的结果是否和输入一致。）
实验B1：在同一行中输入12和2，并以空格分隔，是否得到了预期的结果？
实验B2：在不同的两行中输入12和2，是否得到了预期的结果？
实验B3：在实验B1和B2中，在12和2的前面和后面加入大量的空格或水平制表符（TAB ），甚至插入一些空行。
实验B4：把2换成字符s ，重复实验B1～B3。
同样，你不必解释背后的原因，但需注意现象。
1.5.3 printf 语句输出实验
和上面的实验不同，除了注意现象之外，你还需要找到问题的解决方案。
实验C1：仅用一条printf 语句，打印1+2和3+4的值，用两个空行隔开。
实验C2：试着把%d 中的两个字符（百分号和小写字母d ）输出到屏幕。
算法竞赛入门经典
·14·
实验C3：试着把\n 中的两个字符（反斜线和小写字母n ）输出到屏幕。
实验C4：像C2、C3那样也需要“特殊方法”才能输出的东西还有哪些？哪些是printf 函数引起的问题，哪些不是？
第1章
程序设计入门·15·
1.5.4 测测你的实践能力
如何用实验方法确定以下问题的答案？注意，不要查书，也不要在网上搜索答案，必须亲手尝试——实践精神是极其重要的。
问题1：int型整数的最小值和最大值是多少？（需要精确值）
问题2：double型浮点数能精确到多少位小数？或者，这个问题本身值得商榷？
问题3：double型浮点数最大正数值和最小正数值分别是多少（不必特别精确）？
问题4：逻辑运算符号&&、||和!（它表示逻辑非）的相对优先级是怎样的？也就是说，a&&b||c应理解成(a&&b)||c还是a&&(b||c)，或者随便怎么理解都可以？
问题5：if(a) if(b) x++; else y++的确切含义是什么？这个else应和哪个if配套？有没有办法明确表达出配套方法，以避免初学者为之困惑？
1.5.5 小结
对于不少读者来说，本章的内容都是直观、容易理解的，但这并不意味着所有人都能很快地掌握所有内容。相反，一些勤于思考的人反而更容易对一些常人没有注意到的细节问题产生疑惑。对此，笔者提出如下两条建议。
一是重视实验。哪怕不理解背后的道理，至少要清楚现象。例如，读者若亲自完成了本章的探索性实验和上机练习，一定会对整数范围、浮点数范围和精度、特殊的浮点值、scanf 对空格、TAB和回车符的过滤、三角函数使用弧度而非角度等知识点有一定的了解。这些东西都没有必要死记硬背，但一定要学会实验的方法。这样即使编程时忘记了一些细节，手边又没有参考资料，也能轻松得出正确的结论。
二是学会模仿。本章始终没有介绍#include
当然，这样的策略并不一定持续很久。当学生有一定的自学、研究能力之后，本书会在适当的时候解释一些重要的概念和原理，并引导学生寻找更多的资料进一步学习。要想把事情做好，必须学得透彻——但没有必要操之过急。
算法竞赛入门经典
·16· 1.5.6 上机练习
程序设计是一门实践性很强的学科，读者应在继续学习之前确保下面的题目都能做出来。 习题1-1 平均数（average ）
输入3个整数，输出它们的平均值，保留3位小数。
习题1-2 温度（temperature ）
输入华式温度f ，输出对应的摄氏温度c ，保留3位小数。提示：c =5(f -32)/9。 习题1-3 连续和（sum ）
输入正整数n ，输出1+2+…+n 的值。提示：目标是解决问题，而不是练习编程。 习题1-4 正弦和余弦（sincos ）
输入正整数n （n <360），输出n 度的正弦、余弦函数值。提示：使用数学函数。 习题1-5 距离（distance ）
输入4个浮点数x 1, y 1, x 2, y 2，输出平面坐标系中点(x 1,y 1)到点(x 2,y 2)的距离。
习题1-6 偶数（odd ）
输入一个整数，判断它是否为偶数。如果是，则输出“yes ”，否则输出“no ”。提示：可以用多种方法判断。
习题1-7 打折（discount ）
一件衣服95元，若消费满300元，可打八五折。输入购买衣服件数，输出需要支付的金额（单位：元），保留两位小数。
习题1-8 绝对值（abs ）
输入一个浮点数，输出它的绝对值，保留两位小数。
习题1-9 三角形（triangle ）
输入三角形三边长度值（均为正整数），判断它是否能为直角三角形的三个边长。如果可以，则输出“yes ”，如果不能，则输出“no ”。如果根本无法构成三角形，则输出“not a triangle ”。
习题1-10 年份（year ）
输入年份，判断是否为闰年。如果是，则输出“yes ”，否则输出“no ”。提示：简单地判断除以4的余数是不够的。
蓝书刘汝佳算法竞赛入门经典勘误
#《算法竞赛入门经典》勘误 关于勘误?下面的勘误很多来自于热心读者，再次向他们表示衷心的感谢！我并不清楚这些错误实际是在哪个版本中改正过来的，所以麻烦大家都看一下。 有发现新错误的欢迎大家在留言中指出，谢谢！ 一些一般性的问题?运算符?已经被废弃，请用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
最新算法竞赛入门经典各章(第二版)前4章课后习题答案电子教案
第一章习题1-1 #include
习题1-3 #include
习题1-5 #include
大师兄教你如何过华为机试
大师兄教你如何过华为机试 宝典1—内功心法 大华为这个大数据时代土豪金海量式的招聘又要开始了！！！ 近期听说大华为的校招机试马上就要开始了，由于华为软件岗位的招聘只有技术面跟机试是与技术有关的内容，所以机试的地位非常重要。对于机试，除了长期积累的软件基本功以外，还有很多可以短期训练的东西，类似于考试之前的突击，可以迅速提高机试成绩，就像在我西电大杨老师考前最后一堂课一定要去，那个重点就是考点阿。 这篇机试葵花宝典的内容是针对华为软件类上机准备的，如果你认真看了本宝典,如果你是真正通过自己能力考上西电的话,想不过都难。同样想拿高级题的同学，请移步 https://www.sodocs.net/doc/0c150079.html,/land/或者https://www.sodocs.net/doc/0c150079.html,，刷上200道题，机试不想拿满分都难。 对于机试，首先应该调整好自己的心态，不要觉得写程序很难，机试题很难，也不要去考虑，万一机试考到自己不会的内容怎么办，要相信，机试题永远是考察每个人的基础，基础是不会考的很偏的，会有人恰好做过某个题而做出来那个题，但不会有人恰好没做过一个题而做不出来那个题。 机试之前，应该做的准备有： 1、买一本《算法竞赛入门经典》，这本书不同于普通的算法或者编程语言的书籍，这 本书既讲语言，又讲算法，由浅入深，讲的很好，能看完前几章并且把例题都做 会，想通过机试就很简单了 2、调整好心态，时刻告诉自己，哪些小错误是自己以前经常犯的，最好用笔记本记录 下来，写每道题前再看一遍，如果遇到代码调不出来了，先想想自己是否犯过以 前那些错误。还有就是，看了题目以后，先仔细想清楚细节，在纸上写清楚自己 需要用到的变量，以及代码的基本框架，不要急于动手去写代码 3、不要惧怕任何一道看起来很难的题目，有不会的就去问身边会的人，让别人给自己 讲清楚 4、心中默念10遍C++跟C除了多了两个加号其实没有区别，会C就能上手C++ 5、大量的练习是必要且有效的 6、看完这篇宝典，预过机试、必练此功。 在这里推荐一个帖子，是机试归来的学长写的，写的很不错，里面的例题在后面的攻略
(完整)信息学奥赛(NOIP)必看经典书目汇总,推荐文档
信息学奥赛（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。赛题质量极高，命题人大多为现役集训队选手。
BIG NUMBER 算法竞赛入门经典 刘汝佳
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章暴力求解法 【教学内容相关章节】 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章数据结构基础 【教学内容相关章节】 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章循环结构程序设计 【教学内容相关章节】 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 算法竞赛入门经典 刘汝佳
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
相关文档
- 算法竞赛入门经典1-3章习题答案
- number theory 算法竞赛入门经典 刘汝佳
- 最新算法竞赛入门经典各章(第二版)前4章课后习题答案电子教案
- 信息学奥赛(NOIP)必看经典书目汇总
- TclTk入门经典(第2版)
- 算法竞赛入门经典第二版习题问题详解
- 算法竞赛入门经典各章(第二版)前4章课后习题答案汇编
- 算法竞赛入门经典各章(第二版)前4章课后习题答案
- BIG NUMBER 算法竞赛入门经典 刘汝佳
- 蓝书刘汝佳算法竞赛入门经典勘误
- 信息竞赛推荐书籍
- 算法竞赛入门经典第二章习题编程C#
- 算法竞赛入门经典各章习题答案
- UVaOJ+算法竞赛入门经典+挑战编程+USACO题库
- 算法竞赛入门经典授课教案第7章 暴力求解法
- 信息学奥赛(NOIP)必看经典书目汇总
- 蓝书刘汝佳算法竞赛入门经典勘误
- Graphs 算法竞赛入门经典 刘汝佳
- (完整)信息学奥赛(NOIP)必看经典书目汇总,推荐文档
- 算法竞赛入门经典授课教案第1章 算法概述