算法竞赛入门经典授课教案第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 页

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新小学教育算法竞赛入门经典授课教案第1章 算法概述 全文阅读和word下载服务。