| |
| Autor |
  Rekursionsformel aufstellen für Addition zweier Zahlen n und m |
|
aaron
Ehemals Aktiv 
Dabei seit: 04.02.2005
Mitteilungen: 210
 |  Themenstart: 2008-12-29
|
Hallo
Ich bearbeite gerade folgende Aufgabe:
a) Stellen sie eine Rekursionsformel auf für die Addition zweier Zahlen n und m.
b)Stellen Sie eine Rekursionsformel auf für das Minimum zweier Zahlen n und m.
Also die b) habe ich durch tüfteln herausbekommen.
min=cases(0,n=0 und m=0; min (n-1,m-1) +1,sonst)
Bei der a) klemmts, aber ich habe mir ein paar Gedanken dazu gemacht:
Man kann sagen: m+n=n+1+1+1+1+1+1........ also n+m-mal die 1, aber das ist ja in keinster Weise
eine Rekursionsformel.
Ich komm da irgendwie nicht weiter, wenn ihr mir dabei unter die Arme greifen könntet, würde ich mich sehr freuen.
Gruss
Aaron
|
 Profil
|
gaussmath
Senior 
Dabei seit: 16.06.2007
Mitteilungen: 9044
Wohnort: Hannover
 | Beitrag No.1, eingetragen 2008-12-29
|
Hallo,
sind m und n natürliche Zahlen? Was wäre denn hier der Rekursionsanker und was passiert von n -> n-1?
gaussmath
|
Profil
|
aaron
Ehemals Aktiv
Dabei seit: 04.02.2005
Mitteilungen: 210
| Beitrag No.2, vom Themenstarter, eingetragen 2008-12-29
|
\quoteon(2008-12-29 16:16 - gaussmath in Beitrag No. 1)
Hallo,
sind m und n natürliche Zahlen? Was wäre denn hier der Rekursionsanker und was passiert von n -> n-1?
gaussmath
\quoteoff
Hi
Also m und n sind natürliche Zahlen und der Rekursionsanker müsste 1 sein wegen:
n+m=(n+m)
n+0=n
Wenn ich nun n->n-1 gehe, geht das gegen 1, also den Rekursionsanker.
Ich hoffe das stimmt einigermaßen, was ich mir überlegt habe.
Gruss
Aaron
|
Profil
|
Tetris
Senior 
Dabei seit: 28.08.2006
Mitteilungen: 7818
| Beitrag No.3, eingetragen 2008-12-29
|
Hi, versuche es mal so:
add(n,m)=cases(\
n, falls m=0;\
add(?,?), falls m>0)
Lg, T.
|
Profil
|
viertel
Senior 
Dabei seit: 04.03.2003
Mitteilungen: 27787
Wohnort: Hessen
 | Beitrag No.4, eingetragen 2008-12-29
