Das Wechselwegnahmeverfahren

Streichhölzer wegnehmen

Auf dem Tisch liegen zwei Reihen von Streichhölzern. Von der jeweils längeren Reihe sollen so viele weggenommen werden, wie in der kürzeren vorkommen. Aufgehört wird, wenn beide Streichholzreihen gleich lang sind.

Aufgabe 1

Führe das Verfahrens mit verschiedenen Streichholzreihen durch und notiere jeweils die Anzahl der Streichhölzer, die am Schluss in jeder Reihe liegen.

• 15; 7
• 10; 21
• 3; 20

Der Wechselwegnahme-Algorithmus

Wenn man die Streichholzreihen durch Zahlen darstellt, so lässt sich das oben beschriebene Wechselwegnahmeverfahren durch den folgenden Algorithmus beschreiben:

Aufgabe 2

(a) Was leistet der Algorithmus? Formuliere eine erste Vermutung.

(b) Wie verhält sich der Algorithmus, wenn man für x und y dieselbe Zahl übergibt?

(c) Führe weitere Tests durch. Welche Vermutung ergibt sich jetzt?

• 15; 10
• 10; 6
• 12; 18

(d) Wie verhält sich der Algorithmus, wenn man für x oder y eine 0 übergibt?

(e) Formuliere abschließend möglichst präzise, was der Algorithmus leistet.