Binomialkoeffizient, wie findet man k und n heraus

[sserio]

Ich habe mich mal an https://projekteuler.de/problems/18 drangesetzt und mir überlegt, dass ich ja jeden Weg in einer Liste speichern könnte. Die Listen dann jeweils zusammen rechnen und die größte wiedergeben. Die Frage ist bloß, wie man k und n herausfindet oder ob man diese gar nicht erst dafür braucht.

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

 

[thecain]

Wieso willst du bei der Aufgabe den Binomialkoeffizient verwenden?

 

[sserio]

Wieso willst du bei der Aufgabe den Binomialkoeffizient verwenden?

Wie den sonst? Mir fällt sonst nichts ein

 

[thecain]

Was soll er denn bringen? Wieviele verschiedene Wege es gibt steht ja schon da, da musst du nichts mehr rechnen...

 

[sserio]

Was soll er denn bringen? Wieviele verschiedene Wege es gibt steht ja schon da, da musst du nichts mehr rechnen...

Dachte man kann mit diesem auch alle möglichen wegen berechnen, also rechts links links rechts etc... wie sonst

 

[Jw456]

Du sollst doch genau so duch das Dreieck gehen wie in dem Beispiel.

Also Spitze
Dann erste Zahl
Dann zweite
Dritte ....

 

[thecain]

Ich würde mal einen Ansatz mit Dynamic Programming versuchen.

 

[Jw456]

Du brauchst doch nur von der Spitze
Dach unten immer in der Zeile unter dem Wert den größeren Wert benutzen.
Ausgehend von diesem wider eins tiefer und den größeren von den beiden benutzen.
....

 

[thecain]

Nein, das funktioniert nicht...

 

[sserio]

Nein, das funktioniert nicht...

ja das habe ich mir auch gedacht, weil ja theoretisch irgendwo ne 1 sein kann und dann nur noch 99 darunter

 

[fhoffmann]

Ich würde mal einen Ansatz mit Dynamic Programming versuchen.

Das ist im Prinzip korrekt - wird aber erst im Euler-Problem 67 verlangt.
Im Euler-Problem 18 kannst du alle möglichen Pfade ausprobieren und dir das Maximum merken:

int max = 0;
für jeden möglichen Pfad {
  int berechneteLänge = ...
  if (berechneteLänge > max) {
    max = berechneteLänge;
  }
}
System.out.println(max);

 

[Jw456]

Fange unten an bilde die beiden Pärschen. Trage das größere Ergebnis in das Array ein .
Mit der nächsten Zeile das gleiche bis nach oben dann hast du dein Ergebnis.

      3
    7   4
  2   4   6          
8   5   9   3          



                3+20=23

         7+13=20     4+15=19

    2+8=10    4+9=13     6+9=15

8          5          9            3

 

[sserio]

Fange unten an bilde die beiden Pärschen. Trage das größere Ergebnis in das Array ein .
Mit der nächsten Zeile das gleiche bis nach oben dann hast du dein Ergebnis.

      3
    7   4
  2   4   6         
8   5   9   3         



                3+20=23

         7+13=20     4+15=19

    2+8=10    4+9=13     6+9=15

8          5          9            3

Ich habe es jetzt geschafft, durch "Glück"

package ProjectEuler18;

public class Main {
    public static int triangle[][];

    public static void main(String[] args) {
        triangle = new int[15][15];
        addTo(0, new int[]{75});
        addTo(1, new int[]{95, 64});
        addTo(2, new int[]{17, 47, 82});
        addTo(3, new int[]{18, 35, 87, 10});
        addTo(4, new int[]{20, 4, 82, 47, 65});
        addTo(5, new int[]{19, 1, 23, 75, 3, 34});
        addTo(6, new int[]{88, 2, 77, 73, 7, 63, 67});
        addTo(7, new int[]{99, 65, 4, 28, 6, 16, 70, 92});
        addTo(8, new int[]{41, 41, 26, 56, 83, 40, 80, 70, 33});
        addTo(9, new int[]{41, 48, 72, 33, 47, 32, 37, 16, 94, 29});
        addTo(10, new int[]{53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14});
        addTo(11, new int[]{70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57});
        addTo(12, new int[]{91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48});
        addTo(13, new int[]{63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31});
        addTo(14, new int[]{4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23});
        for (int i = 0; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                System.out.printf("%1$02d ", triangle[i][j]);
            }
            System.out.println();
        }
        System.out.println(biggestPathSum(triangle));
    }

    public static void addTo(int row, int[] numbers) {
        int index = numbers.length;
        int temp = 0;
        for (int i = 0; i < triangle[row].length; i++) {
            if (temp < index) {
                triangle[row][temp] = numbers[temp];
                temp++;
            }
        }
    }

    public static int biggestPathSum(int[][] triangle) {
        int summenHalter = 0;
        for (int i = triangle.length - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                final int LEFT = j;
                final int RIGHT = j + 1;
                triangle[i][j] += Math.max(triangle[i + 1][LEFT], triangle[i + 1][RIGHT]);
            }
        }
        return triangle[0][0];
    }
}

