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

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

 

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

①递归法：

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

实现代码：

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;vector
        
          RecursiveGrayCode(int N){    vector
         
           temp;    if (1 == N)    {        temp.push_back("0");        temp.push_back("1");        return temp;    }    vector
          
            temp1 = RecursiveGrayCode(N-1); int size = temp1.size(); int i=0; for (i=0;i
           
            =0;i--) { temp.push_back("1"+temp1[i]); } return temp;}void GrayCode(int N){ if (N<=0) { cout << "Error\n"; return ; } vector
            
              result = RecursiveGrayCode(N); for (int i=0;i
            
           
          
         
        
       
      
     

 

②异或转换：

二进制码-->格雷码

1. 对n位二进制的码字，从右到左，以0到n-1编号；
2. 如果二进制码字的第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

 

格雷码-->二进制码

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

 公式表示：

 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

 

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 
     
       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<
     

 

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
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            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 " <
          <
         
        
       
      
     

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

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            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 " <
          <
         
        
       
      
     

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

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