Problem 57: Quadratwurzelkonvergenzen

Gesucht wird die Anzahl von Brüchen innerhalb der ersten 1000 Erweiterungen der unendlichen Summe zur Lösung der Wurzel aus 2, bei denen der Zähler mehr Stellen hat, als der Nenner! [das englische Original]

Dieses Problem wirkt auf den ersten Blick sehr komplex, da scheinbar für jede einzelne Erweiterung die unendliche Summe neu berechnet werden muss. Schaut man sich die Vorschrift aber genau an, sieht man schnell den einfachen Zusammenhang zwischen zwei Schritten. Damit lassen sich wiederum sehr einfach Gleichungen für die Berechnung der Zähler und Nenner aufstellen:

Projekt Euler - Problem 57 - Umstellung der Iteration
Auflösung der einzelnen Iterationsschritte für eine schrittweise Berechnung von Zähler und Nenner

 

Da ich kein Gefühl dafür hatte, wie groß die Zahlen in den ersten 1000 Erweiterungen werden würden, habe ich mich wieder einmal für den Einsatz meiner Klasse für große Zahlen entschieden. Damit war die Ermittlung der Länge von Zahler und Nenner kein Problem:

@Override
public String solve() {

   long count = 0;
   LargeNumber num = new LargeNumber( 3 );
   LargeNumber den = new LargeNumber( 2 );
   LargeNumber nnum;
   LargeNumber nden;
 
   for( int i = 1; i < 1000; i++ ) {
      nnum = num.add( den.mult( 2 ) );
      nden = num.add( den );
      if( nnum.getLength() > nden.getLength() ) {
         IO.debugln( "found " + nnum + " / " + nden );
         count++;
      }
      den = nden;
      num = nnum;
   }
 
   return IO.l2s( count );
}

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

<< Problem 56 Übersicht Problem 58 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: