一道广搜的题目:很容易做错,当然如果不较真的话,早就搞定了!
  • 要点1:open_close表,注意区别状态空间[pre]辅助栈[sk]的状态[天真了,开始想了半天]
  • 要点2:其实不用两个表也能做,只是判重比较耗时间;可以用编程之美的那种思路,把跑过的状态作为close表,因此close表的区间为[0,bt+1),注意是半开区间;如果要用STL algorithm来判重的话,可以作一个unary_function函数子,在find_if在半开区间搜索,注意STL的搜索算法失败是置在结束位的!
  • C++的收获:如何管理堆内存?“零散”堆内存是必须要回收的,否则bad_alloc在搜索里面是非常容易出现的!顺便提一句,这种代码风格不值得提倡,主要是为了练习算法所以才这样写[先抽自己一下],全局变量在大型开发里,还是少用为妙,在多线程坏境里面问题尤其多;就面向对象而言,这种代码完全达不到c++的大众水平,会带坏小朋友的!
  1. 用一个全局的指针数组来保存,然后统一回收[有问题来回折腾heap,效率不高]
  2. 用一个全局的void* buffer来统一分配对内存[这里犯了个错,placement new的buffer也是有地址指向的,因此转成int来更好操作],统一管理内存!
  • STL的效率比较,开始用vector来作open_close表的容器,程序跑了1.2s还可以;换为数组之后,翻了一倍多400MS就搞定了,只是要估计状态空间的总值,开得有点大!

BFS:

1。open_close表vector实现:GCC,1.2s

#include <iostream>
#include <fstream>
#include <memory>
#include <string>
#include <assert.h>
#include <vector>

//Optimal Program : BFS
using namespace std;
const int MaxSize=200, Threshold=10, CMDT=5, MAXVALUE=30000, MAX=5000000;
int a[MaxSize],b[MaxSize],pairs;
int* buffer;

typedef struct{//in order to re-allocate the pointer
 int* s, l, pre/*pre-state in state space*/, sk,/*pre-stack*/ cmd, cmdnum;
}state;

#define fbased 1
long times=0;

char *cmdStr[CMDT]={"ADD", "DIV", "DUP", "MUL", "SUB"};

