第二讲 简单程序设计练习

1、程序设计实习课程 (C+ Programming Practice)程序设计实习第二讲 简单程序设计练习北京大学程序设计实习课程2课堂调查o 是否学过C语言，或有过C语言编程经验?o 有过C+编程经验？o 是否熟练使用VC+编程环境？北京大学程序设计实习课程3上次课内容回顾o 位运算o 函数指针o 指针和动态内存分配o 命令行参数o C语言标准库函数o 程序风格建议o 课堂测验北京大学程序设计实习课程4内容提要o C语言的基础知识与程序架构介绍o C语言的标准输入输出语句n 上节课的测验题讲解o 程序阅读练习o 程序设计练习o 作业o 课程练习与习题出自:PKU JudgeOnline htt

2、p:/ 一般计算机中用16位或32位来表示整数,位数越多,能表示数的范围就越大。o 整数有正负之分,为此,我们可以用一个二进位作为符号位,一般总是最高位,当符号位为0是表示正数,符号位为1时表示负数。例如,当我们用16位来表示一个整数时,有0000 0000 0010 1011=+431000 0000 0010 1011=-43o 上述表示法,称为整数的表示法。北京大学程序设计实习课程6整数也可采用表示法,对于负整数来说,符号位作为1,但绝对值部分正好与原码相反（即0变为1,1变为0）。因此：(-43)原原=1000 0000 0010 1011(-43)反反=1111 1111 1101

3、0100而实际上,整数在机器内大多用表示,对负整数而言,符号位仍为1,但绝对值部分却是反码的最低位加1得到的结果,因此(-43)补补=1111 1111 1101 0101注意,对正整数而言,其原码、反码、补码均相同。数在计算机内的表示北京大学程序设计实习课程7 任何程序设计语言，都是由语言语言规范规范和一系列标准开发库标准开发库组成的。如标准C，除了语言规范外，还有很多函数库；MS Visual C+更是提供了庞大的APIs和MFC。 学习任何程序设计语言，都是要从这两方面着手，尤其是要能够熟练地使用后者。程序设计语言程序设计语言开发库北京大学程序设计实习课程8p 程序结构p 基本元素：标识

4、符和关键字p 变量、常量和数据类型p 运算符和表达式p 语句及控制流p C语言标准库函数语言规范语言规范开发库开发库C程序设计语言程序设计语言北京大学程序设计实习课程9o 一个C程序是由一个固定名称为main的主函数和若干个自定义函数（可缺省）组成。编译预处理（宏、头文件）自定义函数声明int main( )说明部分 /*变量定义等*/执行部分 /*输入/输出/计算*/ 自定义函数C程序基本框架程序基本框架北京大学程序设计实习课程10/*求圆的面积*/#define PI 3.14159 /*预编译：宏定义*/#include /*预编译：文件包含*/#include float getAre

5、a(float r); /*自定义函数：求面积函数*/*主函数*/int main(int argc, char* argv) float s1,s2; /*定义变量*/ float r1,r2; /*计算第1个圆的面积*/ printf(“请输入第一个圆的半径：”); /*调用stdio.h中的函数printf()，将相关内容输出到屏幕中去*/ scanf(%f, &r1); /*调用stdio.h中的函数scanf()，从键盘中输入半径r1的值*/ s1 = 3.14159f * r1 * r1; /*求面积*/ printf(“n第一个半径为%f的圆的面积为：%fn”, r1,s1);

