算法竞赛入门经典授课教案第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+2的值#include <stdio.h>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 <stdio.h>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 <stdio.h>#include <math.h>int main(){printf("%.8lf\n", 1+2*sqrt(3)/(5-0.1));return 0;}说明：（1）整数-浮点数是整数先“变”成浮点数，然点浮点数-浮点数=浮点数。

（2）在程序1-3中用到数学函数sqrt。

数学函数sqrt(x)的作用是计算x的算术平方根。

一般来说，只要在程序中用到了数学函数，就需要在程序最开始的地方包含文件math.h1.2 变量及其输入在程序中可以通过键盘输入，然后根据输入内容来计算结果。

程序如下：程序1-4 A+B问题#include <stdio.h>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 <stdio.h>#include <math.h>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.141593（π的近似值）。

（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 <stdio.h>int main(){int n;scanf("%d", &n);printf("%d%d%d\n", n%10, n/10%10, n/100);return 0;}注意：程序1-6的输出结果是025。