Problem 26: Reziproker Zyklus

Gesucht wird die Zahl d < 1000, deren Division durch 1 den längsten wiederkehrenden Zyklus in den Nachkommastellen enthält! [ das englische Original ]

Um dieses Problem mit Hilfe eines Computerprogramms lösen zu können, muss man sich einmal anschauen, wie man die Division per Hand ausrechnen würde. Ich habe dies einmal am Beispiel von d = 7, also dem Buch 1/7 getan:

Herleitung des Algorithmus zur Bestimmung eines Zyklus bei der Teilung einer Zahl am Beispiel 1 / 7
Herleitung des Algorithmus zur Bestimmung eines Zyklus bei der Teilung einer Zahl am Beispiel 1 / 7

Man kann an diesem Beispiel zwei Dinge erkennen bzw. ableiten:

  1. Man muss lediglich den Rest der Division betrachten, denn wenn ein Rest erneut (zum wiederholten Male) entsteht, ist der Zyklus beendet.
  2. Als Rest können maximal so viele Zahlen entstehen, wie der aktuelle Wert von d – 1. Damit ist klar, dass man unbedingt von 1000 rückwärts gehen sollte, da das Ergebnis von einer großen Zahl zu vermuten ist.

Zur Lösung des Problems habe ich erst einmal eine Methode geschrieben, die die Länge eines Zyklus für eine gegebene Zahl ermittelt:

private int getCycle( int d ) {
  int n = 1, cur = -1, s = 0;
 
  int[] mods = new int[ d ];
  mods[ 0 ] = 1;
 
  IO.debug( "0." );
 
  do {
    s++;
    n *= 10;
    cur = n % d;
    IO.debug( IO.i2s( n / d ) );
    mods[ cur ] += s;
    n -= d * ( n / d );
  } while( mods[ cur ] == s );
 
  IO.debugln( " => " + ( s - ( mods[ cur ] - s ) ) );
 
  return ( n == 0 ) ? 0 : s - ( mods[ cur ] - s );
}

Auf dieser Basis war dann die Lösung des Problem keine Schwierigkeit mehr:

@Override
public String solve() {
 
  int maxC = 0, maxD = 0;
  for( int i=1000; i>maxC; i-- ) {
    int c = getCycle( i );
    if( maxC < c ) {
      maxC = c;
      maxD = i;
      IO.debugln( "found new max for d=" + i + " => " + c );
    }
  }
 
  return IO.i2s( maxD );
}

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

<< Problem 25 Übersicht Problem 27 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: