Problem 30: Ziffern hoch Fünf

Gesucht ist die Summer aller Zahlen, die genauso groß sind, wie die Summe ihrer mit 5 potenzierten Ziffern! [ das englische Original ]

Die Schwierigkeit beim Lösen dieses Problem liegt in drei, die Performance hemmenden, Details:

  1. Wenn man bei 10 beginnt und jeweils um 1 erhöht, müsste man in jedem Schritt die Zahl in ihr Ziffern zerlegen.
  2. Wenn man ohne einen Cache arbeitet, müsste man die Summe der Potenzen für jede Zahl erneut berechnen, auch wenn eine andere Zahl mit denselben Ziffern bereits berechnet wurde.
  3. Wo ist die Obergrenze der zu betrachtenden Zahlen?

Das erste Detail konnte ich leicht klären, in dem ich einfach die bestehende Klasse für Große Zahlen benutzte. Da hier alle Ziffern als einzelne Zahlen in einem Array bespeichert werden, spare ich das Zerlegen. Ich habe einfach eine Methode für die Berechnung der Summe alle potenzierten Ziffern ergänzt.

Um den Cache zu realisieren, war ein wenig mehr Arbeit nötig: Durch die nochmalige Erweiterung der Klasse für Große Zahlen um eine Methode zur Sortierung der Ziffern, konnte ich eine Ziffernfolge als Schlüssel in einer Hashtable verwenden. Dadurch berechne ich nur für eine bisher unbekannte Folge von Ziffern die Summe neu.

Die Obergrenze konnte (oder besser gesagt, wollte) ich nicht bestimmen. So habe ich meinen Algorithmus einfach bis 500.000 laufen lassen. Da bereits ab ca. 125.000 keine neuen Treffer gefunden wurden, war ich mir ziemlich sicher, dass es keine größeren Zahlen mehr geben würde.

Damit ergibt sich folgender Code für die Lösung des Problems:

@Override
public String solve() {
 
   int i = 0;
   LargeNumber one = new LargeNumber( 1 );
   LargeNumber num = new LargeNumber( 9 );
   LargeNumber sum = new LargeNumber();
   LargeNumber tmp, key;
 
   while( i < 500000 ) {
      num = num.add( one );
      key = num.getWithSortedDigits();
 
      if( cache.containsKey( key ) ) {
         tmp = cache.get( key );
      } else {
         tmp = num.sumOfDigitPowers( 5 );
         cache.put( key, tmp );
      }
 
      if( num.equals( tmp ) ) {
         IO.debugln( tmp + " <-> " + tmp );
         sum = sum.add( num );
      }

      i++;
   } 
 
   return sum.toString();
}

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

<< Problem 29 Übersicht Problem 31 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: