• Als Spam markieren
• Beitrag melden

• 
  Diese Gruppe Alles

• Archiv
• RSS-Feeds

• Kontakt
• Hilfe
• Impressum
• Datenschutz

Fallschirm-Roboter am Kreis

Zwei Roboter springen mit Fallschirmen aus einem Flugzeug auf
einen Zahlenkreis ab (und landen in zwei verschiedenen Punkten).
Der Zahlenkreis besteht aus den Zahlen modulo M, wobei M eine
grosse ganze Zahl (M>1.000) ist.  Die Roboter kennen den Wert
von M nicht.
Beide Roboter lassen ihren Fallschirm auf ihrem Landepunkt
liegen, und beginnen ihr Programm abzuarbeiten.  Beide Roboter
arbeiten exakt nach dem selben Programm, und sie arbeiten genau
einen Befehl pro Minute ab.

Das Programm besteht aus einer endlichen Anzahl von Zeilen, die
vier verschiedene Befehle enthalten koennen. Die Befehle sind
durchnumeriert (so wie anno dazumal in BASIC):

NACH LINKS:
Der Roboter bewegt sich einen Schritt nach links,
vom momentanent Punkt x nach x-1 (modulo M)

NACH RECHTS:
Der Roboter bewegt sich einen Schritt nach rechts,
vom momentanent Punkt x nach x+1 (modulo M)

GOTO n:
Die Abbarbeitung des Programms springt zur Zeile
mit der Nummer n.

IF FALLSCHIRM THEN (Befehl):
Falls der Roboter gerade auf einem Fallschirm steht,
dann wird der Befehl (Befehl) ausgefuehrt.
(Und falls nicht, laeuft das Programm mit der
naechsten Zeile weiter.)

Ziel der Roboter ist es, einander zu treffen. (Sie koennen
entweder im selben Punkt stehen bleiben, oder einander begegnen,
indem einer von x nach x+1 und der andere gleichzeitig von x+1
nach x laeuft.)


Frage:
Gibt es ein Programm, mit dem die Roboter auf jeden Fall ihr
Ziel erreichen werden?

___________________________________________________________
Gerhard J. Woeginger       http://www.win.tue.nl/~gwoegi/

Antworten