Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » Rätselecke » komplexes Problem
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 <
000
19.06.2007, 21:45 Uhr
MausFan



 Hallo liebes Forum,

ich habe ein riesen Problem, bei dem ich mit meinen Programmierkenntniessen nicht mehr weiterkomme.

Ich möchte ein Dreieck, weleche aus zufälligen Zahlen basteln. Dies ist mir auch soweit gelungen. Nun kommt der schwierige Teil. Es soll die größt mögliche Summe berechnet werden, die man auf seinem Weg nach unten erreichen kann. Schaut euch zum besseren Verständnis dieses Beispiel an, beidem der rote Faden den Weg darstellt, der die größte Summe ergibt.

www.abload.de/image.php?img=bild23wr.gif

Diese Aufgabenstellung wurde auch noch auf anderen Internetseiten gestellt:
http://projecteuler.net/index.php?section=view&id=18

Nun brauche ich einen Algorithmus der genau dies für mich erledigt. Bis jetzt habe ich mir dafür schon einige Tipps geben lassen.

Ich liste das hier auf und hoffe das Ihr was damit anfangen könnt:

Man kann das als Graphenproblem betrachten (der Graph ist sogar azyklisch). Jede Zahl ist ein Knoten, es gibt von jedem Knoten, der kein Blatt ist, zwei Kanten zu seinen beiden Nachfolgern. Es geht jetzt darum, zu jedem Blatt den Pfad zu finden, bei dem die Summe der Zahlen am größten ist. Dazu speichert man in jedem Knoten zwei Dinge:
1) die maximal erreichbare Summe bis dorthin
2) von welchem Vorgängerknoten man dorthin gekommen ist (diese Information entfällt beim Startknoten a)

Jetzt geht man den Baum ebenenweise durch:
maximal erreichbare Summe bei a ist a
bei b: a+b, bei c: a+c (soweit noch uninteressant)
bei d: a+b+d
bei e: a+b+e oder a+c+e, je nachdem welches größer ist. Entsprechend wird in e vermerkt, ob der Vorgänger b oder c ist, so dass man später den Pfad zurückverfolgen kann.
bei f: a+c+f.
usw., die maximal erreichbare Summe bei einem Knoten x ist immer das Maximum der erreichbaren Summen der beiden Vorgänger von x plus x.

Es ist wichtig zu erkennen, dass, egal was weiter unten noch passiert, sich die maximal erreichbare Summe weiter oben nicht mehr ändern kann. Man kann also unbesorgt Ebene für Ebene abarbeiten und hat irgendwann die maximal erreichbare Summe für jedes Blatt, sowie über die Rückwärtskanten den Pfad, der auf diese Summe führt.

Das ist übrigens eine einfache Variante von Dijkstras Algorithmus zur Bestimmung kürzester Pfade in Graphen.

vlt. könntet Ihr auch auch mal das hier anschauen:

www.c-plusplus.de/forum/viewtopic-var-t-is-184034.html

Ich hoffe nun das mir jemand einen Code in c++ schreiben kann, der mir die größt mögliche Summe ausgibt.

Viele Grüsse und vielen Dank
MausFan
Dieser Post wurde am 19.06.2007 um 21:48 Uhr von MausFan editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
19.06.2007, 22:20 Uhr
mike
Pinguinhüpfer
(Operator)




1. Kein Ansatz
2. Hausübungsverdacht
--
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
19.06.2007, 22:22 Uhr
mike
Pinguinhüpfer
(Operator)


Du suchst evntl. Graphen mir gewichteten Kanten:
www.boost.org/libs/graph/doc/index.html
--
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
19.06.2007, 22:33 Uhr
öni



 Da muss man doch jetzt nur schauen (nehmen wir an das Dreieck ist im Array), wo die größte Zahl im Array steckt? Oder habe ich da jetzt was falsches verstanden? Und von dieser Zahl eben wieder nach der größten Zahl suchen!
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
19.06.2007, 23:15 Uhr
xXx
Devil


Hmm ... hab mir nur mal den 1. Teil deiner Aufgabe angeguckt und die Abbildung: Ich würde einfach ein Tree erstellen in die die Zahlen gepackt werden ... dann gucken welcher Ast den größten Wert hat. Von da aus dann wieder gucken welcher den größten "Unterwert" usw. ... wo ist das Problem? das ist nicht soo schwer zu Implementieren.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
19.06.2007, 23:20 Uhr
Reyx
IT-fetischistischer Wurstsalat mit rostigem Berghorn
(Operator)


@xXx
Der Ansatz dürfte nicht funktionieren. Nur weil ein Ast in seiner Hierarchiereihe den größten Wert hat, heißt es nicht, dass der Weg, der durch diesen Ast führt, auch zwangsläufig zur größten Summe führen muss!

Code:
       1
   /   |  \
  5   4   3
/ | \ | / | \
1  2   5  1  101

(einfaches Bsp., aber egal)
Dieser Post wurde am 19.06.2007 um 23:22 Uhr von Reyx editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
20.06.2007, 13:18 Uhr
xXx
Devil


hmm stimmt ... ja ok ... dann bleibt einem nicht's anderes übrig als jeden Ast durchzugehen.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
20.06.2007, 13:40 Uhr
FloSoft
Medialer Over-Flow
(Administrator)


kommt natürlich auf deinen graph an - wenns ein baum wär - dann wär der rechte ast der "teuerste"
--
class God : public ChuckNorris { };
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
20.06.2007, 17:22 Uhr
öni
Zitat von MausFan:
Es ist wichtig zu erkennen, dass, egal was weiter unten noch passiert, sich die maximal erreichbare Summe weiter oben nicht mehr ändern kann. Man kann also unbesorgt Ebene für Ebene abarbeiten und hat irgendwann die maximal erreichbare Summe für jedes Blatt, sowie über die Rückwärtskanten den Pfad, der auf diese Summe führt.


Demnach ist meine und xXx seine Lösung richtig. Reyx hat aber auch recht aber vielleicht sind die Zahlen so gewählt das, das zutrifft was MausFan gesagt hat, demnach kann man die einfachere Variante wählen!
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
20.06.2007, 20:18 Uhr
0xdeadbeef
Gott
(Operator)


Es geht ja nur um die größtmögliche Summe, welcher Pfad dafür benutzt wurde, ist nicht gefragt. Ich würd das stumpf als binären Baum implementieren, der halt die selben Nodes mehrfach benutzt (Vorsicht, wenn das auf dem Heap passiert - das Aufräumen wird dadurch komplex - ich würd mir die Nodes außerdem noch in einer Liste aufbewahren, um da drum herum zu kommen), und den dann rekursiv behandeln. Also

C++:
typedef struct node_impl {
  struct node_impl *left, *right;
  int value;
} node;

int max_sum(node *n) {
  int l, r;

  if(n == NULL) return 0;
  l = max_sum(n->left);
  r = max_sum(n->right);

  return n->value + (l < r ? r : l);
}

--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 <     [ Rätselecke ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: