Problem 20: Summe von Ziffern in Fakultäten

Gesucht wird die Summe der Ziffern (Quersumme) der Fakultät von 100! [ das englische Original ]

Da die Fakultät von 100 ist eine so große Zahl, dass sie auf keinem handelsüblichen PC berechnet werden kann. Glücklicherweise habe ich seit dem Problem 13 eine eigene Klasse für große Zahlen zur Verfügung. Dort steht mir bisher allerdings nur eine Methode für die Addition von 2 solcher Zahlen zur Verfügung. Da aber die Berechnung einer Fakultät über eine iterative Multiplikation dargestellt werden kann, und jede Multiplikation wiederum über eine Addition berechenbar ist, reicht mir diese Methode! Ich habe meinen Algorithmus einmal für das Beispiel der Fakultät von 5 dargestellt:

Herleitung des Algorithmus zur iterativen Berechnung von Fakultäten
Herleitung des Algorithmus zur iterativen Berechnung von Fakultäten

Diese Iteration lässt sich leicht durch zwei ineinander verschachtelte Schleifen implementieren. Die Klasse für große Zahlen musste nur um eine Methode zur Berechnung der Quersumme erweitert werden:

@Override
public String solve() {
   int target = 100;
   LargeNumber num = new LargeNumber( 1 );

   for( int i=2; i<=target; i++ ) {
      LargeNumber tmp = num.clone();
      for( int j=1; j<i; j++ ) {
         num = num.add( tmp );
      }
      IO.debugln( i + "! = " + num.toString() );
   }

   return IO.l2s( num.sumOfDigits() );
}

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

<< Problem 19 Übersicht Problem 21 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: