Rekursion

Stein

Stein

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

Weil mein Programm leider nicht funktioniert habe. Ich es erstmal mit einen 1x1 Kasten versucht:
PHP: 
<?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
 
Code: 
$xkord = $groesse

= ist ein Zuweisungsoperator und kein Vergleichsoperator. Nimm ==

:D

Gruß odigo
 
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.
 
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! :(
 
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! :(
Zum Vergrößern anklicken....

Kleiner Tipp: Es gibt ein bestimmtes Untergebiet der Stochastik, mit dem man derartige Probleme beschreiben/lösen kann. Dann reicht sogar ein Taschenrechner.
 
Original von Lesco
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! :(
Zum Vergrößern anklicken....

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

uh, in dem bestimmten untergebiet war ich extrem schlecht, aber danke für den tipp! ;)
ich such mal rum!
 
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?
 
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:
countWays M N := (M + N)! / (m!n!)
?!?!LaTeX!?!
 
Original von Lep
Wenns um Rekursion geht so nehme man LISP, Scheme oder ne ML-Sprache wie OCaml :D
Zum Vergrößern anklicken....

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.
 
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 ;)).
 
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.
 
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 :D

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.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben