Project Euler Problem Nr. 11 / Wegfindung in Matrix

[Saheeda]

Hallo,

ich versuche mich grad an dieser Aufgabe: Problem 11 - Project Euler

(Und möchte das auch gern rekursiv lösen, da ich hier noch großen Übungsbedarf habe...)

Problem:

Beim Ausführen bekomme ich nach einer Weile eine OutOfMemoryException für die mit <<< markierte Zeile.

Ich verstehe nur nicht, warum.

Mir ist klar, dass er einige Möglichkeiten durchprobieren muss und das auch einen Moment dauern kann, aber eigentlich sollte er doch trotzdem irgendwann ein Ergebnis zurückliefern :confused:

        private double findProduct(int y, int x)

        {

            if ((y + 3 < matrix.Length) && (x + 3 < matrix[0].Length))

            {

                double dOne = matrix[y][x];

                double dTwo = matrix[y + 1][x + 1];

                double dThree = matrix[y + 2][x + 2];

                double dFour = matrix[y + 3][x + 3];

                double dProduct = dOne * dTwo * dThree * dFour;

                products.Add(dProduct);


                findProduct(y + 1, x + 1);

            }

            if ((x + 3 < matrix[0].Length))

            {

                double hOne = matrix[y][x];

                double hTwo = matrix[y][x + 1];

                double hThree = matrix[y][x + 2];

                double hFour = matrix[y][x + 3];

                double hProduct = hOne * hTwo * hThree * hFour;

                products.Add(hProduct); <<<<<<<<

                findProduct(y, x + 1);

            }

            if (y + 3 < matrix.Length)

            {

                double vOne = matrix[y][x];

                double vTwo = matrix[y + 1][x];

                double vThree = matrix[y + 2][x];

                double vFour = matrix[y + 3][x];

                double vProduct = vOne * vTwo * vThree * vFour;

                products.Add(vProduct);

                findProduct(y + 1, x);

            }

            return 0;

}

[Shadowman]

Hast du mal geprüft, ob du da vielleicht mit Y ausserhalb deines Wertebereichs liegst?

[Shadowman]

Guten Morgen! Erst wach werden, dann posten... (sorry für den doppelpost)

products ist definiert als List<double>?

An deinem Gerät steht zu einem gewissen Zeitpunkt kein Speicherplatz für einen weiteren Eintrag zur Verfügung.

Du könntest ein try-catch einbauen und im Fehlerfall return 0 machen

Ausserdem könntest du genau an die Fehlerstelle springen und per debugger sehen was das Problem ist.

        private double findProduct(int y, int x)

        {

            try

            {

                if ((y + 3 < matrix.Length) && (x + 3 < matrix[0].Length))

                {

                    double dOne = matrix[y][x];

                    double dTwo = matrix[y + 1][x + 1];

                    double dThree = matrix[y + 2][x + 2];

                    double dFour = matrix[y + 3][x + 3];

                    double dProduct = dOne * dTwo * dThree * dFour;

                    products.Add(dProduct);

                    findProduct(y + 1, x + 1);

                }

                if ((x + 3 < matrix[0].Length))

                {

                    double hOne = matrix[y][x];

                    double hTwo = matrix[y][x + 1];

                    double hThree = matrix[y][x + 2];

                    double hFour = matrix[y][x + 3];

                    double hProduct = hOne * hTwo * hThree * hFour;

                    products.Add(hProduct);

                    findProduct(y, x + 1);

                }

                if (y + 3 < matrix.Length)

                {

                    double vOne = matrix[y][x];

                    double vTwo = matrix[y + 1][x];

                    double vThree = matrix[y + 2][x];

                    double vFour = matrix[y + 3][x];

                    double vProduct = vOne * vTwo * vThree * vFour;

                    products.Add(vProduct);

                    findProduct(y + 1, x);

                }

            }

            catch(OutOfMemoryException) { }

            return 0;

        }

[flashpixx]

Rekursionen können schnell zu Speicherproblemen führen, da man aber jede Rekursion als Iteration umformulieren kann, sollte eine Iteration hier besser sein. Rekursionen führen eben zu mehrfacher Sicherung des Stackframes und damit höherem Speicherbedarf