Wüsstest du warum man bei meiner Methode biggestPathSum() bei der ersten ForSchleife bei length -2 anfängt und nicht bei length -1. Also ich habe es ausprobiert und -2 ist richtig, jedoch erscheint mir -1 logischer

 

[mihe7]

Wüsstest du warum man bei meiner Methode biggestPathSum() bei der ersten ForSchleife bei length -2 anfängt und nicht bei length -1.

Weil Du ausgehend von der vorletzten Zeile (i == length-2) auf die Werte der letzten Zeile (i+1) zugreifst.

 

[Jw456]

Minus 1 ist ja weil das Array von 0 bis 14 geht und triangle.length dir 15 die Anzahl der Elemente gibt.
Die letzte Zeile hast du ja schon also geht es bei 0-14 bei 13 los.

Wenn dir triangle.length 15 gibt dann minus 2

 

[berndoa]

Also falls du die einzelnen Zeilen der Pyramide als Listen /arrays gegeben hast, dann würde ich mir ganz salopp nur das in der letzten Reihe benutzte Element und dessen Index merken.

Also zuerst Element=75, index=0 (1. reihe hat halt nur 1 element welches an index=0 ist)
nächste reihe hat 2 elemente mit index 0 und 1.
dann guckst du dir deinen aus der vorreihe üebrnommenen index an und vergleichst ob
reihe2[index] oder reihe2[index+1] größer ist.
je nachdem wird element und idnex auf das gewählte objekt angepasst.

rinse and repeat. Und natürlich nicht vergessen, bei jeder wahl eines Elements das zu einer separat geführten Summierungsvariable hinzuzuzählen (schließlich wilslt du ja nicht nur den gewissen pfad an elemente lang gehen sondern auch deren Summe wissen!

Edit: Nur wie ich die Aufgabe verstand, falls es da andere Auffassungen gibt:
Man hat ein rotes gewähltes Element in zeile k an index i.
das nächste element in der zeile darunter, also in zeile k+1, findet man indem man sich in zeile k+1 die elemente an idnexstelle i und i+1 anguckt, guckt, wldches von beiden größer ist und dasjenige als das folgelement des pfades nimmt.
rinse and repeat bis man von ganz oben nach ganz unten kam.
und halt zwischendurch die jeweils gewählten elemente aufaddieren, was nicht schwer ist.

habt ihr die Aufgabe anders aufgefasst?
Manche der Beiträge hier lassen es vermuten

 

[mihe7]

habt ihr die Aufgabe anders aufgefasst?

Ja. Es soll die maximale Summe gefunden werden.

Beispiel:

  1
 1 3
9 3 4

Nach Deiner Methode würdest Du den Pfad 1 -> 3 -> 4 wählen (Summe 8). Gesucht wäre aber 1 -> 1 -> 9 (Summe 11).

 

[M.L.]

andere Auffassungen

die ganzen Project-Euler Aufgaben verlangen u.a. die Anwendung von Methoden um "brute-Force" (weitgehend) zu vermeiden. Die Vorgabe von Problem 18 (oder 67) hat z.B. strukturelle Ähnlichkeiten zum "AVL-Baum" oder "Binärer Suchbaum".

 

[berndoa]

Ja. Es soll die maximale Summe gefunden werden.

Beispiel:

  1
 1 3
9 3 4

Nach Deiner Methode würdest Du den Pfad 1 -> 3 -> 4 wählen (Summe 8). Gesucht wäre aber 1 -> 1 -> 9 (Summe 11).

Ja, nahc etwas mehr Überlegen habe ich auch den Untershcied verstanden.

Aber, gerade wenn man die Beispielpyramide anguckt, scheint es ja wirklich so als würde man von oben nach unten immer zum Größeren der beiden Nachfolgewerte gehen.

Im Beispiel also der Pfad 3,7,4,9.
Dass der, rein zufällig, der Pfad ist wo die Summe der Pfadelemente größer ist als alle anderen möglichen Pfade, war aus der schlecht gewählten Pyramide so nicht ersichtlich für mich.

Aber jetzt versteh ichs auch und es ist fast schon genial wie man die bisherige Summe der Pfadelemente von unten immer weiter mit nach oben zieht.,

Muss man erst mal draufkommen.

Nur, falls mal gefragt, dadraus dann den perfekten Pfad zu rekonstruieren wird schwierig

An sich habt ihr das in ein hübsches Rekursionsproblem umgeformt, bei dem die Arraylänge immer kleiner wird




@M.L. : Mein Vorgehen hatte auch Methode, es hat nur die falsche Aufgabenstellung beantwortet