Problem 44: Fünfeckszahlen

Gesucht wird das Paar von Fünfeckszahlen, dessen Summe und Differenz ebenfalls Fünfseckszahlen sind und die Differenz minimal ist! [das englische Original]

Wie schon in Problem 42 brauchte es  eine Methode die prüft, ob eine gegebene Zahl eine Fünfeckszahl ist. Um dies zu Testen muss man die gegeben Formel zur Berechnung einer Fünfeckszahl umstellen:

Herleitung der Formel zum Prüfen, ob eine gegebene Zahl eine Fünfeckszahl ist.
Herleitung der Formel zum Prüfen, ob eine gegebene Zahl eine Fünfeckszahl ist.

Dies lässt sich im folgenden Einzeiler umsetzen:

public static boolean isPentagonNumber( int num ) {
   return ( 1 + Math.sqrt( 24.0 * num + 1 ) ) % 6 == 0;
}

Um nun sowohl die Iteration über alle Fünfeckszahlen zu beschleunigen als auch eine Abbruchbedingung zu definieren, habe ich mir die Differenz zwischen zwei Fünfeckszahlen angeschaut:

Für zwei aufeinanderfolgende Fünfeckszahlen x1 und x2 kann man die Differenz leicht als

x2 - x1 = 3 * i +1

berechnen! Mit diesem Zusammenhang und der obigen Formel ist die Lösung des Problems recht einfach:

@Override
public String solve() {
 
   int next = 0, i = 0, D = Integer.MAX_VALUE;
 
   while( D > ( 3 * i + 1 ) ) {
      next += 3 * i + 1;
      for( int p = pentagons.size()-1; ( p >= 0 ) && ( D > ( next - pentagons.get( p ) ) ); p-- ) {
         int curr = pentagons.get( p );
         if( Mathe.isPentagonNumber( next + curr ) && Mathe.isPentagonNumber( next - curr ) ) {
            IO.infoln( "found @ {" + i + "|" + p + "} >> " + next + " + / - " + curr + " = " + ( next + curr ) + " / " + ( next - curr ) );
            D = ( D > ( next - curr ) ) ? ( next - curr ) : D;
         }
      }
      pentagons.add( next );
      i++;
   }
 
   IO.infoln( "stop @ i=" + i );
 
   return IO.i2s( D );
}

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

<< Problem 43 Übersicht Problem 45 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: