腾讯2016编程笔试题

1、在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。请编写一个函数，使用递归方法生成N位的格雷码，并且保证这个函数的健壮性。

首先的搞清楚格雷码是什么，百度百科

生成格雷码的方法很多，百科中提到几种生成格雷码的方法，其中包括如下几种：

①递归法：

1位格雷码有两个码字；
(n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0；
(n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1；

实现代码：

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> RecursiveGrayCode(int N)
{
    vector<string> temp;
    if (1 == N)
    {
        temp.push_back("0");
        temp.push_back("1");
        return temp;
    }
    vector<string> temp1 = RecursiveGrayCode(N-1);

    int size = temp1.size();
    int i=0;

    for (i=0;i<size;i++)
    {
        temp.push_back("0"+temp1[i]);
    }

    for (i=size-1;i>=0;i--)
    {
        temp.push_back("1"+temp1[i]);
    }

    return temp;
}

void GrayCode(int N)
{
    if (N<=0)
    {
        cout << "Error
";
        return ;
    }
    vector<string> result = RecursiveGrayCode(N);
    for (int i=0;i<result.size();i++)
    {
        cout << result[i]<<endl;
    }
}

int main()
{
    GrayCode(4);
    return 0;
}

②异或转换：

二进制码-->格雷码

对n位二进制的码字，从右到左，以0到n-1编号；
如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）；

公式表示：

Gi=Bi^Bi+1（G：格雷码，B：二进制码）

例如：二进制码0101，为4位数，所以其所转为之格雷码也必为4位数，因此可取转成之二进位码第五位为0，即0 b3 b2 b1 b0。

0 xor 0=0，所以g3=0

0 xor 1=1，所以g2=1

1 xor 0=1，所以g1=1

0 xor 1=1，所以g0=1

因此所转换为之格雷码为0111

代码：

 1 string BinaryCodeToGrayCode(string binaryCode)
 2 {
 3     string GrayCode="";
 4     int size = binaryCode.length();
 5     bool c;
 6     bool temp=0;
 7     bool bit;
 8     for (int i=0;i<size;i++)
 9     {
10         bit = binaryCode[i]-'0';
11         c=temp^bit;
12         if (c)
13         {
14             GrayCode +="1";
15         }
16         else
17         {
18             GrayCode +="0";
19         }
20         
21         temp = bit;
22 
23     }
24     return GrayCode;
25 }

格雷码-->二进制码

　　从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。

公式表示：

Bi=Gi^Bi+1 （G：格雷码，B：二进制码）

举例：

如果采集器器采到了格雷码：1010

就要将它变为自然二进制：

0 与第四位 1 进行异或结果为 1

上面结果1与第三位0异或结果为 1

上面结果1与第二位1异或结果为 0

上面结果0与第一位0异或结果为 0

因此最终结果为：1100 这就是二进制码即十进制 12

实现代码：

 1 string GrayCodeToBinaryCode(string GrayCode)
 2 {
 3     string binaryCode="";
 4     int size = GrayCode.length();
 5     bool c;
 6     bool temp=0;
 7     bool bit;
 8     for (int i=0;i<size;i++)
 9     {
10         bit = GrayCode[i]-'0';
11         c=temp^bit;
12         if (c)
13         {
14             binaryCode +="1";
15         }
16         else
17         {
18             binaryCode +="0";
19         }
20         
21         temp = c;
22 
23     }
24     return binaryCode;
25 }

2、题目如图所示，求出所有满足条件的情况：

这道题的第一思路就是找出隐含关系，然后暴力求解。假设所填空格从上往下，从左往右依次为a,b,c,d,e,f,g,h即：

a	b	9
c	d	e
f	g	h

通过找隐含关系可以找到如下关系：

a+b=13;

0<=a<=4;

e+h=5;

0<=e<=5;

因为b最大为13，所以有b-d*g==4可知，d<=9,g<=9且d，g都不能为0；

1<=f<=100

接下来就是暴力求解，代码如下：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 void main()
 5 {
 6     int a,b,c,d,e,f,g,h;
 7     for (a=0;a<=4;a++)
 8     {
 9         b=13-a;
10         for (e=0;e<=5;e++)
11         {
12             h=5-e;
13             
14             for (d=1;d<=9;d++)
15             {
16                 c=d*e+4;
17                 for (g=1;g<=9;g++)
18                 {
19                 
20                     for (f=1;f<=100;f++)
21                     {
22                         if (c%f == 0)
23                         {
24                             if ((a+c/f == 4)&&(b-d*g == 4)&&(f+g-h == 4))
25                             {
26                                 cout << a << " "<< b <<" "<<9<<endl;
27                                 cout << c << " "<< d <<" "<<e<<endl;
28                                 cout << f << " "<< g <<" "<<h<<endl;
29 
30                             }
31                         }
32                         else
33                             continue;
34                         
35                     }
36                 }
37             }
38                 
39         }
40     }
41 
42 }

3. 如图所示，系统中有三个进程Producer，Transmitter和Consumer。Producer和Transmitter共用缓冲区ProduceBuf，Consumer和Transmitter共用缓冲区ConsumeBuf。

Producer进程负责不断地将输入信息送入ProduceBuf；Transmitter进程负责从ProduceBuf中取出信息进行处理，并将处理结果送到ConsumeBuf；Consumer进程负责从ConsumeBuf中读取结果并输出。

假设ProduceBuf中最多可放12个信息，现已放入了3个信息；ConSumeBuf最多可放6个信息。试写出正确实现进程Producer,Transmitter和Consumer的同步与互斥的算法（要求：用类C语言描述，条理清楚，注释恰当；）

分析：

要解决这道题目，首先需要掌握一般的producer和consumer问题（操作系统经典问题）

附上本科操作系统课程实验代码

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<windows.h>
  4 #include<stdio.h>
  5 #include<ctime>
  6 using namespace std;
  7 
  8 /*****定义缓冲区单元******/
  9  
 10 typedef int buffer_item;
 11 #define BUFFER_SIZE 5
 12 
 13 buffer_item buffer[BUFFER_SIZE+1];//利用数组模拟缓冲区，因为可使用的个数比数组个数少一个
 14 int first,last;//first指向已经插入的第一个单元，last指向下一个可插入的单元
 15 HANDLE mutex,empty,full;
 16 
 17 int insert_item(buffer_item item){
 18     /*insert a buffer item into buffer,
 19       return 0 if successful,otherwise 
 20       return -1 indicating an error condition
 21     */
 22 
 23     if((last+1)%BUFFER_SIZE==first)//判断满？
 24         return -1;//Yes
 25     else{
 26         buffer[last]=item;
 27         last = (last+1)%BUFFER_SIZE;
 28         return 0;
 29     }
 30 }
 31 
 32 int remove_item(buffer_item* item){
 33     /*romove a buffer item into buffer,
 34       return 0 if successful,otherwise 
 35       return -1 indicating an error condition
 36     */
 37 
 38     if(first == last)//判断空？
 39         return -1;//Yes
 40     else{
 41         *item=buffer[first];
 42         first = (first + 1)%BUFFER_SIZE;
 43         return 0;
 44     }
 45 }
 46 
 47 DWORD WINAPI Producer(LPVOID Param){
 48     int i = *(int *)Param;
 49     int ran;
 50     srand(time(0));
 51     while(true){
 52         Sleep(rand()%1000);
 53         //参照书本算法P177页
 54         WaitForSingleObject(empty,INFINITE);
 55         WaitForSingleObject(mutex,INFINITE);//当有多个Producer线程时，这个变量是有用的
 56         /*临界区*/
 57             ran = rand();
 58             cout << "producer produced " << ran <<" by " <<i<<endl;
 59             if(insert_item(ran)==-1)
 60                 cout<<"insert data error!
";
 61         ReleaseMutex(mutex);
 62         ReleaseSemaphore(full,1,NULL);//1表示递增信号量值（步长）
 63     }
 64 
 65     return 0;
 66 }
 67 
 68 DWORD WINAPI Consumer(LPVOID Param){
 69     int i = *(int *)Param;
 70     buffer_item ran;
 71     srand(time(0));
 72     while(true){
 73         Sleep(rand()%1000);//随机等待也是为了防止各个线程等待时间一样，导致工作方式同步
 74         //参照书本算法P177页
 75         WaitForSingleObject(full,INFINITE);
 76         WaitForSingleObject(mutex,INFINITE);
 77         /*临界区*/
 78             //ran = rand();
 79             
 80             if(remove_item(&ran)==-1)
 81                 cout<<"remove data error!
";
 82             else
 83                 cout << "consumer consumed " << ran <<" by " <<i<< endl;
 84         ReleaseMutex(mutex);
 85         ReleaseSemaphore(empty,1,NULL);//1表示递增信号量值（步长）
 86     }
 87 
 88     return 0;
 89 }
 90 
 91 int main(int argc,char* argv){
 92 
 93     /*初始化缓冲*/
 94     first=last=0;
 95 
 96     int sleeptime;//睡眠时间
 97     int proNum,conNum;//生产者和消费者线程数量
 98     HANDLE *ThreadHandleOfProducer,*ThreadHandleOfConsumer;//线程句柄
 99     unsigned long *ThreadIDProducer,*ThreadIDConsumer;//线程ID数组
100     int * ParamOfProducer,*ParamOfConsumer;
101     /*
102     sleeptime=atoi(argv[1]);
103     proNum=atoi(argv[2]);
104     conNum=atoi(argv[3]);
105     */
106 
107     sleeptime = 1000;
108     proNum=3;
109     conNum=3;
110 
111     ThreadHandleOfProducer = new HANDLE[proNum];
112     ThreadHandleOfConsumer = new HANDLE[conNum];
113     ThreadIDProducer = new unsigned long[proNum];
114     ThreadIDConsumer = new unsigned long[conNum];
115     ParamOfProducer = new int[proNum];
116     ParamOfConsumer = new int[conNum];
117     
118     /*信号量的声明*/
119     mutex=CreateMutex(NULL,FALSE,NULL);
120     empty=CreateSemaphore(NULL,BUFFER_SIZE,BUFFER_SIZE,NULL);//第二个参数是初值，第三个是最大值
121     full=CreateSemaphore(NULL,0,BUFFER_SIZE+1,NULL);//第二个参数是初值，第三个是最大值
122     //创建生产者线程
123     for(int i =0;i<proNum;i++){
124         ParamOfProducer[i]=i+1;
125         ThreadHandleOfProducer[i]=CreateThread(
126             NULL,//default
127             0,//default stack size
128             Producer,//thread function
129             &ParamOfProducer[i],//parameter to thread function
130             0,//default creation flags;
131             &ThreadIDProducer[i]//返回线程的ID
132             );
133     }
134     //创建消费者线程
135     for(int j =0;j<conNum;j++){
136         ParamOfConsumer[j]=j+1;
137         ThreadHandleOfConsumer[j]=CreateThread(
138             NULL,//default
139             0,//default stack size
140             Consumer,//thread function
141             &ParamOfConsumer[j],//parameter to thread function
142             0,//default creation flags;
143             &ThreadIDConsumer[j]//返回线程的ID
144             );
145     }
146 
147     Sleep(sleeptime);
148     return 0;
149 }

仔细研究上面的代码，可以发现第108和109行，其实现了多个生产者和多个消费者，并且需要注意各个信号量的初始值。本题需要解决两个buffer，生产者buffer和消费者buffer各一个。按照上面代码思路，解决此题的需要再增加几个信号量，添加一个transmitter函数，其功能是作为一个传递者，代码实现如下（仅供参考），其主要部分是transmitter函数，transmitter必须在produceBuffe有数据，并且consumeBuffer不是满的情况下才能执行操作：

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<windows.h>
  4 #include<stdio.h>
  5 #include<ctime>
  6 using namespace std;
  7 
  8 /*****定义缓冲区单元******/
  9  
 10 typedef int buffer_item;
 11 #define PRODUCE_BUFFER_SIZE 12
 12 #define CONSUME_BUFFER_SIZE 6
 13 
 14 
 15 buffer_item producebuffer[PRODUCE_BUFFER_SIZE+1];//利用数组模拟缓冲区，因为可使用的个数比数组个数少一个
 16 buffer_item consumebuffer[CONSUME_BUFFER_SIZE+1];//利用数组模拟缓冲区，因为可使用的个数比数组个数少一个
 17 
 18 int firstofproduce,lastofproduce,firstofconsume,lastofconsume;//first指向已经插入的第一个单元，last指向下一个可插入的单元
 19 HANDLE mutexofproduce,emptyofproduce,fullofproduce;//produce buffer
 20 HANDLE mutexofconsume,emptyofconsume,fullofconsume;//consume buffer
 21 HANDLE mutexoftransimitter;
 22 
 23 int insert_item_pro(buffer_item item){
 24     
 25     if((lastofproduce+1)%PRODUCE_BUFFER_SIZE==firstofproduce)//判断满？
 26         return -1;//Yes
 27     else{
 28         producebuffer[lastofproduce]=item;
 29         lastofproduce = (lastofproduce+1)%PRODUCE_BUFFER_SIZE;
 30         return 0;
 31     }
 32 }
 33 
 34 int insert_item_con(buffer_item item){
 35 
 36     if((lastofconsume+1)%CONSUME_BUFFER_SIZE==firstofconsume)//判断满？
 37         return -1;//Yes
 38     else{
 39         consumebuffer[lastofconsume]=item;
 40         lastofconsume = (lastofconsume+1)%CONSUME_BUFFER_SIZE;
 41         return 0;
 42     }
 43 }
 44 
 45 int remove_item_pro(buffer_item* item){
 46     
 47     if(firstofproduce == lastofproduce)//判断空？
 48         return -1;//Yes
 49     else{
 50         *item=producebuffer[firstofproduce];
 51         firstofproduce = (firstofproduce + 1)%PRODUCE_BUFFER_SIZE;
 52         return 0;
 53     }
 54 }
 55 
 56 int remove_item_con(buffer_item* item){
 57     
 58     if(firstofconsume == lastofconsume)//判断空？
 59         return -1;//Yes
 60     else{
 61         *item=consumebuffer[firstofconsume];
 62         firstofconsume = (firstofconsume + 1)%CONSUME_BUFFER_SIZE;
 63         return 0;
 64     }
 65 }
 66 
 67 
 68 DWORD WINAPI Producer(LPVOID Param){
 69     int i = *(int *)Param;
 70     buffer_item ran;
 71     srand(time(0));
 72     while(true){
 73         Sleep(rand()%1000);
 74         //参照书本算法P177页
 75         WaitForSingleObject(emptyofproduce,INFINITE);
 76         WaitForSingleObject(mutexofproduce,INFINITE);
 77         /*临界区*/
 78             ran = rand();
 79             cout << "producer produced " << ran <<" by " <<i<<endl;
 80             if(insert_item_pro(ran)==-1)
 81                 cout<<"insert data error!
";
 82         ReleaseMutex(mutexofproduce);
 83         ReleaseSemaphore(fullofproduce,1,NULL);//1表示递增信号量值（步长）
 84     }
 85 
 86     return 0;
 87 }
 88 
 89 DWORD WINAPI Transmitter(LPVOID Param){
 90     int i = *(int *)Param;
 91     buffer_item ran;
 92     srand(time(0));
 93     
 94     Sleep(rand()%1000);
 95     //参照书本算法P177页
 96     while (true)
 97     {
 98         Sleep(rand()%1000);
 99         WaitForSingleObject(fullofproduce,INFINITE);//等到produce buffer 队列里面有内容
100         WaitForSingleObject(emptyofconsume,INFINITE);//此时consume buffer 队列有空位
101 
102         WaitForSingleObject(mutexoftransimitter,INFINITE);
103         
104         if(remove_item_pro(&ran)==-1)
105             cout<<"remove data error!
";
106 
107         //数据处理
108         cout << "transimitter consumed " << ran <<" by " <<i<<endl;
109         ran = ran + 10;
110         
111         if (insert_item_con(ran) == -1)
112         {
113             cout<<"insert data error!
";
114         }
115 
116         cout << "transimitter produced " << ran <<" by " <<i<<endl;
117         ReleaseMutex(mutexoftransimitter);
118 
119         ReleaseSemaphore(fullofconsume,1,NULL);//可以理解为fullofconsume+1
120         ReleaseSemaphore(emptyofproduce,1,NULL);//1表示递增信号量值（步长）
121     }
122 
123     return 0;
124 }
125 
126 DWORD WINAPI Consumer(LPVOID Param){
127     int i = *(int *)Param;
128     buffer_item ran;
129     srand(time(0));
130     while(true){
131         Sleep(rand()%1000);
132         //参照书本算法P177页
133         WaitForSingleObject(fullofconsume,INFINITE);
134         WaitForSingleObject(mutexofconsume,INFINITE);
135         /*临界区*/
136             //ran = rand();
137             
138             if(remove_item_con(&ran)==-1)
139                 cout<<"remove data error!
";
140             else
141                 cout << "consumer consumed " << ran <<" by " <<i<< endl;
142         ReleaseMutex(mutexofconsume);
143         ReleaseSemaphore(emptyofconsume,1,NULL);//1表示递增信号量值（步长）
144     }
145 
146     return 0;
147 }
148 
149 int main(int argc,char* argv){
150 
151     /*初始化缓冲*/
152     firstofproduce=0;
153     firstofconsume=0;
154     lastofproduce=2;
155     lastofconsume=0;
156 
157     //初始化producebuffer中前三个数
158     producebuffer[0]=1;
159     producebuffer[1]=2;
160     producebuffer[2]=3;
161 
162 
163     int sleeptime;//睡眠时间
164     int proNum,conNum,traNum;//生产者和消费者线程数量
165     HANDLE *ThreadHandleOfProducer,*ThreadHandleOfConsumer,*ThreadHandleOfTransimitter;//线程句柄
166     unsigned long *ThreadIDProducer,*ThreadIDConsumer,*ThreadIDTransimitter;//线程ID数组
167     int * ParamOfProducer,*ParamOfConsumer,*ParamOfTransimitter;
168     /*
169     sleeptime=atoi(argv[1]);
170     proNum=atoi(argv[2]);
171     conNum=atoi(argv[3]);
172     */
173 
174     sleeptime = 10000;
175     proNum=1;
176     conNum=1;
177     traNum=1;
178 
179     ThreadHandleOfProducer = new HANDLE[proNum];
180     ThreadHandleOfConsumer = new HANDLE[conNum];
181     ThreadHandleOfTransimitter = new HANDLE[traNum];
182     ThreadIDProducer = new unsigned long[proNum];
183     ThreadIDConsumer = new unsigned long[conNum];
184     ThreadIDTransimitter = new unsigned long[traNum];
185     ParamOfProducer = new int[proNum];
186     ParamOfConsumer = new int[conNum];
187     ParamOfTransimitter = new int[traNum];
188     
189     /*信号量的声明*/
190     mutexofproduce=CreateMutex(NULL,FALSE,NULL);
191     mutexofconsume=CreateMutex(NULL,FALSE,NULL);
192     mutexoftransimitter=CreateMutex(NULL,FALSE,NULL);
193 
194     emptyofproduce=CreateSemaphore(NULL,PRODUCE_BUFFER_SIZE,PRODUCE_BUFFER_SIZE,NULL);//第二个参数是初值，第三个是最大值
195     fullofproduce=CreateSemaphore(NULL,3,PRODUCE_BUFFER_SIZE,NULL);//第二个参数是初值，第三个是最大值
196 
197     emptyofconsume=CreateSemaphore(NULL,CONSUME_BUFFER_SIZE,CONSUME_BUFFER_SIZE,NULL);
198     fullofconsume=CreateSemaphore(NULL,0,CONSUME_BUFFER_SIZE,NULL);
199 
200 
201     //创建生产者线程
202     for(int i =0;i<proNum;i++){
203         ParamOfProducer[i]=i+1;
204         ThreadHandleOfProducer[i]=CreateThread(
205             NULL,//default
206             0,//default stack size
207             Producer,//thread function
208             &ParamOfProducer[i],//parameter to thread function
209             0,//default creation flags;
210             &ThreadIDProducer[i]//返回线程的ID
211             );
212     }
213 
214     //创建传递者线程
215     for(int j =0;j<traNum;j++){
216         ParamOfConsumer[j]=j+1;
217         ThreadHandleOfTransimitter[j]=CreateThread(
218             NULL,//default
219             0,//default stack size
220             Transmitter,//thread function
221             &ParamOfConsumer[j],//parameter to thread function
222             0,//default creation flags;
223             &ThreadIDConsumer[j]//返回线程的ID
224         );
225     }
226 
227     //创建消费者线程
228     for(int j =0;j<conNum;j++){
229         ParamOfConsumer[j]=j+1;
230         ThreadHandleOfConsumer[j]=CreateThread(
231             NULL,//default
232             0,//default stack size
233             Consumer,//thread function
234             &ParamOfConsumer[j],//parameter to thread function
235             0,//default creation flags;
236             &ThreadIDConsumer[j]//返回线程的ID
237             );
238     }
239 
240     
241 
242     Sleep(sleeptime);
243     return 0;
244 }

4. 春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。

这道题有比较巧妙的解题算法，参考“编程之美----发帖水王”，代码如下