Blog

In dem nachfolgenden 20×20 Gitter sind vier Nummern entlang einer Diagonalen Linie grün markiert:

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

Das Produkt dieser Zahlen ist 1788696.

Was ist das größte Produkt von vier Zahlen in einer Linie (horizontal, vertikal oder diagonal)?

Lösung

Dieses Problem löst man am einfachsten mit einem Scan-Algorithmus analog zu der Aufgabe mit der 1000-stelligen Zahl.

Man braucht vier Schleifen für horizontale, vertikale und diagonale Suche:

m = [08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
% ...
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48];

test = zeros(1,4);
maxProdukt = 0;

for i = 1 : 20
    for j = 1 : 17
        for k = 0 : 3
            test(k + 1) = m(i, j+k);
        end
        produkt = prod(test);
        if produkt > maxProdukt
            maxProdukt = produkt;
        end
    end
end

for i = 1 : 17
    for j = 1 : 20
        for k = 0 : 3
            test(k + 1) = m(i+k, j);
        end
        produkt = prod(test);
        if produkt > maxProdukt
            maxProdukt = produkt;
        end
    end
end

for i = 1 : 17
    for j = 1 : 17
        for k = 0 : 3
            test(k + 1) = m(i+k, j+k);
        end
        produkt = prod(test);
        if produkt > maxProdukt
            maxProdukt = produkt;
        end
    end
end

for i = 1 : 17
    for j = 4 : 20
        for k = 0 : 3
            test(k + 1) = m(i+k, j-k);
        end
        produkt = prod(test);
        if produkt > maxProdukt
            maxProdukt = produkt;
        end
    end
end

maxProdukt

Ergebnis: 70600674
Rechenzeit: 0.001530 Sekunden