fork(2) download
copy 
  1. #include <array>
  2. #include <cstdint>
  3. #include <iostream>
  4. #include <stdexcept>
  5.  
  6. #if 1 // Not in C++11 // make_index_sequence
  7.  
  8. template <std::size_t...> struct index_sequence {};
  9.  
  10. template <std::size_t N, std::size_t... Is>
  11. struct make_index_sequence : make_index_sequence<N - 1, N - 1, Is...> {};
  12.  
  13. template <std::size_t... Is>
  14. struct make_index_sequence<0u, Is...> : index_sequence<Is...> {};
  15.  
  16. #endif // make_index_sequence
  17.  
  18. namespace detail
  19. {
  20.  
  21. template <std::size_t N>
  22. struct Fibo :
  23.     std::integral_constant<size_t, Fibo<N - 1>::value + Fibo<N - 2>::value>
  24. {
  25.     static_assert(Fibo<N - 1>::value + Fibo<N - 2>::value >= Fibo<N - 1>::value,
  26.                   "overflow");
  27. };
  28.  
  29. template <> struct Fibo<0u> : std::integral_constant<size_t, 0u> {};
  30. template <> struct Fibo<1u> : std::integral_constant<size_t, 1u> {};
  31.  
  32. template <std::size_t ... Is>
  33. constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>)
  34. {
  35.     return const_cast<const std::array<std::size_t, sizeof...(Is)>&&>(
  36.         std::array<std::size_t, sizeof...(Is)>{{Fibo<Is>::value...}})[n];
  37. }
  38.  
  39. template <std::size_t N>
  40. constexpr std::size_t fibo(std::size_t n)
  41. {
  42.     return n < N ? fibo(n, make_index_sequence<N>()) : throw std::runtime_error("out of bound");
  43. }
  44. } // namespace detail
  45.  
  46. constexpr std::size_t fibo(std::size_t n)
  47. {
  48.     // 48u is the highest
  49.     return detail::fibo<48u>(n);
  50. }
  51.  
  52. int main()
  53. {
  54.     std::cout << fibo(42) << std::endl;
  55.     std::size_t input;
  56.     std::cin >> input;
  57.     std::cout << fibo(input) << std::endl;
  58.  
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
42
stdout
copy 
267914296
267914296
https://ideone.com/F0b4D3
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!