Datei:Monte-carlo-4.png und Java/Ulam-Folge: Unterschied zwischen den Seiten
(User created page with UploadWizard) Markierung: Hochladeassistent |
(Artikel von Claus Schmitt, importiert aus ZUM-Classic) |
||
Zeile 1: | Zeile 1: | ||
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 … | |||
| | |||
| | |||
=={{int: | 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<br> zur Bestimmung der Kreiszahl|weiterlink=Java/Monte-Carlo-Methode| | |||
übersicht=Einstieg in Java<br>(Ü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.<br>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<br> zur Bestimmung der Kreiszahl|weiterlink=Java/Monte-Carlo-Methode| | |||
übersicht=Einstieg in Java<br>(Übersicht)|übersichtlink=Java#Übersicht|}} | |||
== Siehe auch == | |||
* {{wpde|Ulam-Folge}} | |||
* {{wpde|Ulam-Spirale}} | |||
* [[Java/Erste Schritte]] | |||
[[Kategorie:Java]] |
Aktuelle Version vom 25. August 2019, 04:57 Uhr
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-Folge:
- Wähle als Startzahl n eine beliebige natürliche Zahl.
- Für gerades
n
entsteht das nächste Element der Folge, indem mann
halbiert. - Für ungerades
n
muss mann
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":
- 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.
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:
- Mit
n % 2
wird der Modulo-Operator verwendet;n % 2
liefert also den Rest bei Ganzzahldivision durch 2.
z.B.13 % 2 = 1
und13 / 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:
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);
}
}
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, …
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);
}
}
Siehe auch
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
---|---|---|---|---|---|
aktuell | 04:55, 25. Aug. 2019 | 435 × 128 (3 KB) | Matthias Scharwies (Diskussion | Beiträge) | User created page with UploadWizard |
Du kannst diese Datei nicht überschreiben.
Dateiverwendung
Die folgende Seite verwendet diese Datei: