[Geschlossen] rätsel (5$ inside)

Original von Zachanassian
Also mein ahk (s.u.) gibt nach 100,000 versuchen

41,59 Züge. Also aufgerundet 42!

anzahl := 0
tries := 100000
loop, %tries%
{
  anzahl := anzahl + walk()
}
result := anzahl / tries 
MsgBox, %tries%: %result%

walk()
{
 xpos := 13
 ypos := 13
 zug := 0
 loop
 {
  zug := zug + 1
  Random, rand, 1, 8
  if (rand = 1)
  {
    xpos := xpos + 2
    ypos := ypos + 1
  } else if(rand = 2)
  {
    xpos := xpos + 2
    ypos := ypos - 1
  } else if(rand = 3)
  {
    xpos := xpos + 1
    ypos := ypos + 2
  } else if(rand = 4)
  {
    xpos := xpos + 1
    ypos := ypos - 2
  } else if(rand = 5)
  {
    xpos := xpos - 1
    ypos := ypos + 2
  } else if(rand = 6)
  {
    xpos := xpos - 1
    ypos := ypos - 2
  } else if(rand = 7)
  {
    xpos := xpos - 2
    ypos := ypos + 1
  } else if(rand = 8)
  {
    xpos := xpos - 2
    ypos := ypos - 1
  }
 if (xpos < 1) or (xpos > 25) or (ypos < 1) or (ypos > 25)
   break
  
 } 
  
  return zug
}

bei dir werden manchmal felder übersprungen.

die 8 verschiedenen zugkombinationen lauten:

x = x+1
y = y+1

x = x+0
y = y+1

x = x-1
y = y+1

x = x+1
y = y+0

x = x+1
y = y-1

x = x+0
y = y-1

x = x-1
y = y-1

x = x-1
y = y+0

Simulation mit 10mio versuchen:
1. versuch: 134
2. versuch: 130

Mit wie vielen Versuchen hat OP simuliert? Das dauert ja ewig bis da was halbwegs verlässliches rauskommt...

Original von MrBeam06
Also ich bin iwie der festen Meinung, dass der Durchschnitt der verschiedenen Möglichkeiten Unendlich ist.

Tritt nur ein einziges Mal der Fall ein, dass die Lösung unendlich ist hebt dies den Durchschnitt ja dementsprechend (kurz formuliert).

Ist es nicht im Prinzip das gleich wie beim St Petersburg Paradoxon??
Bzw wo ist der Unterschied, wenn meine Lösung falsch ist?

da du ja "unendlich" lange warten musst, bis der mensch "unendlich" lange auf dem brett bleibt, hebt sich dieses "unendlich" wieder auf

du gewichtest die dauer (=unendlich) mit der wahrscheinlichkeit (1/unendlich) und erhältst dann für einen unendlichen weg eine endliche (sehr geringe) endliche zahl (wenn nicht sogar null, aber das sollte ein mathematiker nachrechnen

es gibt eben verschieden grosse "unendlich"

ist nicht ganz sauber mathematisch formuliert, aber ich hoffe, du verstehst auf was ich hinaus will

Hm jetzt bin ich etwas verwirrt. Mein Fehler war der, dass die Figur auch stehen bleiben konnte, was aber dennoch als Zug gezählt wurde. Deshalb hätte ich erwartet das mein Ergebnis (199) um 1/9 zu hoch läge. Aber dem ist wohl nicht so.

Naja mein nächster Versuch lautet: 133

bei mir ca 5min für 10 mio durchgänge :-)

die abweichungen sind bei dir aber zu groß für 10 mio !!
da sollte sich nur noch an der hundertstel stelle was tun!

ps: einer ist schon verdammt knapp dran!

Original von MrMaxx
Hm jetzt bin ich etwas verwirrt. Mein Fehler war der, dass die Figur auch stehen bleiben konnte, was aber dennoch als Zug gezählt wurde. Deshalb hätte ich erwartet das mein Ergebnis (199) um 1/9 zu hoch läge. Aber dem ist wohl nicht so.

Naja mein nächster Versuch lautet: 133

AND THE WINNER IS MrMAXX !!!!!!!!!!!!!!!!!!!!!!!!

war noch am tippen meones letzten posts, als du deinen getippt hattest !!!

gerundet auf ganze zahlen sind wirklich 133 !!!

prima!

Na bitte es geht doch

Habs am Ende mal mit 1mio abgesichert aber eigentlich reichen schon 100k. Der Wert liegt irgendwo bei 132,9.

Grinsefisch und FjodorM waren schon sehr nah dran, jeweils um eins falsch!

bin gespannt, ob meine studis das morgen auch hinkriegen :-) :-)

MrMaxx, kanst mich im communitytool kontaktieren, wie ich dir die 5$ shippen soll :-)

hier die (meine) lösung dazu:

int x, dx;
int y, dy;
int zaehler = 0;
int summe = 0;
int versuche = 10000000;
int feldgroesse = 25;

for (int i = 0; i < versuche; i++) {

x = feldgroesse/2 + 1;
y = feldgroesse/2 + 1;
zaehler = 0;

do
{
zaehler++;
do {
dx = int(random(3)) - 1;
dy = int(random(3)) - 1;
}
while (dx == 0 && dy == 0);

x = x + dx;
y = y + dy;
}
while (x >= 1 && x <= feldgroesse && y >= 1 && y <= feldgroesse );

summe = summe + zaehler;
}

