Problem 28: Diagonalen einer Zahlenspirale

Gesucht ist die Summe aller Elemente auf den Diagonalen einer 1001 x 1001 großen Matrix! [das englische Original]

Die Elemente der Matrix werden dabei, beginnend in der Mitte, spiralenförmig erzeugt. Mein erster Gedanke war, die bereits vorhandene Matrix-Klasse zu nutzen, um alle Elemente zu erzeugen. Dies würde allerdings schon einige Zeit brauchen. Schaut man sich die gesuchten Elemente einzeln an, erkennt man einen wesentlichen einfacheren Algorithmus, wie die nachfolgende Grafik zeigt:

Herleitung des Algorithmus zur Lösung des Problem 28
Herleitung des Algorithmus zur Lösung des Problem 28

Somit reicht eine einfache Schleifen, um die gewünschte Lösung zu finden:

@Override
public String solve() {
   int num = 1, sum = num, diff = 2;
   
   int size = 1001;
   
   for( int i=1; i<=(size-1)/2; i++ ) {
      num += diff; sum += num;
      num += diff; sum += num;
      num += diff; sum += num;
      num += diff; sum += num;
      diff += 2;
   }

   return IO.i2s( sum );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 28 kann man sich hier anschauen!

<< Problem 27 Übersicht Problem 29 >>

 

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: