1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
|
#include <algorithm>
#include <boost/lambda/lambda.hpp>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <sys/time.h>
#include <vector>
template< typename T, size_t N >
size_t asize( T (&)[ N ] )
{ return N; }
template< typename T, size_t N >
T* abegin( T (&a)[ N ] )
{ return a; }
template< typename T, size_t N >
T* aend( T (&a)[ N ] )
{ return a + N; }
void Output( const std::vector<int>& ans, int last, int sum )
{
std::for_each( ans.begin(), ans.end(), std::cout << boost::lambda::_1 << " + " );
std::cout << last << " = " << sum << std::endl;
}
void Run( int target, std::vector<int>& ans, int sum, const int* first, const int* last )
{
for( const int* cur = first; cur != last; ++first )
if( sum + *first == target )
{
Output( ans, *first, target );
break;
}
else if( sum + *first < target )
{
ans.push_back( *first );
Run( target, ans, sum + *first, first + 1, last );
ans.pop_back();
}
else
break;
}
int main() {
int nums[] = {
103, 107, 109, 113, 127, 131, 137, 151, 157, 167,
1, 2, 3, 5, 7, 11, 13, 17, 19, 23,
67, 71, 73, 79, 83, 89, 97, 101, 139, 149,
29, 31, 37, 41, 43, 47, 53, 59, 61, 163
};
std::vector<int> ans;
ans.reserve( asize( nums ) );
struct timespec start, finish, diff;
assert( clock_gettime( CLOCK_PROCESS_CPUTIME_ID, &start ) == 0 );
std::sort( abegin( nums ), aend( nums ) );
Run( 473, ans, 0, abegin( nums ), aend( nums ) );
assert( clock_gettime( CLOCK_PROCESS_CPUTIME_ID, &finish ) == 0 );
if( finish.tv_nsec < start.tv_nsec )
{
finish.tv_nsec += 1000000000UL;
--finish.tv_sec;
}
diff.tv_sec = finish.tv_sec - start.tv_sec;
diff.tv_nsec = finish.tv_nsec - start.tv_nsec;
std::cerr
<< "Execution time: " << diff.tv_sec << '.' << std::setw( 9 )
<< std::setfill( '0' ) << diff.tv_nsec << 's' << std::endl;
}
| |