[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]="ABABABABBBABAB";

int AB()
{
 int index,i,j;
 double first[27];
 double second[27];
 double sum=0;
 memset(first,0,sizeof(first));
 memset(second,0,sizeof(second));
 str_len=strlen(ABstring);

 first[0]=1;
 for(index=0;index<=str_len;index++)
 {
  sum=0;
  for(i=0;i<index+1;i++)
  {
   sum+=first[i];
   if(sum>LARGE_NUM)
   {
    return -1;
   }
  }


  if(ABstring[index]=='A')
  {
   for(i=0;i<=index;i++)
   {
    for(j=i+1;j<=index+1;j++)
    {
     second[j]+=first[i];
    }
   }
  }
  else
  {
   for(i=0;i<=index;i++)
   {
    for(j=0;j<=i;j++)
    {
     second[j]+=first[i];
    }
   }
  }

  memcpy(first,second,sizeof(second));
  memset(second,0,sizeof(second));
 }

 return (int)sum;
}


int main()
{
 printf("%d\n",AB());
}
思路：（举个例子）
已知串 "AB"
有 2  个
acb
cab

现在推"ABA"

已经有了AB的答案，现在第3个是"A"，也就是d在c后出现。

对于AB的答案（acb,cab），

先考虑第一个acb，既然d在c后出现，那么c后一共有2个地方可以插入d，
ac_b_ ，就是下划线的地方。

 再考虑第二个cab，既然d在c后出现，那么c后一共有3个地方可以插入d，
c_a_b_ ，就是下划线的地方。

那么ABA的答案就清楚了，也就是
     acb x  2
     cab x  3
---------------------
               5
就是5。

如果已知AB，求的是ABB，也是相似的道理。



在06-3-21，Chen Shuo <giantchen at gmail.com> 写道：
>
> 你这个程序的复杂度，在最坏情况下（"ABABABABABABAB...."），很可能是指数级的（我觉得）。
>
> On 3/21/06, Yi Fan <heavenstar at gmail.com> wrote:
> >
> > 恩，呵呵，纯递归的东西，写完就感觉着上亿的话，会慢得要死。
> >
> > 在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
> >
> >
> >
> > _______________________________________________
> > 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/20060322/eb6b2fe0/attachment.html