[HaBo]

Stein · 18.12.08, 16:40

Ich habe da ein php-Problem:
Es geht um diese Aufgabe:
http://projecteuler.net/index.php?se...problems&id=15

Weil mein Programm leider nicht funktioniert habe. Ich es erstmal mit einen 1x1 Kasten versucht:

PHP-Code:

  <?php
function find($xkord, $ykord, $groesse)
{    
    global $number;
    if($xkord < $groesse){
        echo "<tr><td>". $xkord ."</td><td>".$ykord."</td><td>".$number."</td></tr>";
        find($xkord + 1, $ykord, $groesse);
    }
    if($ykord < $groesse){
        echo "<tr><td>". $xkord ."</td><td>".$ykord."</td><td>".$number."</td></tr>";    
        find($xkord, $ykord + 1, $groesse);
    }
    if($xkord = $groesse and $ykord = $groesse){
        $number++;
        echo "<tr><td><b>". $xkord ."</b></td><td><b>".$ykord."</b></td><td><b>".$number."</b></td></tr>";    
    }

}
echo '<html><table border="1"><tr><th>X-Kord</th><th>Y-Kord</th><th>Anzahl</th></tr>';

$number = 0;
find(0,0,1);



echo '</table></html>';

?>

Ich habe die Ausgabe so detailiert gemacht damit ich sehe wo der Fehler ist. Wer sicher die ausgabe mal ansehen will: http://waba.bplaced.net/ways.php Eigentlich läuft ja alles richtig, aber warum wird nachdem das Programm 1x nach rechts und einmal nach unten ist der Zähler doppelt(bzw. beim 2. mal 3-fach) um erhöht?

wenn es ins Code-Kitchen gehört bitte verschieben

odigo · 18.12.08, 16:44

Code:

$xkord = $groesse

= ist ein Zuweisungsoperator und kein Vergleichsoperator. Nimm ==

Gruß odigo

Anzeige

- Anzeige -

Stein · 18.12.08, 16:53

oh meine Gott ist das peinlich. Was es auch immer so dumme Bugs sein müssen die man nie findet. Zu meiner Verteidigung: Ich muss in der Schule immer Pascal nehmen.

easteregg · 18.12.08, 18:29

ich bin lustigerweise auch grad bei dem problem und hatte an sich den gleichen ansatz!
aber durch die rekursion explodiert bei nem 20x20 feld die zeit der berechnung.

aber wie man das optimieren kann, habsch keinen plan!

Lesco · 18.12.08, 20:18

Zitat:

Original von easteregg
ich bin lustigerweise auch grad bei dem problem und hatte an sich den gleichen ansatz!
aber durch die rekursion explodiert bei nem 20x20 feld die zeit der berechnung.

aber wie man das optimieren kann, habsch keinen plan!

Kleiner Tipp: Es gibt ein bestimmtes Untergebiet der Stochastik, mit dem man derartige Probleme beschreiben/lösen kann. Dann reicht sogar ein Taschenrechner.

Stein · 18.12.08, 20:22

Ich versuch gleich mal ob man aus den 1. 10 werten nicht ne Formel bastel kann

easteregg · 18.12.08, 20:36

Zitat:

Original von Lesco

Zitat:

Original von easteregg
ich bin lustigerweise auch grad bei dem problem und hatte an sich den gleichen ansatz!
aber durch die rekursion explodiert bei nem 20x20 feld die zeit der berechnung.

aber wie man das optimieren kann, habsch keinen plan!

Kleiner Tipp: Es gibt ein bestimmtes Untergebiet der Stochastik, mit dem man derartige Probleme beschreiben/lösen kann. Dann reicht sogar ein Taschenrechner.

uh, in dem bestimmten untergebiet war ich extrem schlecht, aber danke für den tipp!

ich such mal rum!

Lep · 18.12.08, 20:40

Wenns um Rekursion geht so nehme man LISP, Scheme oder ne ML-Sprache wie OCaml

easteregg · 18.12.08, 20:48

mit welchem hintergrund?
wenns einfach zum komplex wird, bringt doch die andere sprache auch nichts?
oder gibts da in lisp irgendwleche tollen features die das beschleunigen?

Heinzelotto · 18.12.08, 21:21

Zitat:

Original von easteregg
uh, in dem bestimmten untergebiet war ich extrem schlecht, aber danke für den tipp!

ich such mal rum!

noch ein tipp: überleg dir, wie viele schritte du laufen musst, und wie viele davon nach unten (bzw. rechts) gehen.

mu_ · 18.12.08, 21:37

Code:

(define (countWays x y)
  (cond [(or (= x 0) (= y 0)) 1]
        [else (+ (countWays x (- y 1)) (countWays (- x 1) y))]))

(countWays 20 20)

Eine Lösung in Scheme

Allerdings gibt es eine bessere Möglichkeit:

Mathematische Lösung

Lesco · 19.12.08, 10:45

Zitat:

Original von Lep
Wenns um Rekursion geht so nehme man LISP, Scheme oder ne ML-Sprache wie OCaml

