不吉利的日期

[编程题]不吉利的日期

热度指数：1377 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

在国外，每月的 13 号和每周的星期 5 都是不吉利的。特别是当 13 号那天恰好是星期 5时，更不吉利。
现在给你一个年份，请你从小到大依次输出当年所有13 号是星期 5 的月份。

输入描述:

输入包含多组数据，每组数据包含一个正整数year（2000≤year≤9999）。

输出描述:

对应每一组数据，输出所有符合条件的月份，月份之间用空格隔开。
如果当年不存在13号是星期五的月份，就输出一行Luck。

示例1

输入

2000<br/>2001<br/>2002

输出

10<br/>4 7<br/>9 12

算法知识视频讲解

查看答案及解析

推荐

MrBearman

我的做法和前面的不一样

先分析完所有的情况，所有的阳历年历只有如下14种：

（依次编号L[0]~L[6]、C[0]~C[6]）

第一类：元旦为周一的平年，元旦为周二的平年，...，元旦为周日的平年

第二类：元旦为周一的闰年，元旦为周二的闰年，...，元旦为周日的闰年

两个要素：(1)平年or闰年？ (2)元旦为周几？

这两个要素一旦确定，全年的历表就确定了。

例如：元旦为周日的闰年，13th与Friday相遇的月份就一定是Jan. Apr. Jul.

剩下的工作就是找出年份year与L[x]或C[x]之间的对应关系，也就是求函数 x = f ( year )。

这个算法的时间复杂度O(n)，空间复杂度O(1)。

#include<stdio.h>
int isLeapYear(int n){
	int rtn=0;
	if(n%400==0 || (n%100!=0 && n%4==0))rtn=1;
	return rtn;
}
int main(){
	char*L[7]={"1 4 7\n","9 12\n","6\n","3 11\n","2 8\n","5\n","10\n"};
	char*C[7]={"1 10\n","4 7\n","9 12\n","6\n","2 3 11\n","8\n","5\n"};
	int n;
	while(scanf("%d",&n)!=EOF){
		int flag=isLeapYear(n);
		n=(6+(n-2000)+(n-1997)/4+(n-2001)/400-(n-2001)/100)%7;
		char*s;
		if(flag)s=L[n];
		else s=C[n];
		printf("%s",s);
	}
	return 0;
}

编辑于 2016-05-28 10:25:41 回复(10)