6、/*调用函数printf()，将计算的面积输出到平面中去*/ /*计算第2个圆的面积*/ r2 = 104.6f; /*半径为104.6*/ s2 = getArea(r2); /*调用自定义函数求圆的面积*/ printf(n第二个半径为%f的圆的面积为：%fn, r2,s2); /*调用函数printf()，将计算的面积输出到平面中去*/*自定义函数：求半径为r的圆的面积*/float getArea(float r) float s; s = (float)(PI * pow(r, 2); /*利用所定义的宏PI替换3.14159，调用math.h中的求幂函数pow()*/ return

7、 s;C程序基本框架程序基本框架北京大学程序设计实习课程11n一个C程序是由一个固定名称为main的主函数和若干个其他函数（可没有）组成。n一个C程序必须有一个、也只能有一个主函数。n程序执行时总是从主函数开始，在主函数内结束。n主函数可以调用其他各种函数（包括标准库函数和用户自己编写的函数），但其他函数不能调用主函数。其他函数相互之间遵循一定的规则是可以相互调用的。C程序基本框架程序基本框架主函数主函数北京大学程序设计实习课程12其他函数其他函数o标准库函数：随C语言环境语言环境一起提供的各种标准的通用功能函数，只能调用(先文件包含先文件包含) 。例： s = (float)(PI * po

8、w(r, 2); pow(x,y) 求xy （math.h，数学函数）scanf(%f, &r1);scanf(“%f”, ) 从键盘中输入数据（stdio.h，输入输出函数）printf(n第一个半径为%f的圆的面积为：%fn, r1,s1);printf(“%f”, ) 往屏幕中输出数据（stdio.h，输入输出函数）o自编（定义）函数：必须先定义（声明），后调用必须先定义（声明），后调用例： s2 = getArea(r2); C程序基本框架程序基本框架函数函数北京大学程序设计实习课程13C程序基本框架程序基本框架函数函数/主函数主函数主函数main()标准库函数自定义函数自定义函数自定

9、义函数函数的调用函数的调用北京大学程序设计实习课程14n变量：变量：存放数据的容器，有不同的数据类型。n语句：语句：一个由分号（;）结尾的单一命令是一条语句（Statement），一条语句可以完成一条或若干条指令功能。如：nfloat s, r; / 变量定义语句nr = 10; / 变量赋值语句ns = 3.1416*r*r; / 执行乘法运算并赋值的语句n代码段：代码段：用大括号（ ）围起来的多条语句构成一个代码段（Code block）；如：nint i;nfor (i=0; i=1; i+) nnC程序基本框架程序基本框架变量变量/语句语句/代码段代码段北京大学程序设计实习课程15形式

10、：形式： PI 符号常量（宏名，最好用大写，以区别一般变量）3.14159 宏体（可以是一个表达式）o作用：用简单符号代表宏体部份内容（编译时会先自动替换），可用作常量定义或其他作用o意义：直观/多次使用/便于修改o注意： #define 可出现在程序的任一位置（作用范围：作用范围：由此行到程序末尾），宏定义不是C语句，不必在行未加分号，否则会连分号一起置换。C程序基本框架程序基本框架预编译处理预编译处理北京大学程序设计实习课程16编译预处理编译预处理文件包含文件包含形式：形式： stdio.h “头文件”，标准前导文件myhead.h “头文件”，自定义前导文件oC语言是一种“装配式”语言，

11、许多常规的工作如输入、输出、数学函数等，往往事先由人做成各种“程序模块”(.lib)，并将其定义存放在各种所谓“头文件”(.h)中。o文件包含的作用，就是根据需要把相应的某个“头文件”定义所涉及的“程序模块”在编译时先整体嵌入所编的程序中。o用户也可以将自己设计的程序模块等做成“程序模块”及“头文件”，供其他程序“包含”（调用）。C程序基本框架程序基本框架预编译处理预编译处理北京大学程序设计实习课程17n注释注释：为了增加程序的可读性而附加的说明性文字，它们在编译时会被忽略。n/ 单行注释，简单的解释语句含义. 注释到行末n/* 多行注释，用来说明更多的内容，包括算法等.nn*/C程序基本框架

12、程序基本框架注释注释北京大学程序设计实习课程18C语言是一种函数式语言，其程序基本组成是函数。每个C程序必须有一个、也只能有一个主函数main()。不管主函数在程序中的位置如何，程序执行总是从主函数开始，在主函数内结束。#include 语句 - 头文件包含#define 语句 - 宏定义每个语句必须用分号“；”结束（注意是“每个语句”而不“每行语句”）。语句可以用大括号组成语句段。函数可以调用其它函数 结构化编程/分而治之C程序基本框架程序基本框架 - 总结总结北京大学程序设计实习课程19三种基本算法结构o 顺序结构o 选择结构（分支结构）o 循环结构（重复结构）n 当型循环（While型循

13、环）n 直到型循环（Do-While型循环）北京大学程序设计实习课程20三种基本算法结构的共同特点o 只有一个入口o 只有一个出口o 结构内每一部分都有机会被执行到o 结构内不存在“死循环”AabBABa北京大学程序设计实习课程21结构化程序设计方法o 结构化算法n 由基本结构顺序组成的算法结构o 结构化程序设计方法n 自顶向下n 逐步细化n 模块化设计n 结构化编码北京大学程序设计实习课程22C语言的输入输出语句o #include n scanf( ) 将输入读入变量 scanf(“格式控制串”, 变量地址1 , 变量地址2, )n printf( ) 将变量内容输出 printf(“格式

14、控制串”, 待输出项1 ,待输出项2, )o 两点注意n 格式控制串数应和变量地址/待输出项数一致n 变量地址：变量前加&字符；指针；数组名int i, nArr200, *pInt;&i, nArr, pInt北京大学程序设计实习课程23输入输出控制o 格式控制的完整格式：% - 0 m.n l或h 格式字符n%：表示格式说明的起始符号，不可缺少。n-：有-表示左对齐输出，如省略表示右对齐输出n0：有0表示指定空位填0,如省略表示指定空位不填。nm.n：m指域宽，即对应的输出项在输出设备上所占的字符数。n指精度。用于说明输出的实型数的小数位数。未指定n时，隐含的精度为n=6位。nl或h：l对

15、整型指long型，对实型指double型。h用于将整型的格式字符修正为short型。 o scanf() 和 printf()的基本格式控制符有：n%d：整数n%c：字符n%s：字符串n%f：浮点数n%u：无符号整数n%o, %x：八进制/十六进制n%e：指数北京大学程序设计实习课程24输入输出控制o scanf()中的格式控制中，还可以控制多个输入数据之间的分隔标记，如：scanf(“%c,%d,%f”, &c, &n, &f)。若多个输入控制符之间没有任何分隔标记，则输入数之间以换行（回车）作为分隔，如：scanf(“%c%d%f”, &c, &n, &f)。o 在printf()中的格式

16、控制中，还可以包含其他希望输出字符（串），如：printf(“nThis is a %d !”, n)。o 复杂格式控制：可以进行长度控制北京大学程序设计实习课程25scanf( ) 语句# include int a;long bfloat c;char d;char e20;double f;scanf(“%d %ld %f %c %s %lf”,&a,&b,&c,&d,e,&f);北京大学程序设计实习课程26scanf( ) 语句o 返回值n 0 成功读入的数据项个数；n 0 没有项被赋值；n EOF 第一个尝试输入的字符是EOF(结束)。北京大学程序设计实习课程27printf( )

17、语句printf(“%d %ld %f %c %s %lf”, a, b, c, d,e, f );printf(“%5d”,a); 至少占5个字符printf(“%ld”,b);printf(“%.2f”,c); 精确到小数点后两位printf(“%5c”,d);printf(“%sn”,e); 末尾回车换行printf(“%.5lf”,f); 精确到小数点后5位北京大学程序设计实习课程28printf( ) 语句o 返回值n 成功打印的字符数；n 返回负值为出错。北京大学程序设计实习课程29sscanf( )o sscanf() 函数从一个字符串，而不是标准输入中读入；例如： char s

18、tr10=12:30 am; int h,m; char tag3; sscanf(str,%d:%d %s,&h,&m,tag); printf(%d:%d %s,h,m,tag);北京大学程序设计实习课程30sprintf( )o sprintf() 函数向一个字符串，而不是标准输出中输出；例如： char str10; int h=12,m=7; char tag3=am; sprintf(str,%d:%d %sn,h,m,tag); printf(%s,str);北京大学程序设计实习课程31C语言的输入输出语句o 在vc 中安装 MSDN，学会使用帮助，即在源文件编辑窗中输入待查函数

19、名，将光标移动至函数名上，按F1键；o 除了scanf 和 printf 还可以查 getchar(), putchar()北京大学程序设计实习课程32C+语言的输入输出语句 # include cin 变量名1 变量名2; cout 变量 常量endl;o 自动类型检查北京大学程序设计实习课程33C+语言的输入输出语句cin.get ()cin.getline()cout.put()cin.read()cout.write()cin.gcout()cout dec oct hex setbase(i)北京大学程序设计实习课程34课堂测验小结:校门外的树o 解法n设置数组，初始化，将地铁区域内

20、位置 改变属性，统计剩余数目，输出0123i i+1 i+2L1 1 1 1 1 1 1 1标记数组路标0123i i+1 i+2L1 1 1 1 0 0 1 1标记数组路标0123i i+1 i+2L1 1 1 1 0 0 0 1标记数组路标北京大学程序设计实习课程35校门外的树o 有关实现的细节n 数组的定义p 静态数组， 大小为10001 足够，可能会冗余 int trees10001; bool trees10001;p 动态数组，int *trees; trees = new intL+1; delete trees;n 初始化 #include void main()int L,i

21、,j,M;/L为区间长度为区间长度,M为区间个数，为区间个数，i,j为循环变量为循环变量bool bTrees10001;/用一个用一个bool数组模拟树的存在情况数组模拟树的存在情况for (i=0;i10001;i+)bTreesi = true;scanf(%d%d,&L,&M);for (i=0;iM;i+)int nBegin,nEnd;/ 用用nBegin,nEnd存储区间的起止位置存储区间的起止位置scanf(%d%d,&nBegin,&nEnd);for (j= nBegin;j=nEnd;j+)/移除区间内的树移除区间内的树bTreesj = false;int nCount

22、 = 0; / nCount存放剩余的树的数量存放剩余的树的数量for (i=0;i=L;i+) / 统计剩余的树的数量统计剩余的树的数量if (bTreesi) nCount +;printf(%dn,nCount);解法一:采用静态数组#include int main()int L, M;bool *bTrees;scanf(%d%d,&L,&M);bTrees=new boolL+1; /动态定义一个数组模拟树的存在情况动态定义一个数组模拟树的存在情况for(int i=0;i=L;i+) /数组初始化数组初始化bTreesi=true;for(i=0;iM;i+)int start,

23、 end;scanf(%d%d,&start,&end);for(int k = start; k = end; k+)if(bTreesk)bTrees k = false;L-; /有一棵树被移去，则有一棵树被移去，则L减一减一printf(%dn, L+1);delete bTrees;return 0;解法二:采用动态数组北京大学程序设计实习课程38代码阅读o 阅读的目的n 读懂别人的程序是一种能力；n 更重要的是充分理解程序就是在对一个内存区域反复做内容上的修改，最后得到问题的解的过程。n 程序运行的每一步结束，内存的状态可以视为一个现场，程序调试主要是通过打印现场的方式进行。北京大

24、学程序设计实习课程39程序阅读练习 例1#include int main()int u4, a, b, c, x, y, z;cinu0u1u2u3;a = u0 + u1 + u2 + u3 - 5;b = u0 * (u1 - u2 / u3 + 8);c = u0 * u1 / u2 * u3;x = (a + b + 2) * 3 - u(c + 3) % 4;y = (c * 100 - 13) / a / (ub % 3 * 5);if (x + y) % 2 = 0) z = (a + b + c + x + y) / 2;z = (a + b + c - x - y) * 2

25、;cout x + y - z;return 0;输入：2 5 7 4输出： 北京大学程序设计实习课程40程序阅读练习 例2#define N 100void main( ) int number; int primeN; int i, k; prime0 = 2; number=1; for(i=3; iN; i+) for(k=0; primek*primeki) primenumber = i; number+; 阅读代码，说出这段程序在做什么。北京大学程序设计实习课程41程序阅读练习 例2#define N 100void main( ) int number; / 小于小于N的质数个

26、数；的质数个数； int primeN; / 从从prime0 primenumber-1 中存放生成的质数；中存放生成的质数； int i, k; / 循环变量；循环变量； prime0 = 2; number=1; for(i=3; iN; i+) / 从整数从整数3开始检查开始检查 i 是否为质数是否为质数for(k=0; primek*primeki) / 如果如果 i 不能被前面的质数整除，不能被前面的质数整除， / 则将它作为新质数存入数组则将它作为新质数存入数组 primenumber = i; number+; 北京大学程序设计实习课程42程序阅读练习 例3#include i

27、nt calculateGCD(int a, int b) if(b=0) return a; return calculateGCD(b,a%b);void main() int n,m; cin n m; cout calculateGCD(n,m) endl;输入：5 6 输出：输入：72 16 输出：输入：20 30 输出：北京大学程序设计实习课程43o上面的求最大公约数的函数只需证明a 和 b的最大公约数也是b和a%b的最大公约数。o证明:1. 如果 ab, 则a%b=a kb(k为正整数)，令r为a和b的公约数， 则a%b=k1r kk2r=(k1-kk2)r, k1,k2为正整数

28、 所以r也是a%b的因子。 如果a%b和b的公约数为p，则 m1p = a km2p, a=(m1+km2)p, 则p也是a的因子。所以a%b和b 与 b和a 具有相同的公约数，它们的最大公约数也相同。北京大学程序设计实习课程44程序设计练习 例1：1006 生理周期o人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。o每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。o因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。o对于每个人，我们想知道何时三个高峰落在同一天。对于每

29、个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。o你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。 北京大学程序设计实习课程451006题o 输入n 输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于21252 。 o

30、 输出n 从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。北京大学程序设计实习课程461006题：问题分析o 令所求的时间为当年的第x天，则x具有如下性质：1) 21252 = x d2) (x-p)%23=03) (x-e)%28=04) (x-i)%33=0北京大学程序设计实习课程471006题o 一个最简单直观的做法就是枚举从d+1 到 21252 之间所有的数字，寻找第一个满足条件2）3）4）的数字，注意输出时间减去d.。北京大学程序设计实习课程481006题o 可以做的进一步改进是从d+1开始逐一枚举寻找满足条件2）的数字a，从a开始每步加23寻找满足条件2）3）的数字

