摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : DFS建樹

直接照著題目打下來,懶得多做其他的優化

主要是因為不懂 F B I的放置條件,所以才拖很久才寫

F ->左右兩邊不能同時為BB或II
BB上面是B
II上面是I  其餘都是F

/**********************************************************/

#include<stdlib.h>
#include<stdio.h>
#include<math.h> 
char s[2000];
int link[3000][2],top=1;
void makeTree(int now,int L)
{
   if(L>10) return;
   link[now][0]=++top;
   makeTree(top,L+1);
   link[now][1]=++top;
   makeTree(top,L+1);
}
int flag=0;
int NUM[3000]={0};
void Tree(int now,int L,int stop,char s[])
{
   if(L==stop+1)
          {
            NUM[now]=s[flag++]-48;
            return;
          }
   Tree(link[now][0],L+1,stop,s);
   Tree(link[now][1],L+1,stop,s);
}
int print(int now,int L,int stop)
{
   if(L==stop+1)
         {
            if(NUM[now]==1) {printf("I");return 1;}
            if(NUM[now]==0) {printf("B");return 0;}
         }
   int Flagr,Flagl;
   Flagl=print(link[now][0],L+1,stop);
   Flagr=print(link[now][1],L+1,stop);
   if(Flagl==1&&Flagr==1)
     {printf("I");return 1;}
   else if(Flagl==0&&Flagr==0)
     {printf("B");return 0;}
   else
     {printf("F");return -1;}
}
main()
{
  makeTree(1,1);
  int N;

  while(scanf("%d",&N)==1)
       {
          scanf("%s",s);
          flag=0,Tree(1,1,N,s);
          print(1,1,N);
       }
   return 0;
}

/**********************************************************/

作法 :遞迴

二分搜尋的遞迴... 該死寫了上面那麼長串  其實只要一點點就夠了

/**********************************************************/

#include<stdlib.h>
#include<stdio.h>
char s[2000];
int print(int l,int h)
{
    int m=(l+h)/2,r,ll;
    if(l>=h)
         {
            if(s[m]=='1') {printf("I");return 1;}
            if(s[m]=='0') {printf("B");return 0;}
         }
    r=print(l,m);
    ll=print(m+1,h);
    if(r==0&&ll==0)  {printf("B");return 0;}
    else if(r==1&&ll==1) {printf("I");return 1;}
    else {printf("F");return -1;}
}
main()
{
  int N,s2[11]={1,2,4,8,16,32,64,128,256,512,1024};
  while(scanf("%d",&N)==1)
       {
          scanf("%s",s);
          print(0,s2[N]-1);
          puts("");
       }
   return 0;
}