甘南州城乡建设局网站,免费建网站软件,广州品牌网站建设,服装私人订制网站【题目描述】
输入年份#xff0c;判断是否为闰年。如果是#xff0c;则输出yes#xff0c;否则输出no。
提示#xff1a;简单地判断除以4的余数是不够的。
【题目来源】
刘汝佳《算法竞赛入门经典 第2版》习题1-7 年份#xff08;year#xff09; 【解析】
一、闰…【题目描述】
输入年份判断是否为闰年。如果是则输出yes否则输出no。
提示简单地判断除以4的余数是不够的。
【题目来源】
刘汝佳《算法竞赛入门经典 第2版》习题1-7 年份year 【解析】
一、闰年的由来及设定规则
首先要明白设置闰年的目的是为了弥补历法规定的年度天数与地球实际公转周期一个回归年的时间差。因为规定平年365天而实际的一个回归年大约比平年多出0.2422天。为了补偿这个差异使历法年与回归年相适应产生了闰年的概念。
在现行公历中闰年的设定遵循以下规则
①能被4整除但不能被100整除的年份为普通闰年。
②能被400整除的年份为世纪闰年。
为什么是这么个复杂规则呢
前面说过一个回归年大约比平年多出0.2422天4年就多0.2422×40.9688天而历法是每4年补1天相当于每4年多补了1-0.96880.0312天。
短期内这点误差没什么影响可时间长了误差会越来越大每400百年就会多被3.12天。所以为了减小误差在每4年一个闰年的基础上每400年还要减少3个闰年。
减少哪3个闰年呢历法制定者一拍脑门就设在世纪之交吧在第100、200、300年各减少1个。
这个拍脑门动作直接将世纪闰年变成稀有产品比如2000年是世纪闰年这意味着其后300年内出生的小朋友都与世纪闰年无缘了。
以上就是“四年一闰、百年不闰、四百年又闰”的规则的由来。
二、判定闰年的程序
需把闰年的判定规则转化为对应的表达式
规则①中“能被4整除但不能被100整除”表示这两个条件需同时成立这是“逻辑与”的关系用表示即year % 4 0 year % 100 ! 0。
规则②的表达式为year % 400 0
满足规则①与②任意一项就是闰年所二者是“逻辑或”的关系用||表示即①||②。
c代码
#include stdio.hint main() {int year;scanf(%d, year);if ((year % 4 0 year % 100 ! 0) || year % 400 0) {printf(yes\n);} else {printf(no\n);}return 0;}
上述代码中用于判断的表达式① year % 4 0 year % 100 ! 0的括号其实是没有必要的因为的优先级是高于||的。但是为了代码的清晰性和可读性加上括号是一个比较好的习惯——尤其在涉及复杂逻辑运算时。
好了这道题就讲完了。
我估计解这道题的多数同学都只会给出上面的代码认为它就是正解。
可能连出题人也都这样认为。
因为算法课上老师都是这么讲的所以我们都容易依惯性思维给出上面的答案。
然而这道题真的解完了吗
NONONO这里面还有一个大坑。
认为上述代码是正解的都忽略了一个问题。
那就是公元前的年份。
在一般的算法竞赛的题目中都会给出年份的范围比如1900 year 2500。但是本题并没有给出范围所以公元前的年份无疑也是符合题目要求的。
问题来了公元前的闰年与公元后的闰年判定规则是一样的吗
如果你在网上搜索一下公元前闰年的判定规则会发现有如下一些表述 这些描述都有一些共同的特点
①表现得神乎其神却让人看得云里雾里
②满满的漏洞
③将简单的问题复杂化。
公元前闰年的判定本就是很简单的问题。
只需一句话把公元前的年份减1然后按公元后的规则判定即可。
比如公元前2001年减1等于2000年按公元后的判定规则判定为闰年。
不知为啥网上居然没见到一个以这种方式描述的。
为什么公元前的闰年规则和公元后不一样呢这是个数学问题。
因为公历没有公元0年公元1年的前一年就是公元前1年而闰年的基本规则是每4年一个闰年所以公元前1年就变成了闰年。 前6 前5 前4 前3 前2 前1 1 2 3 4 5 6 闰年 闰年 闰
换句话说如果有公元0年的话那公元前和公元后的闰年规则就是一样的了。
正因为差了这一年导致了公元前后闰年判定的差异。
现在你明白了刚刚说的公元前要减1再判断的原因了吧
为简化起见咱们在编程时假定用负数表示公元前的年份这样的话就不再是减1后判断而是要加1了。比如公元前1年表示为“-1”要加1才能变成0。
原来的代码改起来很简单只要在判断之前加一个if语句即可
if(year0) year1;
以上就是本题的答案部分。
三、逻辑表达式的效率判定
下面再讨论一下由本题衍生出来的一个问题逻辑表达式的效率问题。
从效率角度讲下面的表达式A与B、C与D是一样的吗
表达式Ayear % 4 0 year % 100 ! 0
表达式Byear % 100 ! 0 year % 4 0
表达式C(year % 4 0 year % 100 ! 0) || year % 400 0
表达式Dyear % 400 0 ||(year % 4 0 year % 100 ! 0)
这涉及到、||这两个运算符的一个运算特点短路short-circuit效应。
这个短路效应其实很好理解
①如果a为假则b无论真假ab均为假所以就不再计算b的值。
②如果a为真则b无论真假a||b均为真所以就不再计算b的值。
表达式year % 4 0为假指年份不能被4整除表达式year % 100 ! 0为假指年份能被100整除从输入年份的概率角度讲显然前者远远大于后者所以把前者放在之前就能减小计算次数故表达式A的效率高于表达式B。
表达式year % 4 0 year % 100 ! 0为真指年份能被4整除但不能被100整除表达式year % 400 0为真指年份能被400整除显然前者概率远远大于后者把前者放在||之前也能减小计算次数故表达式C的效率高于表达式D。
也就是说咱们代码中逻辑表达式的排序即表达式C就是效率最高的。
而效率最低的是下面这个表达式
表达式Eyear % 400 0 ||( year % 100 ! 0 year % 4 0)
从概率的角度说可能不易理解如果把这道题改成依次输出公元前3000年到公元3000年每一年是否是闰年大家就能立刻明白逻辑表达式不同的排序计算次数会有很大的不同了。
但是能不能输出具体的计算次数对比呢
我家孩子提供了一个思路逻辑判断可以用if-else语句替换通过这种替换就能直接让程序输出不同排序的计算次数。
以下是孩子编的C代码我没更改只是把变量名改得更清晰些比如将bool变量名由s改为is_true将循环变量i改为year加了些注释。
表达式C的计算次数代码如下
#include iostreamusing namespace std;int main () {bool is_true; //判断表达式真假//sum4是i%40的计算次数//sum100是i%100!0的计算次数//sum400是i%4000的计算次数int sum40,sum1000,sum4000,sum;for(int year-3000;year3000;year){if(year0) year; //跳过0年//公元前的年份1int year1year;if(year10) year1year1;//获得第1、2个表达式的计算次数sum4;if(year1%40){sum100;if(year1%100!0)is_truetrue;elseis_truefalse;}else{is_truefalse;}//获得第3个表达式的计算次数if(is_truefalse) {sum400;if(year1%4000)is_truetrue;elseis_truefalse;}//输出年份是否为闰年if(is_truetrue)coutyear yesendl;elsecoutyear noendl;}sumsum4sum100sum400;coutsum4 sum100 sum400 sum;return 0;}
表达式E的计算次数代码如下
#include iostreamusing namespace std;int main () {bool is_true;int sum40,sum1000,sum4000,sum;for(int year-3000;year3000;year){if(year0) year; //跳过0年//公元前的年份1int year1year;if(year10) year1year1;//获得第1个表达式的计算次数sum400;if(year1%4000)is_truetrue;elseis_truefalse;//获得第2、3个表达式的计算次数if(is_truefalse){sum100;if(year1%100!0){sum4;if(year1%40)is_truetrue;}}//输出年份是否为闰年if(is_truetrue)coutyear yesendl;elsecoutyear noendl;}sumsum4sum100sum400;coutsum4 sum100 sum400 sum;}
程序输出的两种表达式的计算次数如下 表达式 year % 4 0 year % 100 ! 0 year % 400 0 合计 表达式C 6000 1500 4560 12060 表达式E 5940 5985 6000 17925 E-C -60 4485 1440 5865
上面的代码逻辑有一点点复杂但仔细看还是能看明白的。有一点比较有意思的是这个程序还有一个小坑就是“公元0年”是没有的要注意刨除掉。我本来想顺道考查下孩子会不会用continue这小子果然不会但人家也不含糊想到用year的这种方式跳过了0。
