|
|
和媳妇玩算24的扑克游戏，（轮流摸牌，看谁的牌点数加减乘除得24，每一张仅能用一次，也必须用一次） 有时怎么都算不出来。于是无聊写了这程序！
两个版本，版本一属于涂鸦可以很好得工作，版本二是精练后得。
下面是源代码，在vc.net 2003 下编译通过
#include <windows.h>
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#define MAX_INPUT 32
int g_value = 24;
/*
//第一个版本
bool is24_print( int buf[],int op[],int len ){
int i;
int value = buf[0];
for( i = 1;i < len;i++ ){
switch( op[i-1] ){
case 0:
value += buf;
break;
case 1:
value -= buf;
break;
case 2:
value *= buf;
break;
case 3:
if( value % buf == 0 )
value /= buf;
else
return false;
break;
default:
std::cout<<"error op:"<<op[i-1]<<std::endl;
return false;
}
}
if( value == g_value ){
// value = buf[0];
// std::cout << "[";
// std::cout << buf[0];
// for( i = 1;i < len;i++ ){
// switch( op[i-1] ){
// case 0:
// std::cout<< "+";
// value += buf;
// break;
// case 1:
// std::cout<< "-";
// value -= buf;
// break;
// case 2:
// std::cout<< "*";
// value *= buf;
// break;
// case 3:
// std::cout<< "/";
// value /= buf;
// break;
// }
// std::cout << buf;
// std::cout << "=" << value << " " << value;
}
std::cout << "]" << std::endl;
return true;
}
return false;
}
void jprint( int b[],int len ){
int i,value = 0;
int buf[MAX_INPUT];
int op[MAX_INPUT];
for( i = 0;i < len;i++ ){
buf = b[2*i];
if( i < len-1 )
op = b[2*i+1];
}
value = buf[0];
std::cout << "[";
std::cout << buf[0];
for( i = 1;i < len;i++ ){
switch( op[i-1] ){
case 0:
std::cout<< "+";
value += buf;
break;
case 1:
std::cout<< "-";
value -= buf;
break;
case 2:
std::cout<< "*";
value *= buf;
break;
case 3:
std::cout<< "/";
value /= buf;
break;
}
std::cout << buf;
std::cout << "=" << value << " " << value;
}
std::cout << "]" << std::endl;
}
void n_for_( int layer,int buf[],int n,int inx[],int m,void (*func)( int buf[],int n,void* pd),void* pp ){
if( layer == 0 )std::cout << "[" << m << "]";
for( int i = 0;i < m;i++ ){
if( layer == 0 ){
std::cout << " " << i;
}
buf[layer] = inx[layer];
for( int j = layer+1;j < n;j++ )
inx[j] = 0;
if( layer == n-1 )
func( buf,n,pp );
else
n_for_( layer+1,buf,n,inx,m,func,pp );
inx[layer]++;
}
if( layer == 0 )
std::cout << " " << m << " ok!" << std::endl;
}
bool is_bad( int buf[],int n ){
for( int i = 0;i < n;i++ ){
for( int j = 0;j < n;j++ ){
if( i != j && buf == buf[j] )
return true;
}
}
return false;
}
bool g_is_bad;
void my_back( int buf[],int n,void* pp ){
std::list<int>* pst;
pst = (std::list<int>*)pp;
if( g_is_bad && is_bad( buf,n ) )
return;
for( int i = 0;i < n;i++ ){
pst->push_back( buf );
}
}
void getZuHe( int n,int m,std::list<int>& st ){
int buf[MAX_INPUT];
int inx[MAX_INPUT];
for( int i = 0;i < n;i++ )
inx = 0;
n_for_( 0,buf,n,inx,m,my_back,&st );
}
bool iseq( int buf[],int buf2[],int len ){
for( int i = 0;i < len;i++ ){
if( buf != buf2 )return false;
}
return true;
}
bool ishava( int buf[],int op[],int len,std::list<int>* pst ){
int inx = 0;
int buf2[2*MAX_INPUT];
int buf3[2*MAX_INPUT];
for( int j = 0;j < len;j++ ){
buf2[2*j] = buf[j];
if( j < len - 1)
buf2[2*j+1] = op[j];
}
for( std::list<int>::iterator i = pst->begin();i != pst->end();i++ ){
buf3[inx] = *i;
if( inx == 2*len - 2 ){
if( iseq( buf2,buf3,2*len-1 ) ){
return true;
}
}
inx++;
if( inx == 2*len-1 )inx = 0;
}
return false;
}
int main(int argc, char* argv[])
{
int const_buf[MAX_INPUT];
int buf[MAX_INPUT];
int buf2[MAX_INPUT];
int op[MAX_INPUT];
int inx,inxj;
int len,count;
DWORD t0 = GetTickCount();
if( argc == 1 ){
len = 5;
const_buf[0] = 13;
const_buf[1] = 13;
const_buf[2] = 3;
const_buf[3] = 4;
const_buf[4] = 8;
}else{
len = argc-1;
for( int i = 1;i < argc;i++ ){
const_buf[i-1] = atoi( argv );
}
}
if( len < 2 || len > 8 ){
std::cout << "error param!" << std::endl;
return 0;
}
{
std::cout << "input: ";
for( int i = 0;i < len;i++ ){
std::cout << const_buf << " ";
}
std::cout << std::endl;
}
std::list<int> stop;
std::list<int> st;
std::list<int> sst;
std::list<int> stmin;
g_is_bad = false;
getZuHe( len-1,4,stop );
g_is_bad = true;
getZuHe( len,len,st );
inx = 0;
inxj = 0;
{
std::list<int> temp;
std::cout << "1.[" << st.size() << "] - ";
for( std::list<int>::iterator j = st.begin();j != st.end();j++ ){
buf[inxj] = const_buf[*j];
temp.push_back( *j );
if( inxj == len-1 ){
bool is_same = false;
inx = 0;
for( std::list<int>::iterator i = sst.begin();i != sst.end();i++ ){
buf2[inx] = const_buf[*i];
if( inx == len-1 ){
//if( memcmp( buf,buf2,sizeof(int)*len ) == 0 ){
if( iseq( buf,buf2,len ) ){
is_same = true;
break;
}
}
inx++;
if( inx == len ) inx = 0;
}
if( is_same == false ){
for( std::list<int>::iterator i = temp.begin();i != temp.end();i++ ){
sst.push_back( *i );
}
temp.clear();
}
}
inxj++;
if( inxj == len )inxj = 0;
}
}
inx = 0;
inxj = 0;
count = 0;
{
std::cout << "2.[" << sst.size() << "] - ";
for( std::list<int>::iterator i = stop.begin();i != stop.end();i++ ){
op[inx] = *i;
if( inx == len-2 ){
for( std::list<int>::iterator j = sst.begin();j != sst.end();j++ ){
buf[inxj] = const_buf[*j];
if( inxj == len-1 ){
if( is24_print( buf,op,len ) ){
if( !ishava( buf,op,len,&stmin ) ){
stmin.push_back( buf[0] );
for( int i = 1;i < len;i++ ){
stmin.push_back( op[i-1] );
stmin.push_back( buf );
}
count++;
}
}
}
inxj++;
if( inxj == len )inxj = 0;
}
}
inx++;
if( inx == len-1 )inx = 0;
}
std::cout << "count = " << count << std::endl;
}
{
int bb[2*MAX_INPUT];
inx = 0;
std::cout << "3.[" << stmin.size() << "]"<<std::endl;
for( std::list<int>::iterator i = stmin.begin();i != stmin.end();i++ ){
bb[inx] = *i;
if( inx == 2*len-2){
jprint( bb,len );
}
inx++;
if( inx == 2*len-1 )inx = 0;
}
}
std::cout << "use time: " << GetTickCount() - t0 << std::endl;
return 0;
}
*/
//第二个版本
class for_m{
public:
int n;
int m;
std::vector<int> table;
for_m( int _n,int _m ){
n = _n;
m = _m;
for( int i = 0;i < n;i++ )
table.push_back( 0 );
}
bool next(){
table[0]++;
for( int i = 0;i < n;i++ ){
if( table == m ){
table = 0;
if( i+1 < n )
table[i+1]++;
else
return false;
}else return true;
}
return true;
}
};
inline bool is_g_value_print( std::vector<int>& inx,std::vector<int>& s,std::vector<int>& o ){
std::vector<int>::iterator k = s.begin();
int value = *(k + *inx.begin());
for( std::vector<int>::iterator j = o.begin(), i = inx.begin()+1;i != inx.end();i++,j++ ){
switch( *j ){
case 0:
value += *(k + *i);
break;
case 1:
value -= *(k + *i);
break;
case 2:
value *= *(k + *i);
break;
case 3:
if( value % *(k + *i) == 0 )
value /= *(k + *i);
else
return false;
break;
default:
std::cout<<"error op:"<< *j <<std::endl;
return false;
}
}
if( value == g_value ){
value = *(k + *inx.begin());
std::cout << "[";
std::cout << value;
for( std::vector<int>::iterator j = o.begin(), i = inx.begin()+1;i != inx.end();i++,j++ ){
switch( *j ){
case 0:
std::cout << "+";
value += *(k + *i);
break;
case 1:
std::cout << "-";
value -= *(k + *i);
break;
case 2:
std::cout << "*";
value *= *(k + *i);
break;
case 3:
std::cout << "/";
value /= *(k + *i);
break;
}
std::cout << *(k + *i);
std::cout << "=" << value << " " << value;
}
std::cout << "]" << std::endl;
return true;
}
return false;
}
int main( int argc,char* argv[] ){
std::vector<int> minput;
std::vector<int> inx;
DWORD t0 = GetTickCount();
int count = 0;
if( argc < 3 )return -1;
for( int i = 1;i < argc;i++ ){
minput.push_back( atoi( argv ) );
inx.push_back( i-1 );
}
do{
for_m op( minput.size()-1,4 );
do{
if( is_g_value_print( inx,minput,op.table ) ){
count++;
}
}while( op.next() );
}while( std::next_permutation( inx.begin(),inx.end() ) );
std::cout << "Count = " << count << " User time: " << GetTickCount() - t0 << std::endl;
return 0;
}
|
|
发表于 2004-3-1 18:20:00
楼主