Stringsobits
Kim Schrijvers

Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.

This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.

Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

PROGRAM NAME: kimbits

INPUT FORMAT

A single line with three space separated integers: N, L, and I.

SAMPLE INPUT (file kimbits.in)

5 3 19

OUTPUT FORMAT

A single line containing the integer that represents the Ith element from the order set, as described.

SAMPLE OUTPUT (file kimbits.out)

10011

题意:
找出N为的二进制数中1个数小于等于L的第I个数

代码如下:
/*
LANG: C
TASK: kimbits
*/
#include
<stdio.h>
long long cmb[33][33];
void setCmb(long long n)
{
    
long long i, j;
    
for (i = 0; i <= n; i++)//零位数中'1'个数为0的情况数是1 
    {
        cmb[i][
0= 1;
        
//cmb[i][i+1] = 0;
    }
    
for (i = 1; i <= n; i++)//i位数中恰好有j个'1'的个数 
    {
        
for (j = 1; j <= i; j++)
        {
            cmb[i][j] 
= cmb[i-1][j-1+ cmb[i-1][j];
        }
    }
    
for (i = 0; i <= n; i++)//i位数中'1'个数小于等于j的情况数 
    {
        
for (j = 1; j <= n; j++)
        {
            cmb[i][j] 
+= cmb[i][j-1];
        }
    }
}
void find(long long n, long long m, long long th)
{
    
long long i;
    
for (i = n; i >= 1; i--)
    {
        
//如果i-1位数中1个数大于等于th,说明前i-1位就能满足th个'1'个数小于等于m的数。
        if (cmb[i-1][m] >= th) 
        {
            printf(
"0");
        }
        
else//否则,说明第i位是1,要利用到第i位 
        {
            printf(
"1");
            
//情况数th减去第i位是0的前i-1位'1'个数小于等于m的情况数,剩下第i位是1,前i-1位'1'个数小于等于m-1的情况数 
            
//已经定了一个'1',接下来找小于等于m-1个'1'的情况
            th -= cmb[i-1][m--];            
        }
    }
    printf(
"\n");
}
int main()
{
    freopen(
"kimbits.in""r", stdin), freopen("kimbits.out""w", stdout);
    
long long n, m, th;
    scanf(
"%lld%lld%lld"&n, &m, &th);
    setCmb(n);
    find(n, m, th);
    fclose(stdin), fclose(stdout);
    
//system("pause");
    return 0;
}