#04: "Reisekosten", Geschwindigkeit, 16.03.2008

1
2
3
4
…
- 5
- 6
- 7
- 8
- 9
10

Werbeanzeige

S.Seegel

2x Contest-Sieger

Beiträge: 95

22.02.2008, 18:37

Schade. Ich schließe mich vorerst dem Club der Fehlerhaften an, ich komme auch auch 27 :?

Kann einer der 26-als-Lösung-Raushabenden evtl. den Weg angeben ? Nur so zum nachvollziehen, könnte bei der Fehlersuche hilfreich sein.

Zum Seitenanfang

XP^

Treue Seele

Beiträge: 130

22.02.2008, 19:19

[...]

Zum Seitenanfang

grek40

Alter Hase

Beiträge: 1 491

Wohnort: Dresden

22.02.2008, 19:31

Zitat von »"S.Seegel"«

Schade. Ich schließe mich vorerst dem Club der Fehlerhaften an, ich komme auch auch 27 :?

Kann einer der 26-als-Lösung-Raushabenden evtl. den Weg angeben ? Nur so zum nachvollziehen, könnte bei der Fehlersuche hilfreich sein.

Bitte beachten, dass ich den Weg aus Algotechnischen Gründen hier von hinten nach vorn präsentiere und auch grad keinen Bock auf gestalterische Ausarbeitung hab

Durch meinen Lösungstracker hab ich meinen zwischenzeitlichen Speicherverbrauch auf über 500 mb gebracht und das Prog wurde zur lahmen Ente :shock:

Quellcode

7726710 resultiert aus X-11
7726721 resultiert aus X+7
7726714 resultiert aus X*13
1895384 resultiert aus X-11
1895395 resultiert aus X+7
1895388 resultiert aus X*13
6650906 resultiert aus X+7
6650899 resultiert aus X*13
1812629 resultiert aus X-11
1812640 resultiert aus X+7
1812633 resultiert aus X+7
1812626 resultiert aus X+7
1812619 resultiert aus X*13
2741475 resultiert aus X*13
8017011 resultiert aus X-11
8017022 resultiert aus X+7
8017015 resultiert aus X*13
5820779 resultiert aus X*13
3049795 resultiert aus X-11
3049806 resultiert aus 'from'

Zum Seitenanfang

neido

Treue Seele

Beiträge: 225

Wohnort: Wien

22.02.2008, 19:57

Erstmal: Geile Geschichte, David! Gratulation!

Ich denk ich weiß schon wie ich das mache. Ich halte das auch eher für eine Mathe-Aufgabe, aber ich hab überhaupt kein Problem damit. Im Gegenteil.

Zum Seitenanfang

Florianx

Frischling

Beiträge: 49

22.02.2008, 19:59

Ich hätte meinen letzten Post net abschicken sollen, bevor das prog zuende war

beim vorletzten Testcase hängt es in einer Endlosschleife fest

die anderen tests dauern etwa 1000 mal so lange wie bei grek40

Ich sollt mir mal nen verfünftigen Ansatz überlegen...

Zum Seitenanfang

XP^

Treue Seele

Beiträge: 130

22.02.2008, 20:10

Zitat

Die Züge verkehren aber nur nach ganz bestimmten Regeln. Vom Bahnhof Nummer X aus kann man ausschließlich zu den Bahnhöfen mit den folgenden Nummern fahren: X + 7, X - 11 und X * 13. Die Tickets "+7" und "-11" kosten jeweils 1 Sm (Schokomünze), und das Ticket "*13" kostet 2 Sm.

Wie kommst du zu den Werten?

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

22.02.2008, 20:29

Diese Werte sind mir in einer Vision erschienen!

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

XP^

Treue Seele

Beiträge: 130

22.02.2008, 21:46

Zitat von »"David Scherfgen"«

Diese Werte sind mir in einer Vision erschienen!

toll, hab auf so eine Antwort gehofft..

ne aber mal im Ernst.. wie kommst du drauf? Bin ma jetzt net sicha was ich machen soll.

Zum Seitenanfang

Mastermind

unregistriert

22.02.2008, 22:16

Zitat von »"David Scherfgen"«

Hat jemand eine Idee, wie man herausfinden könnte, wie teuer bei N Bahnhöfen die teuerste Strecke ist, die es gibt? Also wie hoch kann das korrekte Ergebnis maximal sein?

Da es wohl nicht die Lösung ist sag ich das böse wort mit F nun doch: Floyd-Warshall und dann alle Paare durchgehen nach dem Maximum. Das sollte Polynomielle laufzeit haben (Floyd Warshall hat glaube ich N^3 und es gibt n*(n-1)/2 paare das ist dann insgesamt auch O(n^3) aber Diskrete Mathe ist ein Weilchen her)

EDIT: du meintest doch die teuerste optimale strecke?!

Und der der gerade NP Hart in den Raum geworfen hat. Das hier ist kein Traveling Salesman, oder sowas. Es muss schneller gehen als Floyd Warshal und der hat wie gesagt O(n^3), ist also keinesfalls NP hart. Oder ich hab die Aufgabe nicht kapiert.