Matthias Scharwies: Artikel von Claus Schmitt, importiert aus ZUM-Classic

2019-08-25T04:57:09Z

Artikel von Claus Schmitt, importiert aus ZUM-Classic

Neue Seite

Wenn [[BenutzeR:CSchmitt|ich]] mir vornehme, eine neue Programmiersprache zu lernen, bin ich oft enttäuscht, wenn es dann am Anfang nur für das [[Java/Erste_Schritte#Hallo-Welt-Programm|"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!

{{Fortsetzung|
vorher=Erste Schritte|vorherlink=Java/Erste Schritte|
weiter=Die Monte-Carlo-Methode zur Bestimmung der Kreiszahl|weiterlink=Java/Monte-Carlo-Methode|
übersicht=Einstieg in Java (Übersicht)|übersichtlink=Java#Übersicht|}}

== Ulam-Folge ==

Wir beginnen tatsächlich mit einem "phänomenalen Problem", die {{wpde|Ulam-Folge}}:

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

Bekanntlich (aber bis heute nicht bewiesen) hat sich durch ausgiebiges Testen ergeben, dass es für jede Startzahl<code> n </code> 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 [[Algorithmus#Struktogramm|Struktogramm]] entwickeln für diesen "Algorithmus":

[[Datei:Struktogramm-Ulam.svg]]

{{Box|Arbeitshinweis|# Untersuchen Sie, wie dieses Struktogramm in Java-Quelltext übertragen wird.
# Lassen Sie sich von fremdartigen Begriffen nicht irritieren, sondern versuchen Sie nur die Zusammenhänge mit dem Struktogramm zu entdecken.}}

<source lang="java">
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);
}
}
}</source>

Es ergibt sich folgende Ausgabe:

[[Datei:Ulam-Folge-1.png]]

* Mit <code>n % 2</code> wird der {{wpde|Division_mit_Rest#Modulo|Modulo-Operator}} verwendet; <code>n % 2</code> liefert also den Rest bei Ganzzahldivision durch 2. z.B. <code>13 % 2 = 1</code> und <code>13 / 2 = 6</code>
* 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 <code> n </code> 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 <code>args[0]</code> zu; mit Konvertierungsfunktionen kann man geeignete Übergabewerte in Zahlen umwandeln:

<source lang="java">
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
}
}</source>

Liefert mit dem aktuellen Parameter 27:

[[Datei:Ulam-Folge-2.png]]

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

<source lang="java">
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);
}
}</source>

[[Datei: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 <code>3n + 1</code> durch <code>3n - 1</code> ersetzen lässt; die Schüler werden dann sehr schnell nachstehende Folgenentwicklung (und damit eine Endlosschleife) erkennen:

5, 14, 7, 20, 10, 5, 14, …
[[File:Smiley.svg|right|50px]]
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:

<source lang="java">
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);
}
} </source>

[[Datei:Ulam-Folge-4.png]]

{{Fortsetzung|
vorher=Erste Schritte|vorherlink=Java/Erste Schritte|
weiter=Die Monte-Carlo-Methode zur Bestimmung der Kreiszahl|weiterlink=Java/Monte-Carlo-Methode|
übersicht=Einstieg in Java (Übersicht)|übersichtlink=Java#Übersicht|}}

== Siehe auch ==
* {{wpde|Ulam-Folge}}
* {{wpde|Ulam-Spirale}}
* [[Java/Erste Schritte]]

[[Kategorie:Java]]

Java/Ulam-Folge - Versionsgeschichte

Matthias Scharwies: Artikel von Claus Schmitt, importiert aus ZUM-Classic