println("ergebnis: " + float(summe) / versuche);

den zufallszahlenteil hätte man evtl. etwas effizienter machen können (bei x=0 AND y=0 würfle ich halt nochmal), aber ansonsten sollt's passen :-)

danke für euer mitknobeln, hoffe euch hat's auch ein bisschen spass gemacht, wenn mir wieder mal was einfällt meld ich mich wieder :-)

ps: schön, in so einer intelligenten community zu sein!! ernsthaft!

Naja brute force Simulationen haben jetzt nicht wirklich viel mit Intelligenz zu tun. Eine mathematische Lösung wäre mir lieber gewesen (aber sau aufwändig).

Original von Grinsefisch
Naja brute force Simulationen haben jetzt nicht wirklich viel mit Intelligenz zu tun. Eine mathematische Lösung wäre mir lieber gewesen (aber sau aufwändig).

Jo, ne exakte Lösung wäre irgendwie interessanter gewesen. Ich wäre mir aber trotzdem nicht so sicher, ob das überhaupt geht (auch mit viel Aufwand ;)). Ich bin nur auf ziemlich schlechte Schranken gekommen.

Original von Metter3330

Original von Grinsefisch
Naja brute force Simulationen haben jetzt nicht wirklich viel mit Intelligenz zu tun. Eine mathematische Lösung wäre mir lieber gewesen (aber sau aufwändig).

Jo, ne exakte Lösung wäre irgendwie interessanter gewesen. Ich wäre mir aber trotzdem nicht so sicher, ob das überhaupt geht (auch mit viel Aufwand ;)). Ich bin nur auf ziemlich schlechte Schranken gekommen.

Brute force is klar einfach(xD....so hab ich meine erste und einzige stochastische irrmeinung geändert).

random(3) => 0/1/2?

Im Übrigen würde ich noch einen Zusatz mit Einbauen und nach einer bestimmten Zahl von Schritten abbrechen, nur für den Fall, dass wir doch mal bei "unendlich" landen:). Kannst ja einfach dazusagen: 100.000 Schritte sollen als "unendlich" gewertet werden...ist zwar unwahrscheinlich, aber korrekterweise sollten wir das tun.

Dann nochmal ne Frage:

Unterscheidet sich das Ergebnis eigentlich je nach Pseudo-Zufallszahlen-Generator?

Welche Programmiersprache ist das?

java?

Original von trylimits

Original von Zachanassian
Also mein ahk (s.u.) gibt nach 100,000 versuchen

41,59 Züge. Also aufgerundet 42!

...

bei dir werden manchmal felder übersprungen.

die 8 verschiedenen zugkombinationen lauten:

x = x+1
y = y+1

...

OK danke. Hatte die Aufgabe nur überflogen und war von der Schachfigur Springer ausgegangen :-)

Original von Grinsefisch
Naja brute force Simulationen haben jetzt nicht wirklich viel mit Intelligenz zu tun. Eine mathematische Lösung wäre mir lieber gewesen (aber sau aufwändig).

eine exakte mathem. lösung läuft ja (wahrscheinlich???) ebenfalls auf force brute (mit abbruchbedingung, wenn die wahrsch. einen bestimmten weg zu gehen einfach zu klein werden), da es ja unendlich viele, immer länger aber auch immer unwahrscheinlicher werdende wege gibt...

@DeVinschi: im prinzip ja, Java, aber ein "abgespecktes" derivat, mit dem sogar studenten der kunst(!!!) programmieren können, ohne zu wissen, was ein compiler ist http://processing.org/

@fifty: random(3) => 0/1/2? genau! alles gleich wahrscheinlich!
2. frage: sicher, der java zufallsalg. ist aber "aprooved"

Nein, eine mathematische Lösung dürfte nicht brute force sein und dürfte nirgends abbrechen, sondern muss die Lösung anders finden.

Das alles gleichwahrscheinlihc ist wusste ich, ging mehr drum ob random(<Zahl) oder random(bis Zahl)....

Klar, die meisten Generatoren liefern zuverlässige Ergebnisse.....aber wäre mal ne interessante Methode zum testen:)

Letzlich ist Dein Problem die 2-dimensionale Variante von Gambler's Ruin. Die Mathematik der 1-dimensionale Variante kann man zum Beispiel hier anschauen: http://www.mathpages.com/home/kmath084/kmath084.htm

Im eindimensionalen Fall ergibt sich (n=13, N=26):

E(n) = (N/2)^2 - (n-N/2)^2 = 13^2 - 0^2 = 169.

Den 2-dimensionalen Fall mathematisch zu erörtern bleibt dem Leser überlassen

Original von KittenKaboodle
Letzlich ist Dein Problem die 2-dimensionale Variante von Gambler's Ruin. Die Mathematik der 1-dimensionale Variante kann man zum Beispiel hier anschauen: http://www.mathpages.com/home/kmath084/kmath084.htm

Im eindimensionalen Fall ergibt sich (n=13, N=26):

E(n) = (N/2)^2 - (n-N/2)^2 = 13^2 - 0^2 = 169.

Den 2-dimensionalen Fall mathematisch zu erörtern bleibt dem Leser überlassen allerdings gibt dieser ansatz nur die ws wieder, von einem gewissen startpunkt auf null zu kommen, jedoch nicht von einem standpunkt x auf 0 oder 2x, was hier gefragt wäre