Problem 16: Potenz-Ziffern-Summe

Gesucht ist die Summe aller Ziffern – also die Quersumme – der Zahl 21000! [das englische Original]

Die offensichtliche Schwierigkeit dieses Problem besteht darin, dass wieder einmal kein nativer Datentyp eine solch große Zahl darstellen kann. Glücklicher Weise kann ich auf die Klasse für großer Zahlen aus der Aufgabe 13 zurückgreifen! Hier musste ich nur eine Methode für die Berechnung der Quersumme ergänzen und schon war das Datengerüst fertig.

Nun musste ja „nur“ noch der Algorithmus gefunden werden. Glücklicher Weise sollte eine Potenz zur Basis 2 gefunden werden, was die Rechnung sehr vereinfacht:

Herleitung für die iterative Berechnung von 2er Potenzen ab 2^0 = 1
Herleitung für die iterative Berechnung von 2er Potenzen ab 2^0 = 1

Es reicht also eine einfache Schleife, um von 1 bis zur gewünschten Potenz zu rechnen:

@Override
public String solve() {

   int step = 0;
   LargeNumber num = new LargeNumber( 1 );

   while( step < 1000 ) {
      num = num.add( num );
      step++;
   }

   IO.debugln( "2^1000 = " + num );
   return IO.l2s( num.sumOfDigits() );
}

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

<< Problem 15 Übersicht Problem 17 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: