mercredi 22 avril 2015
Pow?
Posted on 02:58 by verona
Sei M eine Menge und ° : M x M -> M eine assoziative Verknupfung auf M. Falls Sie ein konkretes
Beispiel haben wollen, konnen Sie sich also M = |N und a ° b := a (mal) b vorstellen, wobei mit a (mal) b hier die
gewohnliche Multiplikation bezeichnet wird.
Sei n (element) |N und a (element) M. Wir definieren pow(a; n) durch
pow(a; n) := a ° ... ° a (n-mal)
In dem obigen Beispiel von M = N gilt also: pow(a; n) = a^n.
Offensichtlich lasst sich pow(a; n) durch einen naiven Algorithmus in n-Schritten berechnen, wenn eine
Anwendung von ° als ein Schritt gilt.
Entwickeln Sie einen Algorithmus in Pseudocode, der pow(a; 2^m) in m Schritten berechnet. Zeigen Sie
die Korrektheit Ihres Algorithmus und begrunden Sie, dass die geforderte Laufzeitschranke tatsachlich
eingehalten wird.
Wo wird die Assoziativitat von ° benotigt?
Was mich an der Aufgabe stört ist dieses "pow(a; 2^m) in m Schritten" Was ist damit gemeint? Ich dachte pow(a;n) soll 2^n bedeuten? Kann mit das jemand erklären? :)
Beispiel haben wollen, konnen Sie sich also M = |N und a ° b := a (mal) b vorstellen, wobei mit a (mal) b hier die
gewohnliche Multiplikation bezeichnet wird.
Sei n (element) |N und a (element) M. Wir definieren pow(a; n) durch
pow(a; n) := a ° ... ° a (n-mal)
In dem obigen Beispiel von M = N gilt also: pow(a; n) = a^n.
Offensichtlich lasst sich pow(a; n) durch einen naiven Algorithmus in n-Schritten berechnen, wenn eine
Anwendung von ° als ein Schritt gilt.
Entwickeln Sie einen Algorithmus in Pseudocode, der pow(a; 2^m) in m Schritten berechnet. Zeigen Sie
die Korrektheit Ihres Algorithmus und begrunden Sie, dass die geforderte Laufzeitschranke tatsachlich
eingehalten wird.
Wo wird die Assoziativitat von ° benotigt?
Was mich an der Aufgabe stört ist dieses "pow(a; 2^m) in m Schritten" Was ist damit gemeint? Ich dachte pow(a;n) soll 2^n bedeuten? Kann mit das jemand erklären? :)
Pow?
Categories: Pow?
Inscription à :
Publier les commentaires (Atom)
0 commentaires:
Enregistrer un commentaire