|
|
发表于 2006-12-9 23:02:00
|
显示全部楼层
Re:这是我招聘的一个题目。
#include "stdio.h"
#include "stdlib.h"
#include "memory.h"
#include "math.h"
#include <vector>
#include <stack>
using std::vector;
enum {
IS_NUM = 0,
IS_OP = 1,
IS_NONE =0xffffffff //force 32 bit
};
enum {
OP_ADD = '+',
OP_SUB = '-',
OP_MUL = '*',
OP_DIV = '/',
OP_NONE = 0Xffffffff // FORCE 32 bit
};
int nNums[4]={11,3,1,9};
int nOps[4] ={ OP_ADD , OP_SUB ,OP_MUL, OP_DIV };
#define NUM4_SIZE 4
struct num4
{
int array4[NUM4_SIZE];
num4(){memset(array4,0,sizeof(array4));}
num4(int *arr){memcpy(array4,arr,NUM4_SIZE*sizeof(int));}
int& operator [](int pos) {return array4[pos];}
};
#define ORD7_SIZE 7
struct ord7
{
int flags[ORD7_SIZE];
ord7(){memset(flags,0,sizeof(flags));}
ord7(int *arr){memcpy(flags,arr,ORD7_SIZE*sizeof(int));}
int operator [](int pos) {return flags[pos];}
};
#define OP3_SIZE 3
struct op3
{
int op_id[7];
op3(){memset(op_id,0,sizeof(op_id));}
op3(int *arr){memcpy(op_id,arr,OP3_SIZE*sizeof(int));}
int operator [](int pos) {return op_id[pos];}
};
vector<num4> idx;
vector<ord7> ords;
vector<op3> opids;
vector<vector<int> >calc_ords;
int numbers[4]={0,1,2,3};
int flags[4]={0,0,0,0};
int destnums[4];
int destords[7];
void SetOneNum(int *destarr,int *srcarr,int *flags,int count,int pos)
{
for(int i=0;i<count;i++)
{
if(flags!=1)
{
destarr[pos]=srcarr;
if(pos==count-1)
{
idx.push_back( (num4)destarr);
}
else
{
flags=1;
SetOneNum(destarr,srcarr,flags,count,pos+1);
flags=0;
}
}
}
}
void BuildAllNumSeq()
{
// vector<num4> idx;
// int numbers[4]={0,1,2,3};
// int flags[4]={0,0,0,0};
// int destnums[4];
SetOneNum(destnums,numbers,flags,4,0);
}
void SetOneOrd(int * destord,int num_num,int op_num,int count,int pos)
{
if(pos==0 )
{
destord[0]=IS_NUM;
destord[1]=IS_NUM;
SetOneOrd(destord,2,0,count,pos+2);
}
else if(pos== count-1)
{
destord[pos]= IS_OP;
ords.push_back((ord7)destord);
}
else
{
if(num_num <= count/2)
{
destord[pos] = IS_NUM;
SetOneOrd(destord,num_num+1,op_num,count,pos+1);
}
if(op_num < count/2-1 && op_num < num_num-1)
{
destord[pos] = IS_OP;
SetOneOrd(destord,num_num,op_num+1,count,pos+1);
}
}
}
void BuildAllOrdSeq()
{
// vector<ord7> ords;
// int destords[7];
SetOneOrd(destords,0,0,3+4,0);
}
void SetOneCalcIdx(int * destord,int size,int opcount,int pos)
{
for(int i = 0;i<opcount;i++ )
{
destord[pos] = i;
if (pos == size-1)
{
opids.push_back((op3)destord);
}
else
{
SetOneCalcIdx(destord,size,opcount,pos+1);
}
}
}
void BuildAllCalcIdxSeq()
{
// vector<op3> opids;
SetOneCalcIdx(destnums,3,4,0);
}
void BuildAllCalcOrdSeq()
{
// vector<vector<int> >calc_ords;
vector<int> tmpseq;
int ptr_idx=0;
int ptr_op=0;
num4 tmpidx ;
op3 tmpop ;
ord7 tmpord;
for(int i=0;i<ords.size();i++)
{
ord7 tmpord=ords;
for(int j=0;j<idx.size();j++)
for(int k=0;k<opids.size();k++)
{
tmpseq.clear();
tmpidx = idx[j];
tmpop = opids[k];
ptr_idx=0;
ptr_op=0;
for(int n=0;n<7;n++)
if(tmpord[n]==IS_NUM)
{
tmpseq.push_back(nNums[tmpidx[ptr_idx++]]);
}
else // if(tmpord[n]==IS_OP)
{
tmpseq.push_back(nOps[tmpop[ptr_op++]]);
}
calc_ords.push_back(tmpseq);
}
}
}
void PrintCalcOrd(vector<int> &tmpseq)
{
for( int j=0;j<tmpseq.size();j++)
{
if (tmpseq[j]>20)
{
printf("%c ",tmpseq[j]);
}
else
{
printf("%d ",tmpseq[j]);
}
}
printf("\n");
}
struct char_buf
{
char buf[100];
char_buf(){memset(buf,0,100);}
};
void TurnOrdFromSuf2Mid(vector<int> &tmpseq)
{
using std::stack;
stack<char_buf> st_nums;
char_buf tmpbuf,op1,op2;
for(int i=0;i<tmpseq.size();i++)
{
int code = tmpseq;
if(tmpseq < 20)
{
sprintf(tmpbuf.buf,"%d",tmpseq);
st_nums.push( tmpbuf);
}
else
{
op2 = st_nums.top();
st_nums.pop();
op1 = st_nums.top();
st_nums.pop();
//the outest brackets not need
if(i==tmpseq.size()-1)
{
sprintf(tmpbuf.buf,"%s%c%s",op1.buf,tmpseq,op2.buf);
}
else
{
sprintf(tmpbuf.buf,"(%s%c%s)",op1.buf,tmpseq,op2.buf);
}
st_nums.push(tmpbuf);
}
}
tmpbuf = st_nums.top();
printf("%s\n",tmpbuf.buf);
}
int Try24()
{
int ret_val = 0;
vector<int> tmpseq ;
using std::stack;
stack<float> st_nums;
int ptr_seq;
float op1,op2,result;
for(int i=0;i<calc_ords.size();i++)
{
tmpseq = calc_ords;
ptr_seq = 0;
while(ptr_seq<tmpseq.size())
{
if(tmpseq[ptr_seq] < 20)
{
st_nums.push((float) tmpseq[ptr_seq++]);
}
else
{
op2 = st_nums.top() ;
st_nums.pop();
op1 = st_nums.top();
st_nums.pop();
switch (tmpseq[ptr_seq++])
{
case OP_ADD:
result = op1 + op2;
break;
case OP_SUB:
result = op1 - op2;
break;
case OP_MUL:
result = op1 * op2;
break;
case OP_DIV:
result = op1 / op2;
break;
}
st_nums.push(result);
}
}
result = st_nums.top();
if ( fabs (result - 24.0f) <0.01f )
{
//output result
ret_val ++;
//PrintCalcOrd(tmpseq);
TurnOrdFromSuf2Mid(tmpseq);
}
}
printf("total resolution = %d\n" , ret_val);
return ret_val;
}
void main()
{
printf("please input 4 number\n");
scanf("%d %d %d %d",&(nNums[0]),&(nNums[1]),&(nNums[2]),&(nNums[3]));
int i;
FILE* file = fopen("express.log","wt");
BuildAllNumSeq();
for(i=0;i<idx.size();i++)
{
num4 tmp4 = idx;
//printf("%d,%d,%d,%d\n",tmp4.array4[0],tmp4.array4[1],tmp4.array4[2],tmp4.array4[3]);
fprintf(file,"%d,%d,%d,%d\n",tmp4.array4[0],tmp4.array4[1],tmp4.array4[2],tmp4.array4[3]);
}
BuildAllOrdSeq();
for( i=0;i<ords.size();i++)
{
ord7 tmp7 = ords;
//printf("%d,%d,%d,%d,%d,%d,%d\n",tmp7[0],tmp7[1],tmp7[2],tmp7[3],tmp7[4],tmp7[5],tmp7[6]);
fprintf(file,"%d,%d,%d,%d,%d,%d,%d\n",tmp7[0],tmp7[1],tmp7[2],tmp7[3],tmp7[4],tmp7[5],tmp7[6]);
}
BuildAllCalcIdxSeq();
for( i=0;i<opids.size();i++)
{
op3 tmp= opids;
//printf("%d,%d,%d\n",tmp[0],tmp[1],tmp[2]);
fprintf(file,"%d,%d,%d\n",tmp[0],tmp[1],tmp[2]);
}
BuildAllCalcOrdSeq();
for( i=0;i<calc_ords.size();i++)
{
vector<int> t_calc_ords= calc_ords;
for( int j=0;j<t_calc_ords.size();j++)
{
if (t_calc_ords[j]>20)
{
// printf("%c ",t_calc_ords[j]);
fprintf(file,"%c ",t_calc_ords[j]);
}
else
{
// printf("%d ",t_calc_ords[j]);
fprintf(file,"%d ",t_calc_ords[j]);
}
}
//printf("\n");
fprintf(file,"\n");
}
fclose(file);
Try24();
}
|
|
