Problem 39: Ganzzahlige rechtwinklige Dreiecke

Gesucht wird der Umfang eines Dreieckes (kleiner 1000), für den es die meisten Kombinationen an ganzzahligen Seiten gibt! [ das englische Original ]

Für die Lösung dieses Problem kann man natürlich für jeden Umfang von 1 bis 999 die möglichen Seitenkombinationen suchen. Da ich keine Idee hatte, die ich für einen gegebenen Umfang einer Seitenkombination finden kann, habe ich den Spieß einfach umgedreht: Ich kombiniere einfach alle möglichen Seitenlängen, speichere mir für den sich daraus ergebenen Umfang die aktuelle Kombination und weiß so am Ende, für welchen Umfang es die meisten Kombinationen gibt.

Um diesen Algorithmus in einem Programm umzusetzen, muss man sich über die Grenzen der einzelnen Seiten im Klaren werden:

  1. Seite a kann sich grundsätzlich im Bereich von 1 bis 999 bewegen. Sicherlich kann man hier ein wenig optimieren, da es für die genannten Grenzen keine konstruierbaren Dreiecke gibt, was aber recht wenig Aufwand spart.
  2. Seite b kann immer nur im Bereich von b bis 1000 – a liegen, da für alle Fälle in denen b kleiner als a ist, man Kombinationen erhalten würde, die bereits schon einmal aufgetreten sind.
  3. Seite c liegt immer im Bereich von b – a +1 und a + b -1, denn sonst kann man kein Dreieck konstruieren.

Ich habe diese drei Einschränkungen in der nachfolgenden Abbildung dargestellt:

Veranschaulichung, in welchem Bereich die ganzzahlige Seite c eines Dreiecks liegen kann, wenn a und b gegeben sind.
Veranschaulichung, in welchem Bereich die ganzzahlige Seite c eines Dreiecks liegen kann, wenn a und b gegeben sind.

Als ich die obige Grafik zeichnete, fiel mir auf, dass man gar nicht Längen der Seite c in den genannten Grenzen prüfen muss. Denn offensichtlich kann es immer nur eine Länge für c geben, mit der das Dreieck rechtwinkelig wird. Ich habe meine Lösung entsprechend verbessert und konnte die Laufzeit von ca. 250 Millisekunden auf ca. 20 ms absenken!

@Override
public String solve() {
   int[] hits = new int[ 1000 ];
 
   for( int a = 1; a < 1000; a++ ) {
      for( int b = a; b < 1000-a; b++ ) {
         int c = ( int ) Math.sqrt( a*a + b*b );
         if( Mathe.isPythagoreanTriplet( a, b, c ) && ( a+b+c < 1000 ) ) {
            IO.debugln( "found: {" + a + "," + b + "," + c + "} = " + ( a+b+c ) );
            hits[ a+b+c ]++;
         }
      }
   }
 
   int max = 0, pos = 0;
   for( int i = 0; i < hits.length; i++ ) {
      if( max < hits[ i ] ) {
         max = hits[ i ];
         pos = i;
      }
   }
 
   IO.debugln( "max = " + max + " for " + pos );
 
   return IO.i2s( pos );
}

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

<< Problem 38 Übersicht Problem 40 >>

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: