programmier/mathe herausforderung: projekt euler

[Dr. Picasso]

http://projecteuler.net

scheint ja schon etwas älter zu sein, aber ich kannte es nicht, und vielleicht findet sich ja hier der ein oder andere interessierte

es geht um aufgaben wie zB
"Find the largest palindrome made from the product of two 3-digit numbers."
die man mit hilfe von selbst programmiertem code bearbeiten soll

wer also freude am knobeln hat und ein wenige programmieren kann, ist da genau richtig

ich bin jetzt mit problem 5 fertig (von über 250) und fänds cool wenn DU mitmachen würdest, und dann hier postest wie toll das spiel ist, damit es mir noch mehr spaß macht !

ein mächtiger mod möge den thread in ein anderes forum schieben, falls das comm nicht das richtige ist. ich bin mir unsicher.

 

[Tür]

also ich finde der gehörts ins mathe-etc-forum

 

[butzKiLLjoY]

Yo, ist echt sau geil die seite!

Gab vor ca. nem Jahr mal n Thread im Mathe-Forum, daher kenn ichs.
Ich hab damals die ersten 6 Probleme gelöst, dann aufgehört, weils teilweise doch schon etwas Zeit braucht, aber jetzt hab ich wieder Bock bekommen. ;D

Edit: Ich programmiere mit C++. Mit Matlab sind einige der ersten Probleme ja fast Einzeiler, hab aber zuhause keine Version zur Verfügung.^^

 

[MesH]

Das wollte ich mir länger schonmal angucken, glaube das werd ich nun auch nochmal tun.

 

[ChoseYourWeapon]

Hört sich gut an... hab mich gleich mal angemeldet. Danke für die Anregung.

 

[MesH]

Hmm wirklich cooles Spiel, werde mir das auf jeden Fall noch häufiger mal ansehen wenn bisschen Luft ist. Bin nun grade mit #5 fertig, arbeite mit Stift, Zettel, Taschenrechner und Matlab

 

[Dr. Picasso]

ich mache alles in c++ mit visual studio
werde jetzt lvl 6 versuchen

 

[Dr. Picasso]

ersten 10 lvl hab ich nun fertig
ich tu mir jetzt schon schwer

 

[TriloByte]

Hatten wir schon mal http://starcraft2.ingame.de/forum/showthread.php?t=162592

Cooles Spiel, leider bin ich zu unbegabt dafür.

 

[drwilly]

Mhh, so wie das aussieht eignet sich das ganz gut für einen Programmiereinstieg in Haskell

 

[ChoseYourWeapon]

Ich sitz grad an 15... meine 4 Versuche, per Hand eine rekursive Formel zu finden, sind kläglich gescheitert. Aber gefällt mir sehr gut, besonders weil ich solche Zahlenspielereien mit Primzahlen und so mag. Und erstaunlich, wie man manchmal durch eine simple Überlegung die Effizienz des Programms exorbitant steigern kann. In den Infos steht ja, dass man jede Aufgabe mit einem PC und "normaler" Rechenpower unter einer Minute lösen kann, gilt das für heutige Rechenpower oder die, als die ersten Aufgaben rausgekommen sind (2001) ?

 

[Zerush]

coooool 8)

 

[Didier]

In den Infos steht ja, dass man jede Aufgabe mit einem PC und "normaler" Rechenpower unter einer Minute lösen kann, gilt das für heutige Rechenpower oder die, als die ersten Aufgaben rausgekommen sind (2001) ?

Witzigerweise macht das kaum nen Unterschied. Damals hatten Computer so ca. 1,5 Ghz. Heute hast zwar nen Quadcore aber der läuft auch nur auf 2,5 Ghz. Klar ist die Archtitektur ein wenig besser, aber ganz kommst von der Taktung nicht weg. Solange Du Deinen Algorithmus also nicht parallelisierst sind die Unterschiede nicht so krass. Getestet habe ichs nicht, aber mehr als doppelt so schnell wirds kaum sein.

 

[mfb]

Und erstaunlich, wie man manchmal durch eine simple Überlegung die Effizienz des Programms exorbitant steigern kann. In den Infos steht ja, dass man jede Aufgabe mit einem PC und "normaler" Rechenpower unter einer Minute lösen kann, gilt das für heutige Rechenpower oder die, als die ersten Aufgaben rausgekommen sind (2001) ?

Für einige Aufgaben reicht sogar die Geschwindigkeit des Gehirns. Generell kann man die Programme sehr einfach halten, sodass es vermutlich auch ein PC von 2001 ziemlich schnell schafft.

 

[ChoseYourWeapon]

Ja stimmt zu 2001 machts kaum einen Unterschied... ich hab mir mal ein paar von den höheren Aufgaben angeschaut, da geht nichts mehr mit brute force

 

[xornado]

Gott macht das ganze süchtig ich hab jetzt 18 probleme gelöst, und nun ist es nur noch schwer

 

[xornado]

Gott macht das ganze süchtig ich hab jetzt 18 probleme gelöst, und nun ist es nur noch schwer

Sir Brute-A-Lot hat jetzt die ersten 29 Rätsel geknackt.... white and nerdy.

 

[Brusko651]

Ich fänds spaßiger wenn der computer nicht immer gleich überfordert wäre wenn die scripts mal ein bisschen komplizierter werden. Deswegen versuche ich die meisten Aufgaben garnicht mehr weil ich weiß, ich könnte es schreiben, aber der computer schaffts dann eh nicht.

Hab garkeinen schlechten pc, aber halt auch keinen nasa-supercomputer oder sowas.

edit: ok wenn ich die datei nachher mit google chrome statt firefox öffne funktioniert es anscheinend eh.
Ich hab jetzt nach langer Scheu doch Beispiel 4 versucht und das Ergebnis war dann eh nach 1-2 sekunden am bildschirm.
Mit firefox hab ich aber auch schon ganz andere erfahrungen gemacht.
(ich brauche einen browser weil ich in java script schreibe..)

 

[xornado]

Ich fänds spaßiger wenn der computer nicht immer gleich überfordert wäre wenn die scripts mal ein bisschen komplizierter werden. Deswegen versuche ich die meisten Aufgaben garnicht mehr weil ich weiß, ich könnte es schreiben, aber der computer schaffts dann eh nicht.

Das, so scheint mir, ist ja GERADE die herausforderung am Projekt Euler. mit schierer "Brute Force" kann man fast jedes Rätsel lösen (so man es denn versteht und ein bisschen Programmieren kann) !

Der Trick ist hier jedoch, effiziente Algorithmen zu entwerfen. Tja, und schon bleib ich immer noch auf 230 ungelösten Problemen sitzen, einfach weil ich von Mathe gar keine Ahnung hab und vom Programmieren schon gar nicht

Grüxe,
X

PS: Eventuell können wir ja die ein oder andere Lösungsstrategie fernab von vernerdeten Mathematiker-Blogs diskutieren?

 

[Dr. Picasso]

habe jetzt etwa 30 probleme gelöst. habe immer gleich versucht unter 1sec rechenzeit zu bleiben, und das ist auch problemlos möglich.

problem 15 zum beispiel habe ich im ersten versuch rein rekursiv gelöst, da war ab 13x13 aber keine chance mehr.
dann habe ich einfach die zwischenergebnisse abgespeichert, sodass er jede rechnung nur genau 1x macht, und schon gings bis 40x40 hoch

die schwierigkeit beim diskutieren ist leider, dass jeder in ner anderen programmier-sprache schreibt

 

[Gelöschtes Mitglied 160054]

Für das Diskutieren von Lösungsmöglichkeiten dürfte das aber wenig einschränkend sein, schliesslich sind sich doch die meisten Sprachen relativ ähnlich.

 

[xornado]

zumal ich ja auch nicht den code, sondern die herangehensweise diskutieren wollte

z.b. hab ich ne formel gefunden, die für die folge

123456789101112131415...

die n-te Stelle angibt

Gott, was es alles schon gibt !!!

 

[Brusko651]

also das n-te folgenglied ist gleich n soweit ich das sehe.

 

[xornado]

also das n-te folgenglied ist gleich n soweit ich das sehe.

ne du, das ist in der form soweit erstmal falsch. lies dir das problem einfach mal auf euler durch...

 

[Brusko651]

welches problem is das denn?`ich kann ja jetzt nicht alle lesen.

Ich nehme an du hast die Folge
1,2,3,4,5,6,7,8,9,1,0,1,1,1,2...
und nicht die Folge
1,2,3,4,5,6,7,8,9,10,11,12...
gemeint, oder?

 

[xornado]

welches problem is das denn?`ich kann ja jetzt nicht alle lesen.

Ich nehme an du hast die Folge
1,2,3,4,5,6,7,8,9,1,0,1,1,1,2...
und nicht die Folge
1,2,3,4,5,6,7,8,9,10,11,12...
gemeint, oder?

ich meinte keine folge sondern die "zahl" :
123456789101112131415161718192021...

deren 1000000te Stelle wurde gesucht, und da gibts wohl auch eine Formel für (die zehnte stelle wäre hier z.b. enie 1, die elfte eine Null etc..)

Gruß,
X

 

[Gelöschtes Mitglied 160054]

Braucht man 2 zähler für. Einer zählt einfach immer um eins nach oben, der andere organisiert die tatsächliche position der zahl in der reihe.
Ist ganz einfach

 

