Problem 53: Kombinatorische Auswahl

Gesucht ist die Anzahl von Kombinationen von r aus n Zahlen (mit 1 ≤ n ≤ 100 und rn), die größer als eine Million sind! [das englische Original]

Um diesen Problem zu lösen, kann man einfach mit zwei Schleifen alle Werte von r und n in dem oben genannten Bereich durchlaufen und die jeweilige Anzahl von Kombinationen suchen. Da es sich dabei aber um Kombinationen ohne Wiederholung handelt, müsste man für jeden Schritt jeweils drei Fakultäten berechnen, die wiederum drei Schleifen bedeuten.

Schaut man sich die zur Berechnung benutzte Formel an, kann man sie für die Verwendung in einem Programm gut vereinfachen:

Vereinfachung der Formel für die Berechnung der Anzahl von Kombinationen

Sortiert man die benutzten Elemente beginnenden mit n, so kann man diese in einer handlichen Methode realisieren:

private long combi( int n, int r ) {
   long result = 1;
 
   for( int i = n; i > 0; i-- ) {
      if( i > r ) {
         result *= i;
      }
      if( i <= ( n - r ) ) {
         result /= i;
      }
   }
 
   return result;
}

Um den Ablauf des Programmes jetzt noch zu beschleunigen, sollte man einen Blick auf die Entwicklung der Anzahl von Kombinationen für alle r über einem festen n anschauen:

Beispielhafte Darstellung der Anzahl von Kombination für verschiedene n und r

Wie man sie erhält man in jedem Fall eine Art Glockenkurve. Das heißt, wenn man für ein kleines r einmal die Grenze von 1.000.000 überschritten hat, kann man sich den Test aller weiteren r ersparen, bis man für ein großes r die Grenze wiederum überschreitet.

Mit dieser Optimierung der obigen Methode ergibt sich folgende Lösung:

@Override
public String solve() {
 
   long border = 1000000L;
   int count = 0, r, rl, ru;
 
   for( int n = 1; n <= 100; n++ ) {

      r = 1;
      while( ( r < n / 2 ) && ( combi( n, r ) < border ) ) {
         r++;
      }
      rl = r;
 
      r = n;
      while( ( r > n / 2 ) && ( combi( n, r ) < border ) ) {
         r--;
      }
      ru = r;
 
      if( ru > rl ) {
         IO.debugln( "found " + ( ru - rl + 1 ) + " combis for n = " + n );
         count += ( ru - rl + 1 );
      }
   }
 
   return IO.i2s( count );
}

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

<< Problem 52 Übersicht Problem 54 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: