028 – Summe der Elemente auf Diagonalen einer Spirale

 

Wenn man mit der 1 beginnt und dann im Uhrzeigersinn eine Spirale erstellt, sieht die für eine Breite von 5 wie folgt aus:

21 22 23 24 25
20 07 08 09 10
19 06 01 02 11
18 05 04 03 12
17 16 15 14 13

Die Summe der Zahlen auf den beiden Diagonalen ist 101 (die 1 in der Mitte wird nur ein mal gezählt!).

Was ist die Summe der Zahlen auf den beiden Diagonalen, wenn die Spiralmatrix 1001 Elemente breit ist?

Lösung

Es gibt hier verschiedene Lösungsmöglichkeiten. Im Folgenden werden zwei davon vorgestellt.

Möglichkeit 1

Das Problem kann gelöst werden, indem die gewünschte Matrix erstellt und die gesuchten Elemente addiert werden. Dies ist allerdings mit einem erheblichen Aufwand verbunden. Wir wollen diese Lösung daher gar nicht erst implementieren und uns gleich die nächste Möglichkeit anschauen:

Möglichkeit 2

Wenn man die gesuchten Zahlen anschaut, fällt schnell auf, dass sie mit Ausnahme der 1 in Viererblocks auftreten:

1; 3 5 7 9; 13 17 21 25; 31 37 43 49; …

Die Zahlen im ersten Block erhält man, indem man jeweils 2 auf den Vorgänger addiert. Für den nächsten Block muss man jeweils 4 addieren, dann jeweils 6 und so weiter.

Die größte zu addierende Zahl ist 1001*1001, wir schreiben also eine einfache Schleife.

Matlab-Code:

function sum = e028(size)
    tic;
    sum = 1;
    akt = 1;
    summand = 2;
    fertig = 0;

    while fertig == 0
        for i = 1 : 4
            akt = akt + summand;
            if akt <= size*size
                sum = sum + akt;
            else
                fertig = 1;
            end
        end
        summand = summand + 2;
    end
    toc
end

Ergebnis: 669171001
Rechenzeit: 0.000087 Sekunden

Möglichkeit 3

Wenn wir die Zahlen noch ein wenig genauer anschauen, sehen wir, dass die Zahlen rechts oben jeweils die Quadrate der unteraden Zahlen sind, also für alle ungeraden n kleiner oder gleich 1001:

x_0=n^2

Die anderen drei Zahlen ergeben sich zu:

x_1=n^2-n+1

x_2=n^2-2n+2

x_3=n^2-3n+3

Addiert man diese vier Zahlen für einen Schritt auf, ergibt sich:

x_g = 4n^2-6n+6

Wir erhalten dadurch den folgenden Algorithmus.

Matlab-Code:

function sum = e028(size)
    tic;
    sum = 1;
    for n = 3 : 2 : size
        sum = sum + 4 * n^2 - 6 * n + 6;
    end
    toc
end

Ergebnis: 669171001
Rechenzeit: 0.000006 Sekunden

Ähnliche Artikel

Kommentar verfassen