Einführung - TU München

 Documents

 63 views
of 22
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
ACM ICPC Praktikum Prof. Dr. Christian Scheideler TU München ACM International Collegiate Programming Contest ã Hochschulinterner Wettbewerb ã Regionaler…
Share
Transcript
ACM ICPC Praktikum Prof. Dr. Christian Scheideler TU München ACM International Collegiate Programming Contest • Hochschulinterner Wettbewerb • Regionaler Wettbewerb in Universidade Nova de Lisboa, Portugal, Mitte November • Weltfinale 2006: San Antonio, Texas Übersicht • Einführung • Backtracking und • Datenstrukturen Branch-and-Bound • Graphalgorithmen • Zeichenketten • Dynamische • Sortieren Programmierung • Arithmetik und Algebra • Geometrie • Kombinatorik und Buch: Zahlentheorie S. Skiena und M. Revilla Programming Challenges Springer Verlag, 2003 Anforderungen • Anwesenheit im Kurs • Korrekte Lösung der wöchentlichen Programmieraufgaben (in Teams bis zu 3 Personen) Einreichung der Lösungen: • http://acm.uva.es/p/ • Email an scheideler@in.tum.de ICPC Problemarchiv • http://acm.uva.es/p/ • Users->Register • Users->Submit your Code • Statistics->Problem Status • Statistics->Authors Ranklist • Klassifizierung: http://www.cs.uleth.ca/%7Echeng/contest/hints.html Feedback • Akzeptiert (AC): Herzlichen Glückwunsch! • Präsentationsfehler (PE): Ausgabe richtig, aber nicht im richtigen Format • Akzeptiert (PE): Ein geringfügiger Präsentationsfehler, aber das Problem wird trotzdem noch als gelöst betrachtet. • Falsche Antwort (WA): Einer oder mehrere Fälle sind falsch gelöst worden. • Compilerfehler (CE): Die Fehlermeldungen werden zurückgeschickt. • Laufzeitfehler (RE): Das Programm brach während der Abarbeitung mit einem Fehler ab. Die Fehlermeldung wird zurückgeschickt. Feedback • Zeitlimit überschritten (TL): Das Programm hat zu lange gebraucht. • Speicherlimit überschritten (ML): Das Programm hat zuviel Speicher gebraucht. • Ausgabelimit überschritten (OL): Zuviel Ausgabetext (deutet auf Endlosschleife) • Beschränkte Funktion (RF): Benimm Dich! • Einreichungsfehler (SE): User ID oder Problem ID inkorrekt. Programmiersprachen Erlaubte Programmiersprachen: • C, C++, Pascal, Java Ein- und Ausgabe über Standard I/O • C: while (scanf(“%ld”, &x)!=EOF) … printf(“%ld\n”,y); • C++: while (cin >> x) … cout << y << endl; • Pascal: while not eof do … readln(x); … writeln(y); Tipps zum Programmieren Wichtige Kriterien: • Zeitaufwand und Platzaufwand, aber • vor allem Programmieraufwand! • Schreib zunächst Kommentare! • Dokumentiere jede Variable! • Verwende symbolische Konstanten! • Vermeide komplexe Datentypen (Objekte, Pointer)! • Verwende Subroutinen! • Verwende Debugging-Anweisungen klug! (bedingte Ausgabe bei Problemen, gib Erläuterungen zu Ausgabewerten) Elementare Datentypen • char, int, long, real, double,... • Einfache Arrays (A[i]): oftmals vorzuziehen gegenüber Pointerstrukturen - mit Bereichsüberprüfung - etwas größer als notwendig • Mehrdimensionale Arrays (A[i][j]): gut für Gitter und Matrizen • Structs: Nur sinnvoll, wenn Arrays nicht anwendbar (besser typedef int point[2]; als struct point { int x, y; };) Das 3n+1 Problem Betrachte den folgenden Algorithmus zur Berechnung einer Folge von Zahlen: Starte mit einer natürlichen Zahl n. Falls n gerade ist, teile durch 2. Falls n ungerade ist, multipliziere sie mit 3 und addiere 1 hinzu. Wiederhole diese Regel für die neue Zahl, bis die Zahl 1 erreicht ist. Die folgende Folge ergibt sich zum Beispiel für n=22: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 Man nimmt an, dass der Algorithmus für alle natürliche Zahlen terminiert, aber bisher konnte noch niemand einen Beweis dafür finden. Zumindest ist bekannt, dass der Algorithmus für alle Zahlen bis 1.000.000 terminiert. Für eine Zahl n sei die Folgenlänge von n die Anzahl der Zahlen, die erzeugt werden bis und inklusive 1. D.h. im obigen Beispiel ist die Folgenlänge 16. Gib für beliebige zwei Zahlen i und j die maximale Folgenlänge für alle Zahlen zwischen i und j (inklusive i und j) aus. Das 3n+1 Problem Eingabe: Eine Folge von Zahlenpaaren, ein Paar pro Zeile. Alle Zahlen sind kleiner als 1.000.000 und größer als 0. Ausgabe: Für jedes Zahlenpaar i und j, gib i und j und die maximale Folgenlänge für i und j aus. Diese drei Zahlen sollen durch ein Leerzeichen getrennt sein und in einer Zeile stehen, mit einer Zeile pro Zahlenpaar. Beispiel: 1 10 1 10 20 100 200 100 200 125 Erster Versuch 1. #include 2. void main() { 3. unsigned long a, b, c, d, max, i; 4. 5. while (cin >> a >> b) { 6. max = 0; 7. for (c=a; c<=b; c++) { 8. i = 1; 9. d = c; 10. while (d!=1) { 11. if (d%2) d = 3*d+1; 12. else d = d/2; 13. i = i+1; 14. } 15. if (i>max) max = i; 16. } 17. cout << a << " " << b << " " << max << "\n"; 18. } 19. } Das 3n+1 Problem • Das Problem ist kniffeliger als es scheint! • Lies die Spezifikation genau!!! Fallstricke: • Es ist nicht vorgegeben, dass i 2. #define MAXDIGITS 100 /* max length */ 3. typedef struct { 4. char digits[MAXDIGITS]; /* number */ 5. int lastdigit; /* max digit */ 6. } bignum; Bignum 1. print_bignum(bignum *n) 2. { 3. int i; 4. for (i=n->lastdigit; i>=0; i--) 5. printf("%c",'0'+ n->digits[i]); 6. printf("\n"); 7. } Bignum 1. int_to_bignum(int s, bignum *n) 2. { 3. int i; /* counter */ 4. int t; /* int to work with */ 5. for (i=0; idigits[i] = (char) 0; 6. n->lastdigit = -1; 7. t = abs(s); 8. while (t > 0) { 9. n->lastdigit ++; 10. n->digits[ n->lastdigit ] = (t % 10); 11. t = t / 10; 12. } 13. if (s == 0) n->lastdigit = 0; 14. } Bignum 1. add_bignum(bignum *a, bignum *b, bignum *c) 2. { 3. int carry; /* carry digit */ 4. int i; /* counter */ 5. initialize_bignum(c); 6. c->lastdigit = max(a->lastdigit,b->lastdigit)+1; 7. carry = 0; 8. for (i=0; i<=(c->lastdigit); i++) { 9. c->digits[i] = (char) (carry+a->digits[i]+b->digits[i]) % 10; 10. carry = (carry + a->digits[i] + b->digits[i]) / 10; 11. } 12. zero_justify(c); 13. } Die Katze im Hut Eine clevere Katze spaziert in einen unordentlichen Raum, in dem sie aufräumen muss. Anstatt die Arbeit alleine zu tun, benutzt sie ihre kleineren Hilfskatzen. Diese hält sie in ihrem Hut. Jede Hilfskatze besitzt auch eine Menge von kleineren Hilfskatzen in ihrem eigenen Hut, und so weiter, bis die Hilfskatzen eine kleinstmögliche Größe erreichen. Diese kleinsten Katzen haben keine weiteren Katzen in ihrem Hut und müssen daher die Aufräumarbeit leisten. Die Anzahl Katzen im Hut einer Katze ist eine Konstante N. Die Größe dieser Katzen ist 1/(N+1) mal die Größe der Katze, in deren Hut sie sind. Die kleinsten Katzen haben die Größe 1 und alle Größen sind natürliche Zahlen. Gegeben die Größe der Anfangskatze und die Anzahl der arbeitenden Katzen (der Größe 1), bestimme die Anzahl der Katzen, die nicht arbeiten müssen (also Katzen der Größe größer als 1) und die Summer der Höhen aller Katzen. Die Katze im Hut • Eingabe: Eine Folge von Zahlenpaaren, ein Paar pro Zeile. Die erste Zahl gibt die Größe der Anfangskatze an und die zweite Zahl repräsentiert die Anzahl der arbeitenden Katzen. Ein Paar mit Nullen zeigt das Ende der Eingabe an. • Ausgabe: Für jede Eingabezeile (Katze-in-Hut Spezifikation), gib die Anzahl der Katzen aus, die nicht arbeiten, gefolgt von einem Leerzeichen, gefolgt von der Summe der Größen aller Katzen. Für jede Eingabezeile soll eine Ausgabezeile verwendet werden, nur nicht für “0 0”, für das die Eingabe terminiert. Die Katze im Hut • Beispieleingabe: 216 125 5764801 1679616 00 • Beispielausgabe: 31 671 335923 30275911
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks