首先計(jì)算出組合數(shù)。用cmb_num[i][j]表示i位數(shù)中，"1的位數(shù)小于等于j"的數(shù)的個(gè)數(shù)。
這樣，我們從最左邊開始，如果cmb_num[i-1][j]的數(shù)大于n，說明第一位為0，因?yàn)橛胕-1位數(shù)中"1的位數(shù)小于等于j"的數(shù)已經(jīng)大于n個(gè)了。
如果小于n，說明第一位為1，需要i位，才能使"1的位數(shù)小于等于j"的數(shù)大于n個(gè)了。既然第一位已經(jīng)是1了，接下來的i-1位組成的數(shù)的1的個(gè)數(shù)只能小于等于n-1位了。迭代輸出每一位即可。
只是要注意溢出的問題以及cmb_num[0][1]。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("kimbits.in");
ofstream?fout("kimbits.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
unsigned?int?cmb_num[32][32];
void?build_cmb_num()
{
????for(int?i=0;i<32;++i)
????????cmb_num[i][0]?=?1;
????for(int?i=1;i<32;++i)
????????for(int?j=1;j<=i;++j)
????????????cmb_num[i][j]?=?cmb_num[i-1][j-1]+cmb_num[i-1][j];
????for(int?i=0;i<32;++i)
????????for(int?j=1;j<32;++j){
????????????cmb_num[i][j]+=cmb_num[i][j-1];
????????}
}
void?solve()
{
????build_cmb_num();
????unsigned??n,l,i;
????in>>n>>l>>i;
????for(unsigned?idx=n;idx>0;--idx){
????????if(?i>?cmb_num[idx-1][l]?){
????????????out<<1;
????????????i-=cmb_num[idx-1][l];
????????????l--;
????????}else{
????????????out<<0;
????????}???
????}
????out<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}
附題：
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