Entwickler-Ecke :: Thema anzeigen - [Delphi] Ägyptische Multiplikation Rekursiv

Predator1992 - So 25.01.09 12:33
Titel: [Delphi] Ägyptische Multiplikation Rekursiv

Hallo alle zusammen,
ich hätte da eine (für euch wahrscheinlich simple) Frage in Sachen "Rekursionen". Hoffe, dass ihr mir da weiterhelfen könnt.

Kommende Woche schreiben wir einen Test in Informatik über Rekursion und Unwandlung von Iterationen in Rekursionen, nur leider war ich letzte Woche krank und habe nicht so viel vom ganzen mitbekommen. Jetzt haben wir eine Aufgabe fürs Wochenende gekriegt einen Pseudo Algorithmus der ägyptischen Multiplikation in eine Rekursion umzuwandeln (in Pascal). Nur leider weiß ich nicht so wirklich, wie ich das anstellen soll.

Der Algorithmus lautet:

Eingabe: a,b (natürliche Zahlen)
x:=a, y:=b, z:=0;

Solange x>0 Wiederhole:
Wenn x gerade dann
halbiere x; verdopple y;
Sonst
vermindere x um 1, vermehre z um y
Ende (Wenn)
Ende (Wiederhole)

Wäre wirklich nett, wenn ihr mir da weiterhelfen könntet. Und sorry, wenn ich iwas falsch gemacht habe (falsche Sektion, u.s.w.).

- Predator1992

Moderiert von Narses: Titel geändert.

martin300 - So 25.01.09 12:51

Hallo,
im Prinzip steht hier alles Beschrieben http://de.wikipedia.org/wiki/Rekursion
Am Anfang ist es schwierig es zu verstehen, sobald du aber selbst die Lösung hast kannst
du sie immer wieder ableiten. Die Programmiersprache selbst, ist dann wieder eine andere Geschichte.

Predator1992 - So 25.01.09 15:24

Ja, die Seite auf Wikipedia habe ich mir auch schon angeguckt, aber was ich hier jetzt eher gesucht habe ist ein Lösungsbeispiel für die Aufgabe, denn meins sieht total komisch aus und ist noch unvollständig.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

begin
if x<=0 then return e
    else if x mod 2 = 0 then
begin
return f(2*a, b/2)
end
else return f (x-1, ???)
end;
end.

Moderiert von Christian S.: Delphi-Tags hinzugefügt

martin300 - So 25.01.09 17:19

Die Lösung sieht wirklich komisch aus.
Du könntest die mit dieser vergleichen:
http://de.wikibooks.org/wiki/Programmierkurs:_Delphi:_Pascal:_Rekursion
und wirst feststellen das dir etwas wichtiges fehlt.

Alternativ könntest du dir noch diesen Link durchlesen
http://de.wikipedia.org/wiki/Rekursive_Programmierung

JayEff - So 25.01.09 20:13

Predator1992 hat folgendes geschrieben :

...hatte aber gedacht, dass mir einer hier im Forum einfach mal zeigt, wie soetwas aussehen kann, Rekursivmäßig, anstatt Links von Wikipediaartikeln zu kriegen.

Nun, solang du keine Lösung für deine Hausaufgabe erwartest, sondern ein einfaches Rekursionsbeispiel, kann dir geholfen werden :D

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

function Fakultaet(Zahl: Integer): Integer;
begin
  if Zahl <= 1 then //Rekursionsabbruch (ohne: Endlose Rekursion!)
    result := 1
  else
    result := Zahl * Fakultaet(Zahl - 1);  //Rekursiver Aufruf
end;

Diese funktion berechnet die Fakultät von 'Zahl' rekursiv.
Bei Rekursionen muss man immer eine Abbruchbedingung haben, sonst geht's endlos weiter. Und bei Fakultät solltest du nicht versuchen, 12! oder mehr auszurechnen, das klappt dann nicht mehr ;)

ub60 - So 25.01.09 20:59

Predator1992 hat folgendes geschrieben :

...hatte aber gedacht, dass mir einer hier im Forum einfach mal zeigt, wie soetwas aussehen kann, Rekursivmäßig, anstatt Links von Wikipediaartikeln zu kriegen.

