第三讲 数制转换和日期处理

1、程序设计实习课程 (C+ Programming Practice)程序设计实习第三讲 数制转换和日期处理北京大学程序设计实习课程2内容提要o 关于 POJ 评测系统o 程序阅读练习 o 程序设计练习o 作业北京大学程序设计实习课程3关于 POJ 评测系统o 对于每一个题目，评测系统收到源代码后，就用在提交框中指定的编译器进行编译和链接得到目标代码后，将其运行。o 在运行过程中，如果程序要求从标准输入读入数据，则评测系统自动将已经存放在服务器端的测试数据提供给待测程序，待程序产生输出后，评测系统将程序产生的输出，与服务器端的标准答案做比较，如果相同，则程序被Accepted，否则出错。北京大学

2、程序设计实习课程4关于 POJ 评测系统o 出错程序的错误产生序列如下：n Compile Error，此时程序无法运行，可查看错误说明，如果程序有多个编译错，则只显示第一引起编译错的代码行引发的错误，如果你的程序在本机编译没错，通常有几种情况：选用了不正确的编译器，在VC+编程环境中编程由环境自动生成了“stdafx.h” 等等；n Runtime Error，运行错，通常是数组、指针越界，或除零错；北京大学程序设计实习课程5关于 POJ 评测系统n Time Limit Exceeded，超时错，在每个问题的说明里都给出了时限，如果提交的程序在相应的时间内不结束，则评测系统自动将其终止，并

3、返回超时错。引起超时错的原因主要有：死循环（尤其是判断输入结束有误），算法或代码效率不够好；n Output Limit Exceeded，输出过多，如果程序输出比标准答案多一倍以上的内容，则评测系统返回此错误。引发这一错误的原因多半是死循环。北京大学程序设计实习课程6关于 POJ 评测系统n Wrong Answer，结果错，这是最为复杂的一种错误，引发该错误的原因有很多，从读入数据不正确，到算法程序不正确，到输出不正确，都有可能引发该错误；n Presentation Error，格式错，这是最为温和的一类错误，如果得到格式错，表明输入和程序的算法都没有错误，给出的答案是正确的，只是在输出

4、时多余或少了空格空行等。有些时候不容易判格式错的问题也可能答案正确格式不正确，但得到结果错。北京大学程序设计实习课程7关于 POJ 评测系统n Problem Disabled，题目有错，两种可能：该题已被删除，或者是在http:/ 分析求解问题的方法o 架构程序的思路o 设计与调试程序的技巧北京大学程序设计实习课程9程序设计练习 上节课的例2（作业）o 1013 称硬币o 问题描述n 赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。n 但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果

5、赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。 北京大学程序设计实习课程101013题o 输入n 输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用up, down, 或 even表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。 o 输出n 输出哪一个标号的银币是假币;n 并说明它比真币轻还是重。 北京大学程序设计实习课程1110

6、13题o 输入样例1 ABCD EFGH even ABCI EFJK up ABIJ EFGH even o 输出样例K is the counterfeit coin and it is light. 北京大学程序设计实习课程121013题o 问题分析n 此题并非要求你给出如何称量的方案，而是数据已经保证三组称量后答案唯一。不是那道传统的智商测验题。n 此题可以有多种解法，这里只介绍一种比较容易想到和理解的 逐一枚举法。北京大学程序设计实习课程131013题o 总体构想 逐一试探法n 对于每一枚硬币x逐个试探：x比真币轻的猜测是否整理？若成立则输出； x比真币重的猜测是否整理？若成立则输出

7、p isLight ? n Yes. 输出，n No. isHeavy ?-Yes. 输出北京大学程序设计实习课程141013题o 定义变量存储称量结果n char left37,right37,result37;n 数组下标 3 代表3次称量；n 数组下标 7 代表每次左右至多6枚硬币，多出一个字符位置是为了方便用字符串读取的函数。北京大学程序设计实习课程151013题o 逐一枚举硬币的代码 for(char c = A; c = L; c+) if( isLight(c) ) cout c is the counterfeit coin and it is light.n; break;

