考研复试专用算法笔记（二）

曾经终败给现在 2022-04-10 12:08 245阅读 0赞

二、日期部分

计算某个日期是这年第多少天（清华大学机试 ）

思路：用空间换时间，使用预处理（也就是在没有输入的情况下先准备出所有可能结果），先把这一年每一天到这年元旦的天数放出来，有输出时只需输出对应的天数，时间复杂度为O(1)。

核心代码：

//计算给出日期是当年第多少天  
\#include <stdio.h>  
\#define ISLeap(x) x%100!=0&&x%4==0||x%400==0?1:0  
//这里用宏定义，全局变量， 判断是否是闰年  
int dayOfMonth\[13\]\[2\]=\{  
0,0,  
31,31,  
28,29,  
31,31,  
30,30,  
31,31,  
30,30,  
31,31,  
31,31,  
30,30,  
31,31,  
30,30,  
31,31  
\};  
struct Date\{  
int Year,Day,Month;  
void nextDay()\{  
Day++;  
if(Day>dayOfMonth\[Month\]\[ISLeap(Year)\])\{  
Day=1;  
Month++;  
if(Month>12)\{  
Month=1;  
Year++;  
\}  
\}  
\}  
\};  
int buf\[1001\]\[13\]\[32\];  
int Abs(int x)\{  
return x<0?-x:x;  
\}  
int main()\{  
int cnt=0;  
Date tmp;  
tmp.Year=0;  
tmp.Day=1;  
tmp.Month=1;  
while(tmp.Year!=1001)\{  
buf\[tmp.Year\]\[tmp.Month\]\[tmp.Day\]=cnt;  
tmp.nextDay();  
cnt++;  
\}  
int y1,y2,m1,m2,d1,d2;  
while(~scanf("%d%d%d",&y1,&m1,&d1))\{  
printf("%d\\n",Abs(buf\[y1\]\[m1\]\[d1\]-buf\[y1\]\[1\]\[1\])+1);  
\}  
return 0;  
\}

练习：

给出年分n,再给出一个数 m,问这年的第m天的日期是多少。

参考：

\#include <stdio.h>  
\#define ISYEAP(x) x%100!=0&&x%4==0||x%400==0?1:0  
int dayOfMonth\[13\]\[2\]=\{  
0,0,  
31,31,  
28,29,  
31,31,  
30,30,  
31,31,  
30,30,  
31,31,  
31,31,  
30,30,  
31,31,  
30,30,  
31,31  
\};  
struct Date\{  
int Year,Day,Month;  
void nextDay()\{  
Day++;  
if(Day>dayOfMonth\[Month\]\[ISYEAP(Year)\])\{  
Day=1;  
Month++;  
if(Month>12)\{  
Month=1;  
Year++;  
\}  
\}  
\}  
\};  
int buf\[5001\]\[13\]\[32\];  
int main()\{  
int cnt=0;  
int y,num;  
Date tmp;  
tmp.Year=0;  
tmp.Day=0;  
tmp.Month=1;

while(~scanf("%d%d",&y,&num))\{  
tmp.Year=y;  
while(cnt!=num)\{

buf\[tmp.Year\]\[tmp.Month\]\[tmp.Day\]=cnt;  
tmp.nextDay();  
cnt++;  
\}  
printf("%4d-%02d-%02d\\n",tmp.Year,tmp.Month,tmp.Day);  
\}  
return 0;  
\}

可能出现的基本错误：

1.结构体后必须有；

2.定义的基本变量，特别是数组，赋值一堆值后别忘记加；

3.编译错误 error: control may reach end of non-void function解决办法：

这个错误是 因为本该有返回值的函数，可能在某种用例测试下没有返回值，要去在某个地方加返回值。

4 本应输出一个数值， 结果给输出“一串奇怪数字”，可能是你把输出语句中加了&，输出的是这个数值的地址。

日期类问题，主要就是考虑到闰年的问题，仔细思考可破。