[xornado]

Nun, das ist zwar an und für sich richtig, nur leider auch irgendwie äh...ineffizient...z.b. wenn, wie in der aufgabe, die 1000000000te Stelle gefragt ist, oder meinetwegen eine beliebig weiter rechts liegende...

aber an und für sich korrekt

 

[Gelöschtes Mitglied 160054]

naja, wenn man den algorithmus erstmal hingeschrieben hat, sieht man ja die regel nach der das verläuft, von 1-9 braucht man einen Platz für die Zahl, von 10-99, zwei plätze usw.
Das rechnet man dann halt hoch, bis 1 Million ziffern erreicht sind

 

[Brusko651]

Ist die 1000000. Stelle eine 1?
Aber die Aufgabe is ja gar nicht auf Project Euler oder? Da gibts ja keine Aufgaben wo nur 1 Ziffer gesucht ist, das wäre ja recht sinnlos, weil man könnte einfach alle 10 durchprobieren.

Deine Formel kannst du übrigens gerne mal posten
Würde mich interessieren.

edit: Oh ich hab es gefunden. Problem 40.

 

[Gelöschtes Mitglied 160054]

sollte man eigentlich auch per hand lösen können.

1-9 sind die ersten zahlen.
Dann die nächsten 2*90 Stellen für die zahlen von 10-99
dann die nächsten 900 * 3 stellen für die Zahlen von 100-999
die nächsten die nächsten 9000*4...

folgt:

Man schaue wann die Summe: 9*1 + 90 * 2+ 900 * 3 + 9000 * 4 + 90000 *5 usw. gerade noch kleiner ist als eine Million.
Das nächste glied der Summe führt bereits über eine Million hinaus, daher liegt die Zahl darunter.

 

[Brusko651]

sollte man eigentlich auch per hand lösen können.

1-9 sind die ersten zahlen.
Dann die nächsten 2*90 Stellen für die zahlen von 10-99
dann die nächsten 900 * 3 stellen für die Zahlen von 100-999
die nächsten die nächsten 9000*4...

folgt:

Man schaue wann die Summe: 9*1 + 90 * 2+ 900 * 3 + 9000 * 4 + 90000 *5 usw. gerade noch kleiner ist als eine Million.
Das nächste glied der Summe führt bereits über eine Million hinaus, daher liegt die Zahl darunter.

Jo so hab ich das auch gemacht.

 

[xornado]

Jo so hab ich das auch gemacht.

wie gesagt, sicherlich ist dieser ansatz nicht "falsch".

ich persönlich habe es mit VBA gelöst (also einfach alle zahlen als string aneinander gereiht und dann die x-te stelle gesucht), aber irgendwelche crack-mathematiker haben da was erstellt, was viele logs und lamberts W-Funktion enthält.... wenn ihr das problem gelöst habt, müsste dieser vorschlag auch im problem-forum enthalten sein!

x

 

[ROOT]

bitte nur entspoilern wenn ihr aufgabe 3 schon habt :P

Spoiler

lol? zufall?

 

[xornado]

bitte nur entspoilern wenn ihr aufgabe 3 schon habt :P

das ist lulzhaft!

 

[xornado]

Ich weiss ja nicht, ob sich von Euch noch jemand mit dem Spass beschäftigt, aber nichtsdestotrotz hier meine Frage zu Aufgabe 213:

A 30×30 grid of squares contains 900 fleas, initially one flea per square.
When a bell is rung, each flea jumps to an adjacent square at random (usually 4 possibilities, except for fleas on the edge of the grid or at the corners).

What is the expected number of unoccupied squares after 50 rings of the bell? Give your answer rounded to six decimal places.

Mein Lösungsansatz ist nun, genügend oft (ca 400000 mal) diese 50 "Sprünge" zu simulieren, jeweils nach dem 50ten Sprung die Leerstellen zu messen, und am ende, d.h. nach 400000 durchläufen, darüber zu mitteln. Trotzdem ..."computer says: nooo". Falls jemand von Euch das Problem gelöst haben sollte....


Vorschläge?

Gruß,
X

 

[voelkerballtier]

400000 ist halt nicht genuegend oft fuer 6 dezimalstellen. Um die Mittelung auf eine Genauigkeit von 10^-6 zu kriegen musst du eher sowas in der Groessenordnung von 10^12 Werten mitteln (moeglicherweise reicht auch 10^12/50)

 

[xornado]

400000 ist halt nicht genuegend oft fuer 6 dezimalstellen. Um die Mittelung auf eine Genauigkeit von 10^-6 zu kriegen musst du eher sowas in der Groessenordnung von 10^12 Werten mitteln (moeglicherweise reicht auch 10^12/50)

scheisse