Fourth day: 9/26/2003
enumerate:
Backpack problem:
Enumeration strategy: 1) Possible solution: 2 ^ n
2) Judging each program.
Enumeration method General process:
While (there are other possible plans)
{According to some order;
Test scheme;
IF (solution)
Save scheme;
}
}
Enumeration strategy:
Example: P6 = 6!
MIN: 123456
MAX: 654321
A1A2A3A4A5A6 =>? (next arrangement) =>?
Such as: 312654, under the situation => 314256
Recursion
The recursive algorithm usually has such a feature: to solve the problem of N, try to break down into some smaller problems, and then easily construct the solution required for topics from these smaller problems. Smaller problems also use the same method to decompose smaller problems, construct the solution of scale of size, so continuous decomposition and synthesis, and can always decompose to the easiest to Directly Solution.
Therefore, when the title of the algorithm is dected, pay attention to the following points:
1) Find the end condition of the recursive call or continue to recursively call the call.
2) If you find a way to reduce the size of the handling object or the decrease in elements.
3) Since recursive calls can be understood as multiple calls of the same name function, the principle of function call is a layer of call, and a layer is returned. Therefore, it is necessary to pay attention to understand the role of the next statement that is returned. In some simple recursive algorithms, there is often no need to consider the returned statement processing after handset. In some complex recursive algorithms, it is necessary to consider recursion calls returned to the statement processing and further recursive calls.
4) When reading a recursive program or writing a recursive program, it must be probably the role of the recursive function, so that it is easy to understand the functionality of the entire function and know where to write a recursive call statement. Of course, when the rule of the algorithm is required, it also needs to be classified. Internal variables and external variables in the function.
Manifestations:
l Definition is recursive (binary tree, binary sort tree)
l The storage structure is recursive (binary tree, linked list, array)
l The algorithm derived from the first two forms is recursive.
General process: Function (Variable List))
{IF (small scale, known) Return solution;
Else {
Divide questions into several parts;
Some parts can be directly obtained;
And the other part (the size of N-1) is obtained;
}
}
Example 1: Seeking a maximum element in a linked list.
Have you ever thought of this problem with recursive?
Non-recursive methods, everyone should you?
Max (nodetype * h) {
Nodetype * p;
Nodetype * q; // store node containing the maximum value
INT max = 0;
P = H;
While (p! = Null) {
IF (Max
Max = p-> data;
Q = P;
}
P = P-> next;
}
Return Q;
}
The following is true, 嘻嘻 嘻 ~~~
* max (nodetype * h) {
Nodetype * TEMP;
Temp = max (h-> next);
IF (H-> Data> Temp-> DATA)
Return H;
Else
Return Temp;
}
Everyone thinks about this algorithm: see the average of all the data (I haven't tried), I don't have to lazy, try again!
Retrinted programmer exam Type: 1) is some operations of the list (for example, the average of the above)
2) Two-forked trees (traversal, etc.)
Example 2. Judging whether the array element is incremented
INT JIDGE (int A [], int N) {
IF (n == 1) Return 1;
Else
IF (a [0]> a [1]) RETURN 0;
ELSE RETURN JIDGE (A 1, N-1);
}
Example 3. Ask the height of the binary tree (according to the recursive properties of the binary tree: (left subtree) root (right tree))
INT Depth (NodeType * root) {
IF (root == null)
Return 0;
Else {
H1 = depth (root-> lch);
H2 = depth (root-> rch); Return Max (H1, H2) 1;
}
I think I want to ask for the bifurcation of the bifurcation (similar to the above example)
Example 4. It is known to traversal and sequential traversal, and ask for binary tree.
Set one two-fork tree:
Senior order S: E D f B A g J H C i
^ START1 ^ j ^ end1
Rear sequence T: e f D b J h g i c a
^ START2 ^ END2
Node * crete (char * s, char * t, int start1, int start2, int end1, int end2)
{IF (start1> end1) Return null; // Return condition
Root = (node *) malloc (sizeof (node));
root-> DATA = T [end2];
Locate the position of t [end2] in j
ROOT-> LCH = Create (S, T, S1, J-1, Start1, J START2-START1-1);
ROOT-> rCH = CREATE (S, T, J 1, END1, J START2-START1, END2-1);
Return root;
}
Example 5. Combination problem
N Number: (1, 2, 3, 4, ... n) Request all combinations from the R rats.
Set n = 5, r = 3;
Recurrent thinking: First fix one 5 (selected from the other four)
5, 4 (choose one from the other three)
5, 4, 3 (zero from the other two)
That is, all combinations of R-1 number from N-1 number from N-1
N-1 Number of R-2 numbers from N-2 Number
.
.
.
program:
Void Combire (int N, int R) {
For (k = n; k> = n r-1; k -) {
a [r] = k;
IF (r == 0) Print A array (indicating finding a solution);
Else Combire (N-1, R-1);
}
}
