fork download
copy 
  1. #include <iostream>
  2.  
  3. namespace Details
  4. {
  5. template < typename F >
  6. struct has_next
  7. {
  8. 	typedef char yes[1];
  9. 	typedef char no[2];
  10.  
  11. 	template < typename C >
  12. 	static yes& test(typename C::next *);
  13.  
  14. 	template < typename C >
  15. 	static no& test(...);
  16.  
  17. 	enum { value = sizeof(test<F>(0)) == sizeof(yes) };
  18. 	typedef has_next< F > type;
  19. };
  20.  
  21. template < unsigned int n__ >
  22. struct Fibonacci_
  23. {
  24. 	enum { value = Fibonacci_< n__ - 1 >::value + Fibonacci_< n__ - 2 >::value };
  25. 	typedef Fibonacci_< n__ - 1 > next;
  26. 	typedef Fibonacci_< n__ > type;
  27. };
  28.  
  29. template<>
  30. struct Fibonacci_<1>
  31. {
  32. 	enum { value = 1 };
  33. 	typedef Fibonacci_< 1 > type;
  34. 	typedef Fibonacci_< 0 > next;
  35. };
  36.  
  37. template <>
  38. struct Fibonacci_<0>
  39. {
  40. 	typedef Fibonacci_< 0 > type;
  41. 	enum { value = 0 };
  42. };
  43.  
  44. template < typename F, bool has_next__ >
  45. struct Filler_
  46. {
  47. 	static void fill(unsigned int *a)
  48. 	{
  49. 		*a = F::value;
  50. 		Filler_< typename F::next, has_next< typename F::next >::value >::fill(++a);
  51. 	}
  52. };
  53.  
  54. template < typename F >
  55. struct Filler_< F, false >
  56. {
  57. 	static void fill(unsigned int *a)
  58. 	{
  59. 		*a = F::value;
  60. 	}
  61. };
  62.  
  63. // based on idea by Luc Danton described here: http://chat.stackoverflow.com/transcript/message/740324#740324
  64. // modified to use SFINAE and a class to implement the guts (so partial specialization will work)
  65. template < typename F >
  66. void fill(unsigned int *a)
  67. {
  68. 	Filler_< F, has_next< F >::value >::fill(a);
  69. }
  70. }
  71.  
  72. template< unsigned int max__ = 20 >
  73. unsigned int fibonacci(unsigned int n)
  74. {
  75. 	static unsigned int results__[max__ + 1];
  76. 	static bool initialized__ = false;
  77. 	if (!initialized__)
  78. 	{
  79. 		Details::fill< Details::Fibonacci_< max__ > >(results__);
  80. 		initialized__ = true;
  81. 	}
  82. 	if (n <= max__)
  83. 	{
  84. 		return results__[max__ - n];
  85. 	}
  86. 	else throw "something more eloquent here";
  87. }
  88.  
  89. int main()
  90. {
  91. 	using namespace std;
  92.  
  93. 	static const unsigned int max__ = 20;
  94.  
  95. 	for (unsigned int i(0); i <= max__; ++i)	
  96. 		cout << fibonacci< max__ >(i) << '\n';
  97. }
  98.  
Success #stdin #stdout 0s 2828KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
https://ideone.com/Thq96
language:
C++14 (gcc 8.3)
created:
12 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!