Hier also die Rekursion, damit Du nicht weiter schmollst und eine gute Note bekommst :wink: :
Es gibt 3 Fälle, die Du behandeln musst:

1. Der erste Faktor ist 1, dann ist das Produkt gleich der zweiten Zahl. (Rekursionsabbruch)

Ansonsten gibt es die zwei weiteren Fälle:

2. Der erste Faktor ist gerade, dann ist das Produkt gleich dem Produkt aus der Hälfte der ersten und dem Doppelten der zweiten Zahl.
3. Der erste Faktor ist ungerade, dann müssen wir den ersten Faktor "gerade machen" (Beispiel:7*5=5+6*5), also ist das Produkt gleich der Summe aus der zweiten Zahl und dem Produkt aus der um eins verminderten ersten Zahl und der zweiten Zahl (siehe Beispiel).

Viel Spaß beim Umsetzen!
Schreib uns mal Deine Lösung.

ub60

Predator1992 - Mo 26.01.09 21:17

Boldar hat folgendes geschrieben :

mmh also es wird hier wohl kaum einer deine Hausaufgaben machen, denn wenn hier alle, die (angeblich) "krank" waren, ne fertige Lösung bekommen, wärs ein hausaufgaben-Forum und kein Programmierforum...

Oh, danke für die netten Worte. Dich hat keiner gezwungen mir zu glauben.

Ich habe einfach nur gedacht, dass hier einer im Forum vielleicht schon mal eine Ägyptische Multiplikation Rekursiv gemacht hat, und dann wäre es natürlich nicht schlecht gewesen, wenn er sie mir einfach gegeben hätte und ich mir das hätte anschauen können.

Anyway, hier mein nächster Veruch, *seufz*...

Funktion habe ich "AegyptMu" genannt.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

begin if a = 0 then
result = z
else 
if a mod 2 = 0 then
result ;= AegyptMu(a div 2, b*2, z)
else
result := AepyptMu (a-1, b, z+b)
end;

Moderiert von Narses: Delphi-Tags hinzugefügt

JayEff - Mo 26.01.09 21:50

Predator1992 hat folgendes geschrieben :

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

begin   
  if a = 0 then
    result := z
  else 
    if a mod 2 = 0 then
      result := AegyptMu(a div 2, b*2, z)
    else
      result := AepyptMu (a-1, b, z+b);
end;

Bitte delphi-Tags einsetzen (drück bei meinem Beitrag auf "Zitieren" um zu sehen, wie's geht ;) ) und den code ordentlich Einrücken, sonst versteht man ja nix davon. Ausserdem wär eine Fehlerbeschreibung toll gewesen. "Geht nicht" reicht da natürlich dann nicht aus, aber nicht mal der kleinste Kommentar? :nixweiss:

(Boldar's Antwort war tatsächlich etwas rau, aber du musst's mal so sehen: Immer und immer wieder fragen uns Leute, ob wir für sie ihre Hausaufgaben machen, die eigentlich überhaupt kein Interesse am Programmieren haben und auch nix lernen wollen, am besten copy&paste und gut wars - du verstehst sicher, dass wir darüber nicht grade glücklich sind und daher allergisch auf sowas reagieren. Wenn du nicht so einer bist, dann nimm Boldar die Reaktion bitte nicht übel ;)

Leider kann ich tatsächlich nichts aus deinem Code auslesen (ausser hier und da ein tippfehler, ;= statt := ...), da ich keine ahnung hab, was a, b und z darstellen sollen, da du den Funktionskopf leider auch wegrationalisiert hast :(

ub60 - Mo 26.01.09 22:04

Predator1992 hat folgendes geschrieben :

Anyway, hier mein nächster Veruch, *seufz*...

Warum *seufz* ?
Der Quelltext, den Du jetzt hast, funktioniert doch! (bis auf die zwei kleinen Syntaxfehler)

Predator1992 hat folgendes geschrieben :

Funktion habe ich "AegyptMu" genannt.

Kleiner Hinweis dazu: Bitte den Quelltext in Delphi-Tags setzen (unter Bereiche) und zum besseren Verständnis die Kopfzeile der Funktion mit hier hinschreiben.

ub60

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!