[cpp] Re: Cpp Digest, Vol 24, Issue 26

[Yi Fan]

这题有点意思。写了一个递归的实现，不知道对不对。
下面是代码，后面是思路：




#include<stdio.h>
#include<string.h>

#define LARGE_NUM 1000000000
#define ERROR 1000000001
int str_len=0;
char ABstring[27]="ABABABABBBAABB";

//"ABAB";


double Jump(int front, int back, int index)
{
 double num=0;
 if(index==str_len-1){     //if its the last one
  if(ABstring[index]=='A'){  //jump forward
   return front;
  }
  else{  //jump backward
   return back;
  }
 }
 else
 {
  int i;
  if(ABstring[index]=='A'){//jump forward
   for(i=0;i<front;i++){
    num+=Jump(front-i,back+i+1,index+1);
    if(num>LARGE_NUM){
     return ERROR;
    }
   }
  }
  else{ //jump backward
   for(i=0;i<back;i++){
    num+=Jump(front+i+1,back-i,index+1);
    if(num>LARGE_NUM){
     return ERROR;
    }
   }
  }
 }
 return num;
}

int main()
{
 str_len=strlen(ABstring);
 int result=(int)Jump(1,1,0);
 if(result>LARGE_NUM)
 {
  result=-1;
 }
 printf("%d\n",result);
}




思路是这样的：
比如一个串"AB"，

1.  初始状态有一个'a'， 那么读到第1个"A"的时候，
     就知道'b'肯定在'a'后面。
2.  现在计算'a'后面有几个位置可以插入'b'，由于
     现在的状态只有一个'a'，所以后面就只有一个位置插入'b'
     现在状态变成了'ab'。
3.  现在读到第2个"B"，也就是'c'在'b'前面，
     现在'b'前面有2个位置可以插入'c'。
    _a_b，下划线表示插入位置。
4.最后的答案 就是：

                                插入'b'的1种情况，
                            X  插入'c'的2种情况
                           -------------------------------------------
                            =  2


在06-3-20，Chen Shuo <giantchen at gmail.com> 写道：
>
> 看来不对哦。比如 m = 3，AB 串为 "BA" 时，有 bac 和 bca 两种情况，而你的程序算出 s = 1 了。
>
> On 3/20/06, Feng Jiang <feng.a.jiang at gmail.com> wrote:
> > 呵呵。有意思。刚才想了一下，是不是可以这样解决？
> > 假设给定的字符串长度为m，就是那个小写字符串,例如abcd。
> > 那么大写字符串T[]长度应该是m-1。
> > 程序应该是这样的：
> >
> > int s = m!; //m的阶乘
> > for(int i=0; i< m-1; i++) {
> >   char c = T[i];
> >   if( c == 'A' )
> >     s  /= (i+2);
> >   else
> >     s = s* (i +1) / (i+2) ;
> > }
> > printf("%d\n", s);
> >
> > 这样子对吗？
>
> _______________________________________________
> Cpp mailing list
> Cpp at codingnow.com
> http://codingnow.com/mailman/listinfo/cpp
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://codingnow.com/pipermail/cpp/attachments/20060321/c7dbea81/attachment.html