1

我使用以下函数来计算两年之间的闰日数:

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;
}

有没有另一种方法来写这个所以它不需要循环?

4

5 回答 5

6

如果您仔细分析,您可以避免所有循环。

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 %d\n", tests[i].lo, tests[i].hi, tests[i].num, res);
            fail++;
        }
        else
        {
            printf("== PASS == %4d..%4d = %d\n", tests[i].lo, tests[i].hi, tests[i].num);
            pass++;
        }
    }
    if (fail == 0)
        printf("== PASS == %d tests passed\n", pass);
    else
        printf("!! FAIL !! %d tests out of %d failed\n", 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 days\n", 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 个案例。

于 2013-02-14T20:48:40.527 回答
3

可能有更快的替代方案,但这个版本至少将循环次数减少了约 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;
}
于 2013-02-14T15:38:45.590 回答
1

您可以通过以下方式减少循环次数:

  1. 每400年有97个闰日。这可以在不循环的情况下计算。
  2. 将剩余范围内的年数除以 4,然后将其添加到步骤 1 中的数字以获得近似答案。
  3. 在 100 的倍数而不是 400 的倍数范围内的任何年份减去一个。您可以从 (startyear+99)/100*100 开始循环并递增 100,直到您的值 > endYear。这只会循环最多三遍。
于 2013-02-14T15:37:19.910 回答
1

是的,没有循环是可能的。

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
}

基本解释:

  1. 通过 totalYears / 4 计算闰日
  2. 删除所有能被 100 整除的
  3. 加回所有能被 400 整除

为简单起见,该算法假设每种情况至少有 1 个匹配项。如果没有,则将其删除。例如,1997 到 1999 年不包括任何闰年,因此以下情况为真(开始 - 开始 % 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
于 2019-12-21T21:07:27.453 回答
0

我真的不明白为什么只用这个就需要付出太多的努力:

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);
}
于 2018-06-21T16:13:52.177 回答