Entwickler-Ecke :: Thema anzeigen

gerd8888 - Mi 04.11.15 18:06

Ich nehme an, dass die natürlichen Zahlen spaeter wie in dem einfachen Beispiel nicht so aussehen.
Also 1, 2, 3, 4, 5 usw.
Sondern vielleicht so: 2, 2, 3, 6 usw.
Das erinnert mich an das "Haus vom Nikolaus" Problem, das ich einmal rekursiv geschrieben habe.
Ich würde hier ein array hernehmen und dann einfach rekursiv durchlaufen.
Wo liegt das Hauptproblem? In der Rekursion oder im Aufbau?

Narses - Mi 04.11.15 18:24

Moin und :welcome: im Forum!

MCKolumfer hat folgendes geschrieben :

Ich habe Rekursion noch nie in meinem Leben verwendet.
[...]
Um zu verstehen, wie Rekursion funktioniert

Hm, an dieser Stelle ist die Aufgabenstellung aber nicht ... "hilfreich"... :?

Wenn es erstmal um das Verständnis für Rekursion geht, dann empfehle ich dringend die Fakultät [https://de.wikipedia.org/wiki/Fakult%C3%A4t_%28Mathematik%29] und anschließend die Fibonacci-Zahlen [https://de.wikipedia.org/wiki/Fibonacci-Folge] rekursiv zu berechnen (das sind jeweils 1-Zeiler, also schnell machbar und - wie ich finde - ausgesprochen hilfreich beim Verstehen von Rekursion). :idea:

Dann kannst du dich immer noch an den Permutationen versuchen. :zustimm:

cu
Narses

papa69 - Mi 04.11.15 19:05

Jaja, die Rekursion...

Im Grunde heißt das ja nur, dass sich die Funktion solange selber aufruft, bis sie erfüllt ist.

z.B. (Pseudocode)

Quelltext

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

//irgendwas
...
sucheNachbar()
{
   ...
   wenn ja
     sucheNachbar();
   wenn nein
     sucheWasAnderes();
}

gerd8888 - Mi 04.11.15 20:00

Delphi-Quelltext

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

procedure Tform1.rekursion(tiefe:word);
var i:word;
begin
  inc(tiefe);
  if tiefe<4 then begin
    for i:=1 to 3 do begin
      listbox1.items.Add(inttostr(tiefe));
      rekursion(tiefe);
    end;
  end;
end;

Du startest die procedure mit tiefe(0)
Das ist jetzt eine typische Baumstruktur in rekursiver Darstellung. Eine Rekursion ist eine Prodezur oder eine Funktion die man mehrmals aufruft.
Aber die Baumstruktur ist nicht das was Du für Dein Problem brauchst.
Das heisst im Beispiel von 3 Zahlen: 1,2,3 - 2,1,3 - 3,1,2 (so willst Du es doch haben ??)
Wie Du siehst, brauchst Du nichteinmal eine rekursive Permutation.
Bei der Art von Rekursion muust Du immer Deine erste Zahl rausstreichen.
Das nur mal als Tipp.

gerd8888 - Mi 04.11.15 21:37

Hallo,

ich habe dich schon richtig verstanden.
Bei 3 Zahlen wären das dann:
1
2
3
1+2 (x)
1+3
2+1 (x)
2+3 (y)
1+2+3
3+2 (y)

Ich hätte schon eine Lösung des Problems, nur will Dein Lehrer auf etwas bestimmtes hinaus. Ich glaube er hat Zwischenwerte gespeichert, die in rekursion(tiefe, var zwischenwerte) aufgerufen werden. Da müsste ich jetzt wirklich selbst nachdenken, wie man das am besten löst.

Ralf Jansen - Do 05.11.15 00:02

Ich hab versucht einen möglichen Algorithmus zu beschreiben damit du dich daran üben kannst bin aber dran gescheitert. Code ist einfach soviel sprechender als Umgangssprache ;)
Hier mal ein Beispielalgorithmus der sicher nicht dem entspricht an den dein Lehrer gedacht hat und diverse Mängel hat dir aber vielleicht hilft die ~Idee~ bei Rekursion zu verstehen.

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

static void Main(string[] args)
{
    int[] zahlen = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    cmf(10, zahlen);
}

private static void cmf(int ziel, int[] zahlen)
{
    cmfRecursive(ziel, zahlen.ToList(), new List<int>());
}

private static void cmfRecursive(int ziel, List<int> zahlen, List<int> solution)
{
    while(zahlen.Count > 0)
    {
        var localZiel = ziel - zahlen[0];
        var local = zahlen.ToList();
        local.RemoveAt(0);

        var localSolution = solution.ToList();
        localSolution.Add(zahlen[0]);

        if (localZiel == 0)
            Console.WriteLine("Lösung: " + string.Join("+", localSolution)); // Treffer
        else if (ziel > 0)                                      
            cmfRecursive(localZiel, local, localSolution); // weitersuchen       

        zahlen.RemoveAt(0);
    }
}

Quelltext

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

--------Ausgabe------
Lösung: 1+2+3+4
Lösung: 1+2+7
Lösung: 1+3+6
Lösung: 1+4+5
Lösung: 1+9
Lösung: 2+3+5
Lösung: 2+8
Lösung: 3+7
Lösung: 4+6
Lösung: 10

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 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!