# Just for fun: Compile time fibonacci

#include <iostream>

/**
fibonacci(n)
*/
template <std::size_t n>
struct fib {
static constexpr uint64_t cal() {
return fib<n - 1>::cal() + fib<n - 2>::cal();
}
};

/**
base case, fibonacci(0)
*/
template<>
struct fib<0> {
static constexpr uint64_t cal() {
return 0;
}
};

/**
base case, fibonacci(1)
*/
template<>
struct fib<1> {
static constexpr uint64_t cal() {
return 1;
}
};

int main(int argc, const char * argv[]) {
std::cout << fib<10>::cal() << std::endl;
}


defmodule Fib do
def fib(0) do
0
end

def fib(1) do
1
end

def fib(n) do
fib(n - 1) + fib(n - 2)
end
end


Stream.unfold({0, 1}, fn {f1, f2} -> {f1, {f2, f1+f2}} end)
|> Enum.take(10)


def unfold(state, func):
while True:
stream_value, state = func(state)
yield stream_value

def fib(state):
f1, f2 = state
return [f1, [f2, f1 + f2]]

p = unfold([0, 1], fib)

print([next(p) for i in range(10)])


#include <array>
#include <functional>
#include <iostream>
#include <tuple>

/**
unfold

@param state current state
@param func  a function that accepts current state and produces {yield_value, new_state}
@return generator
*/
template<typename Y, typename S>
auto unfold(S state, std::function<std::tuple<Y, S>(S current_state)> func) {
// save current state
std::array<int, 2> _state = state;
// return a function as generator
return [=]() mutable {
// declaration
Y yield_value;
S new_state;

// receive {yield_value, new_state} from current state
std::tie(yield_value, new_state) = func(_state);

// save new state
_state = new_state;

// yield value corresponding to previous state
return yield_value;
};
}

int main(int argc, const char * argv[]) {
// fibonacci starting state
std::array<int, 2> state{{0, 1}};

auto&& fib = unfold<int, decltype(state)>(state, [](auto current_state) {
// fib(n) = fib(n - 1) + fib(n - 2)
// i.e. the value which would be yield
int value = current_state[0] + current_state[1];

// new state from {fib(n - 1), fib(n - 2)} is
// {fib(n - 2), fib(n - 1) + ib(n - 2)}
// i.e. {current_state[1], value}
return std::tuple<int, decltype(current_state)>(value, {current_state[1], value});
});

for (int i = 0; i < 10; i++) {
std::cout << fib() << ' ';
}
}

声明: 本文为0xBBC原创, 转载注明出处喵～