c++ - 解决 USACO 1.1 – Friday the Thirteenth with date.h

Question

USACO 1.1 – Friday the Thirteenth问题已以各种方式多次解决。事实上，它已经通过各种解决方案在 StackOverflow 上产生了一些问题:

• Friday the Thirteenth - USACO
• What is wrong with my code? Usaco: Friday the Thirteenth
• usaco: friday the thirteen error
• Usaco. Friday the thirteen. What is wrong with my code?
• On what days does the thirteenth occur? USACO

问题是:使用 modern C++11/14 date library 的解决方案是什么样的？比如我链接到的那个？

它会比其他解决方案简单得多吗？更容易写？更高效？

Answer 1

问题陈述是计算每个月的 13 号落在 [1900-01-01, 2300-01-01) 范围内给定工作日的频率。 .

使用 date.h这是非常容易和有效地完成这样的:

#include "date/date.h"
#include <chrono>
#include <iostream>

int
main()
{
    using namespace date;
    using namespace std::chrono;
    unsigned freq[7] = {};
    for (auto ym = 1900_y/January; ym < 2300_y/January; ym += months{1})
        freq[weekday{ym/13}.c_encoding()]++;
    for (unsigned i = 0; i < 7; ++i)
        std::cout << weekday{i} << " : " << freq[i] << '\n';
}

ym是 date::year_month目的。你可以把它想象成一个 time_point , 但它的精度非常粗糙 months .

您只需遍历每年和每年的每个月，计算该月 13 日是星期几，然后将其转换为 weekday进入 unsigned .

高级语法非常简单易读。

引擎盖下的算法是 days_from_civil 和 weekday_from_days .这些低级日期算法都不是迭代的，因此它们非常高效。因此，您可以两全其美:可读的高级语法和高性能。

这个简单程序的输出也非常可读:

Sun : 687
Mon : 685
Tue : 685
Wed : 687
Thu : 684
Fri : 688
Sat : 684

事实证明，13 号星期五比一周中的其他日子更有可能。

在 C++17 中，你甚至可以创建一个 constexpr std::array<unsigned, 7>有了这些结果(出于某种原因，在编译时有这样的数字是否很重要):

#include "date/date.h"
#include <array>
#include <chrono>
#include <iostream>

constexpr
std::array<unsigned, 7>
compute_freq() noexcept
{
    using namespace date;
    using namespace std::chrono;
    decltype(compute_freq()) freq = {};
    for (auto ym = 1900_y/January; ym < 2300_y/January; ym += months{1})
        freq[weekday{ym/13}.c_encoding()]++;
    return freq;
}

constexpr auto freq = compute_freq();

int
main()
{
    using namespace date;
    using namespace std::chrono;
    static_assert(freq[Sunday.c_encoding()]    == 687);
    static_assert(freq[Monday.c_encoding()]    == 685);
    static_assert(freq[Tuesday.c_encoding()]   == 685);
    static_assert(freq[Wednesday.c_encoding()] == 687);
    static_assert(freq[Thursday.c_encoding()]  == 684);
    static_assert(freq[Friday.c_encoding()]    == 688);
    static_assert(freq[Saturday.c_encoding()]  == 684);
}

生成这个程序集:

_freq:
    .long   687                     ## 0x2af
    .long   685                     ## 0x2ad
    .long   685                     ## 0x2ad
    .long   687                     ## 0x2af
    .long   684                     ## 0x2ac
    .long   688                     ## 0x2b0
    .long   684                     ## 0x2ac

没有比这更高效的了。

在 C++20 中，这一切都在您的 std::lib 中可用。要将上述程序移植到 C++20，请删除 #include "date/date.h"和 using namespace date; .同时更改 _y y 的后缀.