Tcr
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
More details
- Words: 25,215
- Pages: 34
INHALTSVERZEICHNIS
1
Inhaltsverzeichnis 1 Suchen ¨ und ternare ¨ Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Binare 1.2 N-tes Element (Select) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Teilstringsuche (Knuth-Morris-Pratt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 1 1 1
2 Parsen 2.1 Rekursiver Parser fur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ arithmetische Ausdrucke ¨ 2.2 Umwandlung von Infix- nach Postfix-Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Bottom-up-Parser nach Cocke, Younger und Kasami . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 2 2 3
3 Arithmetik und Algebra 3.1 Bigints . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Schnelles Potenzieren . . . . . . . . . . . . . . . . . . 3.3 Endliche Summation . . . . . . . . . . . . . . . . . . . 3.4 Matrixmultiplikation (ikj, Strassen) . . . . . . . . . . . 3.5 Lineare Gleichungssysteme (LGS) und Determinanten 3.6 Polynome . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
4 . 4 . 8 . 8 . 8 . 9 . 10
4 Rekurrenzen, Kombinatorik und DP 4.1 Lineare Rekurrenzen (z.B. Fibonacci) . . . . . . . 4.2 Urnenmodelle . . . . . . . . . . . . . . . . . . . . . 4.3 Binomialkoeffizienten . . . . . . . . . . . . . . . . ¨ 4.4 Haufige Rekurrenzen in der Kombinatorik . . . . . ¨ 4.5 Langste Teilfolge (LCS, LIS) . . . . . . . . . . . . . 4.6 SUBSET-SUM (KNAPSACK nur mit Gewichten) 4.7 Nim (bisschen Spieltheorie) . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
10 10 11 11 11 11 12 12
5 Zahlentheorie 5.1 GGT und Kongruenzen (Euklid) . . . . . 5.2 Chinesischer Restsatz . . . . . . . . . . 5.3 Eulersche Phi-Funktion . . . . . . . . . 5.4 Primzahlen (Erathostenes, Miller-Rabin)
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
12 12 13 13 13
6 Graphen 6.1 Topologische Sortierung . . . . . . . . . . . . . . . . . . . ¨ (Tarjan) . 6.2 Artikulationspunkte, Brucken und Bikonnektivitat ¨ 6.3 Starke Zusammenhangskomponenten (Tarjan) . . . . . . 6.4 Eulerscher Kreis . . . . . . . . . . . . . . . . . . . . . . . 6.5 Kurzeste Pfade (Dijkstra, Floyd-Warshall, Bellman-Ford) . ¨ 6.6 Minimaler Spannbaum (Kruskal, Prim) . . . . . . . . . . . 6.7 Bipartites Matching . . . . . . . . . . . . . . . . . . . . . . 6.8 Maximaler Fluss (Ford-Fulkerson) . . . . . . . . . . . . . 6.9 Min-Cost-Max-Flow . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
14 14 15 16 16 16 18 19 19 20
7 Geometrie 7.1 Geraden und Punkte . . . . . . . . . . . . . 7.2 Dreiecke und Liniensegmente . . . . . . . . 7.3 Kreise . . . . . . . . . . . . . . . . . . . . . 7.4 Polygone . . . . . . . . . . . . . . . . . . . 7.5 Rasterung von Linien/Kreisen (Bresenham)
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
22 22 23 24 25 28
8 Datenstrukturen 8.1 Disjunkte Mengen (Union-Find) . . . . 8.2 Heap . . . . . . . . . . . . . . . . . . . 8.3 Fenwick-Baum . . . . . . . . . . . . . 8.4 Trie . . . . . . . . . . . . . . . . . . . . ¨ 8.5 Balancierter binarer Suchbaum (AVL)
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
29 29 29 29 30 31
. . . . .
. . . .
. . . . .
. . . .
. . . . .
. . . .
. . . .
. . . .
. . . .
1
SUCHEN
1 1.1
2
Suchen ¨ und ternare ¨ Suche Binare
¨ Wenn moglich, lower bound oder upper bound verwenden. ¨ Wenn nicht, geht der generelle Algorithmus folgendermaßen: Man braucht ein Pradikat (z.B. x < 42, das irgendwo in dieser Liste von true auf false springt. Man setzt seine beiden Anfangsindizes (z.B. lo und hi ) auf Werte, ¨ von denen man sicher weiß, dass das Pradikat an dieses Stellen den jeweiligen Wert annimmt. Achtung: Bei Suche in einem Array kann das heißen, die beiden Startindizes außerhalb des Arrays zu setzen, z.B. lo = −1 und ¨ hi = N. Dann wertet man immer das Pradikat beim arithmetischen Mittel der beiden Indizes aus und setzt je nach Wert entweder lo oder hi auf das Mittel. Solange wiederholen, bis sich diese beiden Indizes nur noch um eins ¨ ¨ unterscheiden, dann zeigt lo auf den hochsten Wert, wo das Pradikat noch true ergibt und hi auf das niedrigste false. ¨ Suche eignet sich fur Die ternare ¨ bitonische (auf einem Abschnitt monoton steigende, auf dem anderen monoton fallende) Funktionen. Immer bei einem und zwei Dritteln des aktuellen Intervalls auswerten und dann nur einen der beiden aktuellen Indizes anpassen.
1.2
N-tes Element (Select)
1 2
# include # include
3 4 5 6 7 8 9 10 11
/ / o r d n e t [ a , b ) so um, dass a [ n ] das g l e i c h e Element e n t h a e l t , / / wie wenn [ a , b ) s o r t i e r t waere , und g i b t a [ n ] zurueck / / L a u f z e i t i n O( b − a ) g a r a n t i e r t int select ( int ∗ a , int ∗ b , int n) { i f ( b − a < 10000) { nth element ( a , a + n , b ) ; return a [ n ] ; }
12
int ∗ q = a; f o r ( i n t ∗p = a ; b − p >= 5 ; p += 5 ) { nth element ( p , p + 2 , p + 5 ) ; swap ( ∗ q++ , p [ 2 ] ) ; }
13 14 15 16 17 18
q = p a r t i t i o n ( a , b , bind2nd ( l e s s ( ) , s e l e c t ( a , q , ( q − a ) / 2 ) ) ) ; return n < q − a ? s e l e c t ( a , q , n ) : s e l e c t ( q , b , n − ( q − a ) ) ;
19 20 21
}
1.3
Teilstringsuche (Knuth-Morris-Pratt)
1 2
void KMP( char ∗x , i n t m, char ∗y , i n t n ) { i n t i , j , kmpNext [m+ 1 ] ;
3 4 5 6 7 8 9 10 11 12 13 14 15 16
/ ∗ P r e p r o ce s si n g ∗ / i = 0; j = kmpNext [ 0 ] = −1; while ( i < m) { while ( j > −1 && x [ i ] ! = x [ j ] ) j = kmpNext [ j ] ; i ++; j ++; i f ( x [ i ] == x [ j ] ) kmpNext [ i ] = kmpNext [ j ] ; else kmpNext [ i ] = j ; }
17 18 19
/ ∗ Searching ∗ / i = j = 0;
2
PARSEN
while ( j < n ) { while ( i > −1 && x [ i ] ! = y [ j ] ) i = kmpNext [ i ] ; i ++; j ++; i f ( i >= m) { p r i n t f ( ”%d\n ” , j − i ) ; i = kmpNext [ i ] ; } }
20 21 22 23 24 25 26 27 28 29 30
}
2 2.1
Parsen Rekursiver Parser fur ¨ arithmetische Ausdrucke ¨
1
3
# include
2 3 4
/ / e r s t p t r setzen , dann A u f r u f von parse ( ) char ∗ p t r ;
5 6 7 8
double atom ( ) ; double prod ( ) ; double parse ( ) ;
9 10 11 12 13 14 15 16 17 18
double atom ( ) { double r e s ; i f ( ∗ p t r == ’ ( ’ ) { ++ p t r ; r e s = parse ( ) ; ++ p t r ; } else r e s = s t r t o d ( p t r , & p t r ) ; return res ; }
19 20 21 22 23 24 25
double prod ( ) { double r e s = atom ( ) ; while ( ∗ p t r == ’ ∗ ’ | | ∗ p t r == ’ / ’ ) r e s = ∗ p t r ++ == ’ ∗ ’ ? r e s ∗ atom ( ) : r e s / atom ( ) ; return res ; }
26 27 28 29 30 31 32
double parse ( ) { double r e s = prod ( ) ; while ( ∗ p t r == ’ + ’ | | ∗ p t r == ’− ’ ) r e s = ∗ p t r ++ == ’ + ’ ? r e s + prod ( ) : r e s − prod ( ) ; return res ; }
2.2
Umwandlung von Infix- nach Postfix-Notation
1
# include <stack>
2 3 4 5 6
i n t p r e c v a l ( char c ) { i f ( c == ’ + ’ | | c == ’− ’ ) r e t u r n 1 ; else r e t u r n 2 ; }
7 8 9 10
bool p r e c I s S m a l l e r ( char op1 , char op2 ) { r e t u r n p r e c v a l ( op1 ) < p r e c v a l ( op2 ) ; }
2
PARSEN
4
11 12 13 14
void parse ( char ∗ i n f i x , char ∗ p o s t f i x ) { stack
15
while ( ∗ i n f i x ! = 0 ) { switch ( ∗ i n f i x ) { case ’ ( ’ : s . push ( ’ ( ’ ) ; break ; case ’ ) ’ : while ( ! s . empty ( ) ) { c = s . top ( ) ; s . pop ( ) ; i f ( c == ’ ( ’ ) break ; ∗ p o s t f i x ++ = c ; } break ; case ’ + ’ : case ’− ’ : case ’ ∗ ’ : case ’ / ’ : while ( ! s . empty ( ) ) { c = s . top ( ) ; i f ( c == ’ ( ’ ) break ; else i f ( ! p r e c I s S m a l l e r ( c , ∗ i n f i x ) ) { s . pop ( ) ; ∗ p o s t f i x ++ = c ; } else break ; } s . push ( ∗ i n f i x ) ; break ; default : ∗ p o s t f i x ++ = ∗ i n f i x ; break ; } ++ i n f i x ; }
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
while ( ! s . empty ( ) ) { ∗ p o s t f i x ++ = s . t o p ( ) ; s . pop ( ) ; }
47 48 49 50 51
∗ p o s t f i x = 0;
52 53
}
2.3
Bottom-up-Parser nach Cocke, Younger und Kasami
Eine kontextfreie Grammatik ist in Chomsky-Normalform, wenn jede Produktion eine der folgenden Formen hat: S → ε,
A → a,
A → BC
Um Grammatik in CNF zu bringen, folgende Schritte: • Jedem Terminal ein Nichtterminal zuordnen, Produktion Xa → a einfugen. ¨ • Wenn wo mehr als zwei Nichtterminale stehen, immer zwei zu einem neuen Symbol zusammenfassen und entsprechende Produktion einfugen. ¨ • ε-Produktionen entfernen. • Kettenproduktionen (A → B entfernen, indem B nacheinander durch alle seine Folgeprodukte ersetzt wird. 1
# define MAX 1024
2 3 4
# define TERMINALS 7 # define NONTERMINALS 14
3
ARITHMETIK UND ALGEBRA
5
5 6
/ / # d e f i n e A 1 , # d e f i n e MOD 2 , # d e f i n e BA 4 , usw f u e r a l l e N i c h t t e r m i n a l e
7 8
i n t nonterminal map [ NONTERMINALS ] [ NONTERMINALS ] , words , symbol [MAX ] [ MAX ] ;
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
/ / am Anfang i n symbol [ i ] [ i ] d i e Maske des N i c h t t e r m i n a l s des i −t e n Wortes e i n t r a g e n bool cyk ( ) { i n t i , j , k , m, n ; f o r ( i = 1 ; i < words ; ++ i ) f o r ( j = 0 ; j + i < words ; ++ j ) { symbol [ j ] [ j + i ] = 0 ; f o r ( k = 0 ; k < i ; ++k ) f o r (m = 0 ; m < NONTERMINALS ; ++m) f o r ( n = 0 ; n < NONTERMINALS ; ++n ) i f ( ( symbol [ j ] [ j + k ] & ( 1 << m) ) && ( symbol [ j + k + 1 ] [ j + i ] & ( 1 << n ) ) ) symbol [ j ] [ j + i ] | = nonterminal map [m] [ n ] ; } r e t u r n words > 0 && ( symbol [ 0 ] [ words − 1 ] & SENTENCE ) ; }
3
Arithmetik und Algebra
3.1
Bigints
3.1.1 1 2
Bigints in C++
# include
3 4 5 6
# define LEN 128 # define DPI 9 # define MOD 1000000000
7 8
typedef i n t bignum [ LEN ] ;
9 10 11 12 13 14
/ ∗ alpha = i n t e g ; ∗ / void s e t i n t ( bignum alpha , i n t i n t e g ) { alpha [ 0 ] = 2 ; alpha [ 1 ] = i n t e g ; }
15 16 17 18 19
/ ∗ alpha = a t o i ( s t r ) ; ∗ / void s e t s t r ( bignum alpha , char ∗ s t r ) { char ∗ p t r = s t r + s t r l e n ( s t r ) ; i n t power10 , d i g i t s = DPI ;
20
alpha [ 0 ] = 1 ; while ( p t r −− ! = s t r ) { i f ( d i g i t s == DPI ) { alpha [ alpha [ 0 ] + + ] = 0 ; power10 = 1 ; d i g i t s = 0; }
21 22 23 24 25 26 27 28
alpha [ alpha [ 0 ] − 1 ] += ( ∗ p t r − ’ 0 ’ ) ∗ power10 ; power10 ∗= 1 0 ; ++ d i g i t s ;
29 30 31
}
32 33
while ( alpha [ 0 ] > 2 && alpha [ alpha [ 0 ] − 1 ] == 0 ) −−alpha [ 0 ] ;
34 35
}
36 37
/ ∗ alpha = beta ; ∗ /
3
38 39
ARITHMETIK UND ALGEBRA
void s e t b i g ( bignum alpha , const bignum beta ) { int i ;
40
f o r ( i = 0 ; i < beta [ 0 ] ; ++ i ) { alpha [ i ] = beta [ i ] ; }
41 42 43 44
}
45 46 47 48
/ ∗ alpha += i n t e g ; ∗ / void a d d i n t ( bignum alpha , i n t i n t e g ) { int i = 1;
49
while ( i n t e g > 0 ) { i f ( i < alpha [ 0 ] ) i n t e g += alpha [ i ] ; alpha [ i ++] = i n t e g % MOD; i n t e g / = MOD; }
50 51 52 53 54 55
i f ( i > alpha [ 0 ] ) alpha [ 0 ] = i ;
56 57
}
58 59 60 61
/ ∗ alpha += beta ; ∗ / void a d d b i g ( bignum alpha , const bignum beta ) { int carry = 0 , i = 1 , j = 1;
62
while ( c a r r y > 0 | | j < beta [ 0 ] ) { i f ( i < alpha [ 0 ] ) c a r r y += alpha [ i ] ; i f ( j < beta [ 0 ] ) c a r r y += beta [ j + + ] ; alpha [ i ++] = c a r r y % MOD; c a r r y / = MOD; }
63 64 65 66 67 68 69
i f ( i > alpha [ 0 ] ) alpha [ 0 ] = i ;
70 71
}
72 73 74 75
/ ∗ alpha −= i n t e g ; ∗ / void s u b i n t ( bignum alpha , i n t i n t e g ) { int i = 1;
76
i n t e g = −i n t e g ; while ( i n t e g < 0 ) { i n t e g += alpha [ i ] ; i f ( i n t e g < 0 ) i n t e g += 2 ∗ MOD; alpha [ i ++] = i n t e g % MOD; i n t e g / = −MOD; }
77 78 79 80 81 82 83 84
while ( alpha [ 0 ] > 2 && alpha [ alpha [ 0 ] − 1 ] == 0 ) −−alpha [ 0 ] ;
85 86
}
87 88 89 90
/ ∗ alpha −= beta ; ∗ / void s u b b i g ( bignum alpha , const bignum beta ) { int carry = 0 , i = 1 , j = 1;
91
while ( c a r r y < 0 | | j < beta [ 0 ] ) { c a r r y += alpha [ i ] ; i f ( j < beta [ 0 ] ) c a r r y −= beta [ j + + ] ; i f ( c a r r y < 0 ) c a r r y += 2 ∗ MOD; alpha [ i ++] = c a r r y % MOD; c a r r y / = −MOD; }
92 93 94 95 96 97 98 99
while ( alpha [ 0 ] > 2 && alpha [ alpha [ 0 ] − 1 ] == 0 ) −−alpha [ 0 ] ;
100 101
}
102 103
/ ∗ alpha ∗= i n t e g ; ∗ /
6
3
104 105 106
ARITHMETIK UND ALGEBRA
void m u l i n t ( bignum alpha , long long i n t e g ) { long long c a r r y = 0 ; int i = 1;
107
while ( c a r r y > 0 | | i < alpha [ 0 ] ) { i f ( i < alpha [ 0 ] ) c a r r y += alpha [ i ] ∗ i n t e g ; alpha [ i ++] = c a r r y % MOD; c a r r y / = MOD; }
108 109 110 111 112 113
i f ( i > alpha [ 0 ] ) alpha [ 0 ] = i ;
114 115
}
116 117 118 119 120
/ ∗ alpha += beta ∗ gamma ; ∗ / void mul add ( bignum alpha , const bignum beta , const bignum gamma) { long long i n t e g , c a r r y ; int i , j , k = 1;
121
while ( k < gamma [ 0 ] ) { i n t e g = gamma [ k ] ; carry = 0; i = k ++; j = 1;
122 123 124 125 126 127
while ( c a r r y > 0 | | j < beta [ 0 ] ) { i f ( i < alpha [ 0 ] ) c a r r y += alpha [ i ] ; i f ( j < beta [ 0 ] ) c a r r y += beta [ j ++] ∗ i n t e g ; alpha [ i ++] = c a r r y % MOD; c a r r y / = MOD; }
128 129 130 131 132 133 134
i f ( i > alpha [ 0 ] ) alpha [ 0 ] = i ;
135
}
136 137
while ( alpha [ 0 ] > 2 && alpha [ alpha [ 0 ] − 1 ] == 0 ) −−alpha [ 0 ] ;
138 139
}
140 141 142 143
/ ∗ alpha ∗= beta ; ∗ / void m u l b i g ( bignum alpha , const bignum beta ) { bignum gamma ;
144
s e t i n t (gamma, 0 ) ; mul add (gamma, alpha , beta ) ; s e t b i g ( alpha , gamma ) ;
145 146 147 148
}
149 150 151 152 153
/ ∗ alpha / = i n t e g ; r e t u r n alpha % i n t e g ; ∗ / i n t d i v i n t ( bignum alpha , i n t i n t e g ) { long long c a r r y = 0 ; i n t i = alpha [ 0 ] ;
154
while ( i > 1 ) { c a r r y ∗= MOD; c a r r y += alpha[−− i ] ; alpha [ i ] = c a r r y / i n t e g ; c a r r y %= i n t e g ; }
155 156 157 158 159 160 161
while ( alpha [ 0 ] > 2 && alpha [ alpha [ 0 ] − 1 ] == 0 ) −−alpha [ 0 ] ;
162 163
return carry ;
164 165
}
166 167 168 169
/ ∗ alpha = pow ( alpha , i n t e g ) ; ∗ / void p o w i n t ( bignum alpha , i n t i n t e g ) { bignum square [ 2 ] , answer [ 2 ] ;
7
3
ARITHMETIK UND ALGEBRA
8
i n t square idx = 0 , answer idx = 0;
170 171
s e t i n t ( answer [ a n s w e r i d x ] , 1 ) ; s e t b i g ( square [ s q u a r e i d x ] , alpha ) ;
172 173 174
while ( i n t e g > 0 ) { i f (( integ & 1)) { s e t i n t ( answer [ a n s w e r i d x ˆ 1 ] , 0 ) ; mul add ( answer [ a n s w e r i d x ˆ 1 ] , answer [ a n s w e r i d x ] , square [ s q u a r e i d x ] ) ; a n s w e r i d x ˆ= 1 ; } i n t e g >>= 1 ;
175 176 177 178 179 180 181 182
s e t i n t ( square [ s q u a r e i d x ˆ 1 ] , 0 ) ; mul add ( square [ s q u a r e i d x ˆ 1 ] , square [ s q u a r e i d x ] , square [ s q u a r e i d x ] ) ; s q u a r e i d x ˆ= 1 ;
183 184 185
}
186 187
s e t b i g ( alpha , answer [ a n s w e r i d x ] ) ;
188 189
}
190 191 192 193
/ ∗ c o u t << alpha ; ∗ / void p r i n t b i g ( bignum alpha ) { i n t i = alpha [ 0 ] − 1 ;
194
c o u t << alpha [ i ] ; cout . f i l l ( ’ 0 ’ ) ; while ( i −− > 1 ) { c o u t . w i d t h ( DPI ) ; c o u t << alpha [ i ] ; } cout . f i l l ( ) ;
195 196 197 198 199 200 201 202
}
3.1.2
Bigints in Java
1 2 3 4
import import import import
java . lang . ∗ ; java . u t i l . ∗ ; java . io . ∗ ; j a v a . math . ∗ ;
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
class Main { f i n a l s t a t i c i n t MAX = 255; static BigInteger [ ] fac ; s t a t i c void i n i t F a c ( ) { B i g I n t e g e r b i = B i g I n t e g e r .ONE; f a c = new B i g I n t e g e r [MAX + 1 ] ; f a c [ 0 ] = B i g I n t e g e r .ONE; f o r ( i n t i = 1 ; i <= MAX; ++ i ) { fac [ i ] = fac [ i − 1 ] . m u l t i p l y ( bi ) ; b i = b i . add ( B i g I n t e g e r .ONE ) ; } } public s t a t i c void main ( S t r i n g [ ] args ) { Scanner sc = new Scanner (new BufferedReader (new InputStreamReader ( System . i n ) ) ) ; while ( sc . h a s N e x t I n t ( ) ) { i n t t o t a l = sc . n e x t I n t ( ) ; B i g I n t e g e r rank = sc . n e x t B i g I n t e g e r ( ) ; } } }
3
ARITHMETIK UND ALGEBRA
3.2
9
Schnelles Potenzieren
1 2
int fast exp ( int a , int b) { int r = 1;
3
while ( b > 0 ) { i f ( ( b & 1 ) ) r ∗= a ; b >>= 1 ; a ∗= a ; }
4 5 6 7 8 9
return r ;
10 11
}
3.3
Endliche Summation
Def. Pochhammer-Symbol: nk = n · (n − 1) · . . . · (n − k + 1). Bei Summation uber Polynome, drucke die normalen ¨ ¨ Potenzen in dieser Schreibweise aus, z.B. 3n2 − n = 3n2 + 2n1 . Dann wie in der Analysis integrieren, ergibt eine Art Stammfunktion: X 3n2 + 2n1 = n3 + n2 Wenn man das Polynom von 1, . . . , N summiert, muss man die Stammfunktion an der Stelle N + 1 und 1 auswerten: N X +1 3n2 + 2n1 = n3 + n2 |N = (N + 1)3 + (N + 1)2 = (N + 1)N 2 1 n=1
Das Gegenteil vomP Summationsoperator entspricht 2n , also 2n = ∆2n = 2n .
3.4 3.4.1
P
ist der Differenzenoperator ∆f (x) = f (x + 1) − f (x). Der e-Funktion
Matrixmultiplikation (ikj, Strassen) Cachefreundliche Matrixmultiplikation
1 2 3 4
f o r ( i = 0 ; i < SIZE ; i ++) f o r ( k = 0 ; k < SIZE ; k ++) f o r ( j = 0 ; j < SIZE ; j ++) c [ i ] [ j ] += a [ i ] [ k ] ∗ b [ k ] [ j ] ;
3.4.2
Algorithmus von Strassen
r t
s a = u c
b e d g
f h
rclp1
=
a(f − h)
(1)
p2
=
(a + b)h
(2)
p3
=
(c + d)e
(3)
p4
=
d(g − e)
(4)
p5
=
(a + d)(e + h)
(5)
p6
=
(b − d)(g + h)
(6)
p7
=
(a − c)(e + f )
(7)
Dann: r = p5 + p4 − p2 + p6 ,
s = p1 + p2 ,
t = p3 + p4 ,
u = p5 + p1 − p3 − p7
3
ARITHMETIK UND ALGEBRA
3.5
10
Lineare Gleichungssysteme (LGS) und Determinanten
3.5.1
Gauß-Algorithmus
1
# define EPSILON 0.0000001
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
bool LGS( double ∗∗ A , double∗ b , i n t m, i n t n , double∗ r e s ) { i n t b l a [ n ] ; / / Werte von 0 . .m−1 memset ( bla , −1 ,n∗ s i z e o f ( i n t ) ) ; i n t x , y , x2 , y2 ; f o r ( y =0; y<m; y ++){ f o r ( x = 0 ; ( x
30
memset ( res , 0 , n∗ s i z e o f ( double ) ) ; f o r ( x =0; x
31 32 33 34 35 36 37
}
3.5.2
LR-Zerlegung, Determinanten
1
const i n t MAX = 4 2 ;
2 3 4
void l r ( double a [MAX ] [ MAX] , i n t n ) { int i , j , k ;
5
f o r ( i = 0 ; i < n ; ++ i ) { f o r ( k = 0 ; k < i ; ++k ) a [ i f o r ( j = i + 1 ; j < n ; ++ j ) f o r ( k = 0 ; k < i ; ++k ) a [ j ] [ i ] /= a [ i ] [ i ] ; f o r ( k = 0 ; k < i ; ++k ) } }
6 7 8 9 10 11 12 13 14
] [ i ] −= a [ i ] [ k ] ∗ a [ k ] [ i ] ; { a [ j ] [ i ] −= a [ j ] [ k ] ∗ a [ k ] [ i ] ; a [ i ] [ j ] −= a [ i ] [ k ] ∗ a [ k ] [ j ] ;
}
15 16 17 18 19 20
double d e t ( double a [MAX ] [ MAX] , i n t n ) { l r (a, n ) ; double d = 1 ; f o r ( i n t i = 0 ; i < n ; ++ i ) d ∗= a [ i ] [ i ] ; return d ;
4
21
REKURRENZEN, KOMBINATORIK UND DP
11
}
22 23 24
void s o l v e ( double a [MAX ] [ MAX] , double ∗b , i n t n ) { int i , j ;
25
f o r ( i = 1 ; i < n ; ++ i ) { f o r ( j = 0 ; j < i ; ++ j ) b [ i ] −= a [ i ] [ j ] ∗ b [ j ] ; } f o r ( i = n − 1 ; i >= 0 ; −− i ) { f o r ( j = i + 1 ; j < n ; ++ j ) b [ i ] −= a [ i ] [ j ] ∗ b [ j ] ; b [ i ] /= a [ i ] [ i ] ; }
26 27 28 29 30 31 32 33
}
3.6 3.6.1
Polynome Newtonsche/Hermitsche Interpolation
Dividierte Differenzen: [xi , . . . , xj ] =
[xi+1 , . . . , xj ] − [xi , . . . , xj−1 ] xj − xi
[xi , . . . , xi ] = f (n−1) (xi )/n! | {z } nmal
Newton-Polynome: Pi =
i−1 Y
(x − xk )
k=1
Also immer ein Term weniger mulitplizieren als das neue xi ! Interpoliertes Polynom: P =
n X [x1 , . . . , xi ] · Pi i=1
Wenn ein xi mehrmals auftaucht, als man auch die ersten paar Ableitungen interpolieren will, wird dieses xi dann halt auch im Newton-Polynom mehrmals dranmultipliziert. 3.6.2
Hornerschema Pn Pm Seien f (T ) = i=0 αi T i und g(T ) = j=0 βj T j zwei Polynome. Setze fur ¨ alle i = n, . . . , 0: min(m,n−i)
X
γi = αi −
βm−j γi+j
j=max(1,m−i)
Dann ist der Rest r(T ) und das Ergebnis s(T ) der Division von f durch g gegeben durch: r(T ) =
m−1 X
γi T i ,
s(T ) =
i=0
4 4.1
n X
γj T j−m
j=m
Rekurrenzen, Kombinatorik und DP Lineare Rekurrenzen (z.B. Fibonacci)
Lassen sich als Matrixgleichung schreiben, z.B. Fibonacci: Fn 1 1 Fn−1 = · Fn−1 1 0 Fn−2 Fur ¨ große n dann einfach die Matrix mittels schneller Potenzierung potenzieren, geht in O(log n).
4
REKURRENZEN, KOMBINATORIK UND DP
4.2
Urnenmodelle
k aus n ziehen mit Beachtung der Reihenfolge ohne Beachtung der Reihenfolge
4.3
12
mit Zurucklegen ¨ nk n+k−1
ohne Zur ¨ ucklegen n k ·k! n
k
k
Binomialkoeffizienten n n! n n r r r−1 r r−1 r−1 = , = , = , = + k k!(n − k)! k n−k k k k−1 k k k−1 r X r r k−r−1 r m r r−k = (−1)k , = , (x + y)r = xk y r−k k k m k k m−k k k=0 X k n + 1 X r + k r + n + 1 X r s r + s = , = , = m m+1 k n k n−k n 0≤k≤n
4.4 4.4.1
k≤n
k
¨ Haufige Rekurrenzen in der Kombinatorik Catalansche Zahlen
Anzahl der Sehnentriangulationen eines n + 2-Ecks, Anzahl der gultigen Klammerausdrucke mit n Klammern, ¨ ¨ Anzahl der Pfade in einem Grid, wobei man nur eins nach rechts und eins nach unten gehen darf. Cn =
4.4.2
2n 1 , n+1 n
Cn+1 =
n X
Ck Cn−k
k=0
Stirlingsche Zahlen 1. Art
Anzahl der n-Permutationen mit genau k Zyklen. sn+1,k = sn,k−1 ± n · sn,k 4.4.3
Stirlingsche Zahlen 2. Art
Anzahl der Partitionen von n Elementen in genau k Mengen. Sn+1,k = Sn,k−1 + k · Sn,k 4.4.4
Eulersche Zahlen
¨ Anzahl der n-Permutation, wo genau k Elemente großer als ihr vorhergehendes sind. En,k = (n − k) · En−1,k−1 + (k + 1) · En−1,k
4.5
¨ Langste Teilfolge (LCS, LIS)
1
# include
2 3 4
i n t eingabe [ SIZE ] ; i n t seq [ SIZE ] ;
5 6 7 8 9 10 11 12 13
int l i s () { int m = 0; f o r ( i n t i = 0 ; i < p ; ++ i ) { i n t j = lower bound ( seq , seq + m, eingabe [ i ] ) − seq ; i f ( j == m) seq [m++] = eingabe [ i ] ; else seq [ j ] = eingabe [ i ] ; } r e t u r n m; }
5
ZAHLENTHEORIE
4.6
13
SUBSET-SUM (KNAPSACK nur mit Gewichten)
1 2
# include
3 4 5 6 7
/ / l i e f e r t d i e g r o e s s t e Summe von Elementen aus v , d i e k l e i n e r oder g l e i c h l i m i t i n t subset sum ( const v e c t o r & v , i n t l i m i t ) { v e c t o r
ist
8
poss [ 0 ] = t r u e ; f o r ( v e c t o r : : c o n s t i t e r a t o r i t = v . begin ( ) ; f o r ( i n t j = m; j >= 0 ; −− j ) i f ( poss [ j ] && j + ∗ i t <= l i m i t ) { poss [ j + ∗ i t ] = t r u e ; m = max (m, j + ∗ i t ) ; }
9 10 11 12 13 14 15
i t ! = v . end ( ) ; ++ i t )
16
r e t u r n m;
17 18
}
4.7
Nim (bisschen Spieltheorie)
Gegeben: n Haufen mit a1 , . . . , an Steinen, wer dran ist nimmt bis zu k Steine von einem Haufen (k = ∞ erlaubt). 1. Variante: Ziel
ist
es
als
letztes
einen
Stein
aufzunehmen.
Man
gewinnt,
wenn
(a[1] \% (k + 1)) XOR ... XOR (a[n] \% (k + 1)) == 0 vor dem eigenen Zug.
` nim, play exactly as if you 2. Variante: Ziel ist es, dass der Gegner den letztes Stein aufnimmt: To win at misere were playing normal play nim, except if your winning move would lead to a position that consists of heaps of size one only. In that case, leave exactly one more or one fewer heaps of size one than the normal play strategy recommends. 3. Variante: Ziel ist es, den letzten Stein eines der Haufen aufzunehmen. Man gewinnt, wenn vor dem eigenem Zug ein Stapel maximal k Steine hat oder (a[1] \% (k + 1)) XOR ... XOR (a[n] \% (k + 1)) == 0, indem man entweder den letzten Stein nimmt oder man genau diesen Zustand herstellt.
5
Zahlentheorie
5.1
GGT und Kongruenzen (Euklid)
1 2 3
# include # include
4 5
using namespace s t d ;
6 7 8
typedef v a l a r r a y a i ; typedef v e c t o r v i ;
9 10 11 12 13 14 15
// // // ai
a % e u c l i d ( a , b ) [ 0 ] == 0 b % e u c l i d ( a , b ) [ 0 ] == 0 e u c l i d ( a , b ) [ 0 ] == a ∗ e u c l i d ( a , b ) [ 1 ] + b ∗ e u c l i d ( a , b ) [ 2 ] euclid ( int a , int b) { int R[ ] = { a , 1 , 0 } , S [ ] = { b , 0 , 1 }; a i r (R, 3 ) , s ( S , 3 ) ;
16 17 18 19 20 21
while ( s [ 0 ] ! = 0 ) { r −= r [ 0 ] / s [ 0 ] ∗ s ; swap ( r , s ) ; }
5
ZAHLENTHEORIE
return r ;
22 23
14
}
24 25 26 27 28
/ / a l l e Loesungen von ( a ∗ x ) % m == b m i t 0 <= x < m v i c o n g s o l v ( i n t a , i n t b , i n t m) { a i gcd = e u c l i d ( a , m) ; v i res ;
29
i f ( b % gcd [ 0 ] == 0 ) { m / = gcd [ 0 ] ; i n t i n v = gcd [ 1 ] < 0 ? (m − (−gcd [ 1 ] % m) ) % m : gcd [ 1 ] % m, s o l = ( b / gcd [ 0 ] ∗ i n v ) % m; f o r ( i n t i = gcd [ 0 ] ; i > 0 ; −− i ) { r e s . push back ( s o l ) ; s o l += m; } }
30 31 32 33 34 35 36 37 38 39
return res ;
40 41
}
5.2
Chinesischer Restsatz
¨ Zwei Kongruenzen der Art x ≡ a1 mod m1 , x ≡ a2 mod m2 lassen sich losen, indem man jeweils geschickt eine Eins dranmultipliziert und das dann aufaddiert. Die erste Kongruenz erweitern wir mit m−1 2 m2 (Inverses bzgl. m1 ) und die zweite mit m−1 m (bzgl. m ). Die Summe der rechten Seiten liefert dann das Ergebnis. Die Inversen 1 2 1 lassen sich mit dem ggT-Algorithmus von Euklid berechnen. Dies funktioniert nur, wenn m1 und m2 teilerfremd sind. Wenn nicht, muss a1 ≡ a2 mod ggT(m1 , m2 ) gelten. Dann kann man die Kongruenzen durch diesen ggT teilen.
5.3
Eulersche Phi-Funktion
ϕ(n) = Anzahl teilerfremden Zahlen kleiner gleich n. ϕ(n) = n ·
Y p−1 , p p|n
m und n teilerfremd =⇒ ϕ(m · n) = ϕ(m) · ϕ(n) und mϕ(n) ≡ 1
mod n)
p prim
Wenn man nur die Werte bis ein paar Millionen braucht, dann mit Backtracking erzeugen: 1 2 3 4 5 6 7 8 9 10 11 12 13 14
unsigned prime [ NUM PRIMES ] , p h i [MAX ] ; bool used [ NUM PRIMES ] ; / / Primzahlen muessen i n prime stehen , A u f r u f m i t genphi ( 0 , 1 , 1 ) void genphi ( unsigned next , unsigned n , unsigned p ) { phi [ n ] = p ; while ( n e x t < primes && n <= MAX / prime [ n e x t ] ) { i f ( ! used [ n e x t ] ) { used [ n e x t ] = t r u e ; genphi ( next , n ∗ prime [ n e x t ] , p ∗ ( prime [ n e x t ] − 1 ) ) ; used [ n e x t ] = f a l s e ; } else genphi ( next , n ∗ prime [ n e x t ] , p ∗ prime [ n e x t ] ) ; ++ n e x t ; } }
5.4 5.4.1
Sieb des Erathostenes
# include
2 3
Primzahlen (Erathostenes, Miller-Rabin)
1
unsigned ∗ s i e v e ( unsigned ∗ next , unsigned h i g h ) {
6
GRAPHEN
15
unsigned char i s p r i m e [ ( h i g h >> 4 ) + 1 ] ; unsigned i , j ;
4 5 6
memset ( i s p r i m e , 0 , ( h i g h >> 4 ) + 1 ) ; i f ( 2 <= h i g h ) { ∗ n e x t ++ = 2 ; }
7 8 9 10 11
f o r ( i = 3 ; i <= h i g h ; i += 2 ) { i f ( ( i s p r i m e [ i >> 4 ] & ( 1 << ( ( i >> 1 ) & 7 ) ) ) == 0 ) { ∗ n e x t ++ = j = i ; while ( ( j += i << 1 ) <= h i g h ) { i s p r i m e [ j >> 4 ] | = 1 << ( ( j >> 1 ) & 7 ) ; } } }
12 13 14 15 16 17 18 19 20
return next ;
21 22
}
Fenstersieb? 5.4.2
Primzahltest nach Miller und Rabin
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
typedef unsigned long long u l l ; const s t r u c t z e r o t { i n t z [ 0 x10000 ] ; zero t () { f o r ( i n t i = 1 ; i < 0x10000 ; ++ i ) z [ i ] = ( i & 1 ) ? 0 : 1 + z [ i >> 1 ] ; } } trail ; i n l i n e bool i s p r o b ( unsigned nr , unsigned base ) { unsigned u = 1 , odd = n r − 1 , sh = ( odd & 0xFFFF ) ? t r a i l . z [ odd & 0xFFFF ] : 16 + t r a i l . z [ odd >> 1 6 ] ; f o r ( odd >>= sh ; odd > 0 ; odd >>= 1 ) { i f ( ( odd & 1 ) ) u = ( u l l ( u ) ∗ base ) % n r ; base = ( u l l ( base ) ∗ base ) % n r ; } i f ( u == 1 ) r e t u r n t r u e ; while ( sh−− > 0 ) { i f ( u == n r − 1 ) r e t u r n t r u e ; u = ( u l l ( u ) ∗ u ) % nr ; } return false ; } bool i s p r i m e ( unsigned n r ) { s t a t i c const unsigned p [ ] = { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 } ; f o r ( i n t i = 0 ; i < 8 ; ++ i ) { i f ( p [ i ] ∗ p [ i ] > nr ) return nr > 1; i f ( n r % p [ i ] == 0 ) r e t u r n f a l s e ; } r e t u r n i s p r o b ( nr , 2 ) && i s p r o b ( nr , 7 ) && i s p r o b ( nr , 6 1 ) ; }
6 6.1
Graphen Topologische Sortierung
1 2 3 4
i n t t o p s o r t ( graph ∗g , i n t s o r t e d [ ] ) { i n t i n d e g r e e [MAXV ] ; / ∗ i n d e g r e e o f each v e r t e x ∗ / queue z e r o i n ; / ∗ v e r t i c e s of indegree 0 ∗ / int x , y ; / ∗ c u r r e n t and n e x t v e r t e x ∗ /
6
GRAPHEN
16
int i , c ;
5 6
compute indegrees ( g , i n d e g r e e ) ; f o r ( i n t i = 0 ; i < g−>n v e r t i c e s ; i ++) i f ( i n d e g r e e [ i ] == 0 ) z e r o i n . push ( i ) ;
7 8 9 10 11
c = 0; while ( ! z e r o i n . empty ( ) ) { c ++; x = zeroin . f r o n t ( ) ; z e r o i n . pop ( ) ; sorted [ c ] = x ; f o r ( i = 0 ; i < g−>degree [ x ] ; y = g−>edges [ x ] [ i ] ; ( i n d e g r e e [ y ]) − −; i f ( i n d e g r e e [ y ] == 0 ) z e r o i n . push ( y ) ; } }
12 13 14 15 16 17 18 19 20 21 22 23 24
i ++) {
25
i f ( c ! = g−>n v e r t i c e s ) return 0; / / p r i n t f ( ” Not a DAG −− o n l y %d v e r t i c e s found \n ” , j ) ; else r e t u r n −1;
26 27 28 29 30 31
}
6.2
¨ (Tarjan) Artikulationspunkte, Brucken ¨ und Bikonnektivitat
1
# include
2 3
using namespace s t d ;
4 5
const i n t MAX = 1024;
6 7 8 9
v e c t o r
10 11 12
i n t v i s i t ( i n t nod , i n t par , i n t dep ) { int children = 0;
13
low [ nod ] = depth [ nod ] = dep ; f o r ( s i z e t i = 0 ; i < graph [ nod ] . s i z e ( ) ; ++ i ) { i n t k = graph [ nod ] [ i ] ;
14 15 16 17
i f ( depth [ k ] < 0 ) { ++ c h i l d r e n ; v i s i t ( k , nod , dep + 1 ) ; i f ( low [ nod ] > low [ k ] ) low [ nod ] = low [ k ] ; i s a r t i [ nod ] = i s a r t i [ nod ] | | low [ k ] >= dep ; i s b r i d g e [ nod ] [ i ] = low [ k ] > dep ; } else i f ( k ! = par ) { i f ( low [ nod ] > depth [ k ] ) low [ nod ] = depth [ k ] ; i s b r i d g e [ nod ] [ i ] = f a l s e ; }
18 19 20 21 22 23 24 25 26 27
} return c h i l d r e n ;
28 29 30
}
31 32 33 34
void t a r j a n ( ) { f i l l ( depth , depth + graph . s i z e ( ) , −1); f i l l ( i s a r t i , i s a r t i + graph . s i z e ( ) , f a l s e ) ;
6
GRAPHEN
f o r ( s i z e t i = 0 ; i < graph . s i z e ( ) ; ++ i ) f i l l ( i s b r i d g e [ i ] , i s b r i d g e [ i ] + graph [ i ] . s i z e ( ) , t r u e ) ; f o r ( s i z e t i = 0 ; i < graph . s i z e ( ) ; ++ i ) i f ( depth [ i ] < 0 ) i s a r t i [ i ] = v i s i t ( i , i , 0 ) > 1 ;
35 36 37 38 39
}
6.3
Starke Zusammenhangskomponenten (Tarjan)
1 2 3
17
v v i gr ; v i dep , low ; stack S ;
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
void v i s i t ( i n t i , i n t d ) { S . push ( i ) ; dep [ i ] = low [ i ] = 0 ; f o r ( v i : : i t e r a t o r i t = g r [ i ] . begin ( ) ; i t ! = g r [ i ] . end ( ) ; ++ i t ) { i f ( dep [ ∗ i t ] < 0 ) { v i s i t (∗ i t , d + 1 ) ; low [ i ] = min ( low [ i ] , low [ ∗ i t ] ) ; } else i f ( dep [ ∗ i t ] == 0 ) { low [ i ] = min ( low [ i ] , d + 1 ) ; } } dep [ i ] = d ; i f ( dep [ i ] == low [ i ] ) { / / a l l e s a u f Stack b i s h i n u n t e r zu i g e h o e r t i n e i n e SCC } }
6.4
Eulerscher Kreis
Bei ungerichteten Graphen existiert ein Eulerkreis genau dann, wenn alle Knoten geraden Grad haben. Bei gerichteten Graphen existiert ein Eulerkreis genau dann, wenn bei allen Knoten Eingangsgrad und Ausgangsgrad ¨ gleich sind. Naturlich sollte der Graph zusammenhangend sein!! ¨ 1 2 3 4 5 6 7
l i s t < i n t > cyc ; void e u l e r ( l i s t < i n t >:: i t e r a t o r i , i n t u ) { f o r ( i n t v = 0 ; v < n ; v++ ) i f ( graph [ u ] [ v ] ) { graph [ u ] [ v ] = graph [ v ] [ u ] = f a l s e ; e u l e r ( cyc . i n s e r t ( i , u ) , v ) ; } }
8 9 10 11 12 13
i n t main ( ) { / / read graph i n t o graph [ ] [ ] and s e t n t o t h e number o f v e r t i c e s e u l e r ( cyc . begin ( ) , 0 ) ; / / cyc c o n t a i n s an e u l e r c y c l e s t a r t i n g a t 0 }
6.5 6.5.1 1 2 3 4
Kurzeste ¨ Pfade (Dijkstra, Floyd-Warshall, Bellman-Ford) Dijkstra
# include # include # include # include
5 6
const i n t INF = 12345678;
7 8
typedef p a i r i i ;
6
9 10
GRAPHEN
18
typedef v e c t o r v i i ; typedef v e c t o r
11 12 13 14 15 16 17 18
/ / Anzahl der Knoten = g r . s i z e ( ) / / Grad des Knotens i = g r [ i ] . s i z e ( ) / / j −t e r b e n a c hb ar t er Knoten des Knotens i = g r [ i ] [ j ] . f i r s t / / Laenge d i e s e r Kante = g r [ i ] [ j ] . second v e c t o r d i j k s t r a ( v v i i & gr , i n t s r c ) { v e c t o r d i s t ( g r . s i z e ( ) , INF ) ; p r i o r i t y q u e u e > kew ;
19
d i s t [ src ] = 0; f o r ( kew . push ( i i ( 0 , s r c ) ) ; ! kew . empty ( ) ; kew . pop ( ) ) { i n t d = kew . t o p ( ) . f i r s t , f r = kew . t o p ( ) . second ; i f ( d <= d i s t [ f r ] ) { f o r ( v i i : : i t e r a t o r i t = g r [ f r ] . begin ( ) ; i t ! = g r [ f r ] . end ( ) ; ++ i t ) { i n t t o = i t −>f i r s t , l e n = i t −>second ; i f ( d i s t [ t o ] > d + l e n ) kew . push ( i i ( d i s t [ t o ] = d + len , t o ) ) ; } } }
20 21 22 23 24 25 26 27 28 29 30
return d i s t ;
31 32
}
6.5.2
Floyd-Warshall
1
const i n t MAX = 100 , INF = 12345678;
2 3 4 5 6
/ / N = Anzahl Knoten / / g r [ i ] [ j ] = Kosten von Knoten i nach Knoten j / / nach A u f r u f : v i a [ i ] [ j ] = n a e c h s t e r Knoten a u f dem k u e r z es t e n Pfad von i nach j i n t N, v i a [MAX ] [ MAX] , g r [MAX ] [ MAX ] ;
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
/ / wer nur d i e Distanzen braucht , n i c h t d i e t a t s a e c h l i c h e n Wege, / / kann auch a l l e s m i t ” v i a ” weglassen void f l o y d w a r s h ( ) { f o r ( i n t i = 0 ; i < N; ++ i ) f o r ( i n t j = 0 ; j < N; ++ j ) via [ i ] [ j ] = j ; f o r ( i n t k = 0 ; k < N; ++k ) f o r ( i n t i = 0 ; i < N; ++ i ) f o r ( i n t j = 0 ; j < N; ++ j ) i f ( gr [ i ] [ j ] > gr [ i ] [ k ] + gr [ k ] [ j ] ) { gr [ i ] [ j ] = gr [ i ] [ k ] + gr [ k ] [ j ] ; via [ i ] [ j ] = k ; } f o r ( i n t i = 0 ; i < N; ++ i ) f o r ( i n t j = 0 ; j < N; ++ j ) i f ( g r [ i ] [ j ] < INF ) while ( v i a [ i ] [ j ] ! = v i a [ i ] [ v i a [ i ] [ j ] ] ) via [ i ] [ j ] = via [ i ] [ via [ i ] [ j ] ] ; }
6.5.3
Bellman-Ford
1 2 3
# define NODES 1000 # define EDGES 1000 # define INFTY 1000000000
4 5 6
struct { s t r u c t { i n t to , l e n ; } edge [EDGES ] ;
6
7 8
GRAPHEN
19
i n t degree , d i s t ; } node [NODES ] ;
9 10
i n t nodes ;
11 12 13 14
/ / t r u e , wenn Graph keinen n e g a t i v e n K r e i s e n t h a e l t bool b e l l m a n f o r d ( i n t source ) { i n t i , j , from , to , d i s t ;
15
f o r ( i = 0 ; i < nodes ; ++ i ) node [ i ] . d i s t = INFTY ; node [ source ] . d i s t = 0 ; f o r ( j = 1 ; j < nodes ; ++ j ) f o r ( from = 0 ; from < nodes ; ++from ) f o r ( i = 0 ; i < node [ from ] . degree ; ++ i ) { t o = node [ from ] . edge [ i ] . t o ; d i s t = node [ from ] . d i s t + node [ from ] . edge [ i ] . l e n ; i f ( d i s t < node [ t o ] . d i s t ) node [ t o ] . d i s t = d i s t ; } f o r ( from = 0 ; from < nodes ; ++from ) f o r ( i = 0 ; i < node [ from ] . degree ; ++ i ) { t o = node [ from ] . edge [ i ] . t o ; d i s t = node [ from ] . d i s t + node [ from ] . edge [ i ] . l e n ; i f ( d i s t < node [ t o ] . d i s t ) r e t u r n f a l s e ; } return true ;
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
}
6.6
Minimaler Spannbaum (Kruskal, Prim)
6.6.1
Kruskal
1
# include
2 3 4 5 6
/ / e d g e t f e h l t , r o o t und j o i n i s t das u e b l i c h e union−f i n d int kruskal ( ) { v e c t o r p a r e n t ( n r o f n o d e s , −1); i n t rem = n r o f n o d e s − 1 , ans = 0 ;
7
s o r t ( edges . begin ( ) , edges . end ( ) ) ; f o r ( v e c t o r <edge t > : : i t e r a t o r i t = edges . begin ( ) ; rem > 0 && i t ! = edges . end ( ) ; ++ i t ) { i n t a = r o o t ( parent , i t −>from ) , b = r o o t ( parent , i t −>t o ) ; i f ( a != b ) { j o i n ( parent , a , b ) ; ans += i t −>l e n ; −−rem ; } } r e t u r n ans ;
8 9 10 11 12 13 14 15 16 17 18
}
6.6.2
Prim
1 2 3 4 5
/ / a l l e s wie b e i D i j k s t r a i n t prim ( v v i i & g r ) { v e c t o r d i s t ( g r . s i z e ( ) , INF ) ; p r i o r i t y q u e u e > kew ; i n t ans = 0 ;
6 7 8 9 10
d i s t [ 0 ] = 0; f o r ( kew . push ( i i ( 0 , 0 ) ) ; ! kew . empty ( ) ; kew . pop ( ) ) { i n t d = kew . t o p ( ) . f i r s t , f r = kew . t o p ( ) . second ; i f ( d <= d i s t [ f r ] ) {
6
GRAPHEN
ans += d ; d i s t [ f r ] = −1; f o r ( v i i : : i t e r a t o r i t = g r [ f r ] . begin ( ) ; i t ! = g r [ f r ] . end ( ) ; ++ i t ) { i n t t o = i t −>f i r s t , l e n = i t −>second ; i f ( d i s t [ t o ] > l e n ) kew . push ( i i ( d i s t [ t o ] = len , t o ) ) ; }
11 12 13 14 15 16
} } r e t u r n ans ;
17 18 19 20
20
}
6.7
Bipartites Matching
1
# include
2 3 4
# define FROM N 1000 # define TO N 1000
5 6
i n t from nodes , to nodes ;
7 8
bool graph [ FROM N ] [ TO N ] , seen [ TO N ] ;
9 10
i n t match from [FROM N] , match to [ TO N ] ;
11 12 13 14 15
bool m a t c h v i s i t ( i n t from ) { f o r ( i n t t o = 0 ; t o < to nodes ; ++ t o ) { i f ( graph [ from ] [ t o ] && ! seen [ t o ] ) { seen [ t o ] = t r u e ;
16
i f ( match to [ t o ] < 0 | | m a t c h v i s i t ( match to [ t o ] ) ) { match from [ from ] = t o ; match to [ t o ] = from ; return true ; }
17 18 19 20 21
}
22
}
23 24
return false ;
25 26
}
27 28 29
i n t match ( ) { i n t res = 0;
30
f i l l ( match from , match from + from nodes , −1); f i l l ( match to , match to + to nodes , −1); f o r ( i n t i = 0 ; i < from nodes ; ++ i ) { f i l l ( seen , seen + to nodes , f a l s e ) ; i f ( match visit ( i )) { ++ r e s ; } }
31 32 33 34 35 36 37 38 39
return res ;
40 41
}
6.8
Maximaler Fluss (Ford-Fulkerson)
1 2
# include # include
3 4 5
# define NODES 100 # define INFTY 1000000000
6
GRAPHEN
21
6 7
i n t nodes , cap [NODES ] [ NODES] , f l o w [NODES ] [ NODES ] ;
8 9
bool s r c s i d e [NODES ] ;
10 11 12 13
struct { i n t node , parent , mincap ; } kew [NODES ] ;
14 15
i n t low , h i g h ;
16 17 18 19
i n t i n i t b f s ( i n t source , i n t t a r g e t ) { memset ( s r c s i d e , 0 , s i z e o f s r c s i d e ) ; s r c s i d e [ source ] = t r u e ;
20
kew [ 0 ] . node = source ; kew [ 0 ] . p a r e n t = −1; kew [ 0 ] . mincap = INFTY ;
21 22 23 24
low = 0 ; high = 1;
25 26 27
return t a r g e t ;
28 29
}
30 31 32
bool b f s ( i n t t a r g e t ) { i n t from , t o ;
33
while ( low < h i g h && ( from = kew [ low ] . node ) ! = t a r g e t ) { f o r ( t o = 0 ; t o < nodes ; ++ t o ) { i f ( ! s r c s i d e [ t o ] && cap [ from ] [ t o ] > f l o w [ from ] [ t o ] ) { srcside [ to ] = true ;
34 35 36 37 38
kew [ h i g h ] . node = t o ; kew [ h i g h ] . p a r e n t = low ; kew [ h i g h ] . mincap = min ( kew [ low ] . mincap , cap [ from ] [ t o ] − f l o w [ from ] [ t o ] ) ;
39 40 41 42
++ h i g h ;
43
}
44
}
45 46
++low ;
47
}
48 49
r e t u r n low < h i g h ;
50 51
}
52 53 54
i n t maxflow ( i n t source , i n t t a r g e t ) { i n t i , j , res = 0;
55
memset ( f l o w , 0 , s i z e o f f l o w ) ; while ( b f s ( i n i t b f s ( source , t a r g e t ) ) ) { r e s += kew [ low ] . mincap ; f o r ( i = low ; i > 0 ; i = j ) { j = kew [ i ] . p a r e n t ; f l o w [ kew [ j ] . node ] [ kew [ i ] . node ] += kew [ low ] . mincap ; f l o w [ kew [ i ] . node ] [ kew [ j ] . node ] −= kew [ low ] . mincap ; } }
56 57 58 59 60 61 62 63 64 65
return res ;
66 67
}
6.9
Min-Cost-Max-Flow
6
GRAPHEN
22
1 2 3 4
# include # include
5 6 7 8 9 10 11
# define NN 110 i n t cap [NN ] [ NN ] ; / / adjacency m a t r i x ( f i l l t h i s up ) i n t c o s t [NN ] [ NN ] ; / / c o s t per u n i t o f f l o w m a t r i x ( f i l l t h i s up ) i n t f n e t [NN ] [ NN] , a d j [NN ] [ NN] , deg [NN ] ; / / f l o w network and adjacency l i s t i n t par [NN] , d [NN ] ; / / par [ source ] = source ; / / D i j k s t r a ’ s successor and depth i n t p i [NN ] ; / / L a b e l l i n g f u n c t i o n
12 13 14
# define CLR( a , x ) memset ( a , x , s i z e o f ( a ) ) # define I n f ( INT MAX / 2 )
15 16 17 18 19 20 21 22
/ / D i j k s t r a ’ s u s i n g non−n e g a t i v e # define Pot ( u , v ) ( d [ u ] + p i [ u ] − bool d i j k s t r a ( i n t n , i n t s , i n t { f o r ( i n t i = 0 ; i < n ; i ++ ) d [ s ] = 0; par [ s ] = −n − 1 ;
edge w e i g h t s ( c o s t + p o t e n t i a l ) pi [ v ] ) t ) d [ i ] = I n f , par [ i ] = −1;
23 24 25 26 27 28 29 30
while ( 1 ) { / / find u with smallest d [ u ] i n t u = −1, bestD = I n f ; f o r ( i n t i = 0 ; i < n ; i ++ ) i f ( par [ i ] < 0 && d [ i ] < bestD ) bestD = d [ u = i ] ; i f ( bestD == I n f ) break ;
31
/ / r e l a x edge ( u , i ) o r ( i , u ) f o r a l l i ; par [ u ] = −par [ u ] − 1 ; f o r ( i n t i = 0 ; i < deg [ u ] ; i ++ ) { / / t r y undoing edge v−>u int v = adj [ u ] [ i ] ; i f ( par [ v ] >= 0 ) continue ; i f ( f n e t [ v ] [ u ] && d [ v ] > Pot ( u , v ) − c o s t [ v ] [ u ] ) d [ v ] = Pot ( u , v ) − c o s t [ v ] [ u ] , par [ v ] = −u−1;
32 33 34 35 36 37 38 39 40 41
/ / t r y edge u−>v i f ( f n e t [ u ] [ v ] < cap [ u ] [ v ] && d [ v ] > Pot ( u , v ) + c o s t [ u ] [ v ] ) d [ v ] = Pot ( u , v ) + c o s t [ u ] [ v ] , par [ v ] = −u − 1 ;
42 43 44
}
45 46
}
47 48
f o r ( i n t i = 0 ; i < n ; i ++ ) i f ( p i [ i ] < I n f ) p i [ i ] += d [ i ] ;
49 50 51 52
r e t u r n par [ t ] >= 0 ; } #undef Pot
53 54 55 56 57 58 59 60
i n t mcmf3 ( i n t n , i n t s , i n t t , i n t & f c o s t ) { / / b u i l d t h e adjacency l i s t CLR( deg , 0 ) ; f o r ( i n t i = 0 ; i < n ; i ++ ) f o r ( i n t j = 0 ; j < n ; j ++ ) i f ( cap [ i ] [ j ] | | cap [ j ] [ i ] ) a d j [ i ] [ deg [ i ] + + ] = j ;
61 62 63 64 65
CLR( f n e t , 0 ) ; CLR( p i , 0 ) ; int flow = 0; fcost = 0;
7
GEOMETRIE
23
66
/ / r e p e a t e d l y , f i n d a cheapest path from s t o t while ( d i j k s t r a ( n , s , t ) ) { / / get the bottleneck capacity i n t b o t = INT MAX ; f o r ( i n t v = t , u = par [ v ] ; v ! = s ; u = par [ v = u ] ) { b o t = min ( bot , f n e t [ v ] [ u ] ? f n e t [ v ] [ u ] : ( cap [ u ] [ v ] − f n e t [ u ] [ v ] ) ) ;
67 68 69 70 71 72 73 74
/ / update t h e f l o w network f o r ( i n t v = t , u = par [ v ] ; v ! = s ; u = par [ v = u ] ) i f ( f n e t [ v ] [ u ] ) { f n e t [ v ] [ u ] −= b o t ; f c o s t −= b o t ∗ c o s t [ v ] [ u ] ; } else { f n e t [ u ] [ v ] += b o t ; f c o s t += b o t ∗ c o s t [ u ] [ v ] ; }
75 76 77 78 79
f l o w += b o t ;
80
}
81 82
return flow ;
83 84
}
7
Geometrie
1 2 3
# include # include
4 5
using namespace s t d ;
6 7
const double PI = 2 ∗ acos ( 0 ) , EPS = 1e−9;
8 9 10
typedef v a l a r r a y <double> vec ; typedef v a l a r r a y
7.1
Geraden und Punkte
1 2 3
# include # include
4 5
using namespace s t d ;
6 7
const double EPS = 1e−9;
8 9 10
typedef v a l a r r a y <double> p o i n t ; typedef v a l a r r a y
p o i n t s ;
11 12 13
typedef v a l a r r a y <double> vec ; typedef v a l a r r a y
14 15 16 17 18
/ / Abstand des Punkts pos zum Ursprung double norm ( const vec& a ) { r e t u r n s q r t ( ( a ∗ a ) . sum ( ) ) ; }
19 20 21 22 23
/ / Abstand z w e i e r Punkte double d i s t ( const vec& a , const vec& b ) { r e t u r n norm ( a − b ) ; }
24 25 26
/ / Punkt a u f Gerade durch Punkt pos i n Richtung d i r / / m i t k l e i n s t e m Abstand zu Ursprung ( o r t h o g o n a l e P r o j e k t i o n )
7
27 28 29
GEOMETRIE
24
vec p r o j ( const vec& pos , const vec& d i r ) { r e t u r n pos − ( pos ∗ d i r ) . sum ( ) / ( d i r ∗ d i r ) . sum ( ) ∗ d i r ; }
30 31 32 33 34
/ / Abstand Punkt−Gerade double d i s t ( const vec& pos , const vec& d i r , const vec& p t ) { r e t u r n norm ( p r o j ( pos − pt , d i r ) ) ; }
35 36 37 38 39 40
/ / S c h n i t t p u n k t Gerade durch pos i n Richtung d i r / / m i t Gerade / Ebene durch Ursprung m i t Normale norm vec i s e c t ( const vec& pos , const vec& d i r , const vec& norm ) { r e t u r n pos − ( pos ∗ norm ) . sum ( ) / ( d i r ∗ norm ) . sum ( ) ∗ d i r ; }
41 42 43 44 45 46 47
/ / 2D−S c h n i t t p u n k t der Geraden durch Punkte a1−a2 und b1−b2 vec i s e c t ( const vec& a1 , const vec& a2 , const vec& b1 , const vec& b2 ) { double temp [ ] = { a1 [ 1 ] − a2 [ 1 ] , a2 [ 0 ] − a1 [ 0 ] } ; vec norm ( temp , 2 ) ; r e t u r n i s e c t ( b1 − a1 , b2 − b1 , norm ) + a1 ; }
48 49 50 51 52 53 54
/ / S c h n i t t p u n k t Gerade durch pos i n Richtung d i r / / m i t K r e i s / Kugel um Ursprung m i t Radius rad i n l i n e vecvec i s e c t ( const vec& pos , const vec& d i r , double rad ) { double pp = ( pos ∗ pos ) . sum ( ) , dd = ( d i r ∗ d i r ) . sum ( ) , pd = ( pos ∗ d i r ) . sum ( ) , r r = rad ∗ rad , d i s = pd ∗ pd − dd ∗ ( pp − r r ) ;
55
i f ( d i s > EPS) { vecvec r e s ( pos , 2 ) ; dis = sqrt ( dis ) ; r e s [ 0 ] −= ( pd + d i s ) / dd ∗ d i r ; r e s [ 1 ] −= ( pd − d i s ) / dd ∗ d i r ; return res ; } else i f ( d i s > −EPS) { vecvec r e s ( pos , 1 ) ; r e s [ 0 ] −= pd / dd ∗ d i r ; return res ; }
56 57 58 59 60 61 62 63 64 65 66 67
r e t u r n vecvec ( ) ;
68 69
}
7.2
Dreiecke und Liniensegmente
1 2 3
# include # include
4 5
using namespace s t d ;
6 7
const double PI = 2 ∗ acos ( 0 ) , EPS = 1e−9;
8 9
typedef v a l a r r a y <double> vec ;
10 11 12 13 14 15
/ / Flaeche des durch a und b aufgespannten Parallelogramms / / p o s i t i v , wenn Winkel zwischen a und b p o s i t i v double sgn area ( const vec& a , const vec& b ) { return a [ 0 ] ∗ b [ 1 ] − a [ 1 ] ∗ b [ 0 ] ; }
16 17 18
/ / p o s i t i v , wenn a−b−c im Gegenuhrzeigersinn ( math . p o s i t i v ) l i e g e n double sgn area ( const vec& a , const vec& b , const vec& c ) {
7
GEOMETRIE
r e t u r n sgn area ( b − a , c − a ) ;
19 20
25
}
21 22 23 24 25
/ / Dreiecksflaeche double area ( const vec& a , const vec& b , const vec& c ) { r e t u r n 0 . 5 ∗ f a b s ( sgn area ( a , b , c ) ) ; }
26 27 28 29 30 31 32 33
/ / D r e i e c k s f l a e c h e aus Se it en la en ge n double area ( double a , double b , double c ) { i f ( a < b ) swap ( a , b ) ; i f ( b < c ) swap ( b , c ) ; i f ( a < b ) swap ( a , b ) ; r e t u r n 0.25 ∗ s q r t ( ( a + ( b + c ) ) ∗ ( c − ( a − b ) ) ∗ ( c + ( a − b ) ) ∗ ( a + ( b − c ) ) ) ; }
34 35 36 37 38
/ / t r u e , wenn a und b verschiedene Vorzeichen haben i n l i n e bool pos neg ( double a , double b ) { r e t u r n ( a < 0 && 0 < b ) | | ( b < 0 && 0 < a ) ; }
39 40 41 42 43 44 45 46
/ / t r u e , wenn Punkt d i n D r e i e c k m i t bool i n s i d e ( const vec& a , const vec& double x = sgn area ( c , b , a ) ; r e t u r n pos neg ( x , sgn area ( a , b , && pos neg ( x , sgn area ( b , c , && pos neg ( x , sgn area ( c , a , }
Eckpunkten a−b−c l i e g t b , const vec& c , const vec& d ) { d)) d)) d));
47 48 49 50 51 52
/ / t r u e , wenn Punkt c i n a c h s e n p a r a l l e l e m Rechteck durch Punkt a und b l i e g t bool i n s i d e ( const vec& a , const vec& b , const vec& c ) { r e t u r n min ( a [ 0 ] , b [ 0 ] ) < c [ 0 ] + EPS && max ( a [ 0 ] , b [ 0 ] ) > c [ 0 ] − EPS && min ( a [ 1 ] , b [ 1 ] ) < c [ 1 ] + EPS && max ( a [ 1 ] , b [ 1 ] ) > c [ 1 ] − EPS ; }
53 54 55 56 57
/ / t r u e , wenn c a u f Segment a−b l i e g t bzw . g l e i c h a oder b i s t bool on seg ( const vec& a , const vec& b , const vec& c ) { r e t u r n i n s i d e ( a , b , c ) && f a b s ( sgn area ( a , b , c ) ) < EPS ; }
58 59 60 61 62 63
/ / S c h n i t t der Liniensegmente a1−a2 und b1−b2 / / 0 = k e i n S c h n i t t , 1 = S c h n i t t , −1 = Beruehrung i n t i s e c t ( const vec& a1 , const vec& a2 , const vec& b1 , const vec& b2 ) { double da1 = sgn area ( b1 , b2 , a1 ) , da2 = sgn area ( b1 , b2 , a2 ) , db1 = sgn area ( a1 , a2 , b1 ) , db2 = sgn area ( a1 , a2 , b2 ) ;
64
i f ( pos neg ( da1 , da2 ) && pos neg ( db1 , db2 ) ) r e t u r n 1 ; i f ( on seg ( a1 , a2 , b1 ) | | on seg ( a1 , a2 , b2 ) | | on seg ( b1 , b2 , a1 ) | | on seg ( b1 , b2 , a2 ) ) r e t u r n −1; return 0;
65 66 67 68 69
}
Abstand eines Punktes, Abstand eines anderen Segments.
7.3
Kreise
1 2 3 4 5
/ / S c h n i t t p u n k t e von K r e i s um 0 m i t Radius r 1 m i t K r e i s um Punkt pos m i t Radius r 2 vecvec i s e c t ( double r1 , vec pos , double r 2 ) { double d2 = ( pos ∗ pos ) . sum ( ) , d = s q r t ( d2 ) ; r 1 ∗= r 1 ; r 2 ∗= r 2 ; double x = 0 . 5 ∗ ( d2 + r 1 − r 2 ) / d , y2 = r 1 − x ∗ x ;
6 7 8 9
i f ( y2 > EPS) { double norma [ ] = { −pos [ 1 ] , pos [ 0 ] } ; vec norm ( norma , 2 ) ;
7
GEOMETRIE
vecvec r ( x / d ∗ pos , 2 ) ; y2 = s q r t ( y2 ) ; r [ 0 ] += y2 / d ∗ norm ; r [ 1 ] −= y2 / d ∗ norm ; return r ; } else i f ( y2 > −EPS) { r e t u r n vecvec ( x / d ∗ pos , 1 ) ; } r e t u r n vecvec ( ) ;
10 11 12 13 14 15 16 17 18 19
26
}
Kreis durch drei Punkte, Kreis durch zwei Punkte mit geg. Radius.
7.4
Polygone
Die N Punkte eines Polygons werden mit (xi , yi ) fur ¨ i = 1, . . . , N bezeichnet. Konvention: (x0 , y0 ) = (xN , yN ). ¨ Die vorzeichenbehaftete Flache A berechnet sich wie folgt: N
A=
1X xi−1 yi − xi yi−1 2 i=1
¨ Bei Polygonen mit ganzzahligen Koordinaten gilt fur A, die Anzahl der Gitterpunkte auf dem Rand B ¨ die Flache und die derjenigen im Innern I: B I =A− +1 2 7.4.1
Punkt in Polygon
1
# include
2 3 4
# define MAX 1024 # define EPS 1e−7
5 6 7 8
struct point { double x , y ; };
9 10 11 12 13 14 15 16
s t r u c t polygon { int n; p o i n t p [MAX ] ; p o i n t &operator [ ] ( i n t i ) { return p [ i ] ; } };
17 18 19 20 21
i n l i n e double d i s t ( const p o i n t &a , const p o i n t &b ) { double dx = a . x − b . x , dy = a . y − b . y ; r e t u r n s q r t ( dx ∗ dx + dy ∗ dy ) ; }
22 23 24
bool c o n t a i n s ( polygon &P , p o i n t &p ) { bool i n s i d e = f a l s e ;
25 26 27 28 29
f o r ( i n t j = P . n − 1 , i = 0 ; i < P . n ; j = i ++) { i f ( f a b s ( d i s t ( p , P [ j ] ) + d i s t ( p , P [ i ] ) − d i s t (P [ j ] , P [ i ] ) ) < EPS) { r e t u r n t r u e ; / / t r u e = Rand g e h o e r t m i t zum Polygon }
30 31 32 33 34 35 36
i f ( min (P [ j ] . y , P [ i ] . y ) <= p . y && max (P [ j ] . y , P [ i ] . y ) > p . y && ( p . y − P [ j ] . y ) ∗ (P [ i ] . x − P [ j ] . x ) / (P [ i ] . y − P [ j ] . y ) > p . x − P [ j ] . x ) { inside = ! inside ; } } return i n s i d e ;
7
37
GEOMETRIE
}
7.4.2
Konvexe Hulle ¨ (Graham’s Scan)
1 2
27
# include # include
3 4
using namespace s t d ;
5 6 7
const long double EPS = 1e−5; const i n t MAXPOINTS = 1005;
8 9 10 11 12
struct point { long double x , y ; } p o i n t s [ MAXPOINTS ] , h u l l [ MAXPOINTS ] ; i n t npoints , n h u l l ;
13 14 15 16
long double signedArea ( const p o i n t & a , const p o i n t & b , const p o i n t & c ) { return a . x ∗ b . y − b . x ∗ a . y + b . x ∗ c . y − c . x ∗ b . y + c . x ∗ a . y − a . x ∗ c . y ; }
17 18 19 20
long double s q r d i s t ( const p o i n t & a , const p o i n t & b ) { return ( a . x − b . x ) ∗ ( a . x − b . x ) + ( a . y − b . y ) ∗ ( a . y − b . y ) ; }
21 22 23
bool bySignedArea ( const p o i n t & a , const p o i n t & b ) { long double sa = signedArea ( p o i n t s [ 0 ] , a , b ) ;
24
r e t u r n ( f a b s ( sa ) < EPS ) ? ( sqrdist ( points [0] , a ) < sqrdist ( points [0] , b ) ) : ( sa > 0 ) ;
25 26 27 28
}
29 30 31 32
void f i n d m i n p o i n t ( ) { long double minx = p o i n t s [ 0 ] . x , miny = p o i n t s [ 0 ] . y ; int currentmin = 0;
33
f o r ( i n t i = 1 ; i < n p o i n t s ; ++ i ) { i f ( p o i n t s [ i ] . y < miny | | ( p o i n t s [ i ] . y == miny && p o i n t s [ i ] . x < minx ) ) { minx = p o i n t s [ i ] . x ; miny = p o i n t s [ i ] . y ; currentmin = i ; } }
34 35 36 37 38 39 40 41
/ / exchange min p o i n t w i t h p o i n t [ 0 ] swap ( p o i n t s [ c u r r e n t m i n ] , p o i n t s [ 0 ] ) ;
42 43 44
}
45 46 47 48 49
void c o n v e x h u l l ( ) { findminpoint ( ); s o r t ( p o i n t s + 1 , p o i n t s + n p o i n t s , bySignedArea ) ;
50 51 52
hull [0] = points [ 0 ] ; nhull = 1;
53 54 55 56 57 58
f o r ( i n t i = 1 ; i < n p o i n t s ; ++ i ) { / / h i e r anpassen , wenn k o l l i n e a r e punkte m i t aufgenommen werden s o l l e n while ( n h u l l > 1 && signedArea ( h u l l [ n h u l l − 2 ] , h u l l [ n h u l l − 1 ] , p o i n t s [ i ] ) < EPS ) { −−n h u l l ; }
59 60
h u l l [ n h u l l ++] = p o i n t s [ i ] ;
7
28
}
61 62
GEOMETRIE
}
7.4.3
Clipping an Halbebene bzw. Gerade
1 2 3
# include
4 5 6 7
struct point { double x , y ; };
8 9
const i n t MAX = 1510
10 11 12 13 14 15 16 17
s t r u c t polygon { p o i n t p [MAX ] ; int n; p o i n t & operator [ ] ( i n t i ) { return p [ i ] ; } } poly , c l i p p e d [ 2 ] ;
18 19
double n o r m a l i z e ;
20 21 22 23 24
double signedPolygonArea ( polygon &p ) { double a = 0 ; f o r ( i n t i = 1 ; i < p . n ; ++ i ) a += p [ i −1]. x ∗ p [ i ] . y − p [ i ] . x ∗ p [ i −1]. y ;
25
a += p [ p . n −1]. x ∗ p [ 0 ] . y − p [ 0 ] . x ∗ p [ p . n −1]. y ;
26 27
return a / 2 ;
28 29
}
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
void i n s e r t ( polygon &p , p o i n t &a ) { i f ( p . n > 0) { i f ( p [ p . n −1]. x == a . x && p [ p . n −1]. y == a . y ) return ; } p [ p . n ++] = a ; } double sa ( p o i n t & a , p o i n t & b , p o i n t & c ) { return ( a . x ∗ b . y − a . y ∗ b . x + b . x ∗ c . y − b . y ∗ c . x + c . x ∗ a . y − a . x ∗ c . y ) ∗ normalize ; } p o i n t i n t e r s e c t ( p o i n t & p1 , p o i n t & p2 , p o i n t & p3 , p o i n t & p4 ) { double a1 = p2 . y − p1 . y , b1 = p1 . x − p2 . x ; double c1 = p1 . x∗p2 . y − p2 . x∗p1 . y ; double a2 = p4 . y − p3 . y , b2 = p3 . x − p4 . x ; double c2 = p3 . x∗p4 . y − p4 . x∗p3 . y ;
46 47 48 49 50
double d = a1∗b2 − a2∗b1 ; point p ; p . x = ( c1∗b2 − c2∗b1 ) / d ; p . y = ( a1∗c2 − a2∗c1 ) / d ;
51 52 53 54 55 56 57 58 59
return p ; } void d o c l i p p i n g ( p o i n t & a , p o i n t & b , polygon& i n p u t , polygon& o u t p u t ) { output . n = 0; f o r ( i n t k = 0 ; k < i n p u t . n ; ++k ) { i n t i = k , i p p = ( k +1) % i n p u t . n ; double s a i = sa ( a , b , i n p u t [ i ] ) ; double s a i p p = sa ( a , b , i n p u t [ i p p ] ) ;
7
GEOMETRIE
29
60
i f ( s a i >= 0 && s a i p p >= 0 ) i n s e r t ( output , i n p u t [ ipp ] ) ; else i f ( s a i >= 0 && s a i p p < 0 ) { point c = i n t e r s e c t (a , b , input [ i ] , input [ ipp ] ) ; i n s e r t ( output , c ) ; } else i f ( s a i < 0 && s a i p p >= 0 ) { point c = i n t e r s e c t (a , b , input [ i ] , input [ ipp ] ) ; i n s e r t ( output , c ) ; i n s e r t ( output , i n p u t [ ipp ] ) ; } else { a s s e r t ( s a i < 0 && s a i p p < 0 ) ; }
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
} } i n t main ( ) { int currentclipped = 0; / / TODO here : / / i n p u t polygon i n t o both p o l y and c l i p p e d [ 0 ] ! !
81
/ / n o r m a l i z e t h e d i r e c t i o n o f t h e p o i n t s o f t h e polygon n o r m a l i z e = signedPolygonArea ( p o l y ) ; i f ( n o r m a l i z e > 0 ) n o r m a l i z e = 1 ; else n o r m a l i z e = −1; f o r ( i n t i = 0 ; i < p o l y . n−1; ++ i ) { d o c l i p p i n g ( p o l y [ i ] , p o l y [ i + 1 ] , c l i p p e d [ c u r r e n t c l i p p e d ] , c l i p p e d [1− c u r r e n t c l i p p e d ] ) ; c u r r e n t c l i p p e d = 1− c u r r e n t c l i p p e d ; } d o c l i p p i n g ( p o l y [ p o l y . n −1] , p o l y [ 0 ] , c l i p p e d [ c u r r e n t c l i p p e d ] , c l i p p e d [1− c u r r e n t c l i p p e d ] ) ; c u r r e n t c l i p p e d = 1− c u r r e n t c l i p p e d ; return 0;
82 83 84 85 86 87 88 89 90 91 92
}
7.5
Rasterung von Linien/Kreisen (Bresenham)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
/ / r u f t do something ( x , y ) m i t a l l e n ( x , y ) auf , / / d i e e i n e g e r a s t e r t e L i n i e von ( x0 , y0 ) nach ( x1 , y1 ) b i l d e n void l i n e ( i n t x0 , i n t y0 , i n t x1 , i n t y1 ) { i n t dx = x1 − x0 , dy = y1 − y0 ; i n t i n c r E = 2 ∗ dy , incrNE = 2 ∗ ( dy − dx ) ; i n t d = 2 ∗ dy − dx , x = x0 , y = y0 ; do something ( x , y ) ; while ( x < x1 ) { i f ( d > 0 ) { d += incrNE ; ++y ; } else d += i n c r E ; do something (++ x , y ) ; } } / / r u f t do something ( x , y ) m i t a l l e n ( x , y ) auf , / / d i e einen g e r a s t e r t e n A c h t e l k r e i s um den Ursprung b i l d e n void c i r c l e ( i n t r a d i u s ) { i n t d e l t a E = 3 , deltaSE = −2 ∗ r a d i u s + 5 ; i n t d = 1 − radius , x = 0 , y = radius ; do something ( x , y ) ; while ( x < y ) { i f ( d < 0 ) d += d e l t a E ; else { d += deltaSE ; deltaSE += 2 ; −−y ; } d e l t a E += 2 ; deltaSE += 2 ; do something (++ x , y ) ; } }
8
DATENSTRUKTUREN
8 8.1
30
Datenstrukturen Disjunkte Mengen (Union-Find)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
# include # include
8.2
Heap
In der STL gibt es make heap, is heap, sort heap, push heap und pop heap. Achtung: Diese Funktionen stellen das ¨ großte Element an die Spitze des Heaps. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
/ / h i e r m i t i n t , aber es r e i c h t , wenn o p e r a t o r < d e f i n i e r t i s t void l i f t ( v e c t o r & v , i n t i ) { for ( int j ; i > 0; i = j ) { j = ( i − 1) / 2; i f ( ! ( v [ j ] < v [ i ] ) ) break ; swap ( v [ i ] , v [ j ] ) ; } } void s i n k ( v e c t o r & v , i n t i ) { for ( i n t j ; ( j = 2 ∗ i + 1) < i n t ( v . size ( ) ) ; i = j ) { i f ( j + 1 < i n t ( v . s i z e ( ) ) && v [ j ] < v [ j + 1 ] ) ++ j ; i f ( ! ( v [ i ] < v [ j ] ) ) break ; swap ( v [ i ] , v [ j ] ) ; } }
8.3
Fenwick-Baum
1 2 3
# include
4 5 6 7 8 9 10 11
/ / v [ i ] += k void i n c r ( v e c t o r & a , i n t i , i n t k ) { a [ i ] += k ; while ( i > 0 ) { i &= i − 1 ; a [ i ] += k ; }
8
12 13 14 15 16 17 18 19 20 21
DATENSTRUKTUREN
} / / Summe von a [ 0 ] b i s a [ i ] ( i n k l . ) i n t g e t ( v e c t o r & a , i n t i ) { int r = a [ 0 ] ; while (++ i < i n t ( a . s i z e ( ) ) ) { r −= a [ i ] ; i |= i − 1; } return r ; }
8.4 8.4.1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
Trie mit verketteter Liste
struct t r i e { s t r u c t t r i e ∗ next , ∗down ; char l e t t e r ; } node [ 1 0 0 0 0 0 0 ] ; / ∗ g g f . Anzahl anpassen ∗ / i n t nodes = 0 ; / ∗ so macht man a l l e T r i e s u n g u e l t i g ∗ / s t r u c t t r i e ∗ r o o t = NULL ; / ∗ so l o e s c h t man einen e i n z e l n e n T r i e ∗ / / ∗ A u f r u f m i t add(& r o o t , s t r ) ; g i b t t r u e zurueck , wenn Wort noch n i c h t vorhanden war ∗ / i n t add ( s t r u c t t r i e ∗∗ r o o t p p , char ∗word ) { s t r u c t t r i e ∗p , ∗∗ prev pp ; i n t n = nodes ; do { f o r ( prev pp = r o o t p p ; ( p = ∗ prev pp ) ! = NULL && p−>l e t t e r < ∗word ; prev pp = &(p−>n e x t ) ) {} i f ( p == NULL | | p−>l e t t e r ! = ∗word ) { p = node + nodes ++; p−>n e x t = ∗ prev pp ; p−>down = NULL ; p−>l e t t e r = ∗word ; ∗ prev pp = p ; } r o o t p p = &p−>down ; } while ( ∗ word + + ) ; r e t u r n n < nodes ; } / ∗ A u f r u f m i t check ( r o o t , s t r ) ; g i b t t r u e zurueck , wenn Wort vorhanden ∗ / i n t check ( s t r u c t t r i e ∗ r o o t , char ∗word ) { do { while ( r o o t ! = NULL && r o o t −>l e t t e r < ∗word ) r o o t = r o o t −>n e x t ; i f ( r o o t == NULL | | r o o t −>l e t t e r ! = ∗word ) r e t u r n 0 ; r o o t = r o o t −>down ; } while ( ∗ word + + ) ; return 1; }
8.4.2
2 3 4 5 6 7 8 9 10 11
Trie mit Array
1
Trie
1
31
# define ALPHA ’A ’ struct t r i e { s t r u c t t r i e ∗down [ 2 6 ] ; bool e n d o f w o r d ; } node [ 1 0 0 0 0 0 ] ; / / g g f . Anzahl anpassen i n t nodes = 0 ; / / so macht man a l l e T r i e s u n g u e l t i g s t r u c t t r i e ∗ r o o t = NULL ; / / so l o e s c h t man einen e i n z e l n e n T r i e / / A u f r u f m i t add(& r o o t , s t r ) ; g i b t t r u e zurueck , wenn Wort noch n i c h t vorhanden war bool add ( s t r u c t t r i e ∗∗ r o o t p t r , char ∗word ) { s t r u c t t r i e ∗p ; do {
8
DATENSTRUKTUREN
p = ∗root ptr ; i f ( p == NULL ) { p = node + nodes ++; f o r ( i n t i = 0 ; i < 2 6 ; ++ i ) p−>down [ i ] = NULL ; p−>e n d o f w o r d = f a l s e ; ∗root ptr = p; } r o o t p t r = p−>down + ( ∗ word − ALPHA ) ; } while ( ∗ word + + ) ; r e t u r n p−>e n d o f w o r d ? f a l s e : ( p−>e n d o f w o r d = t r u e ) ;
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
32
} / / A u f r u f m i t check ( r o o t , s t r ) ; g i b t t r u e zurueck , wenn Wort vorhanden bool check ( s t r u c t t r i e ∗ r o o t , char ∗word ) { while ( ∗ word ) { i f ( r o o t == NULL ) r e t u r n f a l s e ; r o o t = r o o t −>down [ ∗ word++ − ALPHA ] ; } r e t u r n r o o t ! = NULL && r o o t −>e n d o f w o r d ; }
8.5
¨ Balancierter binarer Suchbaum (AVL)
1 2 3 4
# include struct a v l t { a v l t ∗ l e f t , ∗ r i g h t , ∗up ; i n t h e i g h t , s i z e , key ;
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
void r e s e t ( ) ; i n t balance ( ) ; a v l t ∗ l e f t r o t ( ) ; a v l t ∗ r i g h t r o t ( ) ; a v l t ∗ f i x u p ( ) ; avl t ∗ latch ( avl t ∗ , avl t ∗); avl t ∗ find ( int ) ; a v l t ∗minimum ( ) ; a v l t ∗maximum ( ) ; a v l t ∗ pred ( ) ; a v l t ∗ succ ( ) ; }; i n l i n e void a v l t : : r e s e t ( ) { h e i g h t = max ( l e f t ! = NULL ? l e f t −>h e i g h t + 1 : 0 , r i g h t ! = NULL ? r i g h t −>h e i g h t + 1 : 0 ) ; s i z e = 1 + ( l e f t ! = NULL ? l e f t −>s i z e : 0 ) + ( r i g h t ! = NULL ? r i g h t −>s i z e : 0 ) ; } i n l i n e i n t a v l t : : balance ( ) { r e t u r n ( r i g h t ! = NULL ? r i g h t −>h e i g h t + 1 : 0 ) − ( l e f t ! = NULL ? l e f t −>h e i g h t + 1 : 0 ) ; } avl t ∗avl t :: leftrot () { a v l t ∗temp = r i g h t ; i f ( ( r i g h t = temp−> l e f t ) ! = NULL ) r i g h t −>up = t h i s ; temp−> l e f t = t h i s ; temp−>up = up ; up = temp ; r e s e t ( ) ; temp−>r e s e t ( ) ; r e t u r n temp ; } avl t ∗avl t :: rightrot () { a v l t ∗temp = l e f t ; i f ( ( l e f t = temp−>r i g h t ) ! = NULL ) l e f t −>up = t h i s ; temp−>r i g h t = t h i s ; temp−>up = up ; up = temp ; r e s e t ( ) ; temp−>r e s e t ( ) ; r e t u r n temp ; } avl t ∗ avl t : : fixup () { i n t b a l = balance ( ) ; i f ( b a l == 2 ) { i f ( r i g h t −>balance ( ) < 0 ) r i g h t = r i g h t −>r i g h t r o t ( ) ; return l e f t r o t ( ) ; } else i f ( b a l == −2) { i f ( l e f t −>balance ( ) > 0 ) l e f t = l e f t −> l e f t r o t ( ) ; return r i g h t r o t ( ) ; } return this ; } a v l t ∗ a v l t : : l a t c h ( a v l t ∗ root , a v l t ∗ parent ) {
8
44 45 46 47 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
33
i f ( r o o t == NULL ) { l e f t = r i g h t = NULL ; up = p a r e n t ; r e s e t ( ) ; r e t u r n t h i s ; } i f ( key < r o o t −>key ) r o o t −> l e f t = l a t c h ( r o o t −>l e f t , r o o t ) ; else i f ( r o o t −>key < key ) r o o t −>r i g h t = l a t c h ( r o o t −>r i g h t , r o o t ) ; r o o t −>r e s e t ( ) ; r e t u r n r o o t −>f i x u p ( ) ;
43
48
DATENSTRUKTUREN
} a v l t ∗ a v l t : : f i n d ( i n t value ) { a v l t ∗temp = t h i s ; while ( temp ! = NULL ) { i f ( v a l u e < temp−>key ) temp = temp−> l e f t ; else i f ( temp−>key < v a l u e ) temp = temp−>r i g h t ; else r e t u r n temp ; } r e t u r n NULL ; } a v l t ∗ a v l t : : minimum ( ) { a v l t ∗temp = t h i s ; while ( temp−> l e f t ! = NULL ) temp = temp−> l e f t ; r e t u r n temp ; } a v l t ∗ a v l t : : maximum ( ) { a v l t ∗temp = t h i s ; while ( temp−>r i g h t ! = NULL ) temp = temp−>r i g h t ; r e t u r n temp ; } a v l t ∗ a v l t : : pred ( ) { a v l t ∗temp = t h i s ; i f ( l e f t ! = NULL ) r e t u r n l e f t −>maximum ( ) ; while ( temp−>up ! = NULL && temp == temp−>up−> l e f t ) temp = temp−>up ; r e t u r n temp−>up ; } a v l t ∗ a v l t : : succ ( ) { a v l t ∗temp = t h i s ; i f ( r i g h t ! = NULL ) r e t u r n r i g h t −>minimum ( ) ; while ( temp−>up ! = NULL && temp == temp−>up−>r i g h t ) temp = temp−>up ; r e t u r n temp−>up ; }
Related Documents
Tcr
May 2020 5
Tcr
October 2019 4
Tcr
November 2019 7
Tcr Chapter3
November 2019 4
Struttura Tcr, Rag, Catene Alfa E Beta Dei Tcr
November 2019 5