Function nekolib::algo::tortoise_hare::cycle_nth

pub fn cycle_nth<T, F>(x0: T, f: F, n: usize) -> Twhere
    T: Eq + Clone,
    F: Fn(T) -> T,

$n$ 項目を求める。

与えられた $x_0$ と $f$ を用いて $x_i = f(x_{i-1})$ ($i > 0$) として 定義される列 $\{x_i\}_{i=0}^\infty$ の $n$ 項目を求める。

Requirements

$f$ は参照透過である。

Complexuty

$x_{\mu} = x_{\mu+\lambda}$ なる最小の $(\mu, \lambda)$ に対し、$O(\min\{n, \mu+\lambda\})$ time.

Examples

use nekolib::algo::cycle_nth;

let x0 = 0;
let f = |x| (x + 1) % 100; // (mu, lambda) = (0, 100)
assert_eq!(cycle_nth(x0, f, 0), 0);
assert_eq!(cycle_nth(x0, f, 99), 99);
assert_eq!(cycle_nth(x0, f, 100), 0);
assert_eq!(cycle_nth(x0, f, 1000), 0);
assert_eq!(cycle_nth(x0, f, 10_usize.pow(9)), 0);

let x0 = -10;
let f = |x| (x + 1) % 100; // (mu, lambda) = (10, 100)
assert_eq!(cycle_nth(x0, f, 0), -10);
assert_eq!(cycle_nth(x0, f, 99), 89);
assert_eq!(cycle_nth(x0, f, 100), 90);
assert_eq!(cycle_nth(x0, f, 1000), 90);
assert_eq!(cycle_nth(x0, f, 10_usize.pow(9)), 90);