程序设计简单问题

1、2022-2-4第第3章章 程序设计简单问题程序设计简单问题沈云付沈云付上海大学计算机工程与科学学院上海大学计算机工程与科学学院2022-2-4本章主要内容本章主要内容3.1 ACM/ICPC3.1 ACM/ICPC程序设计竞赛的题型程序设计竞赛的题型3.2 3.2 简单例子简单例子3.2.1 3.2.1 空格字符与非空格字符统计空格字符与非空格字符统计3.2.2 3.2.2 荷兰国旗问题荷兰国旗问题3.2.3 3.2.3 城市间的球面距离城市间的球面距离3.2.4 3.2.4 合并电话簿合并电话簿3.2.5 3.2.5 图书排序问题图书排序问题2022-2-43.1 ACM/ICPC程序设计

2、竞赛程序设计竞赛的题型的题型2022-2-4涉及的知识领域涉及的知识领域 计算机学科：程序设计、数据结构、算法设计与分析、计算机学科：程序设计、数据结构、算法设计与分析、编译原理、计算机复杂性、人工智能等，编译原理、计算机复杂性、人工智能等， 数学领域：离散数学、组合数学、数论、群论、图论、数学领域：离散数学、组合数学、数论、群论、图论、代数、初等几何、计算几何、概率与统计、密码学等代数、初等几何、计算几何、概率与统计、密码学等 其他学科：通信、自动化、力学、经济、金融、交通运其他学科：通信、自动化、力学、经济、金融、交通运输、物流等输、物流等2022-2-4ACM竞赛的题型竞赛的题型1、枚举

3、法、枚举法 2、递归算法、递归算法 3、贪心策略、贪心策略4、数值计算方法、数值计算方法 5、动态规划、动态规划 6、回溯法、回溯法7、广度搜索、广度搜索 8、A*算法算法 9、计算几何学、计算几何学10、图的算法、图的算法 11、网络流、网络流 12、博弈论、博弈论13、数论算法、数论算法 14、逻辑问题、逻辑问题 15、近似算法、近似算法16、近似搜索、近似搜索 17、模拟、模拟 18、其他、其他2022-2-43.2 简单例子简单例子2022-2-43.2.1 空格字符与非空格字符统计空格字符与非空格字符统计 问题描述问题描述统计一个文件中每一行某些字符的个数。统计一个文件中每一行某些字

4、符的个数。输入输入输入有若干行，每行中若干个字符，字符中可能含有空输入有若干行，每行中若干个字符，字符中可能含有空格，输入直到文件结束。注意最后一行不再换行。格，输入直到文件结束。注意最后一行不再换行。输出输出 统计输入每行非空格字符与空格字符的个数，并一行输统计输入每行非空格字符与空格字符的个数，并一行输出这两个数，之间空一格。出这两个数，之间空一格。 2022-2-4输入样例与输出样例输入样例与输出样例 输入样例输入样例 123fe*&54 0934jdf *A S 输出样例输出样例 14 15 3 2022-2-4分析分析 字符串中有可能含有空格等字符，因此对字符数组字符串中有可

5、能含有空格等字符，因此对字符数组str，用，用cinstr试图读取整行字符串数据是错误的。试图读取整行字符串数据是错误的。 读取一行字符可采取以下两种典型方法读取一行字符可采取以下两种典型方法 （1）依次读取一行中的每个字符，考察是否是空格字符，）依次读取一行中的每个字符，考察是否是空格字符，直到遇到行尾标志。直到遇到行尾标志。（2）采用）采用getline()函数来读入一行数据，这是常用的、很方函数来读入一行数据，这是常用的、很方便的方法。便的方法。2022-2-4依次读取一行中每个字符的方法依次读取一行中每个字符的方法用用get()函数来读取，这里未用函数来读取，这里未用getline()

6、函数。函数。本题未告诉输入有多少行，所以采用本题未告诉输入有多少行，所以采用while循环比较合适。循环比较合适。用整型变量用整型变量space、n分别统计空格字符数与非空格字符分别统计空格字符数与非空格字符数。数。 操作过程：操作过程：每次读一个字符每次读一个字符ch，若是行结束标志或到达文件尾部时，则输，若是行结束标志或到达文件尾部时，则输出非空格字符与空格字符的个数。出非空格字符与空格字符的个数。否则，再判断是否为非空格字符。否则，再判断是否为非空格字符。若是空格字符，则若是空格字符，则space增增1；1.若是非空格字符，则若是非空格字符，则n增增1。2022-2-4whilewhil