|
Hi aaron,
eine entscheidende Information ist nicht gegeben:
was darf denn in der Rekursion überhaupt benutzt werden?
Es liegt natürlich der Verdacht nahe, daß es auf die Addition von 1 zurück geführt werden soll.
Warum sollte der Rekursionsanker der Fall n=1 sein? Was ist mit n=0?
Wenn Du nur die Addition der 1 benutzen darfst, dann mach das doch auch:
wenn n>0, addiere zu m eine 1 und den Rest von n
Ich habe es extra etwas verdreht hingeschrieben, damit nicht gleich der fertige Rekursionsausdruck dasteht.
Gruß vom 1/4
[Die Antwort wurde nach Beitrag No.2 begonnen.]
|
Profil
|
aaron
Ehemals Aktiv
Dabei seit: 04.02.2005
Mitteilungen: 210
| Beitrag No.5, vom Themenstarter, eingetragen 2008-12-29
|
Hallo
Vielen Dank für die Antworten. Ich habe jetzt die Lösung herausbekommen.
Ich habe noch eine Frage, diese mag vielleicht etwas komisch klingen, aber speziell bei Rekursionen aufstellen tue ich mir sehr schwer und bekomme das meistens erst nach sehr langem überlegen bzw. tüfteln / ausprobieren heraus.
Gibt es denn evtl. eine Systematik oder eine clevere Herangehensweise oder ist das vorwiegend nur eine Übungsfrage ?
Wie geht ihr denn an solch eine Aufgabenstellung heran bzw. was sind denn eure ersten Überlegungen ?
Ich hoffe ihr erachtet meine Frage jetzt nicht als überflüssig oder unnötig.
Ich würde mich sehr über Antworten von Euch freuen.
Grüssle
Aaron
|
Profil
|
Tetris
Senior 
Dabei seit: 28.08.2006
Mitteilungen: 7818
| Beitrag No.6, eingetragen 2008-12-29
|
\quoteon(2008-12-29 22:36 - aaron in Beitrag No. 5)
... Ich habe jetzt die Lösung herausbekommen ...
\quoteoff
Welche Lösung hast Du denn gefunden?
\quoteon(2008-12-29 22:36 - aaron in Beitrag No. 5)
Ich habe noch eine Frage, diese mag vielleicht etwas komisch klingen, aber speziell bei Rekursionen aufstellen tue ich mir sehr schwer und bekomme das meistens erst nach sehr langem überlegen bzw. tüfteln / ausprobieren heraus.
Gibt es denn evtl. eine Systematik oder eine clevere Herangehensweise oder ist das vorwiegend nur eine Übungsfrage ?
Wie geht ihr denn an solch eine Aufgabenstellung heran bzw. was sind denn eure ersten Überlegungen ?
Ich hoffe ihr erachtet meine Frage jetzt nicht als überflüssig oder unnötig.
\quoteoff
Das ist eine gute Frage, auf die ich unmittelbar auch keine Antwort habe. Im Übrigen sind Überlegen, Tüfteln und Ausprobieren sicher nicht die schlechtesten Methoden!
Andererseits halte ich Deine Lösung zu b) für falsch. :-(
Lg, T.
|
Profil
|
Hartmut
Senior
Dabei seit: 22.12.2004
Mitteilungen: 1201
Wohnort: Karlsruhe
| Beitrag No.7, eingetragen 2008-12-30
|
Hallo!
Vielleicht hilft das: Man will eine Funktion f(n,m) berechnen. Stattdessen berechnet man f(n-1,m). Was muss man tun, um daraus f(n,m) zu bekommen? Oder anders: Welcher Rechenausdruck bleibt bei Anwendung der Rekursion invariant?
Also zB Produkt
f(n,m) = n*m
f(n-1,m) = (n-1)*m
f(n-1,m) + m = f(n.m)
f(0,m)=0 oder f(1,m) = 1
Es geht auch ohne m mit Fakultät von n:
f(n) = n!
f(n-1) = (n-1)!
f(n)=n*f(n-1)
f(1) = 1
Schöne Grüße und einen guten Rutsch!
Hartmut
[ Nachricht wurde editiert von Hartmut am 30.12.2008 09:52:51 ]
|
Profil
|
aaron
Ehemals Aktiv
Dabei seit: 04.02.2005
Mitteilungen: 210
| Beitrag No.8, vom Themenstarter, eingetragen 2008-12-30
|
\quoteon(2008-12-29 23:56 - Tetris in Beitrag No. 6)
\quoteon(2008-12-29 22:36 - aaron in Beitrag No. 5)
... Ich habe jetzt die Lösung herausbekommen ...
\quoteoff
Welche Lösung hast Du denn gefunden?
\quoteon(2008-12-29 22:36 - aaron in Beitrag No. 5)
Ich habe noch eine Frage, diese mag vielleicht etwas komisch klingen, aber speziell bei Rekursionen aufstellen tue ich mir sehr schwer und bekomme das meistens erst nach sehr langem überlegen bzw. tüfteln / ausprobieren heraus.
Gibt es denn evtl. eine Systematik oder eine clevere Herangehensweise oder ist das vorwiegend nur eine Übungsfrage ?
Wie geht ihr denn an solch eine Aufgabenstellung heran bzw. was sind denn eure ersten Überlegungen ?
Ich hoffe ihr erachtet meine Frage jetzt nicht als überflüssig oder unnötig.
\quoteoff
Das ist eine gute Frage, auf die ich unmittelbar auch keine Antwort habe. Im Übrigen sind Überlegen, Tüfteln und Ausprobieren sicher nicht die schlechtesten Methoden!
Andererseits halte ich Deine Lösung zu b) für falsch. :-(
Lg, T.
\quoteoff
Hallo Tetris
Also zur a) habe ich folgendes gefunden:
add(n,m)=cases(n,falls m=0;add(n-1,m+1),falls m>0)
Bei der b) habe ich folgendes ( wie oben schon erwähnt ):
min (n,m) =cases(0,falls n=0 und m=0;min((n-1,m-1)+1),sonst)
Also ich denke die b) stimmt, wenn ich als Beispiel nehme:
min (7,5) und ich wende die Rekursion an, dann komme ich auf 5 und das ist ja das Minimum von min (7,5)
Wo liegt deiner Ansicht nach mein Fehler bei der b) ?
Gruss
Aaron
[ Nachricht wurde editiert von aaron am 30.12.2008 00:49:49 ]
|
Profil
|
Tetris
Senior
Dabei seit: 28.08.2006
Mitteilungen: 7818
| Beitrag No.9, eingetragen 2008-12-30
|
Hi, bei a) darfst Du m nicht vergrößern, wenn Du die Fallunterscheidung m=0 bzw. m>0 machst, denn wie willst Du damit zum Ende kommen, wenn m anfänglich größer als Null ist?
Bei b) tritt der Fall n=0 und m=0 möglicherweise (so in Deinem Beispiel) gar nicht ein.
Lg, T.
|
Profil
|
viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27787
Wohnort: Hessen
| Beitrag No.10, eingetragen 2008-12-30
|
Die beiden Lösungen stimmen … leider nur fast.
Bei a) bist Du nicht sorgsam genug mit m und n gewesen. Sie sind an manchen Stellen vertauscht.
Bei b) stimmt die Abbruchbedingung nicht. Prüfe noch mal an einem kleinen Beispiel. Beachte die Bedeutung des logischen und und oder.
Ansonsten muß man bei solchen Rekursionsproblemen überhaupt erst mal sehen, daß es eines ist. Damit ist dann schon mal einiges gewonnen.
Schau Dir z.B. mal Schachbrett Weg an, des Rätsels Lösung liefert Beitrag 7. Schade nur, daß der Fragesteller die Lösung zwar zur Kenntnis genommen, sich aber nicht mehr dazu geäußert hat 
Rekursion tritt auch häufiger auf, als Du denkst.
• Was passiert denn z.B., wenn Du eine Kamera auf einen Fernseher richtest, der das Bild der Kamera wiedergibt?
• Oder Du im Spiegelkabinett zwischen zwei parallelen Spiegeln stehst.
• Oder das alte Kinderlied vom Hund in der Küche, siehe hier: www.labbe.de/liederbaum/index.asp?themaid=58&titelid=345
Manchmal versucht man auch, etwas rekursiv zu lösen, wo es gar nicht nötig ist. Ein schönes Anti-Beispiel ist die Faktultät, die man so schön rekursiv definieren kann:
fak(n):=cases(1,n=0;n*fak(n-1),sonst)
Das dann auch rekursiv zu programmieren grenzt fast an eine Straftat, denn ein iterativer Algorithmus ist deutlich schneller und vor allem weniger speicherfressend (Stack).
Ansonsten dürfte Dir die Forumsuche mit dem Suchwort "rekursi" einiges liefern.
[Die Antwort wurde nach Beitrag No.8 begonnen.]
|
Profil
|
aaron
Ehemals Aktiv
Dabei seit: 04.02.2005
Mitteilungen: 210
| Beitrag No.11, vom Themenstarter, eingetragen 2008-12-30
|
Hallo
Hier sind jetzt die überarbeiteten Rekursionen:
a)
add(n,m)=cases(n,falls m=0;add(n+1,m-1),falls m>0)
b):
min (n,m) =cases(0,falls n=0 oder m=0;min((n-1,m-1)+1),sonst)
Gruss
Aaron
|
Profil
|
Tetris
Senior
Dabei seit: 28.08.2006
Mitteilungen: 7818
| Beitrag No.12, eingetragen 2008-12-30
|
Hi, das sieht doch gut aus! Lg, T.
|
Profil
|
gaussmath
Senior
Dabei seit: 16.06.2007
Mitteilungen: 9044
Wohnort: Hannover
| Beitrag No.13, eingetragen 2008-12-30
|
Hi aaron,
ich finde, Du hast schnell Fortschritte gemacht. Schön! 
Viele Grüße
gaussmath
|
Profil
|
aaron hat die Antworten auf ihre/seine Frage gesehen.
aaron hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
