16. Find algorithms
Folding half lookup
Function Binsearch (K: KeyType): Integer;
Var Low, HIG, MID: Inteder
Begin
Low: = 1; HIG: = N;
MID: = (low HIG) DIV 2;
While (a [mid] .key <> k) and (low <= HIG) DO Begin
IF a [MID] .key> K Then Hig: = MID-1
Else Low: = MID 1;
MID: = (low HIG) DIV 2;
END;
If low> hig kil: = 0;
Binsearch: = MID;
END;
Tree look
Binary Sort Tree: The value of each node is greater than the value of its left sub-tree, which is less than the value of its right tree.
Look up
Function Treesrh (K: KeyType): Pointer;
VAR Q: POINTER;
Begin
q: = root;
While (q <> nil) and (q ^ .key <> K) DO
IF K Else Q: = Q ^ .right; Treesrh: = q; END; 17. KMP algorithm 18. greedy * Meeting questions (1) N An event has a start time and an end time, only one event is only in one activity, and the maximum number of activities is satisfied. Solution: Sort by the end time of each activity, the top priority is satisfied. (2) The meeting room has the least free time. (3) Every customer has a wish to pay for maximum profit. (4) Conference rooms in total R, iile I need to use I meeting rooms, the cost is the same, and ask for maximum profit. Appendix 1 Common Skills 1. Bring a median N (N is not more than 100 natural numbers), and the natural number of Mongolia in my country has N (X1, Y1), P2 (X2, Y2), ... pn (xn, yn), corresponding to Weight Wi, now You are asked to find a point P (XP, YP) on the savanna, so that the P point to any point PI is the sum of the sum of the accumulation of the Wi and Wi. Institutional D = W1 * D1 W2 * D2 ... WI * DI ... WN * DN has a minimum Conclusion: The two directions of X and Y is solved by the median, and converted to one-dimensional. Set the best point P to point K, then point K satisfaction: If W is the sum of the sum of the rolling distance of the remaining points, then SiGema (i = 1 to k-1) wi * di <= W / 2 SiGema (i = k 1 to n) Wi * di <= W / 2 At the same time, the point K of the above two is satisfied is the median. 2. Ask the maximum and the continuous sequence in a sequence Begin Maxsum: = - maxlongint; SUM: = 0; For i: = 1 to n Do Begin INC (SUM, DATA [I]); If SUM> MaxSum the Maxsum: = SUM; If SUM <0 THEN SUM: = 0; END; Writeln (MaxSum); END;
