www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAlgorithmen und DatenstrukturenRekursiver Algorithmus
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Algorithmen und Datenstrukturen" - Rekursiver Algorithmus
Rekursiver Algorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursiver Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:40 Mo 20.10.2014
Autor: evinda

Hallo!!!
Ich soll einen rekursiven Algorithmus schreiben, der, gegeben einer absteigend sortierten Liste mit m Elementen, eine neue Liste kreiert, die die Elemente von L, aufsteigend sortiert, enthält. Wir nehmen an, dass die Liste einfach verbunden ist und dass es einen Pointer gibt, der zum ersten Element der Liste zeigt.

Könntet ihr mir Tipps geben, wie ich so einen rekursiven Algorithmus schreiben könnte?




Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Rekursiver Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 15:29 Mo 20.10.2014
Autor: Event_Horizon

Hallo!

Rekursion bedeutet ja, daß eine Funktion sich immer wieder selbst aufruft. Dabei gibt es immer eine Abbruchbedingung. Ist die erfüllt, ruft sich die aktuelle Funktionsinstanz nicht mehr selbst auf, sondern beendet sich, und die vorherige Instanz macht weiter.

Deine Funktion bekommt einen Zeiger auf das aktuelle Element der alten Liste übergeben, und es würde genau dieses Element an die neue Liste anhängen. Vorher sollte es sich aber noch selbst aufrufen, und dann müßte noch ne Abbruchbedingung rein.

Noch ein Tipp: Die Funktion kann auch den Zeiger auf das nächste Element der alten Liste berechnen!

Bezug
                
Bezug
Rekursiver Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:17 Mi 22.10.2014
Autor: evinda


> Deine Funktion bekommt einen Zeiger auf das aktuelle
> Element der alten Liste übergeben, und es würde genau
> dieses Element an die neue Liste anhängen. Vorher sollte
> es sich aber noch selbst aufrufen, und dann müßte noch ne
> Abbruchbedingung rein.
>  
> Noch ein Tipp: Die Funktion kann auch den Zeiger auf das
> nächste Element der alten Liste berechnen!

Ich habe noch nicht verstanden, wie der Algorithmus  eine neue Liste kreiert, die die Elemente von L, aufsteigend sortiert, enthält, indem sich die Funktion selbst aufruft.

Könntest du mir das nochmal erklären?

Bezug
                        
Bezug
Rekursiver Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 22:26 Mi 22.10.2014
Autor: Event_Horizon

Naja, so einfach mach ich es nicht.

Stell dir vor, ganz viele Informatiker sitzen in einer Reihe. Der erste bekommt eine Liste in die Hand gedrückt, in die jeder der Reihe nach, beginnend mit dem letzten Informatiker in der Reihe, seinen Namen eintragen soll.
Schenkt man den Gerüchten glauben, bewegen sich Informatiker nicht so gerne, daher wird der erste nicht aufstehen, und die Liste dem letzten bringen. Jeder kann die Liste nur seinem direkten Nachbarn weitergeben.

Frage: Wie machen die Informatiker das nun, daß am Ende alle Namen in umgekehrter Reihenfolge auf der Liste stehen?

Und genauer: Was sind die einzelnen Schritte, die jeder Informatiker ausführt?

Bezug
                                
Bezug
Rekursiver Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:19 Do 23.10.2014
Autor: evinda

Sind die Schritte die folgenden?

Der erste Informatiker gibt dem zweiten Informatiker die Liste weiter, der zweite Informatiker gibt dem dritten Informatiker die Liste weiter,...., der vorletzte gibt dem letzten Informatiker die Lister weiter. Er schreibt dann seinen Namen, und gibt die Liste seinem direkten Nachbarn zurück, der vorletzte Informatiker schreibt dann seinen Namen und gibt die Liste den dritten von hinten weiter,..., der erste Informatiker bekommt die Liste und schreibt seinen Namen.

Bezug
                                        
Bezug
Rekursiver Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:59 Fr 24.10.2014
Autor: evinda

Also muss der Algorithmus so sein?

Funktion(List1){
    Pointer *p,*q;
    p=List1;
    while (p!=NULL){
                p=p->next;
    }
    q=p;
}

Falls ja, wie kann ich weitermachen?
    

Bezug
                                                
Bezug
Rekursiver Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 15:58 Fr 24.10.2014
Autor: sijuherm

Nein, das ist keine Rekursion. Genau das gleiche Code-Fragment hast du auch schon in einer anderen Frage gestellt. Event_Horizon hat dir ja schon einen guten Tipp gegeben, den du auch richtig verstanden hast. Offensichtlich hat der Transfer auf dein eigentliches Problem nicht geklappt, daher noch ein Tipp von mir: Deine Funktion muss sich selbst aufrufen. Eine while-Schleife ist nicht notwendig.

Bezug
                                        
Bezug
Rekursiver Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 16:01 Fr 24.10.2014
Autor: sijuherm

Richtig. Überlege dir nun, wie du das in Code umsetzen kannst. Das Stichwort ist bereits in der ersten Antwort gefallen.

