Problem 31: Summen von Münzen

Gesucht ist die Anzahl der Möglichkeiten, um mit den 8 Münzen der Britischen Währung genau 2 Pfund zu erhalten! [ das englische Original ]

Dieses Problem lässt sich mit einer Rekursion recht einfach lösen. Dabei ist es sehr vorteilhaft, dass – egal welche Kombination von Münzen gewählt wird – der möglicher Weise fehlende Betrag immer durch eine ganzzahlige Anzahl von 1 Pence Stücken auffüllbar ist:

private void check( int level ) {
   int div = 200 / coins[ level ];
   for( int i=0; i<=div; i++ ) {
      used[ level ] = i;
      int sum = getSum();
      if( sum == 200 ) {
         count++;
         IO.debugln( "found [ " + IO.join( used, ", " ) + " ]" );
         i = div;
         used[ level ] = 0;
      } else if( sum > 200 ) {
         i = div;
         used[ level ] = 0;
      } else {
         if( level == 6 ) {
            count++;
            used[ 7 ] = 200 - sum;
            IO.debugln( "found [ " + IO.join( used, ", " ) + " ]" );
            used[ 7 ] = 0;
         } else {
            check( level+1 );
         }
      }
   }
}

Nun braucht es nur noch eine Methode, um die Summe der aktuellen Kombination zu berechnen:

private int getSum() {
   int res = 0;

   for( int i=0; i<coins.length; i++ ) {
      res += coins[ i ] * used[ i ];
   }

   return res;
}

Der Aufruf der rekursiven Methode und das Auslesen des Attributes zum Zählen der Schritte sind dann die einzigen Aufrufe, um das Problem zu lösen!

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

<< Problem 30 Übersicht Problem 32 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: