Algorithmus - Schleifeninvariante

Neue Frage »

prinzschleifer Auf diesen Beitrag antworten »
Algorithmus - Schleifeninvariante
Da ich es irgendwie nicht hinbekomme mich beim Informatik Board anzumelden, post ich hier mal eine Aufgabe:

So, die Aufgabe befindet sich im Anhang.

Nun müssen wir erstmal rausfinden, das dieser Algorithmus macht. Dazu hab ich einfach mal Beispielwerte genommen, es kommt bei mir aber nichts sinnvolles für raus.

Hier meine Eingaben: a = 6 und b = 9

Bei einer Wertetabelle für jeden Schleifendurchlauf hab ich sowas bekommen

(minus als seperator)
0 1 6 9 0
1 1 3 81 1
2 81 1 9^4 0
3 81 0 9^6 0

Nunja, das Ergebnis soll nun 81 sein. Leider finde ich keine Verbindung zwischen den beiden?

Brauche dringend Hilfe!
Reksilat Auf diesen Beitrag antworten »
RE: Algorithmus - Schleifeninvariante
Eigentlich sollte ja laut Algorithmus sein, das stimmt aber mit Deiner Tabell nicht überein.

Wenn man eine Vermutung über den Zusammenhang von Eingabewerten und Ausgabewert finden will, benötigt man außerdem mehr als ein Beispiel.

Edit: Und wurde auch falsch berechnet, die Lösung lautet dann 9^4+9^2.

Tipp: Schau Dir mal die Binärdarstellung von a an.
 
 
prinzschleifer Auf diesen Beitrag antworten »

Ah okay, also ich bin auch grade auf meine Fehlergestoßen.

Ich hab das ganze jetzt mit a=3 und b=9 gemacht, weil mich die alten Werte irgendwie genervt haben. geschockt

So, was ich rausgefunden habe ist das 1 mod 2 = 1 ergibt, da 2x0 + 1 = 1 ist. Nunja, und dann noch die Potenzregeln, dass ist.

So, nun schau ich mir mal die Binärschreibweise von a an, diese wäre für a=3


Mit den obigen Parametern hab ichs nochmal durchgerechnet und bin auf folgende Tabelle gekommen, die hoffentlich richtig ist.


0 1 3 9 1
1 9 1 9^2 1
2 9^3 0 9^4 0

Also kommt für raus, was wiederum im Binärschreibweise folgendes wär:

Idee: Könnte es vielleicht sein?

Ich glaube schon. Weiter testen.
Reksilat Auf diesen Beitrag antworten »

Deine Idee ist richtig.

, denn
prinzschleifer Auf diesen Beitrag antworten »

Gut, dazu sollen wir dann noch eine Schleifeninvariante angeben. Dies ist relativ einfach, da man lediglich einen Zusammenhang erkennen muss. Dazu schaut man in die Tabelle und findet folgenden Zusammenhang:



sei eine Aussage, die ich jetzt durch vollständige Induktion beweisen soll muss.

Also I.A. :
Siehe Initalisierung:

I.S: Zeige: i => i+1


Laut Algorumpf:


Also



Laut Algorumpf:

und


Also




Wenn wäre. Wäre meine Induktion fertig.
Ist meine Annahme den richtig, bzw. wo hab ich was falsch gemacht?

Laut Voraussetzung:
Reksilat Auf diesen Beitrag antworten »

Funktioniert, aber es ist (kleines x!)

Danach braucht man nur noch, dass für alle z immer gilt.
prinzschleifer Auf diesen Beitrag antworten »

Gut, ich rechne nochmal den letzen Teil:





So jetzt hier ein kleines Problem:

Im Algorumpf steht nur:


heißt das automatisch dann:


Wenn das gilt steht da:



Da:

// Geht das denn überhaupt so, bei einer Addition darf man das ja nicht einfach so machen?

wegen:



Also:

q.e.d
Reksilat Auf diesen Beitrag antworten »

Zitat:

heißt das automatisch dann:


Ja, wurde ja gerade im vorherigen Schleifendurchlauf so definiert.

Zitat:


// Geht das denn überhaupt so, bei einer Addition darf man das ja nicht einfach so machen?

