Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

#04: "Reisekosten", Geschwindigkeit, 16.03.2008

Werbeanzeige

David_pb

Community-Fossil

Beiträge: 3 886

Beruf: 3D Graphics Programmer

  • Private Nachricht senden

51

25.02.2008, 14:36

Zitat von »"Deviloper"«

Ich wüsste nicht wie, aber ist es eigtl. mit Templates möglich, eine Spezialisierungs nicht nur auf einen Typ auszuweiten, sondern auf mehrere? (also in deinem Fall aus char, signed char und unsigned char eine Spezialisierung machen ...)


Jo, so:

C-/C++-Quelltext

 
1
2
3
4
5

template<>
void fill< int, char* >( char* begin, char* end, const int& value )
{
    memset( begin, value, end-begin );
}


Bringt aber keinen Vorteil...
Wie auch immer, gehört hier egtl nicht rein! :) Back to Topic!
@D13_Dreinig

p0llux

Treue Seele

Beiträge: 101

Wohnort: Aachen

Beruf: HiWi (theo. Inf.)

  • Private Nachricht senden

52

25.02.2008, 15:32

Zitat von »"Mastermind"«

Was mich noch interessieren würde... wofür meinstest du sei Warshall aufgrund des Speicherbedarfs ungeeignet? Darauf bezog sich nämlich auch die Frage mit dem Henker.


Um den längsten kürzesten Weg zwischen zwei Knoten zu finden. Immerhin braucht der Warshall-Algorithmus quadratisch viel Speicher und man kommt auch mit linear viel aus. Wenn die Instanz ( :P ) zu groß wird, gibt das schnell Probleme.

Zitat von »"Mastermind"«

Normative Behauptungen über Sprache sind Bullshit. Richtig ist, wie die Leute sprechen, nicht wie irgendwelche Klugscheißer meinen.


Ey Alter, du hasst voll Rescht! Habsch schtotal nisch dran gedacht, Alter! Tut misch escht leid, so richtig konkret! Du könnest ja wenigstens versuchen Beleidigungen aus deinen Posts zu nehmen ;)

PS: Werd' mal dem Duden-Verlag schreiben, sie möchten bitte die Produktion des Dudens einstellen, weil es unwichtig ist, wie Klugscheisser meinen, man müsse sprechen und schreiben *SCNR*
http://www.scienceandcode.org http://www.mathestudium.org

Mastermind

unregistriert

53

25.02.2008, 16:48

Wegen Warshall: Mach einen besseren Vorschlag. Quadratischer Speicherbedarf und Kubische Laufzeit klingen für mich erstmal nicht nach einem großen Drama. Natürlich gibt es praktische Grenzen für n, aber die begrenzen ja auch die eigentliche Aufgabenstellung.

Wenn du den Unterschied zwischen einer (zugegeben "falschen") übersetzung, die ihren Weg in die Akademische Literatur und Lehre gefunden hat und Rechtschreib- bzw. Aussprachefehlern nicht sehen willst ist das dein Problem.

Die Duden Redaktion bemüht sich eigentlich den allgemeinen Sprachgebrauch abzubilden, deswegen werden auch immer neue Wörter und neue Bedeutungen für alte Wörter in den Duden aufgenommen.

Enormator

Frischling

Beiträge: 1

  • Private Nachricht senden

54

25.02.2008, 17:07

Hi

Hi Leute
Das Problem da hat mich jetzt doch auch mal interessiert. Ich bekomme mit meinem Algorithmus ganz gute Zeiten (für nen gnu compiler) aber leider ist immer ein Ergebnis falsch...
Bei 0 zu 49 bei 50 Bahnhöfen sagt er, es ginge mit 3 Sm aber man braucht 5 Sm...
Ansonsten schau ich mal, dass ich mein Programm mal unter Windows kompiliere, damit ich vergleichbare Werte habe.

Bin ein C++ n00b und habe daher eigentlich keine Ahnung von memset oder sowas... hab ne rekursive Funktion geschrieben, die bis auf den o.g. Fehler recht gut läuft.

Wird eigentlich am Ende der Quelltext des Gewinners veröffentlicht? Würde mich mal interessieren wie andere an das Problem rangehen.
Was geht ab? - Wasserfarbe geht immer ab!

S.Seegel

2x Contest-Sieger

Beiträge: 95

  • Private Nachricht senden

55

25.02.2008, 17:39

Re: Hi