//output to calculation
inline int* output(state& pre, int cmd, vector<state>& open_close){
 int *s2=open_close[pre.sk].s, *s1=pre.s, *cal=NULL;
 cal=new(&buffer[times*pairs])int[pairs](); times++;
 if(cmd==0)//ADD
  for(int i=0; i<pairs; i++){
   cal[i]=s1[i]+s2[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
 else if(cmd==1){//DIV
  for(int i=0; i<pairs; i++){
   if(!s1[i]) return NULL;//quit with zero on the top of stack
   cal[i]=s2[i]/s1[i];
  }
 }
 else if(cmd==3)//MUL
  for(int i=0; i<pairs; i++){
   cal[i]=s2[i]*s1[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
 else if(cmd==4)//SUB
  for(int i=0; i<pairs; i++){
   cal[i]=s2[i]-s1[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
  return cal;
}

void BFS(int i){
 //open-close table
 vector<state> open_close;
 int bt=0,et,cl=0;//cl for command length
 //current element for start
 state item, next;
 item.s=a,item.pre=item.sk=-1,item.l=1,item.cmdnum=0;//item.l represents the height of stack
 open_close.push_back(item);
 bool t=false;times=0;
 while(cl<=Threshold&&bt<open_close.size()){
  et=open_close.size();cl++;
  while(bt<et){//for the same level
   item=open_close[bt];
   if(!memcmp((void*)item.s, (void*)b, sizeof(int)*pairs)){
    cl=item.cmdnum,t=true;break;
   }
   //single operand, having only one choice
   if(item.l==1){//if the stack height is 1, so only one "DUP" operation
    next.pre=next.sk=bt;//index
    next.l=item.l+1;//stack height
    next.cmd=2;
    next.cmdnum=cl;
    next.s=item.s;//check domain [0…b),check duplicate logic
    open_close.push_back(next);
   }
   else{//stack current is two element at least
    for(int k=0; k<CMDT; k++){
     next.pre=bt;//?right or not,wrong!2 stack units back!
     if(k!=2) {
      next.l=item.l-1,next.sk=open_close[item.sk].sk;
      next.s=output(item, k, open_close);//output bugs!
     }
     else{
      next.l=item.l+1,next.sk=bt,next.s=item.s;
     }
     if(!next.s) continue;//go to next command
     next.cmd=k;
     next.cmdnum=cl;
     open_close.push_back(next);
    }
   }
   bt++;
  }
  if(t)break;
 }//while testing

 cout<<"Program "<<i<<endl;
 if(cl<=Threshold){
  int p,z; string cd;
  if(cl>0){
   do{
    p=item.cmd,z=item.pre;
    cd=" "+cd;
    cd=cmdStr[p]+cd;
    if(z!=-1) item=open_close[z];//both of vector and array support []
   }while(z!=-1&&item.l!=1);//stack keep only one unit, sorry! it’s wrong!
   cout<<cd.c_str()<<endl;
  }
  else if(cl==0)
   cout<<"Empty sequence"<<endl;
 }
 else cout<<"Impossible"<<endl;
}

int main()
{
#ifdef fbased
 ifstream in("input.txt");
 if(!in){
  cerr<<"error to open file"<<endl;
  return EXIT_FAILURE;
 }
 cin.rdbuf(in.rdbuf());
#endif
 buffer=new int[MAX];
 assert(buffer!=NULL);
 int i=1,j,k;
 while(cin>>pairs&&pairs){
  for(k=0;k<2;k++){
   if(!k)
    for(j=0;j<pairs;j++) cin>>a[j];
   else for(j=0;j<pairs;j++) cin>>b[j];
  }
  BFS(i++);
 }

 delete[] buffer;
 int sum=1;
 for(int i=0; i<10; i++)sum*=5;
 cout<<sum<<endl;

 system("pause");

 return 0;
}
#undef fbased

2。open_close表数组实现:GCC,400ms

#include <iostream>
#include <fstream>
#include <memory>
#include <string>
#include <assert.h>
#include <vector>

//Optimal Program : BFS
using namespace std;
const int MaxSize=200,Threshold=10,CMDT=5,MAXVALUE=30000,MAXBUF=5000000;
int a[MaxSize],b[MaxSize],pairs;
int *buffer;//the sum of buffer
//int *g[MAXBUF];
#define std 2

typedef struct{//in order to re-allocate the pointer
 int* s, l, pre/*pre-state in state space*/, sk,/*pre-stack*/ cmd, cmdnum;
}state;

#define fbased 1
long times=0;
state buf[MAXBUF];//state space buffer

char *cmdStr[CMDT]={"ADD", "DIV", "DUP", "MUL", "SUB"};

//output to calculation
inline int* output(state& pre, int cmd){
 int *s2=buf[pre.sk].s, *s1=pre.s, *cal=NULL;
 //cal=new int[pairs];
 //g[times++]=cal;
 cal=new(&buffer[times*pairs])int[pairs](); times++;
 if(cmd==0)//ADD
  for(int i=0; i<pairs; i++){
   cal[i]=s1[i]+s2[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
 else if(cmd==1){//DIV
  for(int i=0; i<pairs; i++){
   if(!s1[i]) return NULL;//quit with zero on the top of stack
   cal[i]=s2[i]/s1[i];
  }
 }
 else if(cmd==3)//MUL
  for(int i=0; i<pairs; i++){
   cal[i]=s2[i]*s1[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
 else if(cmd==4)//SUB
  for(int i=0; i<pairs; i++){
   cal[i]=s2[i]-s1[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
  return cal;
}

void BFS(int i){
 //open-close table
 //vector<state> open_close;
 int bt=0,et,cl=0,top=0;//cl for command length
 //current element for start
 state item, next;
 item.s=a,item.pre=item.sk=-1,item.l=1,item.cmdnum=0;//item.l represents the height of stack
 buf[top++]=item;
 //open_close.push_back(item);
 bool t=false;times=0;
 while(cl<=Threshold&&bt<top){
  et=top;cl++;
  while(bt<et){//for the same level
   item=buf[bt];
   if(!memcmp((void*)item.s, (void*)b, sizeof(int)*pairs)){
    cl=item.cmdnum,t=true;break;
   }
   //single operand, having only one choice
   if(item.l==1){//if the stack height is 1, so only one "DUP" operation
    next.pre=next.sk=bt;//index
    next.l=item.l+1;//stack height
    next.cmd=2;
    next.cmdnum=cl;
    next.s=item.s;//check domain [0…b),check duplicate logic
    buf[top++]=next;
    //open_close.push_back(next);
   }
   else{//stack current is two element at least
    for(int k=0; k<CMDT; k++){
     next.pre=bt;//?right or not,wrong!2 stack units back!
     if(k!=2) {
      next.l=item.l-1,next.sk=buf[item.sk].sk;
      next.s=output(item, k);//output bugs!
     }
     else{
      next.l=item.l+1,next.sk=bt,next.s=item.s;
     }
     if(!next.s) continue;//go to next command
     next.cmd=k;
     next.cmdnum=cl;
     buf[top++]=next;
     //open_close.push_back(next);
    }
   }
   bt++;
  }
  if(t)break;
 }//while testing

 cout<<"Program "<<i<<endl;
 if(cl<=Threshold){
  int p,z; string cd;
  if(cl>0){
   do{
    p=item.cmd,z=item.pre;
    cd=" "+cd;
    cd=cmdStr[p]+cd;
    if(z!=-1) item=buf[z];//both of vector and array support []
   }while(z!=-1&&item.l!=1);//stack keep only one unit, sorry! it’s wrong!
   cout<<cd.c_str()<<endl;
  }
  else if(cl==0)
   cout<<"Empty sequence"<<endl;
 }
 else cout<<"Impossible"<<endl;
 //strategy 1: im-efficient!
 //for(int k=0; k<times; k++) delete[] g[k];
}

int main()
{
#ifdef fbased
 ifstream in("input.txt");
 if(!in){
  cerr<<"error to open file"<<endl;
  return EXIT_FAILURE;
 }
 cin.rdbuf(in.rdbuf());
#endif
 buffer=new int[MAXBUF];
 assert(buffer!=NULL);
 int i=1,j,k;
 while(cin>>pairs&&pairs){
  for(k=0;k<2;k++){
   if(!k)
    for(j=0;j<pairs;j++) cin>>a[j];
   else for(j=0;j<pairs;j++) cin>>b[j];
  }
  BFS(i++);
 }

 delete[] buffer;
 return 0;
}
#undef fbased

马上把双向广搜模型和DFS版本写了,搜索是比较有意思,模型比较难,但写出来一种,以后就可以复用了,比较经济的一种算法!

Advertisements