Warum sollte Rekursion in anderen Sprachen schlechter verwendbar sein? Natürlich sieht sowas in Haskell/Scheme/Lisp/$FP-Sprache eleganter aus, doch das ist nicht nur bei Rekursion der Fall. Und tail-recursion können mittlerweile sehr viele Compiler(u.a. auch gcc) wegoptimieren.

mu_ · 19.12.08, 13:53

Schlechter sein wird es nicht. Allerdings denke ich, dass man sich bei Sprachen, die hauptsächlich mit Rekursion arbeiten ( wie eben z.b. Scheme ), mehr Gedanken über den Abarbeitung des Problems macht ( Aufteilung des Problems in Teilprobleme, Wann ist ein Problem tivial lösbar?, usw.. ), als dass man es bei Sprachen macht, die Schleifen nutzen. Und das führt oft zu besseren Ergebnissen, auch wenn Rekursion letztendlich auch nur Schleifen sind.
Ich will das jetzt nicht verallgemeinern, das kommt natürlich immer auf den Programmierer und seinen Wissensstand an. Rein technisch gesehen gibt es afaik keinen Unterschied bis auf die "Implementierung der Sprache" (dass PHP langsamer als C ist sollte man natürlich wissen

).

easteregg · 19.12.08, 14:12

nuja, in dem fall ist php ausreichend, da für die probleme bei euler ja eh der algo ausschlaggebend ist.

und ob ich bei soner rekursionstiefe php oder c nutze spielt glaube keine rolle mehr, weil selbst mit c dürfte das in der form nicht in einer kleinen endlichen zeit lösbar sein.

t3rr0r.bYt3 · 19.12.08, 17:51

OT: Das gleiche Rätsel wurde bei Google Treasure Hunt gestellt.
Spoiler: Es sind immer 20 Schritte rechts und 20 Schritte runter, dabei alle Permutationen? /edit: Vertauschung von 2 gleichgerichteten Schritten natürlich noch wegdividieren.

/edit2: Auf die Gefahr hin, dass ich mich jetzt völlig blamiere, hab ich das mal in SML hingehackt. Viel Spaß beim warten auf die Rekursion

Code:

fun     foo (0, 0)      = 0
|       foo (0, x)      = 1
|       foo (x, 0)      = 1
|       foo (x, y)      = foo (x, y-1) + foo (x-1, y)

/edit3: Produziert ab 17*17 sowieso nen Int-Overflow.

Anzeige

- Anzeige -

18.12.08, 16:40	#1 (permalink)
Stein Registriert seit: 10.10.05 Likes: 0	Rekursion Anzeige Ich habe da ein php-Problem: Es geht um diese Aufgabe: http://projecteuler.net/index.php?se...problems&id=15 Weil mein Programm leider nicht funktioniert habe. Ich es erstmal mit einen 1x1 Kasten versucht: PHP-Code: <?php function find($xkord, $ykord, $groesse) { global $number; if($xkord < $groesse){ echo "<tr><td>". $xkord ."</td><td>".$ykord."</td><td>".$number."</td></tr>"; find($xkord + 1, $ykord, $groesse); } if($ykord < $groesse){ echo "<tr><td>". $xkord ."</td><td>".$ykord."</td><td>".$number."</td></tr>"; find($xkord, $ykord + 1, $groesse); } if($xkord = $groesse and $ykord = $groesse){ $number++; echo "<tr><td><b>". $xkord ."</b></td><td><b>".$ykord."</b></td><td><b>".$number."</b></td></tr>"; } } echo '<html><table border="1"><tr><th>X-Kord</th><th>Y-Kord</th><th>Anzahl</th></tr>'; $number = 0; find(0,0,1); echo '</table></html>'; ?> Ich habe die Ausgabe so detailiert gemacht damit ich sehe wo der Fehler ist. Wer sicher die ausgabe mal ansehen will: http://waba.bplaced.net/ways.php Eigentlich läuft ja alles richtig, aber warum wird nachdem das Programm 1x nach rechts und einmal nach unten ist der Zähler doppelt(bzw. beim 2. mal 3-fach) um erhöht? wenn es ins Code-Kitchen gehört bitte verschieben __________________ Steinhagelvoll

18.12.08, 16:44	#2 (permalink)
odigo Senior Member Registriert seit: 25.12.04 Likes: 54	Code: $xkord = $groesse = ist ein Zuweisungsoperator und kein Vergleichsoperator. Nimm == Gruß odigo __________________ [HaBo] @ Facebook - Gefällt mir!

18.12.08, 16:53	#3 (permalink)
Stein Themenstarter Registriert seit: 10.10.05 Likes: 0	oh meine Gott ist das peinlich. Was es auch immer so dumme Bugs sein müssen die man nie findet. Zu meiner Verteidigung: Ich muss in der Schule immer Pascal nehmen. __________________ Steinhagelvoll

