Vorrunde

Die SOI ist ein Programmierwettbewerb für Jugendliche unter 20 Jahren. In verschiedenen Runden löst Du knifflige Aufgaben und lernst effizientes Programmieren. Löse den Fragebogen und nimm teil – vielleicht reist Du im nächsten Sommer an die Internationale Informatikolympiade in Taiwan!

Diese Aufgaben vermitteln dir einen ersten Eindruck der Aufgabenstellungen der Informatik-Olympiade. Die offizielle erste Runde startet dann am 1. Oktober 2013. Wenn du unten deine E-Mail-Adresse angibst, dann informieren wir dich rechtzeitig, wenn es losgeht.

Nun kannst du an den 12 Fragen herumknobeln und anschliessend deine Lösung korrigieren lassen. Zu jeder Frage erhältst du auch die korrekte Lösung mit einer kurzen Erklärung. Viel Erfolg!

1. Du befindest dich an der Stelle im Labyrinth, die mit einem Pfeil markiert ist (Blick in Richtung Pfeilspitze). Mit welcher Strategie kommst du am schnellsten aus dem Labyrinth?
Labyrinth

(a) Immer der linken Wand folgen
(b) An jeder Kreuzung geradeaus gehen
(c) Immer der rechten Wand folgen

2. Welche dieser drei Vorschriften gibt nicht in jedem Labyrinth einen eindeutigen Weg vor?

(a) Immer der linken Wand folgen
(b) An jeder Kreuzung geradeaus gehen
(c) Immer der rechten Wand folgen

3. Angenommen, es gibt mindestens einen erreichbaren Ausgang, unter welcher Bedingung findet man ihn immer mit einer der oben stehenden Strategien?

(a) Wenn alle Wände miteinander verbunden sind
(b) Wenn alle Wege miteinander verbunden sind
(c) Wenn alle Ausgänge mit Wegen verbunden sind

4. Wie viele zweistellige Zahlen mit Quersumme 9 gibt es? (99 hat Quersumme 18!)

(a) 8
(b) 9
(c) 10
(d) 11

5. Du kannst mit einer Waage jeweils zwei Gegenstände vergleichen. Wie oft musst du wägen, um den leichtesten von n Gegenständen zu finden?

(a) n2
(b) n
(c) n-1
(d) n/2

6. Wie viele Vergleiche brauchst du maximal um zu entscheiden, ob die Gegenstände ihrer Grösse nach sortiert sind?

(a) n2
(b) 2n
(c) n
(d) n-1

7. Welche Zahlen druckt der Algorithmus im Kasten (print)?
1: X = 1
2: X = X+2
3: PRINT X
4: X = X-1
5: IF X≠6 GOTO 2
6: END

(a) 1,2,3,4,5,6
(b) 3,4,5,6
(c) 3,4,5,6,7
(d) 3,5,7

8. Was passiert, wenn man Zeile 4 (X = X-1) abändert zu X = X+1?

(a) Es werden weniger Zahlen als in Aufgabe 7 gedruckt.
(b) Es werden genau gleich viele Zahlen gedruckt.
(c) Es werden mehr Zahlen als in Aufgabe 7 gedruckt.

9. Zeichne ein beliebiges, geschlossenes Polygon auf ein Blatt Papier. Wähle nun zwei Punkte im Innern so, dass keine Ecke des Polygons auf der Geraden durch beide Punkte liegt. Wie oft schneidet diese Gerade das Polygon zwischen den gewählten Punkten? (n ∈ N0, die ganzen Zahlen ≥ 0)

(a) 1 mal
(b) 2n mal
(c) 2n + 3 mal

10. Wie musst du die zwei Punkte platzieren, dass 7 Schnittpunkte möglich sind?

(a) Sie müssen beide im Innern des Polygons liegen
(b) Sie müssen auf verschiedenen Seiten der Polygonlinie liegen
(c) Sie müssen beide ausserhalb des Polygons liegen

11. Ein reguläres n-Eck kann nicht in weniger als x Dreiecke zerlegt werden.

(a) x = n
(b) x = n-1
(c) x = n-2

12. Ein Programm löst Aufgaben mit einer Schwierigkeit n in n! (n Fakultät) Sekunden. Wie lange dauert das Lösen einer Aufgabe mit Schwierigkeitsgrad n = 12?

(a) 15 Minuten
(b) 15 Wochen
(c) 15 Monate
(d) 15 Jahre


Vorname:
Nachname:
E-Mail:
Wenn du hier deine E-Mail-Adresse angibst, schicken wir dir die Auswertung auch per E-Mail zu und informieren dich rechtzeitig über den Start der SOI 2014. Wir geben deine Adresse natürlich nicht weiter.