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

[Chen Shuo]

看上去结果是对的（和我自己的程序比过），只是速度有点慢，如果是"ABABABABAAAAAAAA"，要半秒钟才能出结果，"ABABABABABAAAAAA"的话，要十多秒才能算出来。

On 3/21/06, Yi Fan <heavenstar at gmail.com> wrote:
>
> 这题有点意思。写了一个递归的实现，不知道对不对。
> 下面是代码，后面是思路：
>
>
>
>
>
> #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
>
>
>
> _______________________________________________
> Cpp mailing list
> Cpp at codingnow.com
> http://codingnow.com/mailman/listinfo/cpp
>
>