18.12.08, 18:29	#4 (permalink)
easteregg Member of Honour Registriert seit: 14.09.07 Likes: 62	ich bin lustigerweise auch grad bei dem problem und hatte an sich den gleichen ansatz! aber durch die rekursion explodiert bei nem 20x20 feld die zeit der berechnung. aber wie man das optimieren kann, habsch keinen plan! __________________ » Flattr mich! - Wenn dir mein Beitrag geholfen hat! « <\| 2 AMD Opterons 2384@ 8x3,2ghz \| Tyan S2915 \| 10GB \| 2x 8800GT \| 8400GS \| Dell 3008WFP + 2x2007FP \|>

18.12.08, 20:22	#6 (permalink)
Stein Themenstarter Registriert seit: 10.10.05 Likes: 0	Ich versuch gleich mal ob man aus den 1. 10 werten nicht ne Formel bastel kann __________________ Steinhagelvoll

18.12.08, 20:40	#8 (permalink)
Lep Registriert seit: 15.10.08 Likes: 0	Wenns um Rekursion geht so nehme man LISP, Scheme oder ne ML-Sprache wie OCaml

18.12.08, 20:48	#9 (permalink)
easteregg Member of Honour Registriert seit: 14.09.07 Likes: 62	mit welchem hintergrund? wenns einfach zum komplex wird, bringt doch die andere sprache auch nichts? oder gibts da in lisp irgendwleche tollen features die das beschleunigen? __________________ » Flattr mich! - Wenn dir mein Beitrag geholfen hat! « <\| 2 AMD Opterons 2384@ 8x3,2ghz \| Tyan S2915 \| 10GB \| 2x 8800GT \| 8400GS \| Dell 3008WFP + 2x2007FP \|>

18.12.08, 21:37	#11 (permalink)
mu_ Registriert seit: 01.12.08 Likes: 0	Code: (define (countWays x y) (cond [(or (= x 0) (= y 0)) 1] [else (+ (countWays x (- y 1)) (countWays (- x 1) y))])) (countWays 20 20) Eine Lösung in Scheme Allerdings gibt es eine bessere Möglichkeit: Mathematische Lösung countWays M N := (M + N)! / (m!n!) ?!?!LaTeX!?!

19.12.08, 13:53	#13 (permalink)
mu_ Registriert seit: 01.12.08 Likes: 0	Schlechter sein wird es nicht. Allerdings denke ich, dass man sich bei Sprachen, die hauptsächlich mit Rekursion arbeiten ( wie eben z.b. Scheme ), mehr Gedanken über den Abarbeitung des Problems macht ( Aufteilung des Problems in Teilprobleme, Wann ist ein Problem tivial lösbar?, usw.. ), als dass man es bei Sprachen macht, die Schleifen nutzen. Und das führt oft zu besseren Ergebnissen, auch wenn Rekursion letztendlich auch nur Schleifen sind. Ich will das jetzt nicht verallgemeinern, das kommt natürlich immer auf den Programmierer und seinen Wissensstand an. Rein technisch gesehen gibt es afaik keinen Unterschied bis auf die "Implementierung der Sprache" (dass PHP langsamer als C ist sollte man natürlich wissen ).

19.12.08, 14:12	#14 (permalink)
easteregg Member of Honour Registriert seit: 14.09.07 Likes: 62	nuja, in dem fall ist php ausreichend, da für die probleme bei euler ja eh der algo ausschlaggebend ist. und ob ich bei soner rekursionstiefe php oder c nutze spielt glaube keine rolle mehr, weil selbst mit c dürfte das in der form nicht in einer kleinen endlichen zeit lösbar sein. __________________ » Flattr mich! - Wenn dir mein Beitrag geholfen hat! « <\| 2 AMD Opterons 2384@ 8x3,2ghz \| Tyan S2915 \| 10GB \| 2x 8800GT \| 8400GS \| Dell 3008WFP + 2x2007FP \|>

19.12.08, 17:51	#15 (permalink)
t3rr0r.bYt3 Senior Member Registriert seit: 07.01.03 Likes: 19	OT: Das gleiche Rätsel wurde bei Google Treasure Hunt gestellt. Spoiler: Es sind immer 20 Schritte rechts und 20 Schritte runter, dabei alle Permutationen? /edit: Vertauschung von 2 gleichgerichteten Schritten natürlich noch wegdividieren. /edit2: Auf die Gefahr hin, dass ich mich jetzt völlig blamiere, hab ich das mal in SML hingehackt. Viel Spaß beim warten auf die Rekursion Code: fun foo (0, 0) = 0 \| foo (0, x) = 1 \| foo (x, 0) = 1 \| foo (x, y) = foo (x, y-1) + foo (x-1, y) /edit3: Produziert ab 17*17 sowieso nen Int-Overflow.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Kombinationsbildung per Rekursion	Ook!	Code Kitchen	5	02.11.08 14:27
Rekursion - mal wieder... [editiert]	Ook!	Code Kitchen	4	13.07.08 15:26
[Diskusion]: Warum überhaupt Rekursion verwenden?	_fux_	Code Kitchen	16	06.07.08 08:40
[C++] Fragen zur Rekursion	shUnderdog	Code Kitchen	3	28.05.07 17:42

[HaBo]

Rekursion