31、b，从b开始每步加23*28寻找满足条件2）3）4）的数字x。x就是我们要找的数字，输出时输出x-d。北京大学程序设计实习课程491006题解题思想o 程序设计n / 读入p, e, i, d n / j从d+1 循环到21252， 如果 (j-p)%23=0，跳出循环n / j从上次跳出循环的值循环到21252， n 如果 (j-e)%28=0，跳出循环n / j从上次跳出循环的值循环到21252， n 如果 (j-i)%33=0，跳出循环n / 输出j-d#includeusing namespace std;int main() int p,e,i,d,j,no=1; cin p e i

32、 d; while(p!=-1 & e!=-1 & i!=-1 & d!=-1) for(j=d+1; j=21252; j+) if (j-p)%23 = 0) break; for( ; j=21252; j=j+23) if (j-e)%28 = 0) break; for( ; j=21252; j=j+23*28) if (j-i)%33 = 0) break; cout Case no; cout : the next triple peak occurs in ; cout j-d days. p e i d; no+; return 0;北京大学程序设计实习课程51程序设计练习

33、 例2：1013 称硬币o 问题描述n 赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。n 但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。 北京大学程序设计实习课程521013题o 输入n 输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的

34、硬币 天平右边放置的硬币 平衡状态。其中平衡状态用up, down, 或 even表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。 o 输出n 输出哪一个标号的银币是假币，并说明它比真币轻还是重。 北京大学程序设计实习课程531013题o 输入样例1 ABCD EFGH even ABCI EFJK up ABIJ EFGH even o 输出样例K is the counterfeit coin and it is light. 北京大学程序设计实习课程541013题o 问题分析n 此题并非要求你给出如何称量的方案，而是数据已经保证三组称量后答案唯一。不是那道传统的智商测验题

35、。n 此题可以有多种解法，这里只介绍一种比较容易想到和理解的 逐一枚举法。北京大学程序设计实习课程551013题o 总体构想 逐一试探法n 对于每一枚硬币p isLight ? n Yes. 输出，n No. isHeavy ?-Yes. 输出北京大学程序设计实习课程561013题o 定义变量存储称量结果n char left37,right37,result37;n 数组下标 3 代表3次称量；n 数组下标 7 代表每次左右至多6枚硬币，多出一个字符位置是为了方便用字符串读取的函数。北京大学程序设计实习课程571013题o 逐一枚举硬币的代码 for(char c=A; c=L;c+) if( isLight(c) ) cout c is the counterfeit coin and it is light.n; break; else if( isHeavy(c) ) cout c is the counterfeit coin and it is heavy.n; break; 北京大学程序设计实习课程581013题bool isLight(char x) / 判断硬币x是否为轻的代码 int i; for(i=0; i3; i+) / 判断是否与三次称量