Re: C++ help
On Mar 5, 3:54 am, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
roy axenov wrote:
[2-, 7- and 9-cent stamps]
Here's what seems to be a general solution (the only
problem with it is that its efficiency borders on that
of bogosort):
[code]
Nice, the first correct solution I have seen in this
thread. But it really gets a little slow on larger
numbers.
Well, using the ideas mentioned earlier in the thread it is
relatively easy to achieve a significant improvement in
performance, at least for the 2-7-9 case. There's still a
noticeable decrease in performance for 3-13-14-15 case, and
something like 3-5-112-1113-10001 would be outright scary.
I wonder if the period is always equal to the largest
coefficient for suffiently large n? It seems so even though
it's kinda counter-intuitive.
Also, it does not give all solutions.
Actually, the code posted seems to find all the
solutions... It just doesn't bother remembering them all.
Try producing this output:
[sample output]
#include <iostream>
#include <vector>
#include <map>
const int stamp_1 = 2 ;
const int stamp_2 = 7 ;
const int stamp_3 = 9 ;
namespace xyz
{
class dio
{
public :
dio ( const std :: vector < int > & c ) ;
std :: vector < std :: map < int , int > > solve
( int s ) const
{ return slv ( s , m_ . begin ( ) ) ; }
private :
std :: map < int , int > m_ ;
std :: vector < std :: map < int , int > > slv
(
int s ,
std :: map < int , int > :: const_iterator im
) const ;
static int trl
(
const std :: map < int , int > & x ,
int ( * f ) ( const std :: pair < int , int > & )
) ;
static int eff
( const std :: pair < int , int > & x )
{ return x . second ; }
static int ttl
( const std :: pair < int , int > & x )
{ return x . first * x . second ; }
} ;
dio :: dio ( const std :: vector < int > & c )
{
for
(
std :: vector < int > :: const_iterator ic =
c . begin ( ) ;
ic != c . end ( ) ; ++ ic
)
{
m_ [ * ic ] = 0 ;
for
(
std :: vector < int > :: const_iterator jc =
ic + 1 ;
jc != c . end ( ) ; ++ jc
)
if ( * jc > m_ [ * ic ] ) m_ [ * ic ] = * jc ;
}
}
int dio :: trl
(
const std :: map < int , int > & x ,
int ( * f ) ( const std :: pair < int , int > & )
)
{
int result = 0 ;
for
(
std :: map < int , int > :: const_iterator i =
x . begin ( ) ;
i != x . end ( ) ; ++ i
)
result += ( * f ) ( * i ) ;
return result ;
}
std :: vector < std :: map < int , int > > dio :: slv
(
int s ,
std :: map < int , int > :: const_iterator im
) const
{
std :: vector < std :: map < int , int > > result ;
int best = 0 ;
if ( im != m_ . end ( ) )
{
std :: map < int , int > empty ;
empty [ 0 ] = 1 ;
result . push_back ( empty ) ;
int cur_c = ( * im ) . first ;
int div_c = s / cur_c ;
int max_c =
std :: min ( ( * im ) . second , div_c ) ;
std :: map < int , int > tmp ;
++ im ;
if ( max_c )
{
for ( int i = 0 ; i <= max_c ; ++ i )
{
std :: vector < std :: map < int , int > > sols =
slv ( s - cur_c * i , im ) ;
for
(
std :: vector < std :: map < int , int > >
:: const_iterator is = sols . begin ( ) ;
is != sols . end ( ) ; ++ is
)
{
tmp = * is ;
if ( tmp [ 0 ] ) continue ;
tmp [ cur_c ] = i ;
if ( trl ( tmp , & ttl ) != s ) continue ;
int cur_val = trl ( tmp , & eff ) ;
if ( ! best || cur_val < best )
{
result . clear ( ) ;
best = cur_val ;
}
if ( cur_val == best )
result . push_back ( tmp ) ;
}
}
}
else
{
tmp [ cur_c ] = div_c ;
if ( trl ( tmp , & dio :: ttl ) == s )
{
result . clear ( ) ;
result . push_back ( tmp ) ;
}
}
}
return result ;
}
} ;
int main ( int argc , char * argv [ ] )
{
std :: vector < int > stamps ;
stamps . push_back ( stamp_1 ) ;
stamps . push_back ( stamp_2 ) ;
stamps . push_back ( stamp_3 ) ;
xyz :: dio d ( stamps ) ;
int max_sum = atoi ( argv [ 2 ] ) ;
for
(
int sum = atoi ( argv [ 1 ] ) ;
sum <= max_sum ; ++ sum
)
{
std :: vector < std :: map < int , int > > solutions =
d . solve ( sum ) ;
std :: cout << sum << " " ;
for
(
std :: vector < std :: map < int , int > > ::
const_iterator si = solutions . begin ( ) ;
si != solutions . end ( ) ; ++ si
)
{
std :: cout << "= " ;
for
(
std :: map < int , int > :: const_iterator i =
( * si ) . begin ( ) ;
i != ( * si ) . end ( ) ; ++ i
)
if ( ( * i ) . first )
std :: cout << ( * i ) . second << " x " <<
( * i ) . first << "c " ;
}
std :: cout << std :: endl ;
}
}
pavel@debian:~/dev/cxx/t14$ time ./a.out 10000 10040
10000 = 0 x 2c 4 x 7c 1108 x 9c
10001 = 1 x 2c 0 x 7c 1111 x 9c
10002 = 0 x 2c 3 x 7c 1109 x 9c
10003 = 0 x 2c 7 x 7c 1106 x 9c = 2 x 2c 0 x 7c 1111 x 9c
10004 = 0 x 2c 2 x 7c 1110 x 9c
10005 = 0 x 2c 6 x 7c 1107 x 9c
10006 = 0 x 2c 1 x 7c 1111 x 9c
10007 = 0 x 2c 5 x 7c 1108 x 9c
10008 = 0 x 2c 0 x 7c 1112 x 9c
10009 = 0 x 2c 4 x 7c 1109 x 9c
10010 = 1 x 2c 0 x 7c 1112 x 9c
10011 = 0 x 2c 3 x 7c 1110 x 9c
10012 = 0 x 2c 7 x 7c 1107 x 9c = 2 x 2c 0 x 7c 1112 x 9c
10013 = 0 x 2c 2 x 7c 1111 x 9c
10014 = 0 x 2c 6 x 7c 1108 x 9c
10015 = 0 x 2c 1 x 7c 1112 x 9c
10016 = 0 x 2c 5 x 7c 1109 x 9c
10017 = 0 x 2c 0 x 7c 1113 x 9c
10018 = 0 x 2c 4 x 7c 1110 x 9c
10019 = 1 x 2c 0 x 7c 1113 x 9c
10020 = 0 x 2c 3 x 7c 1111 x 9c
10021 = 0 x 2c 7 x 7c 1108 x 9c = 2 x 2c 0 x 7c 1113 x 9c
10022 = 0 x 2c 2 x 7c 1112 x 9c
10023 = 0 x 2c 6 x 7c 1109 x 9c
10024 = 0 x 2c 1 x 7c 1113 x 9c
10025 = 0 x 2c 5 x 7c 1110 x 9c
10026 = 0 x 2c 0 x 7c 1114 x 9c
10027 = 0 x 2c 4 x 7c 1111 x 9c
10028 = 1 x 2c 0 x 7c 1114 x 9c
10029 = 0 x 2c 3 x 7c 1112 x 9c
10030 = 0 x 2c 7 x 7c 1109 x 9c = 2 x 2c 0 x 7c 1114 x 9c
10031 = 0 x 2c 2 x 7c 1113 x 9c
10032 = 0 x 2c 6 x 7c 1110 x 9c
10033 = 0 x 2c 1 x 7c 1114 x 9c
10034 = 0 x 2c 5 x 7c 1111 x 9c
10035 = 0 x 2c 0 x 7c 1115 x 9c
10036 = 0 x 2c 4 x 7c 1112 x 9c
10037 = 1 x 2c 0 x 7c 1115 x 9c
10038 = 0 x 2c 3 x 7c 1113 x 9c
10039 = 0 x 2c 7 x 7c 1110 x 9c = 2 x 2c 0 x 7c 1115 x 9c
10040 = 0 x 2c 2 x 7c 1114 x 9c
real 0m0.008s
user 0m0.004s
sys 0m0.000s
--
Pavel Lepin