#include //used just int for simplicity #include /* Recaman sequence Formal Definition: R(0) = 0 R(n>0) = R(n-1) - n if > 0 or not already in the sequence R(n-1) + n otherwise */ /* * * * templatized * * * */ //////// List Device //////// // // List<...> // Add // Contains // printList // ToArray for runtime use // ///////////////////////////// class End{}; template struct List{ static const int head = t; using tail = List; }; template struct List{ static const int head = t; using tail = End ; }; template struct Add{ static const int head = L::head ; using tail = Add; }; template struct Add{ static const int head = n ; using tail = End; }; template void printList( bool isSt = true ){ if ( isSt ) std::cout << "["; else std::cout << ", "; std::cout << L::head; printList(false); } template<> void printList( bool isSt ){ std::cout << "]\n"; } template constexpr bool Contains = L::head == n || Contains; template constexpr bool Contains = false; template constexpr int Nth = Nth; template constexpr int Nth = L::head; template constexpr int Nth = -1; // runtime array conversion template struct Arr{ static int constexpr data[sizeof...( terms )] = {terms...}; }; template< typename L, int...terms> struct ToArray{ typedef typename ToArray::result result ; static int at( int n ){ // * n > length => U.B. ! ! ! return result::data[n]; } static const int length = sizeof(result::data)/sizeof(int); }; template struct ToArray{ typedef Arr result ; }; // // + + + End List Device + + + // //////// Recaman Device //////// // template > constexpr bool NextChoiceCond = last > n && !Contains ; template constexpr int NextChoice = last - n; template constexpr int NextChoice = last + n; template > constexpr int NextRecaman = NextChoice>; template > struct RecamanSeries{ static const int next = NextRecaman; using newList = Add; using result = typename RecamanSeries::result ; }; template struct RecamanSeries{ using result = L; }; // // + + + End Recaman Device + + + // /* * * Loop solution * * */ #include #include std::vector recamanSeries( int n ){ std::vector series = {0}; for ( int i = 1 ; i <= n ; ++i ){ if ( series[i-1]>i && std::find( series.begin(), series.end(), series[i-1]-i ) == series.end() ) series.push_back( series[i-1] - i ); else series.push_back( series[i-1] + i); } return series ; }; #include #include using namespace std; typedef RecamanSeries<10>::result compileTimeRecamanSeries_to10; typedef ToArray< compileTimeRecamanSeries_to10 > First10Recaman; int main(){ vector first10Recaman = recamanSeries(10); std::cout << " * * Recaman series up to(n) result table loop vs recursion( Template Meta Programming ) * *\n\n" << std::setw(6) << std::right << "Nth" << std::setw(8) << std::right << "loop" << std::setw(8) << std::right << "rec"; std::cout << "\n ______________________\n"; for ( uint64_t i = 0 ; i < First10Recaman::length ; ++i ){ std::cout << std::setw(4) << std::right << i ; if ( i%10 == 1 ) std::cout << "st"; else if ( (i+1)%10 == 2 ) std::cout << "nd"; else if ( (i+1)%10 == 3 ) std::cout << "rd"; else std::cout << "th"; std::cout << std::setw(8) << std::right << first10Recaman[ i ] << std::setw(8) << std::right << First10Recaman::at( i ) << "\n"; } cout << "\nUp to 100 at compile time..\nRecamanSeries<100> : "; typedef RecamanSeries<100>::result many_recamans; printList< many_recamans >(); return 0; } // from wikipedia // 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8, 25, 43, 62, 42, 63, 41, 18, 42, 17, 43, 16, 44, 15, 45, 14, 46, 79, 113, 78, 114, 77, 39, 78, 38, 79, 37, 80, 36, 81, 35, 82, 34, 83, 33, 84, 32, 85, 31, 86, 30, 87, 29, 88, 28, 89, 27, 90, 26, 91, 157, 224, 156, 225, 155, ...