一道算法题。

Question

两个人（A,B)下棋：（只有胜负，没有和棋） A胜了m局，B胜了n局，m<n， 并A从来就没有在下的过程中多赢过B,问共有多少种可能在比赛出现？

Answer 1

m+n=T因为”A从来就没有在下的过程中多赢过B“所以按平均排列 B A B A B A ....
总共T个 (这种输赢的排列是B赢的局数一直领先于A的最平均的排列)如果T为偶数，
B A B A B A ... B A
那么可能性就是A在T/2里面选1 到 2/T的排列的总和
A赢一局，剩下全是B赢，那可能性就是P1(T/2)
A赢两局，剩下全是B赢，可能性则是P2(T/2)P1(T/2) + P2(T/2) + P3(T/2)...+ P(T/2)(T/2)如果T为奇数，
B A B A B A ... B
把上式(T/2)改成(T/2-1)即可不知道正确与否

Answer 2

上面漏了m，n的实际意义
应该是P1(T/2) + P2(T/2) + P3(T/2)...+ P(m)(T/2)

Answer 3

又错了，不用累加
    (m)
P
    ((m+n)/2) (奇数的话是 (m+n-1)/2)

Answer 4

貌似还是错了 B _ B _ B _ B _ ...B _ 因为m < n
所以只要降A填入任意的_中都将满足条件
总共有n个_,挑选任意的m个即可。所以，可能性就是
    m
C
    n举个例子，m=2, n=3B _ B _ B _
  A   A
  A       A
      A   AC2,3 = 3

Answer 5

我的思路是这样的
A 胜计 -1；
B 胜计  1；
这就组成了一个长度为 (m + n) 的数组
这个数组满足前 i (0<= i < m + n)个数相加都是小于 0 的
构建数组的过程可以用回溯做
比较笨的方法
在算出多少种情况的同时已经得到了各种符合条件的数组
不知有没好办法能直接算出多少种，而不用构建数组的
坐等高手

Answer 6

没有这么复杂吧？一共m+n局，每局不是A胜就是B胜，那这个不就是 2^(m+n)的数么
然后假设1表示该局A胜，0表示B胜，那么 “A从来...B”就表示为：从bit0开始截止到bitx，都有1个个数小于0的个数 。如果只是要求计算机有解的话，到这里就可以枚举了，不过效率很低。把0和1排队：
0000000000000: B一共赢了n局
 111111111111：A一共赢了m局， m<n
现在问题就变成：如何把1插入0中，且保证 从bit0 开始，无论计算到哪个bit，1个个数始终小于0的个数我们把这个问题再分成两部分：首先是 m个0和1混合，然后是剩下的 n-m个0插入。

Answer 7

先上枚举代码。  public static void main(String[] args) {
int m = 2, n = 3;
testBits(m, n); } private static void testBits(int m, int n) {
int max = 1 << (m + n);
int cnt = 0;
for (int i = 0; i < max; i++) {
if (judgment(i, m, n)) {
System.out.printf("%2d: %s\n", ++cnt, String.format("%6s",
Integer.toBinaryString(i)).replaceAll(" ", "0")
.replaceAll("0", "B").replaceAll("1", "A"));
}
} } private static boolean judgment(int num, int b1, int b0) {
int count0 = 0;
int count1 = 0;
for (int i = 0; i < (b0 + b1); i++) {
int a = (num & 1) == 0 ? count0++ : count1++;
if (count0 > b0 || count1 > b1 || count1 > count0) {
return false;
}
num >>= 1;
}
return true;
}运行结果：
 1: BBABAB
 2: BBAABB
 3: BABBAB
 4: BABABB
 5: BAABBB那个理论分析，遇到问题了，-_-!

Answer 8

public static void main(String[] args) throws Exception {
check(2, 3);
} static void check(int m, int n) {
int len = m + n;
char[] res = new char[len]; int min = (1 << n) - 1;
int max = ((1 << (len)) - 1) & (min << m); loop: for (int i = min; i <= max; i++) {
int a = 0, b = 0;
for (int j = 0; j < len; j++) {
int k = (i >> j) & 1;
if (k == 0) {
a++;
if (a > m)
continue loop;
if (a > b)
continue loop;
res[j] = 'A';
} else {
b++;
if (b > n)
continue loop;
res[j] = 'B';
}
}
System.out.println(new String(res));
}
}和ls差不多的思路

Answer 9

13楼的想法提示我了 
没必要那么笨重的去回溯了
楼主如果只是需要求多少种的话，可以直接公式了
total = (m + n)! / (2m)!
如果需要把各个情况都输出就楼上2位就行了

Answer 10

公式推导感觉很麻烦……
输出的话感觉应该还是回溯来的好，至少没有32位或者64位的限制，而且位数一大暴搜很慢的……………… public static void main(String[] args) throws Exception {
check(2, 3);
} static void check(int m, int n) {
char[] res = new char[m + n];
int[] arr = new int[m];
int index = 0, level = 0;
while (true) {
if (index >= 0 && index < m + n && level >= 0 && level < m
&& index > level * 2) {
arr[level++] = index++;
continue;
}
if (level >= m) {
Arrays.fill(res, 'B');
for (int i = 0; i < m; i++) {
res[arr[i]] = 'A';
}
System.out.println(new String(res));
level = m - 1;
index = arr[level] + 1;
continue;
}
if (index >= m + n) {
level--;
if (level < 0)
break;
index = arr[level] + 1;
continue;
}
index++;
continue;
}
}思路就是从数量少得A入手，简单的说就是m+n个格子里有m个是A，序号从0开始的从前到后第i个A所在的格子序号要大于i*2

Answer 11

公式是：C(m+n, m) - C(m+n, n-1)
具体推导参考 Catalan 数

Answer 12

m+n=1时  n=1
m+n=2时  n=2
m+n=3时  n=2 或者n=3
.....
m+n 时    n>(m+n)/2  
第一局和第二局肯定都是B胜

Answer 13

第一局。B一定要赢。。因为。。“并A从来就没有在下的过程中多赢过B,”

Answer 14

这个是不是一个排列组合的问题啊，如果将A胜利记成1，B胜利记成0。比如A胜利了3局，B胜利了4局。然后这种排列0010101符合题意，而1101000就不符合题意。lz寻求的是这种解吗？

Answer 15

zhuzeitou 的2段代码都可实现楼主的方法
本来准备写一个的，结果发现了他的代码写的比我的简单不贴代码了

Answer 16

这道题考虑AB的排序吗如A先胜和B先胜相同吗