[cpp] Re: Cpp Digest, Vol 24, Issue 26
Yi Fan
heavenstar at gmail.com
Thu Mar 23 12:54:24 CST 2006
呵呵，原来maillist也能开同学会，^_^
不知道是不是jiang feng, 有可能吧，他在网易的。
在06-3-23，Chen Shuo <giantchen at gmail.com> 写道：
>
> N^2 的算法
>
> int countAB(const string& AB)
> {
> vector<int> current, next;
> // should we reserve these vectors?
> current.push_back(1);
>
> for (size_t letter = 0; letter < AB.length(); ++letter) {
> next.resize(current.size()+1);
> next[0] = 0;
> if (AB[letter] == 'A') {
> partial_sum(current.begin(), current.end(), next.begin()+1);
> } else {
> assert(AB[letter] == 'B');
> partial_sum(current.rbegin(), current.rend(), next.begin()+1);
> reverse(next.begin(), next.end());
> }
> swap(current, next);
> }
> return accumulate(current.begin(), current.end(), 0);
> }
>
>
> On 3/23/06, 刘 思立 <neptrue at hotmail.com> wrote:
> > 于我心有戚戚焉~也是这样想的,不知道再提高效率应该怎样....
> > ps:是王一帆吗？
> > ps again:第一个解答者是江峰吗？
> >
> >
> > >From: "Yi Fan" <heavenstar at gmail.com>
> > >Reply-To: C++ Discuss Group <cpp at codingnow.com>
> > >To: "C++ Discuss Group" <cpp at codingnow.com>
> > >Subject: Re: [cpp] Re: Cpp Digest, Vol 24, Issue 26
> > >Date: Wed, 22 Mar 2006 11:08:00 +0800
> > >
> > >那个函数的确很慢，这样递归的搜索不是好的方法，至少对这题不是，因为它只要求
> > 返回一个数字，而不是构造所有的串。早上用动态规划改写了一下，发现这题的动规用
> > 的递推式挺好推的，
> > >效率应该可以。
> > >代码：
> > >
> > >#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
> > > >
> >
> >
> > >_______________________________________________
> > >Cpp mailing list
> > >Cpp at codingnow.com
> > >http://codingnow.com/mailman/listinfo/cpp
> >
> > _________________________________________________________________
> > 免费下载 MSN Explorer: http://explorer.msn.com/lccn
> >
> > _______________________________________________
> > 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/20060323/ea8f12d5/attachment-0001.html
More information about the Cpp
mailing list