算法竞赛入门经典授课教案第1章 算法概述

第1章 程序设计入门

第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-1 计算并输出1+2的值

#include int main(){

printf(\ 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(\ 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(\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 复杂的表达式计算

23的值：

5?0.1#include #include int main(){

第 2 页

第1章 程序设计入门

printf(\ 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(\ printf(\ return 0; }

说明：（1）变量用来存储可变的数据，它像一个筐，什么都往里面装。它只能用来存储事先指定的数据结构。

（2）在scanf语句中，变量a和b前面的&（取地址）符号，不能丢掉。

提示1-3：scanf中的占位符和变量的数据类型应一一对应，且每个变量前需要&符号。 下面来看一个复杂一点的例子。 例1-1 圆柱体的表面积。

输入底面积半径r和高h，输出圆柱体的表面积，保留3位小数，格式见样例。 样例输入：3.5 9 样例输出：Area=274.889 【分析】

2

圆柱体的表面积=底面积×2+侧面积。根据平面几何知识，底面积=πr，侧面积=2πrh。完整的程序如下：

程序1-5 圆柱体的表面积

#include #include int main(){

const double pi=4.0*atan(1.0); double r,h,s1,s2,s; scanf(\ s1=pi*r*r; s2=2*pi*r*h; s=s1*2.0+s2;

printf(\ 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

第 3 页

第1章 程序设计入门

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（这里的%是取余数操作），个位数等于n。完整的程序如下：

程序1-6 三位数反转（1）

#include

int main(){ int n;

scanf(\

printf(\ return 0; }

注意：程序1-6的输出结果是025。如果一个数的个位是0，例如输入是520，输出结果是025，还是25，在算法竞赛中如果遇到这个问题，可向监考老师询问。

提示1-10：算法竞赛的题目应当严密的，各种情况下的输出均应有严格规定。如果在比赛中发现题目有漏洞，应当向相关人员询问，而尽量不要自己随意假定。

对程序1-6，如果要输出25，解决办法是在输出结果前把结果存在变量m中，直接用%d格式输出m，这样可以输出25；如果要输出025，把输出格式变为d即可。

第 4 页

第1章 程序设计入门 程序1-7 三位数反转（2）

#include int main(){ int n, m;

scanf(\

m = (n)*100 + (n/10)*10 + (n/100); printf(\ return 0; }

例1-3 交换变量。

输入两个整数a和b，交换二者的值，然后输出。 样例输入：824 16 样例输出：16 824 【分析】

按题目的所说，先把变量存入变量a和b，然后交换。最经典的方法是三变量法：

程序1-8 变量交换（1）

#include int main(){ int a, b, t;

scanf(\ t = a; a = b; b = t;

printf(\ return 0; }

提示1-11：赋值a=b之后，变量a原来的值被覆盖，而b的值不变。 另一个方法没有借助任何变量，但较难理解：

程序1-9 变量交换（2）

#include int main(){ int a, b;

scanf(\ a = a + b; b = a - b; a = a - b;

printf(\ return 0; }

说明：程序1-9的功能也是交换两个变量的值（少用了一个中间变量来实现），但实际上很少使用，因为它的适用范围很窄：只有定义了加减法的数据类型才能这么做。

提示1-12：交换两个变量的三变量法适用范围广，推荐使用。

多数算法竞赛采用黑盒测试，即只考查程序解决问题的能力，而不关心它采用的方法，所以三变量法不是解决变量交换的最佳途径，对于本题而言，最合适程序如下：

程序1-10 变量交换（3）

#include int main(){ int a, b;

scanf(\ printf(\ return 0;

第 5 页

第1章 程序设计入门

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(\

第 11 页

第1章 程序设计入门

return 0;

}

程序的运行结果为11111*11111=123454321。

（2）计算表达式111111*111111的值

只须将（1）中的printf语句改为printf(\，程序的运行结果为111111*111111=-539247567。正确的结果应为12345654321，由于这个数比较大，所以产生了溢出。

（3）计算表达式111111111*111111111的值 只须将（1）中的printf改为printf(\\11);，程序的运行结果为111111111*111111111=1653732529。正确的结果应为12345678987 654321，由于这个数比较大，所以产生了溢出。

实验A2：把实验A1中的所有数换成浮点数，结果如何？ 解答：（1）计算表达式11111.0*11111.0的值 #include int main(){

printf(\return 0; }

程序的运行结果为11111*11111=123454321.000000。

（2）计算表达式111111.0*111111.0的值

只须将（1）中的printf语句改为printf(\，程序的运行结果为111111.0*111111.0=12345654321.000000。

（3）计算表达式111111111.0*111111111.0的值

只须将（1）中的printf改为printf(\\*111111111.0);，程序的运行结果为111111111.0*111111111.0=12345678987654320.00000 0。

实验A3：表达式sqrt(-10)的值是多少？尝试用种方法输出。在计算过程中系统会报错吗？

解答：

#include #include int main(){

printf(\return 0; }

程序的运行结果为sqrt(-10)=-1.#IND，没有报错，但结果异常。

实验A4：表达式1.0/0.0、0.0/0.0的值是多少？尝试用种方法输出。在计算过程中系统会报错吗？

解答：

#include int main(){

printf(\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(\语句用来输入两个数，可用Tab、空格、回车，作为分隔符。

第 12 页

第1章 程序设计入门

实验B1：在同一行中输入12和2，并以空格分隔，是否得到了预期的效果？ 解答：

#include void main() { int a,b;

scanf(\ printf(\ 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(\ return; }

实验C2：试着把%d中的两个字符（百分号和小写字）。 解答：

#include void main() {

printf(\ return; }

实验C3：试着把\\n中的两个字符（反斜线和小写字母n）输出到屏幕。 解答：

#include void main() {

printf(\ return; }

实验C4：像C2、C3那样也需要“特殊方法”才能输出的东西还有哪些？哪些是printf函数引起的问题，哪些不是？

解答：输出单引号和双引号需要用\\’和\\\。 1.6.4 测试你的实践能力

问题1：int型整数的最小值和最大值是多少？（需要精确度）。 解答：（1）方法一 #include #include

第 13 页

第1章 程序设计入门

int main() { int a,b;

a=-pow(2,31); b=pow(2,31)-1;

printf(\ 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(\ 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(\ return 0; }

double型浮点数隐含输出小数位数为6位，不过还可以通printf(\来重新设置，.20中的20也可以换成其它的数值。

问题3：double型浮点数最大正数值和最小正数值分别是多少？ 解答：

#include int main() {

int y = 1030;

for (double x = 0.999999999; y-- ; x *= 2) cout << x << '\\t'; cout << endl;

第 14 页

第1章 程序设计入门

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=(double)(a+b+c);

printf(\return 0; }

习题1-2 温度（temperature）

输入华式温度f，输出对应的摄氏温度c，保留3位小数。提示：c=5(f-32)/9。

第 15 页

第1章 程序设计入门

解答：

#include int main() {

int f; double c;

scanf(\c=5*(f-32)/9;

printf(\return 0; }

习题1-3 连续和（sum）

输入正整数n，输出1+2+?+n的值。提示：目标是解决问题，而不是练习编程。 解答：

#include int main() { int n;

scanf(\

printf(\ return 0; }

注意：本题利用了等差数列的公式，而不是像平常编程时，用循环来实现。 习题1-4 余弦和正弦（sincos） 输入正整数（n<360），输出n度的正弦、余弦函数值。提示：使用数学函数。 解答：

#include #include int main() {

const double pi = 3.1415926; int n; /* n是角度 */ scanf(\

printf(\printf(\return 0; }

习题1-5 距离（distance）

输入4个浮点数x1，y1，x2，y2，输出平面坐标系中点(x1，y1)和点(x2，y2)的距离。 解答：

#include #include int main() {

double x1,x2,y1,y2;

scanf(\

printf(\ return 0; }

习题1-6 偶数（odd）

输入一个整数，判断它是否为偶数。如果是，则输出“yes”，否则输出“no”。提示：可以用多种方法判断。

解答：

#include int main(){

第 16 页

第1章 程序设计入门

int n;

scanf(\if(n%2==0){

printf(\} else{

printf(\}

return 0;

}

习题1-7 打折（discount）

一件衣服95元，若消费满300元，可打八五折。输入购买衣服件数，输出需要支付的金额（单位：元），保留两位小数。

解答：

#include int main() {

int n; double a;

scanf(\a=n*95.0; if(a<300){

printf(\} else{

printf(\}

return 0; }

习题1-8 绝对值（abs）

输入一个浮点数，输出它的绝对值，保留两位小数。 解答：

#include #include int main() {

double n;

scanf(\

printf(\return 0; }

习题1-9 三角形（triangle）

输入三角形三边长度值（均无正整数），判断它是否能为直角三角形的三个边长。如果可以，则输出“yes”，如果不能，则输出“no”。如果根本无法构成三角形，则输出“not a triangle”。

解答：

#include int main() {

int a,b,c;

scanf(\if(a==b&&b==c) {

printf(\}

第 17 页

第1章 程序设计入门

if((a*a+b*b==c*c)||(a*a+c*c==b*b)||(b*b+c*c==a*a)) {

printf(\}

else {

printf(\}

return 0;

}

习题1-10 年份（year）

输入年份，判断是否为闰年。如果是，则输出“yes”，否则输出“no”。提示：简单地判断除以4的余数的是不够的。

解答：

#include int main() {

int n;

scanf(\if(n%4==0) {

if(n0!=0) {

printf(\} else {

if(n@0==0) {

printf(\} else{

printf(\} } }

else {

printf(\}

return 0; }

布 置 作 业

上机练习 习题1-7、1-8、1-9、1-10

第 18 页

本文来源：https://www.bwwdw.com/article/wqgh.html