Zitat von »"Enormator"«

Hi Leute
Das Problem da hat mich jetzt doch auch mal interessiert.

Willkommen !

Zitat von »"Enormator"«

Ansonsten schau ich mal, dass ich mein Programm mal unter Windows kompiliere, damit ich vergleichbare Werte habe.

Ich entwickele unter Linux (Ubuntu 7.10, gcc 4.1.3). Das wird dich aber auch nicht viel weiter bringen. Für einen aussagekräftigen Vergleich sollten die Werte vielmehr auf dem selben Testsystem bestimmt worden sein.

Zitat von »"Enormator"«

Bin ein C++ n00b und habe daher eigentlich keine Ahnung von memset oder sowas... hab ne rekursive Funktion geschrieben, die bis auf den o.g. Fehler recht gut läuft.

Der erdachte Algorithmus ist viel entscheidender. Erst an zweiter Stelle kommen die Low-Level-Optimierungen ;)

<Edit>
Bei deinem Problem kann ich dir nun doch ohne deinen Code zu kenne helfen (hoffe ich zumindest). Du bist höchst wahrscheinlich in eine kleine Falle bei der Modulo-Rechnung getappt: wenn du das Ziel einer -11-Fahrt berechnest, kann es vorkommen (wenn der Ausgangsbahnhof kleiner 11 ist), dass du eine negative Zahl modulo num_stations rechnen möchtest.
C++ scheint an dieser Stelle zwischen vorzeichenbehafteter und vorzeichenloser Modulo-Rechnung zu unterscheiden. Da num_stations als unsigned int deklariert ist, entscheidet sich der Compiler jedoch falsch.
Ein static_cast dürfte dein Problem lösen:

C-/C++-Quelltext

 
1
2

int destination = (station - 11)%static_cast<int>(num_stations);
if (destination < 0) destination += num_stations;
</Edit>

Viel Erfolg !

Zitat von »"Enormator"«

Wird eigentlich am Ende der Quelltext des Gewinners veröffentlicht? Würde mich mal interessieren wie andere an das Problem rangehen.

Ja, die Quelltexte aller Teilnehmer werden mit der Auswertung veröffentlicht.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

56

27.02.2008, 12:19

Übrigens ...
Tragt mal die Kosten als Graustufenwert in einem Bild auf (x-Achse: from, y-Achse: to). Also so: bild.setPixel(from, to, my_travel_costs(from, to, N)). Das Muster, das dabei herauskommt, sieht sehr interessant aus. Ihr müsst die Graustufenwerte natürlich skalieren, damit man etwas erkennen kann.
David Scherfgens Website | Konzentrationstest Polizei

Mastermind

unregistriert

57

27.02.2008, 13:03

Das ist ja eben die Frage... gibt es ein Muster das man ausnutzen kann (that is kann man die kosten in geschlossener Form ausrechnen), oder muss man wirklich optimieren.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

58

27.02.2008, 13:14

Ich denke nicht, dass es eine geschlossene Form gibt.
David Scherfgens Website | Konzentrationstest Polizei

S.Seegel

2x Contest-Sieger

Beiträge: 95

  • Private Nachricht senden

59

27.02.2008, 13:14

Lustige Idee, sich dem Problem mal durch Visualisierung zu nähern. In so einem Bild ist ja auf den ersten Blick eine gewisse Regelmäßigkeit nicht von der Hand zu weisen.

Trotzdem gehe ich davon aus, dass durch die *13-Schritte (genauer: die Abhängigkeit deren Reichweite vom Ausgangspunkt) eine geschlossene Formel verhindert ist. Für einen Beweis sind meine zahlentheoretischen Kenntnisse jedoch zu sehr eingerostet ;)

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

60

27.02.2008, 14:50

@S.Seegel:
Das menschliche Gehirn ist schließlich der beste bekannte Mustererkennungsapparat, da bietet sich die Visualisierung an.
Übrigens hatte auch ich einen "Geistesblitz" und bekomme nun vergleichbare Zeiten. :D

@Alle:
Achtung, ich habe eine Sache in den Regeln geändert:
Es ist verboten, sich Dinge in statischen oder globalen Variablen für den jeweils nächsten Durchlauf des Algorithmus zu merken, um ihn zu beschleunigen (das gilt auch für Speicherreservierungen o.Ä.).
David Scherfgens Website | Konzentrationstest Polizei

Werbeanzeige