Java/Ulam-Folge

Aus ZUM-Unterrichten

Wenn ich mir vornehme, eine neue Programmiersprache zu lernen, bin ich oft enttäuscht, wenn es dann am Anfang nur für das "Hallo Welt"-Programm reicht …

Das Problem bei der Einführung ist meist, dass der Autor genug mit den Besonderheiten der Syntax und der Benutzeroberfläche zu tun hat, so dass das Problem eher dienenden Charakter hat. In Wirklichkeit sind Programmiersprachen aber nur ein (austauschbares, dienendes) Werkzeug, um Probleme zu lösen.

Lassen Sie uns also ein Problem in den Mittelpunkt und die technischen Randbedingungen zurück stellen!


Ulam-Folge

Wir beginnen tatsächlich mit einem "phänomenalen Problem", die Ulam-FolgeWikipedia-logo.png:

  • Wähle als Startzahl n eine beliebige natürliche Zahl.
  • Für gerades n entsteht das nächste Element der Folge, indem man n halbiert.
  • Für ungerades n muss man n entsprechend verdreifachen und dann 1 addieren.


Bekanntlich (aber bis heute nicht bewiesen) hat sich durch ausgiebiges Testen ergeben, dass es für jede Startzahl n ein letztes Folgenglied gibt, und zwar 1  !!!

Obiges Ulam-Verfahren terminiert also jeweils, und das wäre in der vermuteten Allgemeingültigkeit eine wesentliche Bedingung für einen Algorithmus.

Vom Algorithmus zum Programm

Lassen Sie uns ein Struktogramm entwickeln für diesen "Algorithmus":

Struktogramm-Ulam.svg


Arbeitshinweis
  1. Untersuchen Sie, wie dieses Struktogramm in Java-Quelltext übertragen wird.
  2. Lassen Sie sich von fremdartigen Begriffen nicht irritieren, sondern versuchen Sie nur die Zusammenhänge mit dem Struktogramm zu entdecken.
class Ulam  {
	public static void main (String[] args)  {	      
	  int n = 13;
	  System.out.println(n);
	  while(n != 1) {
	     if(n % 2 == 0)  n = n / 2;
	     else            n = 3*n + 1;
	     System.out.println(n);   
	  }
     }
}

Es ergibt sich folgende Ausgabe:

Ulam-Folge-1.png


  • Mit n % 2 wird der Modulo-OperatorWikipedia-logo.png verwendet; n % 2 liefert also den Rest bei Ganzzahldivision durch 2.
    z.B. 13 % 2 = 1 und 13 / 2 = 6
  • Die Mengenklammern markieren Blöcke, wie man sie z.B. von der "BEGIN END Klammerung" bei Pascal kennt.


Dateneingabe

Da es unpraktisch ist, den Startwert n immer neu zu editieren, sieht man eine kommandozeilenorientierte Eingabe vor:

Die aktuellen Parameter werden als Zeichenketten gelesen; nach einer Leerstelle folgt der nächste Parameter; auf den ersten greift man über args[0] zu; mit Konvertierungsfunktionen kann man geeignete Übergabewerte in Zahlen umwandeln:

class Ulam  {
	public static void main (String[] args)  {
          //Der erste Parameter hat die Nummer 0
	    int n = Integer.parseInt(args[0]); 
          //Die While-Schleife klammert einen Block von Anweisungen
	    while(n != 1) {      
	      if(n % 2 == 0)               
		  n = n / 2;                 
		else                         
		  n = 3*n + 1;               
		System.out.printf("%d,  ",n);    
	    }
              //im Formatstring ist %d ein Platzhalter für eine ganze Zahl
	}
}

Liefert mit dem aktuellen Parameter 27:

Ulam-Folge-2.png

Formatierung

Zur vernünftigen Darstellung der Ulam-Folge fehlt jetzt nur noch eine geeignete Formatierung:


class Ulam  {
  public static void main (String[] args)  {
    int n = Integer.parseInt(args[0]);
    int i = 0;
    while(n != 1) {
     //Index für das Ulam-Folgenglied
     i = i +1;                       
     if(n % 2 == 0)    
         n = n / 2;
     else    
        n = 3*n + 1;
     // 7 Plätze für jede Zahl
     System.out.printf("%7d,",n); 
     // Zeilenwechsel immer nach 10 Zahlen  
     if (i%10 == 0 )
        System.out.println();      
    }
        // Schleife beendet  
   //%n steht für einen Zeilenwechsel                               
   System.out.printf("%n%nDiese Ulamfolge umfasst %d Zahlen.%n",i); 
    }
}

Ulam-Folge-3.png

Problem: Finden der längsten Ulam-Folge

Man kann im Unterricht ein Problembewusstein entwickeln, dass die Termination dieser Entwicklung keinesfalls selbstverständlich ist, indem man z.B. den Term 3n + 1 durch 3n - 1 ersetzen lässt; die Schüler werden dann sehr schnell nachstehende Folgenentwicklung (und damit eine Endlosschleife) erkennen:

5, 14, 7, 20, 10, 5, 14, … 
Smiley.svg

Im Wettbewerb der Gruppenarbeit ist es immer eine spannende Angelegenheit, die Startzahl zu finden, welche die längste (?) Ulam-Folge bewirkt.

Bis die Ulamfolge eine Zweierpotenz trifft, entwickeln sich oft sehr große Zahlen; im obigen Beispiel ist 9232 das größte Folgenglied.

In unserem Java-Programm ist das eine schöne Gelegenheit, auch eine einseitige Verzweigung zu berücksichtigen:

class Ulam  {
  public static void main (String[] args)  {
    int n = Integer.parseInt(args[0]);
    //Zunächst wird das Maximum auf den Startwert gesetzt.
    int max = n;     
    int i = 0;
    while(n != 1) {
     i = i +1;
     if(n % 2 == 0)    
        n = n / 2;
     else    
       n = 3*n + 1;
     if (n > max)
       max = n;
    }
    System.out.printf("%nDiese Ulamfolge umfasst %d Zahlen; %n",i);
         System.out.printf("das groesste Folgenglied ist %d.%n",max);   
  }
}

Ulam-Folge-4.png

Siehe auch