Im使用以下函数计算两年之间的闰日数：
static int CountLeapDays(int startYear, int endYear)
{
int Days = 0;
while (true)
{
if ((startYear % 4 == 0 && startYear % 100 != 0) || startYear % 400 == 0)
Days++;
if (startYear + 1 == endYear) break;
startYear++;
}
return Days;
}
有没有其他方法可以写这个，这样它就不需要循环了？
如果您仔细分析，就可以避免所有循环。
CountLeapDays
算法注释
/*
** Count the number of 4-year leap years.
** Count the number of 100-year non-leap years.
** Count the number of 400-year leap years.
**
** Switchover between 20th and 21st centuries: 2000 was a leap year.
** Early Later year
** 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009
** 1996 0 0 0 0 0 1 1 1 1 2 2 2 2 3
** 1997 - 0 0 0 0 1 1 1 1 2 2 2 2 3
** 1998 - - 0 0 0 1 1 1 1 2 2 2 2 3
** 1999 - - - 0 0 1 1 1 1 2 2 2 2 3
** 2000 - - - - 0 0 0 0 0 1 1 1 1 2
** 2001 - - - - - 0 0 0 0 1 1 1 1 2
** 2002 - - - - - - 0 0 0 1 1 1 1 2
** 2003 - - - - - - - 0 0 1 1 1 1 2
** 2004 - - - - - - - - 0 0 0 0 0 1
** 2005 - - - - - - - - - 0 0 0 0 1
** 2006 - - - - - - - - - - 0 0 0 1
** 2007 - - - - - - - - - - - 0 0 1
** 2008 - - - - - - - - - - - - 0 0
**
** Switchover between 19th and 20th centuries: 1900 was not a leap year.
** Early Later year
** 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909
** 1896 0 0 0 0 0 *0 *0 *0 *0 *1 *1 *1 *1 *2
** 1897 - 0 0 0 0 *0 *0 *0 *0 *1 *1 *1 *1 *2
** 1898 - - 0 0 0 *0 *0 *0 *0 *1 *1 *1 *1 *2
** 1899 - - - 0 0 *0 *0 *0 *0 *1 *1 *1 *1 *2
** 1900 - - - - 0 0 0 0 0 1 1 1 1 2
** 1901 - - - - - 0 0 0 0 1 1 1 1 2
** 1902 - - - - - - 0 0 0 1 1 1 1 2
** 1903 - - - - - - - 0 0 1 1 1 1 2
** 1904 - - - - - - - - 0 0 0 0 0 1
** 1905 - - - - - - - - - 0 0 0 0 1
** 1906 - - - - - - - - - - 0 0 0 1
** 1907 - - - - - - - - - - - 0 0 1
** 1908 - - - - - - - - - - - - 0 0
**
** The dashes can be returned as zero as a special case (invalid input).
** The leading diagonal (zeros) are a special case.
**
** The starred values are 'exceptional', because the (end year - 1) is
** in a different century from the start year.
** Note that the corresponding positions in the other table are doubly
** exceptional because they could be calculated as (end year - 1) is in
** a different century from the start year (one smaller) and (end year -
** 1) is in a different quad-century (one larger) for a net change of
** zero. This matters if the date ranges get bigger (1890..2130, for
** example).
*/
#include <assert.h>
extern int CountLeapDays(int lo, int hi); // Should be in a header
CountLeapDays函数
int CountLeapDays(int lo, int hi)
{
assert(lo >= 1800);
assert(hi <= 9999);
assert(lo <= hi);
/* Covers wild inputs */
/* Beware: 1600 was not a leap year under the Julian calendar then in effect */
if (lo > hi || lo < 1800 || hi > 9999)
return 0;
/* Leading diagonal */
if (lo == hi)
return 0;
/* Regular leap years */
int lo_4 = (lo - 0) / 4; /* 500 */
int hi_4 = (hi - 1) / 4; /* 502 */
int diff = hi_4 - lo_4; /* 2 */
/* Century years are not leap years */
int lo_c = (lo - 0) / 100;
int hi_c = (hi - 1) / 100;
diff -= hi_c - lo_c;
/* Quad-century years are leap years */
int lo_q = (lo - 0) / 400;
int hi_q = (hi - 1) / 400;
diff += hi_q - lo_q;
return(diff);
}
您可以决定是否值得对hi_c != lo_c进行优化测试，如果这是真的，则只进行减法和四世纪计算。所写的计算是整齐对称的（- 0项也用于对称；编译器将放弃减法）。
测试代码
测试数据
测试数据是由Perl脚本从注释中的表中生成的。
#include <stdio.h>
static struct test
{
int lo;
int hi;
int num;
} tests[] =
{
{ 1996, 1996, 0 },
{ 1996, 1997, 0 },
{ 1996, 1998, 0 },
{ 1996, 1999, 0 },
{ 1996, 2000, 0 },
{ 1996, 2001, 1 },
{ 1996, 2002, 1 },
{ 1996, 2003, 1 },
{ 1996, 2004, 1 },
{ 1996, 2005, 2 },
{ 1996, 2006, 2 },
{ 1996, 2007, 2 },
{ 1996, 2008, 2 },
{ 1996, 2009, 3 },
{ 1997, 1997, 0 },
{ 1997, 1998, 0 },
{ 1997, 1999, 0 },
{ 1997, 2000, 0 },
{ 1997, 2001, 1 },
{ 1997, 2002, 1 },
{ 1997, 2003, 1 },
{ 1997, 2004, 1 },
{ 1997, 2005, 2 },
{ 1997, 2006, 2 },
{ 1997, 2007, 2 },
{ 1997, 2008, 2 },
{ 1997, 2009, 3 },
{ 1998, 1998, 0 },
{ 1998, 1999, 0 },
{ 1998, 2000, 0 },
{ 1998, 2001, 1 },
{ 1998, 2002, 1 },
{ 1998, 2003, 1 },
{ 1998, 2004, 1 },
{ 1998, 2005, 2 },
{ 1998, 2006, 2 },
{ 1998, 2007, 2 },
{ 1998, 2008, 2 },
{ 1998, 2009, 3 },
{ 1999, 1999, 0 },
{ 1999, 2000, 0 },
{ 1999, 2001, 1 },
{ 1999, 2002, 1 },
{ 1999, 2003, 1 },
{ 1999, 2004, 1 },
{ 1999, 2005, 2 },
{ 1999, 2006, 2 },
{ 1999, 2007, 2 },
{ 1999, 2008, 2 },
{ 1999, 2009, 3 },
{ 2000, 2000, 0 },
{ 2000, 2001, 0 },
{ 2000, 2002, 0 },
{ 2000, 2003, 0 },
{ 2000, 2004, 0 },
{ 2000, 2005, 1 },
{ 2000, 2006, 1 },
{ 2000, 2007, 1 },
{ 2000, 2008, 1 },
{ 2000, 2009, 2 },
{ 2001, 2001, 0 },
{ 2001, 2002, 0 },
{ 2001, 2003, 0 },
{ 2001, 2004, 0 },
{ 2001, 2005, 1 },
{ 2001, 2006, 1 },
{ 2001, 2007, 1 },
{ 2001, 2008, 1 },
{ 2001, 2009, 2 },
{ 2002, 2002, 0 },
{ 2002, 2003, 0 },
{ 2002, 2004, 0 },
{ 2002, 2005, 1 },
{ 2002, 2006, 1 },
{ 2002, 2007, 1 },
{ 2002, 2008, 1 },
{ 2002, 2009, 2 },
{ 2003, 2003, 0 },
{ 2003, 2004, 0 },
{ 2003, 2005, 1 },
{ 2003, 2006, 1 },
{ 2003, 2007, 1 },
{ 2003, 2008, 1 },
{ 2003, 2009, 2 },
{ 2004, 2004, 0 },
{ 2004, 2005, 0 },
{ 2004, 2006, 0 },
{ 2004, 2007, 0 },
{ 2004, 2008, 0 },
{ 2004, 2009, 1 },
{ 2005, 2005, 0 },
{ 2005, 2006, 0 },
{ 2005, 2007, 0 },
{ 2005, 2008, 0 },
{ 2005, 2009, 1 },
{ 2006, 2006, 0 },
{ 2006, 2007, 0 },
{ 2006, 2008, 0 },
{ 2006, 2009, 1 },
{ 2007, 2007, 0 },
{ 2007, 2008, 0 },
{ 2007, 2009, 1 },
{ 2008, 2008, 0 },
{ 2008, 2009, 0 },
{ 1896, 1896, 0 },
{ 1896, 1897, 0 },
{ 1896, 1898, 0 },
{ 1896, 1899, 0 },
{ 1896, 1900, 0 },
{ 1896, 1901, 0 },
{ 1896, 1902, 0 },
{ 1896, 1903, 0 },
{ 1896, 1904, 0 },
{ 1896, 1905, 1 },
{ 1896, 1906, 1 },
{ 1896, 1907, 1 },
{ 1896, 1908, 1 },
{ 1896, 1909, 2 },
{ 1897, 1897, 0 },
{ 1897, 1898, 0 },
{ 1897, 1899, 0 },
{ 1897, 1900, 0 },
{ 1897, 1901, 0 },
{ 1897, 1902, 0 },
{ 1897, 1903, 0 },
{ 1897, 1904, 0 },
{ 1897, 1905, 1 },
{ 1897, 1906, 1 },
{ 1897, 1907, 1 },
{ 1897, 1908, 1 },
{ 1897, 1909, 2 },
{ 1898, 1898, 0 },
{ 1898, 1899, 0 },
{ 1898, 1900, 0 },
{ 1898, 1901, 0 },
{ 1898, 1902, 0 },
{ 1898, 1903, 0 },
{ 1898, 1904, 0 },
{ 1898, 1905, 1 },
{ 1898, 1906, 1 },
{ 1898, 1907, 1 },
{ 1898, 1908, 1 },
{ 1898, 1909, 2 },
{ 1899, 1899, 0 },
{ 1899, 1900, 0 },
{ 1899, 1901, 0 },
{ 1899, 1902, 0 },
{ 1899, 1903, 0 },
{ 1899, 1904, 0 },
{ 1899, 1905, 1 },
{ 1899, 1906, 1 },
{ 1899, 1907, 1 },
{ 1899, 1908, 1 },
{ 1899, 1909, 2 },
{ 1900, 1900, 0 },
{ 1900, 1901, 0 },
{ 1900, 1902, 0 },
{ 1900, 1903, 0 },
{ 1900, 1904, 0 },
{ 1900, 1905, 1 },
{ 1900, 1906, 1 },
{ 1900, 1907, 1 },
{ 1900, 1908, 1 },
{ 1900, 1909, 2 },
{ 1901, 1901, 0 },
{ 1901, 1902, 0 },
{ 1901, 1903, 0 },
{ 1901, 1904, 0 },
{ 1901, 1905, 1 },
{ 1901, 1906, 1 },
{ 1901, 1907, 1 },
{ 1901, 1908, 1 },
{ 1901, 1909, 2 },
{ 1902, 1902, 0 },
{ 1902, 1903, 0 },
{ 1902, 1904, 0 },
{ 1902, 1905, 1 },
{ 1902, 1906, 1 },
{ 1902, 1907, 1 },
{ 1902, 1908, 1 },
{ 1902, 1909, 2 },
{ 1903, 1903, 0 },
{ 1903, 1904, 0 },
{ 1903, 1905, 1 },
{ 1903, 1906, 1 },
{ 1903, 1907, 1 },
{ 1903, 1908, 1 },
{ 1903, 1909, 2 },
{ 1904, 1904, 0 },
{ 1904, 1905, 0 },
{ 1904, 1906, 0 },
{ 1904, 1907, 0 },
{ 1904, 1908, 0 },
{ 1904, 1909, 1 },
{ 1905, 1905, 0 },
{ 1905, 1906, 0 },
{ 1905, 1907, 0 },
{ 1905, 1908, 0 },
{ 1905, 1909, 1 },
{ 1906, 1906, 0 },
{ 1906, 1907, 0 },
{ 1906, 1908, 0 },
{ 1906, 1909, 1 },
{ 1907, 1907, 0 },
{ 1907, 1908, 0 },
{ 1907, 1909, 1 },
{ 1908, 1908, 0 },
{ 1908, 1909, 0 },
};
enum { NUM_TESTS = sizeof(tests) / sizeof(tests[0]) };
测试功能
static void test_data(void)
{
int pass = 0;
int fail = 0;
for (int i = 0; i < NUM_TESTS; i++)
{
int res = CountLeapDays(tests[i].lo, tests[i].hi);
if (res != tests[i].num)
{
printf("!! FAIL !! %4d..%4d wanted %d actual %dn", tests[i].lo, tests[i].hi, tests[i].num, res);
fail++;
}
else
{
printf("== PASS == %4d..%4d = %dn", tests[i].lo, tests[i].hi, tests[i].num);
pass++;
}
}
if (fail == 0)
printf("== PASS == %d tests passedn", pass);
else
printf("!! FAIL !! %d tests out of %d failedn", fail, pass+fail);
}
static void test_range(int min, int max)
{
for (int lo = min; lo < max; lo++)
{
for (int hi = lo; hi < max; hi++)
{
printf("%d..%d = %d leap daysn", lo, hi, CountLeapDays(lo, hi));
}
}
}
int main(void)
{
test_data();
test_range(1997, 2016);
test_range(1891, 1909);
return(0);
}
测试代码通过了从数据中正式验证的208个测试用例。它还举例说明了19世纪至20世纪和20世纪至21世纪的361例病例。
可能有更快的替代方案，但此版本至少将循环数量减少了约75%的
public static int CountLeapDays(int startYear, int endYear)
{
int Days = 0;
// round startYear up to the nearest multiple of 4
startYear += 3;
startYear &= ~3;
while (startYear <= endYear) {
if (startYear % 100 != 0 || startYear % 400 == 0) {
Days++;
}
startYear += 4;
}
return Days;
}
您可以通过以下方式减少循环次数：
- 每400年有97个闰日。这可以在不循环的情况下进行计算
- 将剩余范围内的年数除以4，然后将其与步骤1中的数字相加，得到近似答案
- 在100的倍数而不是400的倍数范围内的任何年份减去一。您可以从（startyear+99）/100*100开始循环，然后递增100，直到您的值>endYear。这最多只能循环三次
是的，没有循环也是可能的。
static int CountLeapDays(int start, int end)
{
int years = end - start
int days = 0
days += years / 4 + 1
days -= years / 100 + 1
days += years / 400 + 1
if (start - start % 4 + 4 > end)
days -= 1;
if (start - start % 100 + 100 > end)
days -= 1;
if (start - start % 400 + 400 > end)
days -= 1;
return days
}
基本解释：
- 按年总数计算闰日/4
- 删除所有可被100整除的项
- 将所有可被400整除的加回来
为了简单起见，该算法假设每种情况至少有一个匹配。如果没有，那么它会删除它。例如，1997年至1999年不包括任何闰年，因此以下情况成立（start-start%4+4>结束），因此需要从总数中删除1。
或
对于那些喜欢短代码的人（i是开始年份，j是结束年份）。
(j-i)/4-(i-i%4+4>j?-1:0)-(j-i)/100-(i-i%100+100>j?-1:0)+(j-i)/400-(i-i%400+400>j?-1:0)+1
我真的不明白为什么只使用需要付出太多的努力
inline size_t get_leap_days(size_t year)
{
ASSERT_GE(year, 1800);
const size_t prev_year = year - 1;
return prev_year / 4 - prev_year / 100 + prev_year / 400;
}
inline void test_get_leap_days(size_t begin_year, size_t end_year, size_t eta_leap_days)
{
const double leap_days = begin_year < end_year ? get_leap_days(end_year) - get_leap_days(begin_year + 1) : 0;
ASSERT_EQ(leap_days, eta_leap_days);
}