[Saheeda]

@Shadowman

Ja, products ist eine List<double>.

Ich weiß, wie ich im Debugger einen Breakpoint setze, aber ist es möglich, an eine bestimmte Stelle innerhalb der Rekursion zu springen (z.B. wenn products.Count einen bestimmten Wert erreicht?) Ansonsten kann ich den Debugger hier nicht nehmen, da die Exception erst bei ~130000000 Einträgen auftritt.

Ich habe aber gerade festgestellt, dass ich in meiner Wegsuche einen Pfad vergessen hatten (diagonal von rechts oben nach links unten).

Allerdings produziert mir das trotz try-catch eine StackOverflowException. (Ich nehme an, zu viele Daten für ne Liste?)

Nebenbei: Eine OutOfMemoryException soll doch eigentlich den Speicher vor Überlastung schützen, ist es denn da so intelligent, das einfach abzufangen und zu ignorieren?

private double findProduct(int y, int x)

        {

            try

            {

                if ((y - 3 >= 0) && (x - 3 >= 0))

                {

                    double dOne = matrix[y][x];

                    double dTwo = matrix[y - 1][x - 1];

                    double dThree = matrix[y - 2][x - 2];

                    double dFour = matrix[y - 3][x - 3];

                    double dProduct = dOne * dTwo * dThree * dFour;

                    products.Add(dProduct);


                    findProduct(y - 1, x - 1);

                }


                if ((y + 3 < matrix.Length) && (x + 3 < matrix[0].Length))

                {

                    double dOne = matrix[y][x];

                    double dTwo = matrix[y + 1][x + 1];

                    double dThree = matrix[y + 2][x + 2];

                    double dFour = matrix[y + 3][x + 3];

                    double dProduct = dOne * dTwo * dThree * dFour;

                    products.Add(dProduct);


                    findProduct(y + 1, x + 1);

                }

                if ((x + 3 < matrix[0].Length))

                {

                    double hOne = matrix[y][x];

                    double hTwo = matrix[y][x + 1];

                    double hThree = matrix[y][x + 2];

                    double hFour = matrix[y][x + 3];

                    double hProduct = hOne * hTwo * hThree * hFour;

                    products.Add(hProduct);

                    findProduct(y, x + 1);

                }

                if (y + 3 < matrix.Length)

                {

                    double vOne = matrix[y][x];

                    double vTwo = matrix[y + 1][x];

                    double vThree = matrix[y + 2][x];

                    double vFour = matrix[y + 3][x];

                    double vProduct = vOne * vTwo * vThree * vFour;

                    products.Add(vProduct);

                    findProduct(y + 1, x);

                }

            }

            catch (StackOverflowException)

            {

                return 0;

            }

            catch (OutOfMemoryException)

            {

                return 0;

            }


            return 0;


        }

[lilith2k3]

OutOfMemoryException

heißt in Deinem Fall:

Die Ausnahme, die ausgelöst wird, wenn für die weitere Ausführung eines Programms nicht genügend Arbeitsspeicher zur Verfügung steht.

oder einfach: Der Garbage Collector kann nicht mehr Speicher organisieren, was zu einer Ausnahme führt. Wenn kein weiterer Speicher mehr beansprúcht wird, kann das Programm "normal" weiterlaufen bis der GC den Müll aufräumt.

[Shadowman]

Ich kenne den Algorithmus nicht, aber bist du sicher, dass du für jeden Rekursionsschritt 4 neue Schritte aufrufen musst?

Meinst du nicht vielleicht eher elseif anstatt den weiteren if's?

Zum Thema Debugger:

Setz deinen Breakpoint auf das return 0; innerhalb des catch Blocks, dann bist du genau an der Stelle, die für dich wichtig ist.

Ansonsten kannst du mit einer einfachen Methode arbeiten:

        if(x == wunschwert1 && y == wunschwert2)

        {

            int test = 0;

        }

und dann auf das int test = 0; einen Breakpoint