8、else if( isHeavy(c) ) cout c is the counterfeit coin and it is heavy.n; break; 北京大学程序设计实习课程161013题bool isLight(char x) / 判断硬币x是否为轻的代码 int i; for(i=0; i3; i+) / 判断是否与三次称量结果矛盾 switch( resulti0 ) case u: if( ! inRight(i,x) ) return false; break; case e: if(inRight(i,x) | inLeft(i,x) return false; break

9、; case d: if(! inLeft(i,x) return false; break; return true;北京大学程序设计实习课程171013题bool isHeavy(char x) /判断硬币x是否为重的代码 int i; for(i=0; i3; i+) / 判断是否与三次称量结果矛盾 switch( resulti0 ) case u: if( ! inLeft(i,x) ) return false; break; case e: if(inRight(i,x) | inLeft(i,x) return false; break; case d: if(! inRigh

10、t(i,x) return false; break; return true;北京大学程序设计实习课程181013题bool inLeft(int i, char x) / 判断硬币x 是否在第i次称量左侧 int j; for(j=0; jstrlen(lefti); j+) if(leftij = x ) return true; return false; bool inRight(int i, char x)/ 判断硬币x 是否在第i次称量右侧 int j; for(j=0; jstrlen(righti); j+) if(rightij= x) return true; retur

11、n false; 北京大学程序设计实习课程#include #include double mysqrt(double guess, double x);bool goodEnough(double guess, double x);double improve(double guess, double x);void main() coutmysqrt(2.25,2.25) endl;double mysqrt(double guess, double x) if(goodEnough(guess,x) return guess; return mysqrt(improve(guess,x)

12、,x); bool goodEnough(double guess, double x) #define threshold 0.000001 if(fabs(guess*guess-x)threshold) return true; return false;double improve(double guess, double x) return (guess+x/guess)/2; 输出：北京大学程序设计实习课程20小结：如何阅读程序？o阅读程序不能象阅读小说o程序阅读的一些好方法n快速找到Main()和输入输出；n确定程序架构，画出流程图，确定调用关系；n找到关键语句段/函数，作为黑盒

13、子单独阅读/调试。o阅读代码的格言n第一次分析一个程序时，main是一个好的起始点。n层叠if-else if-. -else 序列可以看作是由互斥选择项组成的选择结构。n有时，要想了解程序在某一方面的功能，运行它可能比阅读源代码更为恰当。n在分析重要的程序时，最好首先识别出重要的组成部分。n了解局部的命名约定，利用它们来猜测变量和函数的功能用途。 n推理地递归调用等同于一个回到函数开始处的循环。n北京大学程序设计实习课程21程序阅读练习 例1#include #include double mysqrt(double guess, double x);bool goodEnough(doub

14、le guess, double x);double improve(double guess, double x);void main() coutmysqrt(2.25,2.25) endl;double mysqrt(double guess, double x) if(goodEnough(guess,x) return guess; return mysqrt(improve(guess,x),x); bool goodEnough(double guess, double x) #define threshold 0.000001 if(fabs(guess*guess-x)thr

15、eshold) return true; return false;double improve(double guess, double x) return (guess+x/guess)/2; 输出：1.5Mysqrt(guess,x)2.25,2.25Main()Mysqrt(y,x)Mysqrt(guess,x)goodEnough(guess,x)y=Improve(guess,x)NguessY北京大学程序设计实习课程22数值转换北京大学程序设计实习课程23数制转换（1）o 根据数制表示中相邻位的基数关系，数制可以分为两类n 相邻位的基数为等比关系：如十进制n 相邻位的基数为不等比

16、关系：如时间表示o 数制转换问题的一般处理方法n 数值存储：不是十进制时，一般用字符型数组来存放，数组中每个元素分别存储它的一个数字。n 十进制为中介：按位转换求和，得到十进制表示，再把十进制表示转换成所求的数制表示，结果也用字符型数组存储数制A数值（字符数组）数制B数值（字符数组）十进制数值（整型）北京大学程序设计实习课程24数制转换（2）o 数制B的bmbm-1b1十进制的dndn-1d1n 数制B的中第i位的基数为basei (1=i=m)n (basei * bi)o 十进制的dndn-1d1 数制B的bmbm-1b1n 数制B中相邻位的基数为等比关系：basei可表示为Ci(1)将d

17、ndn-1d1除以C，余数即为b1；(2)将dndn-1d1和C相除的结果再除以C，余数即为b2；直至计算出bm 。n 数制B中相邻位的基数为不等比关系：(1)判断dndn-1d1在数制B中需要的位数m；(2)从高到低依次计算bm , bm-1 , , b1 。北京大学程序设计实习课程25程序设计练习 例1o 1331(确定进制)问题描述n 6*9 = 42 对于十进制来说是错误的，但是对于13进制来说是正确的。即, 6(13) * 9(13) = 42(13)， 而 42(13) = 4 * 131 + 2 * 130 = 54(10)。 n 你的任务是写一段程序读入三个整数p, q和 r，

18、然后确定一个进制 B (2=B=16) 使得 p * q = r. 如果 B有很多选择, 输出最小的一个。n 例如： p = 11, q = 11, r = 121. 则有 对于进制3：11(3) * 11(3) = 121(3) 因为 11(3) = 1 * 31 + 1 * 30 = 4(10) 和 121(3) = 1 * 32 + 2 * 31 + 1 * 30 = 16(10)。 对于进制 10,有 11(10) * 11(10) = 121(10)。这种情况下，应该输出 3。如果没有合适的进制，则输出 0。北京大学程序设计实习课程26程序设计练习 例1o 输入n 输入有 T组测试样

19、例。 T在第一行给出。每一组测试样例占一行，包含三个整数p, q, r。 p, q, r 的所有位都是数字，并且1=p,q, r=1,000,000。o 输出n 对于每个测试样例输出一行。该行包含一个整数 - 即使得p * q = r成立的最小的B。如果没有合适的B，则输出 0。 北京大学程序设计实习课程27程序设计练习 例1o 输入样例3 6 9 42 11 11 121 2 2 2 o 输出样例13 30 北京大学程序设计实习课程28程序设计练习 例1o 此题没难度，逐一试探法，注意一些实现的细节。n 选择一个进制B（2=B=16），按照该进制将被乘数、乘数、乘积分别转换为10进制，然后判

20、断等式是否成立。选择使得等式成立的最小的B。n 分别用一个字符型数组存储p、q、r的各位数字符号。先以字符串的方式读入p、q、r，然后按照不同的进制将它们转换成十进制数，判断是否相等。北京大学程序设计实习课程29程序设计练习 例1long b2ten(char *x, int b) int ret = 0; int len = strlen(x); for(int i = 0; i = b) return -1; ret *= b; ret += xi - 0 ; return (long)ret; 北京大学程序设计实习课程30程序设计练习 例1#include #include long b

21、2ten(char* x,int b); void main( ) int n;char p8,q8,r8; scanf(%d,&n); while(n-) scanf(%s%s%s, p, q, r); for(int b = 2; b = 16; b+) long p2 = b2ten(p,b); long q2 = b2ten(q,b); long r2 = b2ten(r,b); if(p2 = -1 | q2 = -1 | r2 = -1) continue; if(p2*q2 = r2) printf(%dn, b); break; if(b=17) printf(0n);

22、 北京大学程序设计实习课程31小结：程序设计的一般步骤o 问题分析n 理解问题，确定任务、输入、输出n 找到关键条件（如数据的边界、关键数据的性质等）n 确定解题的思路o 框架设计n 用文字描述主程序的框架n 包括输入输出、主要程序块n 确定主要数据的存储结构n 将公用的处理封装成函数o 代码设计n 将程序框架变成代码n 编辑调试北京大学程序设计实习课程32程序设计练习 课堂练习1o 1565(skew数)o 问题描述n 在 skew binary表示中, 第 k 位(从0开始计数)的值xk表示xk* (2k+1-1)。 每个位上的可能数字是0 或 1，最后面一个非零位可以是2, 例如, 10

23、120(skew) = 1 * (25-1) + 0 * (24-1) + 1 * (23-1) + 2 * (22-1) + 0 * (21-1) = 31 + 0 + 7 + 6 + 0 = 44 前十个skew数是 0, 1, 2, 10, 11, 12, 20, 100, 101, and 102。北京大学程序设计实习课程33程序设计练习 课堂练习1o 输入n 输入包含一或多行，每行包含一个整数n。 如果 n = 0 表示输入结束，否则n是一个skew 数.o 输出n 对于每一个输入，输出它的十进制表示。转换成十进制后， n 不超过 231-1 = 2147483647.北京大学程序设

24、计实习课程34程序设计练习 课堂练习1o 输入样例10120 200000000000000000000000000000 10 1000000000000000000000000000000 11 100 11111000001110000101101102000 0 o 输出样例44 2147483646 3 2147483647 4 7 1041110737 北京大学程序设计实习课程35解题思路o skew数中相邻位的基数为不等比关系，因此先需计算基数o 对于长度为k的skew数，最高一位数字的基数为2k-1o 用一个整型数组base31,依次从低到高存放skew数的基数北京大学程序设计

25、实习课程36日期和时间处理北京大学程序设计实习课程37程序设计练习 例1o 问题描述：n 一种细菌的繁殖速度是每天成倍增长。例如：第一天有10个，第二天就变成20个，第三天变成40个，第四天变成80个，。n 现在给出第一天的日期和细菌数目，要你写程序求出到某一天的时候，细菌的数目。北京大学程序设计实习课程38程序设计练习 例1o 输入n 第一行有一个整数n，表示测试数据的数目。其后n行每行有5个整数，整数之间用一个空格隔开。第一个数表示第一天的月份，第二个数表示第一天的日期，第三个数表示第一天细菌的数目，第四个数表示要求的那一天的月份，第五个数表示要求的那一天的日期。n 已知第一天和要求的一天

26、在同一年并且该年不是闰年，要求的一天一定在第一天之后。数据保证要求的一天的细菌数目在长整数（long）范围内。o 输出n 对于每一组测试数据，输出一行，该行包含一个整数，为要求的一天的细菌数。北京大学程序设计实习课程39程序设计练习 例1o 样例输入2 1 1 1 1 22 28 10 3 2 o 样例输出2 40 北京大学程序设计实习课程40解题思路o 求给定的两天之间间隔的天数m，第一天的细菌数乘以2的m次方就是题目的答案o 难点：每月的天数不很规则，程序处理过程中较为复杂n用一个数组将每个月的天数存起来o 算法框架n读入测试样例数n；n做n次(1)读入两个日期及第一天的细菌数；(2)得到

27、两个天数的差，即他们中间间隔的天数m；(3)用第一天的细菌数乘以2的m次方得到x；(4)输出x北京大学程序设计实习课程#include void main()int nDays12=31,28,31,30,31,30,31,31,30,31,30,31;int n; scanf(%d, &n); for (int i = 0; i n; i+)int month_1,day_1,month_2,day_2,num; /起止日期的月份和日期起止日期的月份和日期scanf(%d%d%d%d%d, &month_1, &day_1, &num, &month_

28、2, &day_2);int sum = 0;for (int k = month_1; k month_2; k+)sum += nDaysk - 1;sum -= day_1;sum += day_2;long nNum = num;for (k = 0; k sum; k+)nNum *=2;printf(%dn, nNum);北京大学程序设计实习课程42程序设计练习 例2o POJ 2080o 问题描述：n 给定从公元2000年1月1日(周六)开始逝去的天数，你的任务是给出这一天是哪年哪月哪日星期几。n 在我们现在使用的日历中, 闰年被定义为能被4整除的年份n 但是能被100整

29、除而不能被400整除的年是例外，它们不是闰年。例如：1700, 1800, 1900 和 2100 不是闰年，而 1600, 2000 和 2400是闰年。北京大学程序设计实习课程43程序设计练习 例2o 输入：n 输入包含若干行，每行包含一个正整数，表示从2000年1月1日开始逝去的天数。输入最后一行是1, 不必处理。可以假设结果的年份不会超过9999。o 输出：n 对每个测试样例，输出一行，该行包含对应的日期和星期几。n 格式为“YYYY-MM-DD DayOfWeek”, 其中 “DayOfWeek” 必须是下面中的一个： Sunday, Monday, Tuesday, Wednesd

30、ay, Thursday, Friday and Saturday“。北京大学程序设计实习课程44程序设计练习 例2o 样例输入1730 1740 1750 1751 -1 o 样例输出2004-09-26 Sunday 2004-10-06 Wednesday 2004-10-16 Saturday 2004-10-17 Sunday北京大学程序设计实习课程45程序设计练习 例2o 问题解答n 此题为典型的日期处理程序，没有难度，只是编程需要特别细心，日期处理的程序非常容易出错。o 基本思路：n 确定星期几；n 确定年；闰年366天，否则365天n 确定月；每个月长短不同1. 确定日。北京大

31、学程序设计实习课程46程序设计练习 例2#include void main() int m112=31,28,31,30,31,30,31,31,30,31,30,31; int m212=31,29,31,30,31,30,31,31,30,31,30,31; char week710=Saturday,Sunday,Monday, Tuesday,Wednesday,Thursday,Friday; int days, weekday; scanf(%d,&days);while(days != -1) weekday = days%7; days+; int daysinyea

32、r=0; int ithyear=2000; while(days 0) /确定年确定年 if(ithyear%100=0 & ithyear%400 != 0) daysinyear=365; else if(ithyear%4=0) daysinyear = 366; else daysinyear = 365; days -= daysinyear; ithyear +; 北京大学程序设计实习课程47程序设计练习 例2 ithyear -; days += daysinyear; int ithmonth=0; while(days 0)/确定月确定月 if(daysinyear = 365) days -= m1ithmon