|
|
|
|
|
|
|
Ich bastel mir einen Baum aus Lauter Knoten. Jeder Knoten hat ein Kind links und ein Kind rechts, die wiederum Knoten sind. Außerdem hat jeder Knoten eine Methode sum(), die die Summe der Werte aller Kindknoten plus den eigene Wert zurückliefert.
Ich nehme mir den RootKnoten und frage für den linken und rechten Kindknoten die Summe ab. Ist die Summe links größer als recht, gehe ich in diese Richtung weiter, ist die Summe rechts größer, gehts dahin weiter.
Wenn man also das Beispiel nimm:
.
3
7 5
2 4 6
8 5 9 3
Wenn wir beim Rootknoten sind, liefert sum für das linke Kind 35 (7+2+4+8+5+9) und für das rechte Kind 32 (5+4+6+5+9+3), ich muss also nach links zur 7 weitergehen.
Wenn meine Idee stimmt, sollte sich das ganze relativ schnell lösen lassen. Der (bisher ungetestete) Lösungsalgorithmus sieht so aus:
| |
| Code: |
path = []
currentNode = rootNode
while currentNode.left and currentNode.right:
path.append(currentNode.num)
if currentNode.left.sum() > currentNode.right.sum():
currentNode = currentNode.left
else:
currentNode = currentNode.right
#TODO: path zusammenzählen
|
|
Im moment firckel ich aber noch daran den dummen Text in diese Struktur zu pressen, dass ist viel aufwändiger 
|
|
|
|
|
|
|
|
|
|
|
DAs Problem dabei ist ja aber, dass du immernoch alle Pfade berechnen musst. Und wie Problem 18 bereits erwähnt, wird bei Problem 67 das durchrechnen aller Routen schlicht nichtmehr möglich sein, da du bei 100 Zeilen 2^99 mögliche Routen hast...
Bei deinem Verfahren würde sich das immernoch imens hinziehen (da du ja immer nur halbierst - rechts oder links?)
1. Durchgang 2^99 Berechnungen
2. Durchgang 2^49 Berechnungen
3. Durchgang 2^24 Berechnungen
4. Durchgang 2^12 Berechnungen
5. Durchgang 2^6 Berechnungen
6. Durchgang 2^3 Berechnungen
7. Durchgang 2^1 Berechnungen
Ergebnis 
Insgesamt machst du also 2^194 Berechnungen also ~2,5108406941546723055343157692831e+58
Oder ich habe da was missverstanden 
// Andereseits, würdest du die Ergebnisse Cachen sparst du dir viele Berechnungen. Aber das rettet dich nach meiner Sichtweise auch nicht, da du ja immernoch 2^99 Berechnungen durchführen musst, wenn du dir für jeden Knoten seine Kindknotensumme merkst
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von GH@NDI am 03.08.2007 10:46]
|
|
|
|
|
|
|
|
|
|
3 mal soviel wie Protonen im Universum :x
|
|
|
|
|
|
|
|
|
|
|
ihr spinnt doch! alle! jawoll ja!
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von TriggerTG
3 mal soviel wie Protonen im Universum :x
| |
Wer hat die denn gezählt?
|
|
|
|
|
|
|
|
|
|
|
auch wenn du darauf schwörst daß du nur dir gehörst
geh ich hin und zack unterteile dich in über-ich und unter-ich
und zwischendrin befindet sich dann irgendwo dein wahres ich
|
|
|
|
|
|
|
|
|
|
|
angeblich poste ich zu viel 
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
der/die/das forum
|
|
|
|
|
|
|
|
|
|
|
hier, schon wieder:
Fehler:
Du postest zu viel in zu kurzer Zeit - bitte warte ein wenig
|
|
|
|
|
|
|
|
|
|
|
|
Schweinerei! Ein GSLer hat so nicht behandelt zu werden!
|
|
|
|
|
|
|
|
|
|
|
und der Buzweed behauptet das auch:
| | Zitat von Buzweed
| | Zitat von kleiner blauer Schlumpf
| | Zitat von Buzweed
SCHLUUUUHUUUMPF
| |
Wos? Ich war grade Weißwurst-Essen 
| |
DER MARVIN TUT VIEL ZU FIEL POSTEN!!! *petz*
| |
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von -Marvin- am 03.08.2007 11:12]
|
|
|
|
|
|
|
|
|
Das was mich am meisten an diesem Dreieckproblem wurmt ist, dass bei CodeGolf das selbe Problem existiert und ich damals schon nicht weiter wusste. Es aber Leute mit nur 60Zeichen in Perl lösen können (wohlgemerkt 50Zeilige Dreiecke in weniger als 4 Sekunden CPU-Zeit!)
// Es muss also einen besseren Algorythmus geben, als einfach mal alles durchzusummieren (selbst wenn das summieren bei der 1-Minute-Rule bei ProjectEuler immernoch die Lösung bringen würde )
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von GH@NDI am 03.08.2007 11:16]
|
|
|
|
|
|
|
|
|
Ändert aber nichts an der Sache, dass man nunmal alles Knoten mindenst einmal anfassen muss, sonst ist das ganze nämlich nicht in jedem Fall korrekt.
Was wenn mann so einen Baum hat:
.
01
99 01
99 99 01
01 01 01 99
01 01 01 99 99
01 01 01 99 99 99
usw.
Beschränkt man sich hierbei auf eine Suchtiefe von 3 pro Knoten, läuft man in die Falle. Und selbst wenn man eine höhere Suchtiefe ansetz, kann sowas vorkommen. Und was wäre es bitte für eine Lsöung die nur in 99% aller Fälle das richige Ergebnis liefert?
Wie soll man das lösen?
|
|
|
|
|
|
|
|
|
|
|
So, ich hab das ganze jetzt mal durchlaufen lassen. Ein Ergbnis für 18 hab ich in 0,1s, ein Ergebnis für 67 in 18 Sekunden.
Das Ergbnis ist zwar nicht richtig (da muss ich noch rausfinden wieso), aber er folgt defintiv meiner Idee.
/: Oh, Fehler gefunden, ich ziehe meine vorschnelle Aussage zurück *hüstel*
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Achsel-des-Bösen am 03.08.2007 11:36]
|
|
|
|
|
|
|
|
|
|
Ich stell die Konsole jetzt einfach bei eBay rein und tu so doof wie der jetzige Verkäufer.
|
|
|
|
|
|
|
|
|
|
|
Du bist ja gemein 
|
|
|
|
|
|
|
|
|
|
|
Ich habe jetzt mal Leute die sich damit auskennen müssten gefragt.
Und da ich bis Montag jetzt ja dann erstmal wieder on the road bin (Heute Auftritt Schloßplatz Stuttgart, morgen Auftritt Münster Sarmsheim Kerb, Sonntag heimkommen und Freundin besänftigen ) will ich euch die Möglichkeit geben, etwaige Lösungsanstäze die im Verlauf dieser Zeit gepostet werden auch zu sichtigen und davon zu profitieren
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von GH@NDI
Ich habe jetzt mal Leute die sich damit auskennen müssten gefragt.
Und da ich bis Montag jetzt ja dann erstmal wieder on the road bin (Heute Auftritt Schloßplatz Stuttgart, morgen Auftritt Münster Sarmsheim Kerb, Sonntag heimkommen und Freundin besänftigen ) will ich euch die Möglichkeit geben, etwaige Lösungsanstäze die im Verlauf dieser Zeit gepostet werden auch zu sichtigen und davon zu profitieren
| |
Falsches Forum afaik. Die haben doch ein Informatik-Forum
Vielleicht verwechsle ich das aber auch grad mit http://matheplanet.com
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von TriggerTG am 03.08.2007 11:51]
|
|
|
|
|
|
|
|
|
|
Ich will ja ganz bewusst keine Informatik Lösung sondern wie sowas mathematisch angegangen wird. Programmieren tue ich den Algorithmus (sofern einer dabei rauskommt ) dann schon selbst
|
|
|
|
|
|
|
|
|
|
|
|
Mathematiker interessiert doch soeine aufgabe gar nicht
|
|
|
|
|
|
|
|
|
|
|
|
Es soll sie ja auch nicht interessieren, sie sollen nur wissen wie es geht!
|
|
|
|
|
|
|
|
|
|
|
Zum Teufel nochmal, mein Programm rechnet für die kleinen Beispiellösungen absolut korrekt und für die großen ist das Ergbnis angeblich falsch.
Jetzt hab ich die Logik sogar mal umgedreht und es kommt immernoch das selbe raus. Was ist denn das jetzt wieder für ein scheiss?
Määääh, jetzt ist mir das ganze Wochenende versaut! Ich will wissen wie man das löst 
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Achsel-des-Bösen am 03.08.2007 12:02]
|
|
|
|
|
|
|
|
|
Hab die Konsole wieder eingestellt. Die Dame bei eBay war nicht sehr nett. "Das müssen sie mit einem Rechtsberater klären, ob das überhaupt hätte erwähnt werden müssen" und "Der Käuferschutz würde ihnen 175€ bringen".
Bei 300€ kein tolles Geschäft.
Hab jetzt lustig in den klitzekleinen "Da Privatverkauf, keine Gewährleistung/Garantie"-Absatz noch mit reingepackt:
| | Desweiteren verzichten Sie damit auf das Recht
auf den xbox.com Zugang und die Möglichkeit, die Konsole auf xbox.com zu registrieren. | |
|
|
|
|
|
|
|
|
|
|
|
|
Ach zu, Teufle mit dieser Aufgabe, die entsprechend Shells sind zu und werden heute nicht mehr aufgemacht!
|
|
|
|
|
|
|
|
|
|
|
wuhahaha *durchdreh*
das wird langsam immer besser...
|
|
|
|
|
|
|
|
|
|
|
so, ich muss hier raus... sonst dreh ich gleich durch...
das beste ist, ich bin nicht mal sauer oder enttaeuscht, obwohl ich allen Grund haette...
cya
|
|
|
|
|
|
|
|
|
|
|
Ok, weiter mit Euler18:
Baum ist definitiv die Falsche Lösung, wenn, dann Graph nur dadurch werden die "Teilbäume" auch sauber recycelt, so dass man eben nicht wieder weiter hinabsteigt.
Dadurch bekommt man, wenn man die Kosten für das Bewegen im Baum weg lässt, nämlich auf lineare Kosten, da pro Knoten nur ein Vergleich und eine Summe anfallen.
Im Endeffekt ist der Ansatz also schon richtig, so lange die Funktion die den "Teilbaum" aufsummiert sich das Ergebnis merkt und bei erneutem Aufruf zurück gibt und man das ganze eben nicht als binären Baum sondern als Graphen implementiert.
Fehlt uns nurnoch eine effektive Methode, wie wir den Array-Index der Kinder bestimmen. Aber das sollte kein Problem sein, wenn jeder Knoten weis, wo im Dreieck er sitzt, da ein Knoten in Ebene x an Position y genau die Kinder (x+1,y) und (x+1,y+1) hat. Das Dreieck darüber hat ~ (x-1)*((x-1)/2) Knoten (s.u.), wodurch sich dann die Position in einem Array, das einfach alle Knoten Schicht für Schicht hintereinander hat, ergibt. der rest ist OO 
Zusatz:
(1) Die Formel für die Anzahl der Knoten im Dreieck über der aktuellen Ebene ist noch nicht richtig, aber das sollte sich lösen lassen.
(2) ist ja einfach die Summe der ersten n-1 Zahlen... also schnapp ich mir Gauß... und lande bei (x-1)*((x-1)+1)/2... war ich ja garnicht mal so weit weg
|
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von Elkano am 03.08.2007 12:28]
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
OK, scheint zu laufen:
| |
| Code: |
local data = {
3,
7,5,
2,4,6,
8,5,9,3,
}
sum = setmetatable({}, {__index=function(self,pos)
local posindex = floor((pos[1] - 1)*pos[1]/2) + pos[2]
local summe = data[posindex] and data[posindex] + max(sum[{pos[1] + 1, pos[2]}], sum[{pos[1] + 1, pos[2] + 1}]) or 0
self[pos] = summe
return summe
end})
print(sum[{1,1}]) |
|
|
|
|
|
|
|
|
|
| Thema: Gehirnsalat ( wir unter uns ) |
