#include <iostream.h>
int M;           //导线条数
int *link;                 //link[i]为连接导线i的开关序号

//判断集合p1中的元素是否全为零,若全为零,则返回true;反之,返回false;
bool empty(int p1[])     
{
 int i;
 bool falg=true;
 for(i=0;i<M;i++)
  if(p1[i]!=0)
  {
   falg=false;
   break;
  }
 return falg;
}
//判断导线和开关之间的连接,其中开关左区间的起始下标为head,终止下标为tail;区间开关状态为state:0表示断开,1表示闭合.
void check(int *p1,int head,int tail,int state)
{
 int *p2=new int [M];
 int i,j;
 char ch;

 if(!empty(p1))         
 {
  if(head==tail)      //如果左区间只剩下一个开关,则将p1中所有导线与这个开关连接
  {
   for(i=0;i<M;i++)
    if(p1[i]!=0)
     link[i]=head+1;
  }
  else
  {
   i=(int)((head+tail+1)/2);
   for(j=head;j<i;j++)
   {   //进行人机问答
    cout<<"C"<<j+1<<endl;       
    cin>>ch;
   }
   for(j=0;j<M;j++)      //p2设空
    p2[j]=0;         
   for(j=0;j<M;j++)
    if(p1[j]!=0)     //导线j+1在p1中
    {    //进行人机问答
     cout<<"T"<<j+1<<endl;
     cin>>ch;
     if((state==0&&ch=='N')||(state==1&&ch=='Y'))
     {     //若灯灭而左区间卡关闭合或者灯亮而左区间开关断开,则将导线j+1从p1集合中移到p2集合中
      p1[j]=0;
      p2[j]=j+1;
     }
    }
   check(p1,head,i-1,1-state);   //完成p1集合中的导线与左区间开关的连接
   check(p2,i,tail,state);       //完成p2集合中的导线与右区间开关的连接
  }
 }
 delete [] p2;
}
//输出连接方案
void show()
{
 int i;
 cout<<"D";
 for(i=0;i<M;i++)
  cout<<" "<<link[i];
 cout<<endl;
}
//主程序
int main()
{
 while(cin>>M)
 {
  int i;
  link=new int [M];
  int *p1=new int [M];
  for(i=0;i<M;i++)        //所有导线进入p1集合
    p1[i]=i+1;
  check(p1,0,M-1,0);      //完成导线与开关的连接
  show();
  delete [] p1;
  delete [] link;
 }
 return 0;
}

评论