递归枚举 boj1035

冥王星的故事III-和谈Submit: 602   Accepted:359Time Limit: 1000MS  Memory Limit: 65536KDescription
由于冥王星H将军的强大攻势，已经攻占了地球的几个国家，地球决定派出他们的大使Wing和Pluto的大使xiaolonghingis进行和谈。

经过艰苦的谈判，最终冥王星开除了谈判的条件：
1 恢复Pluto的行星地位，并对战争进行赔偿。
2 完成由Pluto国王zhao0057出的一道智力题

题目描述如下：
由于冥王星采用二进制进位的制度，所以那里的居民经常会提出一些有关于二进制数的问题，其中之一是：给出n个0与n个1，将其按照一定顺序进行排列，则从左向右数，1的累计数总是大于或等于0的累计数，那么这样的排列一共有多少种？地球的命运掌握在你的手中了。


Input
输入第一行是一个正整数 T (T<=10) 表示测试数据的组数。
接下来T行，每一行包括一个数字n（n<=10），表示0和1的个数。

Output
对于每组输入，输出排列的个数。

Sample Input

2
1
2


Sample Output

1
2

Hint
n=1,那么只有10一种组合，n=2，有1010，1100两种组合


写递归的一些技巧：
1.在递归函数中，开始部分先进行条件判断，若不满足，则跳出。若满足，则递归该函数

#include <stdio.h>

int count;

/*one_count表示当前使用的1的个数，zero_count表示当前使用恶的0的个数，now_count表示前两个的和，all表示可以使用的所有0,1的个数*/
void recursion(int one_count, int zero_count, int now_count, int all)
{
    /*保证条件满足，否则跳出*/
    if (now_count > all - 1 || one_count < zero_count || one_count > all/2 || zero_count > all/2)
    {
        return;
    }
    /*找到一个结果，count++*/
    if (now_count == all - 1 && one_count >= zero_count)
    {
        count++;
    }
    recursion(one_count+1, zero_count, now_count+1, all);
    recursion(one_count, zero_count+1, now_count+1, all);
}

int count_entry(all)
{
    int i, zero_count = 0, one_count = 0;
    recursion(one_count, zero_count, 0, all);
}

int main(int argc, char *argv[])
{
    int T, all, i;
    scanf("%d", &T);
    for (i=0 ; i<T ; i++)
    {
        scanf("%d", &all);
        all *= 2;
        count = 0;
        count_entry(all);
        printf("%d\n", count);
    }
}