Seven-based conversion
1 Mutualization of any positive integer
In addition to N
2 Real numbers arbitrarily interacting
Take N
3 negative numbers:
Design a program, read into a base of decimal number and a base of a load, and the decimal number
Converted to this negative number: -r∈ {-2, -3, -4, ....- 20}
Eight all arrangement and combination
1 Arranged: (1..n)
Procedure Solve (dep: integer);
VAR
i: integer;
Begin
IF DEP = N 1 THEN Begin WriteLn (S); EXIT; END;
For i: = 1 to n DO
IF NOT USED [I]
S: = S CHR (i ORD ('0')); used [i]: = true;
Solve (dep 1);
S: = COPY (S, 1, Length (s) -1); used [i]: = false;
END;
END;
2 Combination generation (all options for selecting K numbers in 1..n)
Procedure Solve (dep, pre: integer);
VAR
i: integer;
Begin
IF dep = K 1 THEN Begin Writeln (S); EXIT; END
For i: = 1 to n DO
IF (not used [i]) and (i> pre) THEN BEGIN
S: = S CHR (i ORD ('0')); used [i]: = true;
Solve (DEP 1, I);
S: = COPY (S, 1, Length (s) -1); used [i]: = false;
END;
END;
IX. Find algorithms
1% off
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;
2 tree look
Binary sort tree: The value of each node is greater than the value of the left sub-tree, which is less than the value of the 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; Ten, greedy * Meeting questions (1) N activities have a start time and an end time, only one event is only available. Seeking to meet the most active number. 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. Eleven, backtracking framework 1. N Queens Procedure TRY (i: byte); Var J: byte; Begin IF i = n 1. For j: = 1 to n DO IF a [i] and c [j i] and c [j-i] THEN BEGIN x [i]: = j; a [j]: = false; b [j i]: = false; c [j-i]: = false; TRY (i 1); A [J]: = True; B [i J]: = true; C [J-I]: = TRUE END; END; 2.Hanoi Tower H (n) = 2 * h (N-1) 1 h (1) = 1 Initial all copper sheets are on a column Procedure Hanoi (N, A, B, C: Byte); {Move the nth-block copper sheet from the A column to the C column} Begin IF n = 0. Hanoi (N-1, A, C, B); {Move the above N-1 block from the A column to the B column} Write (N, 'Moved from', A, 'To', C); Hanoi (N-1, B, A, C); {Move the N-1 block on B from the B column to the C column END; The initial copper sheet is distributed on 3 columns, given the target column Goal H [1..3, 0..n] stores three columns, NOW and NOWP's column number and number, H [ I, 0] Save the number on the i-th column. Procedure Move (k, goal: integer; {Move the greatest in position to the target column Goal} Begin IF k = 0. For i: = 1 to 3 do For j: = 1 to han [i, 0] DO IF H [I, J] = K THEN Begin Now: = i; NOWP: = J; END; {Location of K} If NOW <> goal dam {is not moved to the target} Move (K-1, 6-now-goal); {The remaining movement to the unused column} Writeln (K Moved from Now To Goal); H [Goal, H [Goal, 0] 1]: = h [now, NOWP]; H [now, nowP]: = 0; INC (H [Goal, 0]); DEC (H [now, 0]); Move (k-1, goal); {Left movement to the target} END; Twelve, DFS framework Division of NOIP2001 Procedure Work (dep, pre, s: longint); {The entrance is Work (1, 1, n)} {DEP is the number of number DPs of the current test, PRE is the number of previous test places, S is the total number of current remaining can be divided. Var J: longint; Begin IF dep = n Then Begin IF S> = pre. INC (R); END; For J: = pre To S Div 2 Do Work (DEP 1, J, S-J); END; similar: Procedure TRY (dep: integer); VAR i: integer; Begin IF dep = K THEN BEGIN IF TOT> = a [DEP-1] THEN INC (SUM); EXIT; For i: = a [DEP-1] to Tot Div 2 Do Begin a [dep]: = i; dec (TOT, I); TRY (DEP 1); INC (TOT, I); END; End; {TRY} Thirteen, BFS framework IOI94 room problem HEAD: = 1; tail: = 0; While Tail INC; TAIL Fork: = 1 to n DO IF K Direction Extension THEN Begin INC; HEAD; List [head] .x: = list [tail] .x DX [k]; {expand new node list [head]} List [head] .y: = list [tail] .y dy [k]; Handling new nodes list [head]; END; END; Fifteen, data structure related algorithm 1. Link list positioning function LOC (i: integer): Pointer; {look for pointers in the i-th sideworth in the list} Procedure Loc (L: Linklist; i: integer): Pointer; VAR P: POINTER; J: integer; Begin P: = L.HEAD; J: = 0; IF (i> = 1) and (i <= l.len) THEN While j
Loc: = P; END; 2. Single-link table insertion operation Procedure INSERT (L: Linklist; i: integer; x: datatype); VAR P, Q: POINTER; Begin P: = LOC (L, I); NEW (q); Q ^ .data: = x; Q ^ .next: = p ^ .next; p ^ .next: = q; inc (L.LEN); END; 3. Single-link table deletion Procedure delete (l: linklist; i: integer); VAR P, Q: POINTER; Begin P: = LOC (L, I-1); Q: = P ^ .next; p ^ .next: = q ^ .next; Dispose (Q); Dec (L.1); END; 4. Insert operation of the double-linked list (insertion of new node Q) P: = LOC (L, I); NEW (q); Q ^ .data: = x; Q ^ .pre: = P; Q ^ .next: = p ^ .next; p ^ .next: = q; Q ^ .next ^ .pre: = = q; 5. Double-linked list of deletions P: = LOC (L, I); {p is the node to delete} p ^ .pre ^ .next: = p ^ .next; P ^ .next ^ .pre: = p ^ .pre; Dispose (P);