Bezug
                                                
Bezug
Rekursiver Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:20 Fr 24.10.2014
Autor: evinda

Ich habe folgendes versucht, bin mir aber nicht sicher ob es richtig ist:

NODE *Change( NODE *L1){
      NODE *p1=L1;
      NODE *L,new;
      while (p1 != NULL){
             p1=p1->next;
      }
      new=newcell(NODE);
      new->data=p1->data;
      new->next=NULL;
      ListDelete(L1,p1);
      L=new;
      Change(L1);
}

ListDelete wäre ein Algorithmus, der ein Element einer Liste löscht.

Oder könnte man es besser machen?
      

Bezug
                                                        
Bezug
Rekursiver Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 11:47 Sa 25.10.2014
Autor: Event_Horizon

Hallo!

Ich denke,du hast das was konzeptionelles noch nicht verstanden.

Mal einfacher:

Du willst die Summe der Zahlen 1...n rekursiv bestimmen. Eine Funktion dazu sieht so aus:



1: int mySum(int n){
2:     if(n == 0){
3:          return(0);
4:     }
5:     else{
6:         return ( n+ mySum(n-1) );
7:     }
8: }
9:
10:
11: int s = mySum(7);
12:
13: printf(s);


Das wichtige daran ist, daßdie Funktion sich selbst mit einem anderen parameter aufruft.Versuche mal,dieses Beispiel genau zu verstehen.


Dein Programm müßte eher so aussehen:


1: Node* Change(Node *Lold, Node *Lnew){
2:     if(Lold->next != NULL){  // Es gibt noch weitere Elemente in der Liste
3:         Lnew= Change(Lold->next, Lnew);
4:     }
5:     AddNode(Lnew, Lold->Value);
6:    return (Lnew->next);
7: }



Lold ist hier ein Zeiger auf das aktuelle Listenelement der alten Liste. Es muß geprüft werden, ob es noch weitere Listenelemente gibt. Wenn ja, ruft sich die Funktion selbst auf, aber eben mit dem nächsten Element der alten liste als Parameter.
Lnew ist ein Zeiger auf das letzte Element der neuen Liste. Wenn die Funktion ein neues Element an die Liste anhängt, gibt sie den Zeiger auf das nun neue letzte Element zurück, und die aufrufende Funktion muß dies natürlich entgegen nehmen, weil sie ihr Element natürlich auch an dieses neue Ende anhängen will.




Bezug
                                                                
Bezug
Rekursiver Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:24 Sa 25.10.2014
Autor: evinda

Warum ist Lnew ein Parameter der Funktion?

Könntest du mir bei einer bestimmten Liste erklären, wie dein Algorithmus funktioniert?

Bezug
                                                                        
Bezug
Rekursiver Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 23:41 Sa 25.10.2014
Autor: Event_Horizon

Hallo!

Naja, wenn die Funktion doch der neuen Liste ein Element hinzufügen soll, muß sie doch das bisherige letzte Element der neuen Liste kennen.

Wenn also Lnew das letzte Element der neuen Liste ist, wird mit

AddNode(Lnew, Lold->Value);

ein neues Element an die neue Liste angehängt, welches den Wert des aktuellen Elements der alten Liste enthält.

Mit return (Lnew->next); wird anschließend das neue letzte Element der neuen Liste zurück gegeben.

Was denkst du denn, was meine Funktion mit einer konkreten Liste macht?

Bezug
                                                                                
Bezug
Rekursiver Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:36 So 26.10.2014
Autor: evinda

Ich habe es auch nochmal selbst folgenderweise versucht:

Node *Change(Node *Lold){
      if (Lold->next!= NULL)
          Change(Lold->next)
      Addnode(Lnew, Lold->Value);
      return Lnew;
}

Könntest du mir sagen ob es auch richtig ist?

Bezug
                                                                                        
Bezug
Rekursiver Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 07:53 Mo 27.10.2014
Autor: Event_Horizon

Hallo!

Nunja... Lnew ist ja ein Knoten der neuen Liste. Und bei mir sollte Lnew immer das letzte Element der Liste sein.

In der Funktion selbst kommt Lnew gar nicht vor. Das ist durchaus möglich, wenn Lnew eine globale Variable ist. Dann sollte die Funktion AddNode selbst aber Lnew nach dem Anhängen des neuen Elements gegen dieses ersetzen.

Denk bitte auch dran, daß AddNode keine allgemein bekannte Funktion ist. Ich habe AddNode() geschrieben, damit klar ist, daß hier ein Element an eine Liste angehängt werden soll. Im Prinzip mußt du diese Funktion auch noch schreiben.

Noch was: Du benutzt keine geschweiften Klammern hinter dem IF. Das ist korrekt und funktioniert hier bei der einen Zeile, du solltest dir aber dringend angewöhnen, IMMER Klammern zu verwenden. Denn irgendwann schreibst du noch ne Zeile dazu, und vergisst, die dann fälligen Klammern hin zu schreiben. Und dann wunderst du dich, warum der Code nicht das tut, was du willst.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]