[Informatik] Algorithmus

[imported_Tomomo]

Also: Ein Algorithmus soll möglichst immer zu Ende gehn. Also alle Eingaben sollen irgendwann stoppen.

Wir haben heute in der Informatikstunde einen Versuch gemacht:

http://egomanie.pytalhost.com/infoalgo.jpg

versuchsbeschreibung:
1. Des normale Rechteck
2./3./4. Die A-Seite[bzw. die längere Seite] des Rechteckes reduziert sich um die B-Seite[Die kürzere Seite]

Ende: Am Ende hat der Rest gleichlange Seiten. D.h. Das Viereck ist jetzt ein Qudrat und hat gleichlange Seiten. D.h. es kann sich keine seite mehr um die andere reduzieren.

Bedingung:
*Die kürzere Seitenlänge B verändert sich nicht, solange die Seitenlänge A länger als B bleibt.
*Die längere Seitenlänge A wird so lange um die kürzere Seitenlänge B reduziert, bis sie selbst kürzer als B ist.



So soviel dazu.
Meine Aufgabe ist zu überlegen, ob dieses Verfahren IMMER endet.

es gibt die Möglichkeiten:

1. Das Verfahren kommt immer zu einem Ende + Begründung

oder aber

2. Das Gegenteil + Abmessung eines Rechteckes, bei dem das Verfahren nie hält.


Ich denke, das Verfahren kommt immer zu nem Ende im Bezug auf den ggT[größten gemeinsamen Teiler?] und den kgV [kleinsten gemeinsamen Vielfachen?].. mathe 6. klasse :o
Aber ich weiß nich, wie ich das begründen oder ausdrücken soll. @_@
es fehlt nur noch ein Teil zum lösen dieses puzzles, aba ich finds net.. hilfäää >-<

[Anne]

Für natürliche Zahlen entspricht diese Aufgabe dem Euklidischen Algorithmus zur Berechnung des ggT, der terminiert immer. Für reelle Zahlen versuch's mal mit A=1, B=Goldener Schnitt, das sollte sich nur immer weiter 0 annähern.