BWINF – Junioraufgabe 1 – Junioraufgabe 2

View Github Repository Open presentation in a new window

jhbruhn

See all presentation from jhbruhn

BWINF – Junioraufgabe 1 – Junioraufgabe 2

0 0

BWINF-Presentation

Grüße an sgade ihm seine notification.

On Github jhbruhn / BWINF-Presentation

BWINF

Bundeswettbewerb des Todes für Informatik

Warum?

Ruhm Ehre Oder auch nicht...

Junioraufgabe 1

Was ist die Aufgabe?

"Song" mit zufälligen Silben, zufälliger Anzahl von Strophen und Versen darin etc. generieren.

Beispiel:

ko kop di ko ce cep di ce ce cep di ce yeah!

Wie?

Ganz einfach...vielleicht.Anzahl von Strophen zufällig auswählen (z.B. zwischen 2 und 6) ->int strophenZahl Anzahl von Versen zufällig auswählen (z.B. zwischen 2 und 6) ->int versZahl boolean, ob die Länge von Strophen variieren soll ->boolean abwechselndeLaenge Strophen generieren

Strophe generieren

Eine silbenAnzahl von Silben pro Vers zufällig auswählen (z.B. zwischen 2 und 5) 2 zufällige Konsonanten und 3 Vokale zur Nutzung in den Silben auswählen (zufällig) versZahl Verse generieren mit silbenAnzahl Silben und gewählten Buchstaben Am Ende mit 50% Wahrscheinlichkeit einen lustigen "Shout" hinzufügen (z.B. yo man! oder erdbeermarmelade!)

Vers generieren

Eine zufällige Silbe aus der Auswahl von Konsonanten und Vokalen generieren (z.B. ci) silbenAnzahl mal die Silbe aneinanderrehein p di an den String anfügen silbenAnzahl - 1 mal die Silbe anhängen, nur um einen vermindert damit die Gesamtanzahl ungerade is

Fertig

ko kop di ko ce cep di ce ce cep di ce erdbeermarmelade! ji ji jip di ji ji ja ja jap di ja ja ci ci cip di ci cicomposed by Dieter Bohlen

Junioraufgabe 2

  • Gegeben ist ein    Zollstock. 
  • Er besteht aus 10 Segmenten und einem Loch zum aufhängen.
  • Ein Stoffbeutel kann 2 Segmente in Verlängerung aufnehmen.
  • Der Zollstock wird 62-mal zufällig in den Beutel getan.
  • Ist eine Stellung des Zollstocks doppelt vorhanden?

Herangehensweise

  •  Da der Beutel zwei Elemente in der Länge zulässt lassen sich mögliche Lösungen in das  Verhältnis der Segmente auf der einen zu den Segmenten auf der anderen Seite aufteilen. 
  •  Die verschiedenen Lösungen müssen gespiegelt werden und gleiche aussortiert werden.
  • Hat man alle möglichen Lösungen und gibt es weniger oder genau 61 (62 - 1) so hat  Ralucas Verlobter recht. Sonst hat er nur evtl. Recht. 

Deutung

  • Der Zollstock hat ein Aufhängeloch: Jede Lösung hat eine Alternative.
  • Daher: 66 Lösungen *2 = 132
  • Ralucas Verlobter kann Recht haben, muss er aber nicht: 
  • Zufällig sind 2 gleiche Kombinationen möglich.

Aufgabe 1

  • Gegeben ist eine gerundete rationale Zahl n.
  • Gesucht ist ein Bruch mit möglichst kleinem Zähler und Nenner, dessen Wert möglichst nah an n liegt.

Beispiel

n = 1,857143 
1.Versuch
1857143/1000000
=> Zu großer Zähler und Nenner
2. Versuch
13/7
= 1,8571428571428571428571428571429
=> Möglichst kleiner Zähler und Nenner und nah n

Herangehensweise

Gesucht ist ein Näherungsverfahren.
Durch Recherche wurde folgendes Prinzip erarbeitet:
1. Zunächst wird der Bruch
 erstellt. Dabei wird x so gewählt, 
2. Aus dem daraus entstehenden Bruch wird nun ein Kettenbruch generiert (euklidischer Algorithmus).
3. Aus dem Kettenbruch lassen sich Näherungsbrüche generieren.
4. Welcher Näherungsbruch wird gewählt?

Beispiel

 n = 1.414214 
1. Bruch natürlicher Zahlen:
 1414214 /1000000
2. Kettenbruch:

Beispiel

1. Annäherung:
 
=  3/2 = 1,5
2. Annäherung
= 7/5 = 1,4
...

Beispiel

9. Annäherung
= 1970 / 1393 = 1.4142139267767408470...
=> Die 9. Annäherung ist die erste Annäherung, bei der alle Nachkommastellen gerundet mit denen von n übereinstimmen.
Somit ist die 9. Annäherung die erste akzeptable.
Die erste akzeptable Annäherung sollte gewählt  werden, da so Zähler und Nenner bei ausreichender Präzision möglichst klein bleiben.

Aufgabe 3:Vortänzer

Ein Roboter tanzt vor, ein zweiter soll den "Tanz" imitieren
Für das Imitat gibt es Strafpunkte:
I. Für jedes Zeichen des Programmes 3 Punkte
II. Für jede Längeneinheit Abstand pro Sekunde einen Punkt
Aufgabe:
Imitate mit passenden Strafpunkten finden
Programm zur Berechnung der Strafpunkte schreiben

Programmiersprache der Roboter

"F" - Vorwärts
"B" - Rückwärts
"l" - 45° links drehen
"r" - 45° rechts drehen
"-" - nichts machen
"nBefehlsfolge." Führt Befehlsfolge n mal aus
FFrFrrB--3B.
4F. = FFFF

OriginalProgramme

Tanzprogramm Strafpunktgrenze 4FFFFrr. 21 FrrFllFrrFrrrFF 20 lFrrFFllFFFrrFllFrrFF 50

Programm 1

4FFFFrr.
FFFF zu 4F. machen
44F.rr. 
7 Zeichen * 3 Strafpunkte/Zeichen
= 21 Strafpunkte

Programm 2

FrrFllFrrFrrrFF 
Beim Testen des Berechnungsalgorithmus kam heraus:
F
ist die Lösung des Problems
Strafpunkte: 19P

Programm 3

lFrrFFllFFFrrFllFrrFF 
Da der Roboter eigentlich bloß im Zick-Zack gerade ausfährt:
6F-. 
führt zu insgesamt
44 Strafpunkten

BerechnungsProgramm

I. Schleifen aus dem Code entfernen
II. Sowohl Original und Imitat parallel simulieren
III. Nach jedem Schritt Strafpunkte berechnen
IV. Strafpunkte durch Programmlänge dazurechnen

Aufgabe 5

Lustiges durch die Gegend bieten gegen einen dämlichen Feind.

Das feindliche Programm

Ganz einfach: IMMER 100€ BIETEN1!1!!1!!!11!111!!11

Was macht man?

  • Im ersten Schritt 1€ bieten.
  • Danach immer 101€ bieten.
  • Profit.

Warum?

Man wird zwar im ersten Zug vom Feind überboten, überbietet danach jedoch immer den Feind, wodurch man gezwungenermaßen gewinnt.