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

[Feng Jiang]

呵呵。有意思。刚才想了一下，是不是可以这样解决？
假设给定的字符串长度为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);

这样子对吗？

On 3/18/06, cpp-request at codingnow.com <cpp-request at codingnow.com> wrote:
>
> Today's Topics:
>
>    1. [转贴]google的top coder的850分题例 (Chen Shuo)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Fri, 17 Mar 2006 23:48:54 +0800
> From: "Chen Shuo" <giantchen at gmail.com>
> Subject: [cpp] [转贴]google的top coder的850分题例
> To: "C++ Discuss Group" <cpp at codingnow.com>
> Message-ID:
>         <8e6b05440603170748qf5d284bg75c800251ef8aa59 at mail.gmail.com>
> Content-Type: text/plain; charset=GB2312
>
> [转贴]google的top coder的850分题例
>
> 假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前
> m 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5
> 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。
>
> 现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：
>
> 如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
> 如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
> 如果字母 d 在字母 c 的后面，那么 &# 8230;&# 8230; 不用多说了吧？直到这个字符串的结束。
>
> 这规则甚是简单，不过有个问题就是同一个 AB
>
> 序列，可能有多个字符串都与之相符，比方说序列"ABA"，就有"acdb"、"cadb"等等好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的
> AB 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。
>
> 如果结果大于10亿就返回-1。
>
> 大家不妨当个消遣看看，挺有意思的。既有递归的做法，也有递推的做法。
>
>
>
> ------------------------------
>
> _______________________________________________
> Cpp mailing list
> Cpp at codingnow.com
> http://codingnow.com/mailman/listinfo/cpp
>
>
> End of Cpp Digest, Vol 24, Issue 26
> ***********************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://codingnow.com/pipermail/cpp/attachments/20060320/8e21f595/attachment.html