Question: There is N vehicles. The train label is 1,2, ..., n according to their inbound order. The train station is a stake station, asks how many outbound works? Example: n = 5, 12543 is one. Specifically: 1 inbound, 1 outbound, 2 inbound, 2 outbound, 3, 4, 5 inbound, 5, 4, 3 outbound. I have thought of this problem very early, but there is no good solution. I haven't forgotten this problem. A fun question was found in a few days ago, this is the title of 91 years of the China University of Science: The input of the stack is 123 ... n, the output sequence is A1, A2, ... AN. If AI = N (1 <= i <= n), AI> AI 1> AN determines whether this proposition is correct. I feel that the proposition is correct, but the review information I bought said this proposition is wrong, but I didn't give explanation. If there is no meaning, i = n, i 1 does not make sense, this proposition should be correct. It can be said that this condition is a necessary condition for output sequences. But it is not a fill full condition. The following is a fill condition: for each number in the output sequence, it is descended in descending order after it and the number smaller than it is descended. Certification: Necessity: For any AI and the AM1, AM2, ... ALK, which are smaller than it after it. Because of AM1, AM2, ... AMK You can give an example to verify the proof process: input is 1234, the output is 1423. It is obvious that the 23rd ratio of 23 is small but not descended in descending order. Because 4 in the 23rd stack, 23 has been put in the stack before 4 in the stack and has not yet set, and because 2 is in the stack in 3, then 2 in the stack. The input is 1234, and the output is 1432. We can construct into and out stack: 1 Find out the stack. 4 to 1 large, 234 in the stack, 4 out of the stack. 3 = 4-1, 3 out of the stack, 2 = 3-1, 2 out of the stack. With this fill condition, you can judge whether an output sequence is reasonable. If required, reasonable entry and out stack: You can generate N! Aligned, it is judged. It is also very simple to use it to solve some questions, such as some of the topics below. 1. (North Airlines 2002) If the input sequence of a stack is 1, 2, 3, ..., n, the first one of the output sequences is N, then 第 第 第: 2. (Chinese Academy Software 2000) The input sequence of the stack is (1, 2, 3, 4), and it is impossible to be a stack sequence. A 1243 B 2134 C 1432 D 4312 E 3214 There is still a problem that there is a possible output: the answer is (2N)! / (N! * N!) / (N 1). This is a question in North Post. The answer there is: assuming that the n nodes of the binary tree are numbered from 1 to N, and the prior sequence sequence is 1, 2, ..., n, the sequence sequence obtained by different binary trees is different. Therefore, the number of binary trees in different forms is exactly equal to the number of sequence sequences listed in the presenter sequence, and the process of sequential traversal is essentially a node into the stack and out of the stack. The number of columns 1, 2, .., n are in the order of the arrangement that the stack and out of the stack is exactly the number of the sequence sequences that can be obtained by sequence sequences 1, 2, ..., and n. The number of two-fork trees having a sequence of sequences of 1, 2, ... n. This number is: (2N)! / (N! * N!) / (N 1) It transforms this problem into a tree count problem. If you want to break your head, you can't think of it. If you remember the answer. There is also a problem that outputs all reasonable outlet sequences. As mentioned earlier, you can generate all N! A method of combining the number and then judge. An algorithm for backtracking is also given below. The idea of algorithm is: Place the maximum N, which has n possible locations. Then place N-1, if it is in the left side of N (N is not in the first position), there is no limit, but if it is on the right, only the next position can be used. Because N-1 is a maximum of less than n. Then, N-2 is placed, and if the N-2 is on the left side of N-1, the N-2 is in the left side of its large (n, n-1), and can only be on the right of N-1 at the right side of N-2. The first non-air position. PUTNUMBER (int K, int [] POS) {// Arrange K to a suitable location, assuming K 1, ..., n is already put. POS [i] = k indicates that the i-th position has already been placed, and it is 0 when no placement. IF (k == 0) {// Print out array POS RETURN;} // generates K-placed all positions according to the current POS array value. For K PutiblePos POS [PossiblePos] = K; // K Putnumber (K-1, POS); // Trial POS [POSSIBLEPOS] = 0; // Restable} Generate reasonable arrangements Algorithm: Current K's possible position: k 1 position is empty position and K 1 first non-empty position. The following examples are assumed that n = 5, then 5 can be placed in any position, assuming that at the third (the subscript from 1 to 5) can be placed in 1, 2 or 4. It is assumed that 5 placed at positions 3, 4 at position 2, then 3 can be placed on the left of the left spaces 1 and 4 to the right of the first non-vacuum 4. Here is a complete Java implementation: / ** * Title: * Description: * Copyright: Copyright (c) 2004 * Company: * @ Author not attributable * @version 1.0 * / Import java.util. *; import java.io. *; public class StackPushPop {private int totalCount = 0; public StackPushPop () {} public static void main (String [] args) {StackPushPop stackPushPop = new StackPushPop (); int n = 4; BufferedReader reader = new BufferedReader (new InputStreamReader (System .in)); try {string instr = reader.readline (); n = integer.Valueof (instr) .intValue ();} catch (ioException ex) {} int [] pOS = new int [n]; for INT i = 0; i Public void putnumber (int K, int [] POS) {if (k == 0) {this.totalcount ; for (int i = 0; i } List generatepos (int K, int [] POS) {list result = new arraylist (); int i; for (i = 0; i
