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

[Yi Fan]

恩，呵呵，纯递归的东西，写完就感觉着上亿的话，会慢得要死。

在06-3-21，Chen Shuo <giantchen at gmail.com> 写道：
>
>
> 看上去结果是对的（和我自己的程序比过），只是速度有点慢，如果是"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
> >
> >
>
> _______________________________________________
> 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/2d62aa5f/attachment-0001.html