Analyse und Entwerfen von Algorithmen

[witch doctor]

Ich studiere gerade Wirtschaftsinformatik im ersten Semester.

Dort nehmen wir unter anderem in der Einführung in der Informatik

Java Programmierung und halt auch die Analyse und Entwürfe von Algorithmen durch.

Ich habe allerdings nicht das Problem Struktogramme oder PAPs zu erstellen.

Bei mir liegt das Problem in der Analyse und dem Entwerfen von Algorithmen.

Irgendwie blicke ich dann nicht durch.

Ich gebe euch mal ein Beispiel zur Analyse:

lies n E IN ein (Element der natürlichen Zahlen)

lies x E IN

setze k = n

setze y = 1

setze z = x

SOLANGE k ungleich 0 TUE

    WENN k ungerade DANN

        setze k = k - 1

        setze y = y * z

    setze k = k div 2

    setze z = z * z

gib y aus

Was berechnet dieser Algorithmus?

Hat jemand eine Idee? Wie geht ihr denn da vor? Zum Beispiel bei dieser Aufgabe.

Gibt es eigentlich zu diesem Thema ein Buch, wo auch Aufgaben mit Lösungen

enthalten sind?

(Edit: CODE-Tags eingefügt, damit die Einrückung erkennbar ist | Klotzkopp)

[Klotzkopp]

Originally posted by witch doctor

Was berechnet dieser Algorithmus?

Hat jemand eine Idee? Wie geht ihr denn da vor? Zum Beispiel bei dieser Aufgabe.

Was dieser Algorithmus macht, kann man durch Ausprobieren mit mehreren Werten für x und n recht schnell herausfinden. Aber man kann auch ohne Ausprobieren zumindest in die richtige Richtung denken:

Das Ergebnis ist y. Was geschieht mit y? Zu Anfang ist y eins. Im Verlauf des Programms wird y möglicherweise mit z multipliziert. z hat den Anfangswert x, und wird mit sich selbst multipliziert. Das heißt: z ist immer eine Potenz von x mit einem Exponenten, der selbst eine Potenz von zwei ist, also x^1, x^2, x^4 usw. y ist damit auch eine Potenz von x.

Danach kann man untersuchen, wann y mit z multipliziert wird, und was mit k geschieht.

[witch doctor]

Aha. Wird schon etwas klarer....

Mit der Potenz hatte ich auch schon im Hinterkopf.

Aber bei mir hat das nie gepasst. Aber vielleicht habe ich mich auch beim Einsetzen vertan.

Nun denn. Ich danke dir.

[fmarx2000]

Originally posted by witch doctor

Ich studiere gerade Wirtschaftsinformatik im ersten Semester.

Dort nehmen wir unter anderem in der Einführung in der Informatik

Java Programmierung und halt auch die Analyse und Entwürfe von Algorithmen durch.

Ich habe allerdings nicht das Problem Struktogramme oder PAPs zu erstellen.

Bei mir liegt das Problem in der Analyse und dem Entwerfen von Algorithmen.

Irgendwie blicke ich dann nicht durch.

Ich gebe euch mal ein Beispiel zur Analyse:

lies n E IN ein (Element der natürlichen Zahlen)

lies x E IN

setze k = n

setze y = 1

setze z = x

SOLANGE k ungleich 0 TUE

    WENN k ungerade DANN

        setze k = k - 1

        setze y = y * z

    setze k = k div 2

    setze z = z * z

gib y aus

Was berechnet dieser Algorithmus?

Hat jemand eine Idee? Wie geht ihr denn da vor? Zum Beispiel bei dieser Aufgabe.

Gibt es eigentlich zu diesem Thema ein Buch, wo auch Aufgaben mit Lösungen

enthalten sind?

(Edit: CODE-Tags eingefügt, damit die Einrückung erkennbar ist | Klotzkopp)

Das Schlimme ist eigentlich das man jetzt im ersten Semester eine OO-Sprache lernt obwohl man im 1. Semester keine Ahnung von OO-Entwurf und Design hat , dann kommen diese komischen Programme heraus die eigentlich C-Programme sind mit C++ oder JAVA-Syntax.

Schade das sowas an einer Hochschule passiert.

Frank

[frosch03]

halli hallo,

also wenn ich das richtig sehe (hatte leider nur einen stift,

n taschenrechner und papier zur hand)

dann müsste der algorithmus einfach nur

x^n berechnen

(y = x ^ n )

warum die variablen k und z eingeführt werden weiß ich

nicht, macht aber in diesem kurzen abschnitt keinen sinn.

möglicherweise braucht man die, um später noch sagen zu

können woraus man y berechnet hat...

grüße Frosch03

[witch doctor]

Wir habe heute die Musterlösung übers Netz erhalten und es stimmt:

y = x ^n

Doch ich verstehe nicht wieso. Wieso stellt man es so kompliziert dar.

Das geht doch bestimmt einfacher.

Ich meine, wenn man x und n eingelesen hat, kann man dann nicht

einfach dann x ^n nehmen bzw. x so oft multiplizieren wie groß n halt ist.

Oder ist das so in der Schleife dargestellt?

Doch wie?

Anmerkung: Ich stehe erst ganz am Anfang und brauche training.

Wie ist das denn dargestellt und wieso wird berücksichtigt, dass k ungerade bzw gerade ist.

Ich meine, das passt doch gar nicht. Wo übersehe ich was?

Kurz:

Ich verstehe die Schleife in dem Programm nicht.

[Klotzkopp]

Originally posted by witch doctor

Wieso stellt man es so kompliziert dar.

Das geht doch bestimmt einfacher.

Sicher geht das einfacher. Aber daraus lernt man ja nichts.

So wie ich den Algorithmus verstanden habe, wird der Exponent n als Dualzahl interpretiert. Die Prüfung auf ungerade ist der Test, ob an der gerade verarbeiteten Dualstelle des Exponenten eine 1 oder eine 0 steht. Die Division durch zwei wechselt dann zur nächsten Dualstelle. k wird sozusagen bitweise bearbeitet, vom niederwertigsten Bit angefangen.

Ist k zu Anfang ungerade, enthält die Potenz den Fakter x hoch 1, also wird der reinmultipliziert. k wird eventuell vermindert und halbiert, und der Stellenwert der Potenz durch Quadrierung verdoppelt auf x hoch 2. Ob dieser Faktor im Ergebnis enthalten ist, hängt davon ab, ob k jetzt wieder ungerade ist. Beim Beispiel 5 ist k nach dem ersten Durchgang (5-1)/2 = 2, also gerade, damit ist x hoch 2 nicht enthalten. Der "Stellenwert-Faktor" wird wieder quadriert, also x hoch 4, und jetzt ist k wieder ungerade (nämlich 1), also ist x hoch 4 enthalten, und wird reinmultipliziert. Danach ist k Null, und wir sind fertig. Das Ergebnis ist also x hoch 1 mal x hoch 4 gleich x hoch 5.