首页 > 代码库 > 送上今年微软的一道笔试题

送上今年微软的一道笔试题

2024-08-07 23:46:17   217人阅读

这里送上一道微软的笔试题，具体题目如下：

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 <= N + M <= 33 and N , M >= 0),

K(1 <= K <= 1000000000). N stands for the number of ‘0’s, M stands for the number of ‘1’s,

and K stands for the K-th of string in the set that needs to be printed as output.

 

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.然后求出由M，N个1,0组成的第K大的数。如果不存在则输出impossible.

初来乍到的，大家可能会认为这是一个全排列的问题，但是全排列在问题在于不能很好的知道每个数到底排在第几位，并且时间上肯定是不能通过的，递归的效率大家应该都知道。

我们可能会想到另外一种解决方案，直接列举，从最小的000...1111开始，一直列举到1111..000然后记录下当前是否是含N个0，M个1。这种方式是最容易理解的了，但是如果数字比较大，比如17个1,17个0,我们且不说这么大的整数不能保存，就这个时间上也不合算啊，虽然他是线性复杂度，但是这个线性数也太大了点。。。

OK，我接下来又想到了是否可以通过树的遍历，想了想被我否了。

终于想到了一种方式，就是通过不断的交换获得。我们想到，如果从一个第1大的数变成第2大的数，必然要使这个数增大，那么怎么个增大法？才能使得这两个数是最接近的，也就是说我们只增加了1，而不是中间还存在很多数呢？

那就是从左到右扫描数据，直到遇到10就交换，并且在该1之前的1要和最低位的0交换。好的思路已经完全暴露了，我这里就列举一个例子。

比如5个1，5个0的情况。

我们保存的格式是1111100000(实际数为0000011111)，它是最小的数(输出的时候倒着输出，这种结构主要为了理解方便)。最大的数是0000011111.（记住，是倒着哈！）

当我们要增加的时候在J=5的时候，出现了0，且j=4时,它为1，这样就交换他们，j=4之前的1和低位的0交换，这里没有0就不需要交换了。得到1111010000（实际数为0000101111）.

当我们出现0011101100(实际数为0011011100)要使数字增加1应该怎么做呢？显然，还是J=5时出现了0且j-1=4时为1交换他们，并且j=4之前的1和最低位的0开始不断交换，最后我们会得到结果：1100011100.(实际数为00111000011).

Ok,说到这里大家应该就完全懂了，且看算法源代码：[集思广益，你们有没有更好的解决方案？]

  1. //M：0的个数，N，1的个数。K要输出第几个数。 
  2. bool test(int N,int M,int K){ 
  3.     if(calculateTotalNum(M+N,M)<K)//若实际上的数少于k，返回false,则输出impossible 
  4.         return false; 
  5.     int L=M+N,count=1; 
  6.     bitset<MaxLength> bit; 
  7.     map<int,bitset<MaxLength>> mapStr; 
  8.     for(int i=0;i<M;i++)//初始话最小数，即0都在最左边比如0011 
  9.         bit[i]=1; 
  10.     if(K==1){ 
  11.         print(bit,M+N);//输出 
  12.         return true; 
  13.     } 
  14.     int j=0;//表示从低位一直搜索到高位，有没有遇到01，有的话就不断交换。 
  15.     while(!isLast(bit,M,N)){//没有搜索到最后一个数字 
  16.         if(j>=M+N-1) 
  17.             j=0;//已经搜索到最高位了，这个时候就需要从0位搜索 
  18.         if(1==bit[j]&&0==bit[j+1]){ 
  19.             int right=j-1,left=0; 
  20.             //从J的前一个搜素，并且该之前的1全部移动到最左边 
  21.             while(right>=0&&bit[right]==1&&left<right){ 
  22.                 bool temp=bit[right]; 
  23.                 bit[right]=bit[left]; 
  24.                 bit[left]=temp; 
  25.                 right--,left++; 
  26.             } 
  27.             bit[j]=0;//交换0,1 
  28.             bit[j+1]=1; 
  29.             count++;//统计是第几个大的数了 
  30.             if(count==K){ 
  31.                 print(bit,M+N); 
  32.                 return true; 
  33.             } 
  34.             j=0;//重新回过头来搜素 
  35.         } 
  36.         else 
  37.             j++; 
  38.     } 
  39.     return true; 
  40. } 
  41.  
  42. int calculateTotalNum(int N,int M){//组合问题，计算一共多少个数。C(M,N)=A(N,N)/(A(M,M)*A(N-M,N-M)) 
  43.     int result=1; 
  44.     for(int i=1;i<=N;i++) 
  45.         result*=i; 
  46.     for(int i=1;i<=M;i++) 
  47.         result/=i; 
  48.     for(int i=1;i<=N-M;i++) 
  49.         result/=i; 
  50.     return result; 
  51. } 
  52. bool isLast(bitset<MaxLength> bit,int M,int N){ 
  53.     int i=0; 
  54.     while(i<N&&0==bit[i]) 
  55.         i++; 
  56.     if(i==N) 
  57.         return true; 
  58.     else 
  59.         return false; 
  60. } 
  61. void print(bitset<MaxLength> bit,int N){// 
  62.     for(int i=N-1;i>=0;i--) 
  63.         cout<<bit[i]; 
  64.     cout<<""; 
  65. } 

 

附上效果截图：

[庸男勿扰] 同学提供了一种其他的解决方式，主要是通过递归的判断当前0,1组合生成的个数与K进行比较。

(保证在不减一个0时，生成的组合总数是大于K的，否则return。)

若当前0的个数减一后，生成的总数要大于K，则输出0，同时0的个数减一，K,1的个数不变。

若当前0的个数减一后，生成的总数小于K，则输出1，同时1的个数减一，0的个数不变，K=K-当前总数。

递归调用。最后能得到结果。

代码 [庸男勿扰] 已经贴出，在回答留言处！

[有一个问题是，我和庸男勿扰在计算总次数的时候都会有溢出的问题，即使用Long long也会溢出的，大家在计算阶乘或者组合问题对溢出解决方案有什么好的建议可以给出吗？] 

原文链接：http://www.cnblogs.com/xiaoyi115/p/3696507.html

送上今年微软的一道笔试题


联系
我们