- 数据结构编程实验（第3版）
- 吴永辉 王建德编著
- 2605字
- 2021-08-13 17:24:03
4.1.1 日期计算
日期由年、月、日来表示。日期类型的题目可以用数组作为数据结构，存储方式一般有两种：
·用一个结构数组存储，数组元素为一个包含年、月、日等信息的结构体；
·分别使用记录年、月、日的3个整数数组存储。
将输入的日期通过线性表组织起来，其结构特征不仅充分体现了线性表“有限性”（日期元素的个数有限）、“有序性”（日期元素一个接一个排列）、“均匀性”（各日期元素的类型相同）的性质，而且表长相对固定，可直接按下标存取日期元素。因此存储日期元素的线性表是一种典型的直接存取类线性表。
由于日期的计算和日历法的转换需要在表述日期的数据间进行运算，而输出的月份或周几一般需要相应的英文表述，因此可将这些英文表述设成一个线性的字符串常量表，其下标与日期数字对应。计算得出日期数据后，以它为下标，即可从表中找出对应的字符串。下面给出日期计算的两个实例。
【4.1.1.1 Calendar】
日历是用于表述时间的系统，从小时到分钟，从月到日，最后从年份到世纪。术语小时、日、月、年、世纪都是日历系统表述时间的单位。
按照目前国内使用的阳历，闰年被定义为能被4整除的年份，但是能被100整除而不能被400整除的年是例外，它们不是闰年。例如1700、1800、1900和2100年不是闰年，而1600、2000和2400年是闰年。给定公元2000年1月1日后的天数，请你计算这一天是哪年哪月哪日星期几。
输入
输入包含若干行，每行包含一个正整数，表示2000年1月1日后的天数。输入最后一行是-1，程序不必处理。可以假设输出的年份不会超过9999。
输出
对每个测试用例，输出一行，该行给出对应的日期和星期几。格式为“YYYY-MM-DD DayOfWeek”，其中“DayOfWeek”必须是下面中的一个：“Sunday”“Monday”“Tuesday”“Wednesday”“Thursday”“Friday”或“Saturday”。
试题来源：ACM Shanghai 2004 Preliminary
在线测试：POJ 2080，ZOJ 2420
试题解析
首先设计两个函数：
1）days_of_year(year)：计算year年的天数。若year能被4整除但不能被100整除，或者year能被400整除，则year年是闰年，全年366天；否则year年是平年，全年365天。
2）days_of_month(month,year)：计算year年month月的天数。在month==2的情况下，若year年是闰年，则该月天数为29天，否则，year年是平年，该月天数为28天；在month==1、3、5、7、8、10、12的情况下，该月天数为31天；在month==4、6、9、11的情况下，该月天数为30天。
我们以2000年1月1日（星期六）为基准，按照如下方法计算n天后的年、月、日和星期的信息：设year、month、day为表示年、月、日变量，wstr为星期几的字符串常量。初始时year=2000，month=1，day=1。设n是2000年1月1日后的天数。
首先计算星期几：以2000年1月1日的星期六为每周周期的开始，即wstr[0‥6]={"Saturday","Sunday","Monday","Tuesday","Wednesday","Thursday","Friday"}。显然wstr[n%7]即2000年1月1日的n天后的星期几。
接下来计算year：在n>0的情况下，若n≥days_of_year(year)，则n-=days_of_year(year)，++year，直至days_of_year(year)大于n为止，此时的n为year内的天数。
最后计算month和day：在n>0的情况下，若n≥days_of_month(month,year)，则n-=days_of_month(month,year)，++month，直至year年month月的天数大于n为止，此时的n为year年month月内的天数。显然day=n+day，n=0。
参考程序
#include <iostream> //预编译命令
using namespace std; //使用 C++标准程序库中的所有标识符
const char wstr[][20] //周几的字符串常量
= {"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};
int days_of_year(int year) // 返回year年的天数
{
if (year % 100 == 0)
return year % 400 == 0 ? 366 : 365;
return year % 4 == 0 ? 366 : 365;
}
int days_of_month(int month, int year) // 返回year年month月的天数
{
if (month == 2)
return days_of_year(year) == 366 ? 29 : 28;
int d;
switch (month) {
case 1: case 3: case 5: case 7: case 8:
case 10: case 12:
d = 31;
break;
default:
d = 30;
}
return d;
}
int main(void)
{
int n;
cin >> n; //输入第1个测试用例
while (n >= 0) {
int year, month, day, week;
week = n % 7; //为方便起见，将星期六（2000年1月1日为星期六）作为一个星期的开始
year = 2000;
month = 1;
day = 1;
while (n) {
if (n >= days_of_year(year)) { // 先枚举到指定年份
n -= days_of_year(year);
++year;
} else if (n>=days_of_month(month, year)){ // 再枚举到指定月份
n -= days_of_month(month, year);
++month;
} else { // 最后确定日期
day += n;
n = 0;
}
}
//按照格式要求输出对应的日期和星期几
cout << year << '-' << (month < 10 ? "0" : "") << month << '-'
<< (day < 10 ? "0" : "") << day << ' ' << wstr[week] << endl;
cin >> n; //输入下一个测试用例
}
return 0;
}
【4.1.1.2 What Day Is It?】
现在使用的日历是从古罗马时期演变来的。Julius Caesar编纂了日历系统，后来被称为Julius历。在这个日历系统中，4月、6月、9月和11月有30天；非闰年的2月有28天，闰年的2月则有29天；其他月份有31天。此外，在这个日历系统中，闰年是每4年1次。这是由于古罗马的天文学家计算出1年有365.25天，因此在每4年之后，需要添加额外的一天以保持季节的正常。为此，每4年要在一年中增加额外的一天（2月29日）。
Julians历规则：如果年份是4的倍数，则该年是闰年，即有额外的一天（2月29日）。
在1582年，天文学家们注意到，该年不是365.25天，而是接近365.2425天。因此，闰年的规则被修订。
Gregorian历（公历）规则：年份是4的倍数是闰年，但如果这一年是100而不是400的倍数，则不是闰年。
为了弥补在那个时候已经造成的季节与日历的差异，日历被挪后了10天：在第二天，1582年10月4日被宣布为10月15日。
英国（当然，那时还包括美国）当时没有改用公历，一直到1752年，才将9月2日宣布为9月14日。
请你编写一个程序，对美国使用日历的日期进行转换，并输出是星期几。
输入
输入是一个大于零的正整数序列，每行3个代表日期的整数，一个日期一行。日期的格式是“月 日 年”，其中月是1～12的正整数（1表示1月，12表示12月，等等），日是一个1～31的正整数，而年则是一个正整数。
输出
输出按照样例输出中给出的格式给出输入的日期和星期几。在美国使用的日历中，无效的日期或不存在的日期则要输出一个指出无效日期错误消息。输入以三个0结束。
试题来源：ACM Pacific Northwest 1997
在线测试：ZOJ 1256，UVA 602
试题解析
由于输出转换后的日期中，月份和星期是字符串，因此给出月份和星期的字符串常量：
const char wstr[ ][maxs] //表示周几的字符串常量
={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
const char mstr[ ][maxs] //表示月份的字符串常量
= {"", "January", "February", "March", "April","May","June", "July","August", "September", "October", "November", "December"};
一旦确定月份和星期的整数，将其作为对应字符串常量数组的下标，便可以直接取出表述日期的字符串。设year、month和day为当前日期的年月日整数；old为当前日期属于1752年9月2日前的标志，即old=（year<1752||(year==1752 & & month<9)||(year==1752 & & month==9 & & day<=2)）。
若old==true且year能被4整除，则year是闰年；否则若year能被4整除但不能被100整除，或者能被400整除，则year是闰年。
基于old，设计如下4个函数：
·isLeap(year,old)：判断year是否为闰年。
·days_of_year(year,old)：计算year年的天数。
·days_of_month(month,year,isLeap(year,old))：计算year年month月的天数。
·valid(month,day,year,old)：判断year年month月day日是否为无效日期。若(year≥1) & & (1≤month≤12) & & (1≤day≤days_of_month(month,year,isLeap(year,old)) & & （该日期不在1752年9月3～13日的范围内），则有效。
有了以上基础，便可以展开主算法了：反复读入当前日期的year、month、day，每读入一个日期，按照下述方式进行转换。
计算当前是否日期属于1752年9月2日前的标志old；通过执行valid(month,day,year,old)函数判别该日期是否为无效日期。若是，则输出无效日期信息，并继续读下一个日期；否则计算累计公元0年至该日期的总天数；
month(i, year, isleap(yeat, old))+day；若该日期在1752年9月2日之后，则为星期(sum%7)；否则为星期((sum+5)%7)，输出转换后的日期，并继续读下一个日期。
上述过程一直进行至year、month和day全为0为止。
参考程序
#include <iostream> //预编译命令
#include <cstdio>
#include <cstring>
using namespace std; //使用C++标准程序库中的所有标识符
const int maxs = 20; //字符串常量表的容量
const char wstr[][maxs] //表示周几的字符串常量
= {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
const char mstr[][maxs] //表示月份的字符串常量
= {"", "January", "February", "March", "April","May", "June", "July", "August", "September", "October", "November", "December"};
bool isLeap(int year, bool old = false) //判断year是否闰年
{
if (old) //year年month月day日在1752年9
//月2日前
return year % 4 == 0 ? true : false;
return (year % 100 == 0 ? (year % 400 == 0 ? true : false) : (year % 4 == 0 ? true : false));
}
int days_of_month(int month, int year, bool leap) // 返回year年month月的天数
{
if (month == 2)
return leap ? 29 : 28;
int d;
switch (month) {
case 1: case 3: case 5: case 7: case 8:
case 10: case 12:
d = 31;
break;
default:
d = 30;
}
return d;
}
int days_of_year(int year, bool old) // 返回year年的天数
{
return isLeap(year, old) ? 366 : 365;
}
int getNum(char s[], const char ss[][maxs], int tot) //返回s在ss中的位置，如果s在ss
//中不存在，则返回-1
{
int i = 0;
while (i < tot && strcmp(s, ss[i]))
++i;
return i < tot ? i : -1;
}
bool valid(int month, int day, int year, bool old) //若year≥1且month∈{1..12}
//且day∈{1.. year年month月的天数}且year年month月day天不在1752年9月3日到
//1752年9月13日的范围内，则返回true；否则返回false
{
if (year < 1)
return false;
if (month < 0 || month > 12)
return false;
if (day < 1 || day > days_of_month(month, year, isLeap(year, old)))
return false;
if (year == 1752 && month == 9 && 3 <= day && day <= 13)
return false;
return true;
}
bool isOld(int month, int day, int year) //若year年month月day日在1752
//年9月2日前，则返回true；否则
//返回false
{
return year < 1752 || (year == 1752 && month < 9) ||
(year == 1752 && month == 9 && day <= 2);
}
int main(void) //主函数
{ //主函数开始
int month, day, year;
cin >> month >> day >> year; //读入日期
while (month || day || year) {
bool old = isOld(month, day, year); //计算该日期是否在1752年9月2日
//前的标志
if (!valid(month, day, year, old)) { //处理无效日期
cout << month << '/' << day << '/' << year
<< " is an invalid date." << endl;
} else { //累计公元0年至该日期的总天数
int sum = 0;
for (int yy = 1; yy < year; yy++)
sum += days_of_year(yy, old);
for (int mm = 1; mm < month; mm++)
sum += days_of_month(mm, year, isLeap(year, old));
sum += day;
int week = sum % 7; //计算周几
if (old) //若该日期在1752年9月2日前
week = (week + 5) % 7;
cout <<mstr[month]<<' '<<day<<", "<< year //输出转换后的日期和星期几
<< " is a " << wstr[week] << endl;
}
cin >> month >> day >> year; //输入下一个测试组的日期
}
return 0;
}