程序设计简单问题.ppt

上海大学计算机工程与科学学院 第3章 程序设计简单问题 本章主要内容 3.1 ACM/ICPC程序设计竞赛的题型 3.2 简单例子 3.2.1 空格字符与非空格字符统计 3.2.2 荷兰国旗问题 3.2.3 城市间的球面距离 3.2.4 合并电话簿 3.2.5 图书排序问题 涉及的知识领域 计算机学科：程序设计、数据结构、算法设计与分析、编译原理、计算机复杂性、人工智能等， 数学领域：离散数学、组合数学、数论、群论、图论、代数、初等几何、计算几何、概率与统计、密码学等 其他学科：通信、自动化、力学、经济、金融、交通运输、物流等 ACM竞赛的题型 1、枚举法 2、递归算法 3、贪心策略 4、数值计算方法 5、动态规划 6、回溯法 7、广度有哪些信誉好的足球投注网站 8、A*算法 9、计算几何学 10、图的算法 11、网络流 12、博弈论 13、数论算法 14、逻辑问题 15、近似算法 16、近似有哪些信誉好的足球投注网站 17、模拟 18、其他 3.2.1 空格字符与非空格字符统计 问题描述 统计一个文件中每一行某些字符的个数。 输入 输入有若干行，每行中若干个字符，字符中可能含有空格，输入直到文件结束。注意最后一行不再换行。 输出 统计输入每行非空格字符与空格字符的个数，并一行输出这两个数，之间空一格。 输入样例与输出样例 输入样例 123fe*54 0934j df *A S 输出样例 14 1 5 3 分析 字符串中有可能含有空格等字符，因此对字符数组str，用cinstr试图读取整行字符串数据是错误的。 读取一行字符可采取以下两种典型方法 （1）依次读取一行中的每个字符，考察是否是空格字符，直到遇到行尾标志。 （2）采用getline()函数来读入一行数据，这是常用的、很方便的方法。 依次读取一行中每个字符的方法 用get()函数来读取，这里未用getline()函数。 本题未告诉输入有多少行，所以采用while循环比较合适。 用整型变量space、n分别统计空格字符数与非空格字符数。 操作过程： 每次读一个字符ch，若是行结束标志或到达文件尾部时，则输出非空格字符与空格字符的个数。 否则，再判断是否为非空格字符。 若是空格字符，则space增1； 若是非空格字符，则n增1。 while语句的使用问题 在输入流指针指向文件尾部时，用-1表示文件尾部标志。 因此在文件尾部标志前有换行符的情况下，下页的程序运行结果错误。 特别注意： 在Linux和Windows下，文本文件行结束的差异，不同的行结束标志输出的结果是不同的，特别在进行字符串处理时常会出错。 使用语句“while(!cin.eof())”一定要谨慎。 统计字符个数程序 #include iostream using namespace std; int main(){ char ch; int n=0,space=0; while(!cin.eof()){//若不是文件结束标志 if((ch=cin.get())!= ) { //若不是行结束标志，也不是文件结束标志 if ((ch!=\n)(ch!=-1)) n++;//统计非空格字符数 else { coutn spaceendl; n=0;space=0; } } else space++; //若是空格字符，则统计 } return 0; } 3.2.2 荷兰国旗问题 问题描述 荷兰国旗有三横条块构成，自上到下的三条块颜色依次为红、白、蓝。现有若干由红、白、蓝三种颜色的条块序列，要将它们重新排列使所有相同颜色的条块在一起。本问题要求将所有红色的条块放最左边、所有白色的条块放中间、所有蓝色的条块放最右边。 输入 第1行是一个正整数n（n20），表示有n组测试数据。接下来有n行，每行有若干个由R，W，B三种字符构成的字符串序列，其中R，W和B分别表示红、白、蓝三种颜色的条块。 输出 对输入中每行上由R，W，B三种字符构成的字符串序列，将它们重新排列使所有相同颜色的条块在一起，满足前述要求。 分析-第一种方法 本题要求将三种颜色的条块按颜色放在一起，即将红色条块放左边，蓝色条块放右边，剩下放中间。 本方法就是统计这三种条块的块数。这是很简单的事情。 通过getline()读取一行字符。 对读入的字符串进行处理：设三个变量r，w，b，分别表示红色、黄色、蓝色条块数。依次判断读入字符是否为R，W