Problem 8: Größtes Produkt in einer Serie

Gesucht werden die 13 Ziffern innerhalb einer gegebenen 1000-stelligen Zahl, deren Produkt am größten ist! [das englische Original]

Um dieses Problem zu lösen, kann man im einfachsten Fall eine Art Fenster mit der Breite 13 über die 1000 Zeichen laufen lassen und das jeweilige Produkt berechnen. Diese Art und Weise birgt aber 2 Nachteile:

  1. Das Auslesen der Ziffern in einem Fenster erfordert eine Schleife! Und da alles bereits in einer Schleife läuft, erhöht sich hier die Abarbeitungszeit entsprechend.
  2. Wenn einer der Ziffern eine Null ist, ist auch das Produkt für alle 13 Fenster, in denen diese Null vorkommt, Null. Damit könnte man die mindestens 12 Durchläufe sparen.

Ich habe daher lieber eine etwas speicherintensive Lösung gefunden, die allerdings mit nur einem Schleifendurchlauf auskommt:

public String solve() {
   long max = 0;
   for( int i=0; i<digits.length; i++ ) {
      int cur = digits[ i ];

      if( cur == 0 ) {
         resetStorages();
      } else {

         for( int j=0; j<window; j++ ) {
            counts[ j ]++;

            if( counts[ j ] > 0 ) {
               products[ j ] *= cur;
            }

            if( counts[ j ] == window ) {
               if( max < products[ j ] ) {
                  max = products[ j ];
                  IO.debugln( "found new max = " + max );
               }

               products[ j ] = 1;
               counts[ j ] = 0;
            }
         }
      }
   }

   return IO.l2s( max );
}

Dies setzt eine entsprechende Initialisierung voraus:

public void prepare() {
  super.prepare();
  window = 13;
  counts = new int[ window ];
  products = new long[ window ];
  digits = IO.readDigits( "1000digits.txt", 1000 );
  resetStorages();
}

Die in beiden o.g. Codestücken genutzte Methode zum Rücksetzen der internen Speicher ist recht trivial:

private void resetStorages() {
  for( int i=0; i<window; i++ ) {
    counts[ i ] = -i;
    products[ i ] = 1;
  }
}

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

<< Problem 7 Übersicht Problem 9 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: