【2014微软实习生笔试】2：找到第k个字符串

Time Limit: 10000ms Case Time Limit: 1000ms Memory Limit: 256MB Description Consider a string set that each of them consists of {0, 1} only. All strings in the set have the same number of 0s and 1s. Write a program to find and output the K

Time Limit: 10000ms
Case Time Limit: 1000ms
Memory Limit: 256MB

Description

Consider a string set that each of them consists of {0, 1} only. All strings in the set have the same number of 0s and 1s. Write a program to find and output the K-th string according to the dictionary order. If s?uch a string doesn’t exist, or the input is not valid, please output “Impossible”. For example, if we have two ‘0’s and two ‘1’s, we will have a set with 6 different strings, {0011, 0101, 0110, 1001, 1010, 1100}, and the 4th string is 1001.


Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10000), the number of test cases, followed by the input data for each test case.
Each test case is 3 integers separated by blank space: N, M(2 = 0), K(1
Output
For each case, print exactly one line. If the string exists, please print it, otherwise print “Impossible”.

Sample In
3
2 2 2
2 2 7
4 7 47

Sample Out
0101
Impossible
01010111011

题目解析：

题意是所有n个0和m个1，然后组合排列，并按照从小到大的顺序排列，找到第k个二进制表示并输出。

好，我们可以组合一下排列，然后按照从小到大的十进制数据顺序来排列，然后查找第k个数据，最后转换为二进制输出。不过这样工作量挺大，我们组合排列的时候也要用二进制来排列。那么我们怎么去排列？先试着将题目中的例子，看看能不能找到什么规律。（接下来我们会看到，数学是很美妙的东西，等分析透彻了再动手写，代码会很简单）

排列组合我们写成Cmn。对于两个0，两个1来说：0011, 0101, 0110, 1001, 1010, 1100。

第一类：第一个数据为0011，最小，对应n个零+m个1；

第二类：第二个数据和第三个数据的时候，最高位的1增加，最低位的0降低，这时一个0一个1有两种组合（c21）

第三类：第四个到第六个数据，最高位1再提高一位至二进制的最高位，这时后面两个0和一个1有三种组合（c32）

同样我们可以通过两个0和三个1来组合成十个数：00111,01011,01101,01110,10011,10101,10110,11001,11010,11100

第一类：n个零+m个1——00111

第二类：最高位1进一位，后面m-1个1和1个0全排列——01011,01101,01110（c31）

第三类：最高位1再进一位，后面m-1个1和2个0全排列——10011,10101,10110,11001,11010,11100（c42）

通过这两个例子我们可以看到如下规律：

1+c(m-1+1)1+c(m-1+2)1+...+c(m-1+i)i+...+c(m-1+n)n

也就是最高位1不断提高，0的个数不断增加，组合数自然也不断增加。

通过展开组合数，第i个c(m-1+i)i和c(m-1+i-1)(i+1)的关系是：c(m-1+i+1)(i+1) = c(m-1+i)i * (m-1+i+1) / (i+1);

通过上述分析，不难看出，这里可以利用递归的形式，让1不断提高，直到所有的组合数超过k为止，必然k在c(m-1+i)i 中出现，那么可以确定n-i个0在最开始，紧接着是1，最后是i个零和m-1个1的组合！再递归的确定剩余的0和1的关系即可！但有一点需要注意，如果恰好1+...+c(m-1+i)i == k;那么就可以确定i个零在最后，m-1个1在前面。

代码如下：

#include 
#include 



int FindKthString(int arr[],int n,int m,int k);

int main(void)
{
    int n,m,k;

    while(1){
        printf("\nplease input n,m,k:");
        scanf("%d %d %d",&n,&m,&k);
        int *arr = (int *)malloc((n+m) * sizeof(int));
        int result = FindKthString(arr,n,m,k);
        if(!result)
            printf("impossible");
        else{
            for(int i = 0;i = k)       //必须加等号，证明i个0在末尾的时候查找成功。
            break;
        sum += temp;
    }
    if(i>n)
        return 0;
    //--i; 这句话不能要，必须在i个零里面才能匹配

    for(int j = 0;j 

总结：通过这个题可以看出来，数学是多么的美妙，那么复杂的问题，通过一个表达式就给解决了。代码也很简单！碰到问题，尽量导出表达式。