周期検出 (algorithm/tortoise_and_hare.cpp)
- category: algorithm
-
View this file on GitHub
- Last commit date: 2020-04-06 04:52:14+09:00
Verified with
Code
#ifndef H_tortoise_and_hare
#define H_tortoise_and_hare
/**
* @brief 周期検出
* @author えびちゃん
*/
#include <cstdint>
#include <utility>
template <typename Generator>
std::pair<intmax_t, intmax_t> detect_cycle(Generator g) {
Generator tortoise = g;
Generator hare = g;
do {
tortoise.pop();
hare.pop(), hare.pop();
} while (tortoise.peek() != hare.peek());
tortoise = g;
intmax_t mu = 0;
while (tortoise.peek() != hare.peek()) {
++mu;
tortoise.pop();
hare.pop();
}
intmax_t lambda = 0;
hare = tortoise;
do {
++lambda;
hare.pop();
} while (tortoise.peek() != hare.peek());
return {mu, lambda};
}
#endif /* !defined(H_tortoise_and_hare) */
#line 1 "algorithm/tortoise_and_hare.cpp"
/**
* @brief 周期検出
* @author えびちゃん
*/
#include <cstdint>
#include <utility>
template <typename Generator>
std::pair<intmax_t, intmax_t> detect_cycle(Generator g) {
Generator tortoise = g;
Generator hare = g;
do {
tortoise.pop();
hare.pop(), hare.pop();
} while (tortoise.peek() != hare.peek());
tortoise = g;
intmax_t mu = 0;
while (tortoise.peek() != hare.peek()) {
++mu;
tortoise.pop();
hare.pop();
}
intmax_t lambda = 0;
hare = tortoise;
do {
++lambda;
hare.pop();
} while (tortoise.peek() != hare.peek());
return {mu, lambda};
}