7、e语句的使用问题语句的使用问题在输入流指针指向文件尾部时，用在输入流指针指向文件尾部时，用-1表示文件尾部标志。表示文件尾部标志。因此在文件尾部标志前有换行符的情况下，下页的程序因此在文件尾部标志前有换行符的情况下，下页的程序运行结果错误。运行结果错误。特别注意：特别注意：在在Linux和和Windows下，文本文件行结束的差异，不同下，文本文件行结束的差异，不同的行结束标志输出的结果是不同的，特别在进行字符串的行结束标志输出的结果是不同的，特别在进行字符串处理时常会出错。处理时常会出错。1.使用语句使用语句“while(!cin.eof()”一定要谨慎。一定要谨慎。 2022-2-4统计字符

8、个数程序统计字符个数程序#include 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;2022-2-4

9、3.2.2 3.2.2 荷兰国旗问题荷兰国旗问题问题描述问题描述 荷兰国旗有三横条块构成，自上到下的三条块颜色依次为荷兰国旗有三横条块构成，自上到下的三条块颜色依次为红、白、蓝。现有若干由红、白、蓝三种颜色的条块序列，红、白、蓝。现有若干由红、白、蓝三种颜色的条块序列，要将它们重新排列使所有相同颜色的条块在一起。本问题要将它们重新排列使所有相同颜色的条块在一起。本问题要求将所有红色的条块放最左边、所有白色的条块放中间、要求将所有红色的条块放最左边、所有白色的条块放中间、所有蓝色的条块放最右边。所有蓝色的条块放最右边。输入输入 第第1行是一个正整数行是一个正整数n（nn; cin.get();

10、/吸收尾部标记吸收尾部标记 for(j=0;jn;j+) cin.getline(Flag,100,n);/读取一行读取一行 len=strlen(Flag); b=0;r=0;w=0; for(i=0;ilen;i+)/统计个数统计个数 if(Flagi=R) r+; else if(Flagi=B) b+; else w+; for(i=0;ir;i+) coutR; for(i=0;iw;i+) coutW; for(i=0;ib;i+) coutB; coutn; cin.get();/吸收第一行尾部标志吸收第一行尾部标志for(j=0;jn;j+) cin.getline(Flag,

11、100,n);/输入一行，并取字符串长度输入一行，并取字符串长度 len=strlen(Flag); r=0; p=0; b=len-1; while(p=b) if(Flagp=R) Flagp=Flagr, Flagr=R, r=r+1, p=p+1;else if(Flagp=B) Flagp=Flagb; Flagb=B;b=b-1; else p=p+1; printarray(len,Flag); /输出数组输出数组 return 0;2022-2-43.2.3 城市间的球面距离城市间的球面距离问题描述问题描述 假定地球上的位置是用经度和纬度给定的。经度和纬度都假定地球上的位置是用

12、经度和纬度给定的。经度和纬度都是一种角度。某一点的经度，就是该点所在的经线平面与是一种角度。某一点的经度，就是该点所在的经线平面与本初子午线平面间的夹角。纬度是该地对于赤道的方向和本初子午线平面间的夹角。纬度是该地对于赤道的方向和角度，赤道是角度，赤道是0纬线。纬线。 地球的赤道半径地球的赤道半径6378137米，忽略地球非球形对称，其平米，忽略地球非球形对称，其平均半径均半径R=6371公里。为方便起见，将地球看作是半径为公里。为方便起见，将地球看作是半径为6371公里的球体。公里的球体。 现在，告诉你甲地和乙地的位置，要求你求这两地之间的现在，告诉你甲地和乙地的位置，要求你求这两地之间的最

13、短球面距离。最短球面距离。 2022-2-4输入输入 输入的第一行是一个正整数输入的第一行是一个正整数n，（，（n35），表示有），表示有n个城个城市。市。 接下来有接下来有n行，每行是一个城市的描述：城市名行，每行是一个城市的描述：城市名city、城、城市所在的经度市所在的经度longitude和纬度和纬度latitude。输出输出 根据输入中的根据输入中的n个城市，输出一张城市间的球面距离表，个城市，输出一张城市间的球面距离表，即一个（即一个（n+1） （n+1）阵列，每列占）阵列，每列占10个字符位置，左个字符位置，左对齐。第一行上先输出对齐。第一行上先输出“Start-End”，接着按

14、读入城市的，接着按读入城市的次序依次输出次序依次输出n个城市的名称。接着有个城市的名称。接着有n行，第行，第i行上先输行上先输出第出第i个城市的名称，接着依次输出该城市与第个城市的名称，接着依次输出该城市与第j个城市间个城市间的球面距离（四舍五入保留二位小数）。的球面距离（四舍五入保留二位小数）。2022-2-4输入与输出样例输入与输出样例 输入样例输入样例 输出样例输出样例 3Beijing 116.47 39.9Hangzhou 120.15 30.23Shanghai 121.48 31.23 Start-End Beijing Hangzhou Shanghai Beijing 0.0

15、0 1125.91 1064.77 Hangzhou 1125.91 0.00 168.89 Shanghai 1064.77 168.89 0.00 2022-2-4分析分析 地球是一个曲面，如图所示。地球上两点地球是一个曲面，如图所示。地球上两点A，B之间的距之间的距离是在连接离是在连接A、B的沿着地球表面的所有曲线中最短曲线的沿着地球表面的所有曲线中最短曲线的长度。设地球的圆心为的长度。设地球的圆心为O。那么这个长度即为以。那么这个长度即为以A，B，O三点确定的平面与地球的交形成的大圆中劣弧三点确定的平面与地球的交形成的大圆中劣弧AB的长度。的长度。由于地球的半径已知，只要求出由于地球的

16、半径已知，只要求出 AOB的大小，就可以求的大小，就可以求出劣弧出劣弧AB的长度。的长度。 2022-2-4分析分析 假设点假设点A在东经在东经 度、北纬度、北纬 度；点度；点B在东经在东经 度、南纬度、南纬 度。度。设设O1，O2分别为北纬分别为北纬 度纬线圈的圆心和南纬度纬线圈的圆心和南纬 度纬线圈度纬线圈的圆心。那么：的圆心。那么： O1AO = ， O2BO = ， O1A = R cos ，O1O = R sin ， O2B = R cos ，O2O = R sin 。 过过B作作O1O2的平行线、过的平行线、过O1作作BO2的平行线，两线相交于的平行线，两线相交于C，设，设AO1C

17、的值为的值为 ，那么，那么 = | |。 根据余弦定理，可以求得根据余弦定理，可以求得AC2 = O1A2 + O1C2 2O1AO1Ccos 。2022-2-4分析分析 因因O1C = O2B，所以，所以AC2 = R2cos2 + R2cos2 - 2R2cos cos cos 。 但但BC2= (O1O + O1O) 2=R2sin2 + R2sin2 + 2R2sin sin ，所以由，所以由AB2 = AC2 + BC2得得AB2 = R2cos2 + R2cos2 - 2R2cos cos cos + R2sin2 + R2sin2 + 2R2sin sin 即：即：AB2 = 2

18、R2(1 + sin sin - cos cos cos ) 又在三角形又在三角形AOB中，用余弦定理也可得到中，用余弦定理也可得到 AB2 = OA2 + OB2 2OAOBcos AOB = 2R2 2R2cos AOB。 于是，于是，cos AOB= cos cos cos - sin sin 2022-2-4球面距离计算公式球面距离计算公式A、B球面距离球面距离=地球平均半径地球平均半径arccos(cos(北纬北纬A)cos(北纬北纬B)cos(AB两两地经度差绝对值地经度差绝对值)+sin(北纬北纬A)sin(北纬北纬B) )。2022-2-4数据结构数据结构typedef str

19、uct /城市位置城市位置char Cname15; /城市名城市名double Lat;/经纬度经纬度double Lon;CITY;typedef struct /城市表城市表int Nbcities;/城市数城市数CITY cities40;/城市信息城市信息CITIESLIST;2022-2-4计算球面距离计算球面距离void CalculateDistances(CITIESLIST citieslist,double d4040)int i,j;for(i=0;icitieslist.Nbcities;i+) for(j=0;jcitieslist.Nbcities;j+) dij

20、=6371.0*acos( cos(citieslist.citiesi.Lat)*cos(citieslist.citiesj.Lat) *cos(citieslist.citiesj.Lon-citieslist.citiesi.Lon) +sin(citieslist.citiesi.Lat)*sin(citieslist.citiesj.Lat); 2022-2-4输出距离表输出距离表void WriteDistanceMatrix(CITIESLIST citieslist,double d4040) int i,j;coutsetw(10)setiosflags(ios:left)

21、Start-End;for(i=0;i=citieslist.Nbcities-1;i+) coutsetw(10)setiosflags(ios:left) citieslist.citiesi.Cname;coutn;for(i=0;icitieslist.Nbcities;i+) coutsetw(10)citieslist.citiesi.Cname; for(j=0;jcitieslist.Nbcities;j+)coutsetw(10)setiosflags(ios:fixed) setprecision(2) dij; coutn;2022-2-43.2.4 合并电话簿合并电话簿

22、问题描述问题描述 有两本电话簿，现要合并这两本电话簿形成一本新的电话有两本电话簿，现要合并这两本电话簿形成一本新的电话簿，使新电话簿无冗余信息。簿，使新电话簿无冗余信息。输入输入 有两本电话簿的描述。描述每本电话簿的第有两本电话簿的描述。描述每本电话簿的第1行是一个正行是一个正整数整数n（n50），接下来有），接下来有n行，每行是一个人的个人数行，每行是一个人的个人数据，包含：姓、名、所在城市和电话号码。每本电话簿都据，包含：姓、名、所在城市和电话号码。每本电话簿都按姓以字典序升序排列。按姓以字典序升序排列。输出输出 对这两本电话簿进行合并，使合并后仍按姓以字典序升序对这两本电话簿进行合并，使

23、合并后仍按姓以字典序升序排列。首先输出合并后的个人数据总数，接着输出个人信排列。首先输出合并后的个人数据总数，接着输出个人信息。如果两本电话簿中的个人数据完全一致，则保留一个。息。如果两本电话簿中的个人数据完全一致，则保留一个。如果两个人的姓相同，那么先出现的人仍在前。如果两个人的姓相同，那么先出现的人仍在前。 2022-2-4输入与输出样例输入与输出样例输入样例输入样例输出样例输出样例2Dupont Albert Paris 45247000Smith John Washington 185544203Brown Gordon London 44863645Martin Martin Tro

24、yes 25452829Popov Nikolai Moscow 182229315Brown Gordon London 44863645Dupont Albert Paris 45247000Martin Martin Troyes 25452829Popov Nikolai Moscow 18222931Smith John Washington 185544202022-2-4分析分析建立一个数据结构，称为建立一个数据结构，称为PhoneForm，储存一个人，储存一个人的姓、名、所在城市和电话号码。的姓、名、所在城市和电话号码。struct Phonechar snameMAXN;ch

25、ar otherInfoMAXN;PhoneForm;Sname记录姓，记录姓， otherInfo记录记录名、所在城市和电话号码名、所在城市和电话号码等其它信息。等其它信息。本题中每本电话簿中的个人数据已按姓升序排列。本题中每本电话簿中的个人数据已按姓升序排列。为能合并这两本电话簿，需要将第一本中姓为能合并这两本电话簿，需要将第一本中姓name1与第与第二本中的姓二本中的姓name2进行比较，通过函数进行比较，通过函数strcmp实现实现。2022-2-4分析分析合并的基本原则是：合并的基本原则是：通过类似于擂台赛的方式对两队队列进行比较，直到一通过类似于擂台赛的方式对两队队列进行比较，直到

26、一个电话簿的结束：个电话簿的结束： 读出第一本电话簿中一行个人数据读出第一本电话簿中一行个人数据person1与第二本与第二本电话簿中的一行个人数据电话簿中的一行个人数据person2。 将将person1的姓与的姓与person2的姓进行比较。的姓进行比较。 如果如果person1的姓在前，或者两者姓相同但个人信息的姓在前，或者两者姓相同但个人信息不完全相同，那么将不完全相同，那么将person1个人数据进行输出，再个人数据进行输出，再从第一本电话簿中读后继的一个人；从第一本电话簿中读后继的一个人； 如果如果person1的姓在后，那么将的姓在后，那么将person2个人数据进行个人数据进行

27、输出，再从第二本电话簿中读后继的一个人；输出，再从第二本电话簿中读后继的一个人；1. 如果两个人信息完全相同，那么分别从第一、二本如果两个人信息完全相同，那么分别从第一、二本电话簿中读后继的一个人作为电话簿中读后继的一个人作为person1和和person2。2022-2-4两个人的姓相同时情况的处理两个人的姓相同时情况的处理 若两本电话簿中的个人数据完全一致，则保留一个。若两本电话簿中的个人数据完全一致，则保留一个。 合并后个人信息条数将会减少合并后个人信息条数将会减少1条。条。 为输出合并后的个人信息条数，需要进行一些处理，为输出合并后的个人信息条数，需要进行一些处理，即采用边合并边统计的

28、方法。即采用边合并边统计的方法。 再输出个人信息条数以及所有这些个人信息。再输出个人信息条数以及所有这些个人信息。2022-2-4合并电话簿信息程序实现合并电话簿信息程序实现PhoneForm *merge(PhoneForm *person1, PhoneForm *person2,int np1,int np2,int *total)int order, num1=0,num2=0,num=0;PhoneForm *person=new PhoneForm(np1+np2)*sizeof(PhoneForm);while(num1np1) & (num2np2) order=str

29、cmp(person1num1.sname, person2num2.sname); if(order0|order=0&strcmp(person1num1.otherInfo , person2num2.otherInfo)!=0) strcpy(personnum.sname,person1num1.sname);strcpy(personnum.otherInfo,person1num1.otherInfo);num1+; 续2022-2-4 elseif(strcmp(person1num1.otherInfo, person2num2.otherInfo)=0) strcpy(personnum.sname,person1num1.sname); strcpy(personnum.othe