Niuke real problem programming - Day10

Compile environment ：c++

1、 Generate Gray code

describe

In the coding of a set of numbers , If any two adjacent codes have only one binary number different , This code is called gray code (Gray Code), Please write a function , Use recursive method to generate N Bit gray code .

Given an integer n, Please return n Bit gray code , The order is from 0 Start .

Algorithmic thought ：

According to the characteristics of gray code , It's not hard to find out ,N Bit gray code is in N-1 Add 1 Bit 0 perhaps 1, And the number is 2 Of N individual ： front 2 Of N-1 And after 2 Of N-1 The first N-1 Bit symmetry , All are N-1 Bit generated gray code , the N-1 Bit generated gray code +0/1 Output in positive and negative order . According to this design recursive function getGray, When N by 1 when , Gray code is 0 and 1. Note that the output of the topic just returns to the previous N Gray code generated by sub recursion .

The code part implements ：

2、zj2 Programming questions 1

describe

There are three teams , Each team number is team 1, The team 2, The team 3, The three teams need to play a total of n game . Now it's over k game , Every game can't be tied , Win a game and get a point , If you lose, you can't lose points . Known team 1 And the team 2 There is a difference in the score between d1 branch , The team 2 And the team 3 There is a difference in the score between d2 branch , You can choose two teams to play in each game . Please, if you finish the last (n-k) game , Is it possible that the scores of the three teams are even .



Algorithmic thought ：

    The title just gives the difference , But there is no positive or negative difference , Therefore, it can be divided into four situations to discuss respectively . At the same time, the scores of the three teams are added =k,ab The difference is +-d1,bc The difference is +-d2 Equation thinking to divide the situation, exhaustive . When a<0,b<0,c<0;n No 3 A multiple of the , It must not meet the conditions . classification 1:a<b<c when , here a+b+c=a+(a+d1)+(a+d1+d2)=3x1+2d1+d2=k, Yes x1=（k-2*d1-d2）/3, obviously , In order to catch up, we need to meet the remaining games n-k Greater than or equal to （2*d2+d1）, At the same time, the extra games should be allocated to three teams at the same time . The other three cases are the same , Press d1d2 Positive and negative classification discussion .

The code part implements ：

3、DNA Sequence

describe ：

Niuniu has another task from biological researchers , Niuniu needs to help scientific researchers from DNA Sequence s Find the shortest that does not appear in DNA Sequence s Medium DNA Length of segment .
for example :s = AGGTCTA

The sequence contains all elements with a length of 1 Of ('A','C','G','T') fragment , But the length is 2 Of does not contain all , For example, the sequence does not contain "AA", So the output 2.

notes ： The length is 2 All DNA The clip has "AA"、"AC"、"AG"、"AT"、"CA"、"CC"、"CG"、"CT"、"GA"、"GC"、"GG"、"GT"、"TA"、"TC"、"TG" and "TT", common 16 Kind of .

Algorithmic thought ：

    make the best of c++ Library function , Received s After the string , From the length to 1 Start intercepting substrings , Then put it into a set , Because the element key is unique in the set , So the insert operation first checks whether the given key already exists in the collection , It's equivalent to removing weight . At this time, you only need to judge whether the number of elements in the set meets the inclusion length of i All of the DNA fragment , namely size Be greater than 4 Of i Power .

The code part implements ：