c++ - 使用 date.h 解决 USACO 1.1 – 十三号星期五

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(例如我链接到的那个)的解决方案会是什么样的？

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

最佳答案

问题陈述是计算每个月的 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 。

关于c++ - 使用 date.h 解决 USACO 1.1 – 十三号星期五，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38040530/