Deshalb ersetzen wir hier das Plus auch lieber durch ein Mal Big Laugh
prinzschleifer Auf diesen Beitrag antworten »

Ich Fisch!

Vielen, vielen, vielen Dank.

So nun die letzte Aufgabe - eine äußerst kleine.

Also: wird ja auf die nächste ganze Zahl aufgerundet. Nun sollen wir argumentieren was passieren würde wenn die Zahl abgerundet werden würde.

Meine Antwort wär folgedens:
Unter Umständen könnte es passieren, dass der Algorithmus nicht zu einem korrekten Ergebnis kommen würde, da der Exponent noch nicht null erreicht hat, da es noch nicht genug Schleifen durchläufe gab.

???
Reksilat Auf diesen Beitrag antworten »

Einfach ausprobieren (vorzugsweise mit a als einer Zweipotenz, in den anderen Fällen sollte es klappen) Wink
prinzschleifer Auf diesen Beitrag antworten »

Ja, wenn dann wird es keine Rundungsfehler geben, weil es ja dann automatisch eine ganze Zahl ist.

Wie hab ich das den zuverstehen, bedeuten die Striche nach unten, dass aus 2,64 = 2 wird?

Anders würde es keinen Sinn ergeben.


Also durch Test hab ich rausgefunden, dass manchmal einfach nicht null wird und dadurch zwar die Schleifeninvariante erfüllt wird, aber nicht das Ergebnis hat. Ist das ein Argument?
Reksilat Auf diesen Beitrag antworten »

War natürlich Unsinn was ich geschrieben habe, im Fall a=2^r ändert sich ja durch die Veränderung der Gaußklammer nichts. In allen anderen Fällen dagegen gibt es vielleicht Probleme:
Ansatz , wobei , dann ist beim Abrunden .

Nun sieht es für mich so aus, als wenn am Ende trotzem immer gilt, der Algorithmus würde also weiterhin funktionieren. Du hast es doch implementiert... Ausprobieren!

Gute Nacht! Tanzen
prinzschleifer Auf diesen Beitrag antworten »

Mein Prof hat irgendwas gemeint mit der Logarithmus für die Zahl 0 ist nicht definiert, aber a darf ja nach Vorraussetzung nicht die Null sein.

Also ist die Antwort auf die Frage, dass sich nichts verändert und dass der Exponent . Gibt es dafür eine logische Begründung. Warum dann überhaupt auf oder abrunden?
Reksilat Auf diesen Beitrag antworten »

dieser Logarithmus kann also gar nicht existieren.

Für gibt es natürlich eine logische Erklärung, denn es ist die rekursive Definition und mit dem obigen Ansatz sieht man auch warum man spätestens nahc n Schritten auf 0 kommt.
prinzschleifer Auf diesen Beitrag antworten »

Gut, also zum letzen Mal zur Klarheit (will nunmal meine Punkte in dem Blatt):

Nach n Schritten ist der Exponent, also auf null reduziert worden, da
gilt. Deswegen hat das aufrunden (ceil) bzw. abrunden (floor) keine Auswirkung auf das Ergebnis des Algorithmus.

Erklärung so einleuchtend?
Reksilat Auf diesen Beitrag antworten »

Ich kann Dir den Algorithmus erklären. Wie Du es dann verständlich aufschreibst ist Deine Sache. Wenn Du alles verstanden hast, solltest Du auch wissen, was alles zur Lösung dazugehört.
Ciao. Prost
JuliusSpringer Auf diesen Beitrag antworten »

Der nette Herr wollte lediglich wissen ob seine Antwort richtig ist und ja, deine Antwort ist einleuchtend und richtig! Hammer
Reksilat Auf diesen Beitrag antworten »

@JuliusSpinner:
Lies Dir mal durch was in diesem Thread steht! Er wollte nicht wissen, ob seine Antwort richtig ist, denn dies haben wir ja schließlich zusammen erarbeitet, sondern ob das was er da geschrieben hat ausreicht.
Ich helfe gerne bei Fragen des Verständnis, aber wenn ich der Meinung bin, an einem Punkt angelangt zu sein, an dem prinzschleifer allein weiterarbeiten kann, so solltest Du dies akzeptieren. Gib Deinen Senf dazu, aber lass mich in Ruhe!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »