Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

Javakurs/Übungsaufgaben/Brainfuck: Unterschied zwischen den Versionen
(→‎Kommentare)
 
(23 dazwischenliegende Versionen von 16 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
−
'''1.) (Schwierigkeitsgrad: mittel)'''
+
===Einführung===
  
−
In dieser Aufgabe bauen wir uns eine simple Turingmaschine. Die Turingmaschine besitzt dabei nur ein Arbeitsband (workingTape) der Länge 10. Es existiert ein Lese/Schreibe-Kopf (head) der über das workingTape gleiten kann, dort Werte ändern und Werte ausgeben soll. Bewegt sich der Kopf über ein Ende des Arbeitsbandes hinaus, so taucht er auf der anderen Seite wieder auf (wenn also z.B der head auf das 11. Feld zeigt, dann soll er wieder auf das 1. zeigen).
+
Java ist eine komplexe und mächtige Programmiersprache mit der man viele Informatikprobleme lösen kann. Doch wie weit kann man den Befehlssatz einer Sprache reduzieren, ohne dass diese die Eigenschaft verliert, beliebige mathematische Probleme zu lösen? Diese spezielle Eigenschaft wird [[wikipedia:Turing-Vollständigkeit|Turing-Vollständigkeit]] genannt. Alle Programmiersprachen sind für gewöhnlich turingvollständig, was bedeutet, dass sie jedes berechenbare Problem lösen können. Zu diesen Problemen zählen zum Beispiel sämtliche mathematische Probleme, aber auch Probleme die eher struktureller Natur sind, also auch das Suchen von Einträgen in einer Kontaktliste (nein, der Weltfrieden ist leider nicht berechenbar).
 +
 
 +
[[wikipedia:Brainfuck|Brainfuck]] ist eine Programmiersprache, die ebenfalls turingvollständig ist, allerdings nur aus '''acht''' Befehlen besteht. In dieser Aufgabe könnt ihr selbst einen auf einer Turingmaschine basierten Interpreter für eine eigene kleine Sprache schreiben, die man in einen weiteren Schritt Brainfuck-kompatibel machen kann und damit auch turingvollständig.
 +
 
 +
===Aufgabenstellung===
 +
 
 +
In dieser Aufgabe bauen wir uns eine simple [[wikipedia:Turingmaschine|Turingmaschine]], welche vorgegebenen Programmcode einer eigenen Sprache lesen und auswerten soll. Die Turingmaschine besitzt dabei nur ein Arbeitsband (workingTape) der Länge 10. Es existiert ein Lese/Schreibe-Kopf (head), der über das workingTape gleiten kann, dort Werte ändern und Werte ausgeben soll. Bewegt sich der Kopf über ein Ende des Arbeitsbandes hinaus, so taucht er auf der anderen Seite wieder auf (wenn also z.B der head von Feld 10 auf das 11. Feld bewegt wird, dann soll er wieder auf das 1. zeigen).
  
 
Die Maschine selbst wird durch einen einfachen Programmcode gesteuert, der aus 5 Befehlen besteht:
 
Die Maschine selbst wird durch einen einfachen Programmcode gesteuert, der aus 5 Befehlen besteht:
Zeile 10: Zeile 16:
 
* '''#''' Dieser Befehl gibt den aktuellen Wert auf der Konsole aus
 
* '''#''' Dieser Befehl gibt den aktuellen Wert auf der Konsole aus
  
−
Der Programmcode der die Turingmaschine steuert, soll in einem Array namens ''sourceCode'' stehen, der Code soll Schritt für Schritt durchgegangen und ausgeführt werden. Auf dem Arbeitsband werden Werte vom Typ char gespeichert die anfangs alle den Wert 'a' haben. Der head zeigt am Anfang auf das erste Feld auf dem workingTape.
+
Der Programmcode der die Turingmaschine steuert, soll in einem Array namens ''sourceCode'' stehen, der Code soll Schritt für Schritt durchgegangen und ausgeführt werden. Auf dem Arbeitsband werden Werte vom Typ '''char''' gespeichert, die anfangs alle den Wert 'a' haben. Der head zeigt am Anfang auf das erste Feld auf dem workingTape.
 +
 
 +
'''Hinweis 1:''' char-Werte werden intern als Zahlenwerte gespeichert, deshalb könnt ihr ohne Probleme sowas wie '''char example = (char)('a'+1);''' schreiben, dies nennt man casten. Wenn ihr wissen wollt, welche Zeichen durch welche Zahlen repräsentiert werden, dann schaut in die [[wikipedia:ASCII-Tabelle|ASCII-Tabelle]].
 +
 
 +
Jetzt solltet ihr auch in der Lage sein, mit eurer eigenen Turingmaschine ein "Hello World"-Programm zu schreiben. Wenn ihr eure Turingmaschine eigenständig erweitern wollt, dann schaut euch die Sprache [[wikipedia:Brainfuck|Brainfuck]] an. Brainfuck ist eine Programmiersprache, welche ähnlich arbeitet wie unsere Turingmaschine in dieser Aufgabe.
 +
 
 +
'''Hinweis 2:''' Zum Testen verwendet einfach diese Initialisierung der Variable Source-Code. Wenn ihr alles richtig gemacht habt, dann sollten die Buchstaben a, b  und c ausgegeben werden. Die Schreibweise mit den geschweiften Klammern und den Kommawerten legt automatisch ein Array an und füllt es mit den beschriebenen Werten (Deklaration & Initialisierung in einem Schritt):
 +
char[] sourceCode = {'#', '+', '#', '+', '#'};
 +
 
 +
== Kommentare ==
 +
Wenn du Anmerkungen zur Aufgabe hast oder Lob und Kritik loswerden möchtest, ist hier die richtige Stelle dafür. Klicke einfach ganz rechts auf "bearbeiten" und schreibe deinen Kommentar direkt ins Wiki. Keine Scheu, es geht nichts kaputt ;)
 +
 
 +
<!--
 +
Als kleine Starthilfe folgt ein Beispiel, wie so ein Kommentar formatiert sein könnte. Mit "Vorschau zeigen" kannst du dir ansehen, was deine Änderung bewirken würde, ohne wirklich etwas zu ändern.
 +
Du musst übrigens außerhalb dieses auskommentieren Bereichs schreiben ;)
 +
 
 +
==== Robert ====
 +
Na mal schauen, ob irgendjemand diese Funktion wirklich benutzt. Ich fände es jedenfalls toll.
 +
 
 +
==== FehlerKategorie ====
 +
Um den Char um einen Wert zu erhöhen müsst ihr eure Variable zurück casten.
 +
char Example = (char)('a'-1);
 +
 
 +
----
 +
 
 +
Das stimmt nicht man kann auch das schreiben:
 +
char Example = 'a' - 1;
 +
-->
 +
----
 +
<br/>
 +
 
 +
Sorry wenn ich das so schreibe, aber das ist die erste Aufgabenstellung wo sich mir der Hintegrund, bzw. der Sinn nicht wirklich erschliesst, wäre jemand der das verstanden hat so freundlich das ganze ein wenig mehr zu erläutern? Das wäre ultranett :>.
 +
-mw-
 +
<br/>
 +
----
 +
 
 +
<br/>
 +
Also zur Erklärung:
 +
Ich habe das zu beginn auch nicht so recht verstanden ... frag mal nen Tutor, die erklären das dann nochmal und auch ganz gut ...
 +
Für die, die es interessiert ... hier der Code für "Hallo"
 +
 
 +
char[] sourceCode = {'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#', '>', '#', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#', '#', '+', '+', '+', '#'};
 +
 
 +
Wer will kann ja noch "World" hinten ran hängen!
 +
 
 +
 
 +
----
 +
 
  
−
Hinweis 1: char-Werte werden intern als Zahlenwerte gespeichert, deshalb könnt ihr ohne Probleme sowas wie '''char example = 'a'+1;''' schreiben. Wenn ihr wissen wollt durch welche Zahlen, welche Character repräsentiert werden, dann schaut hier auf diese Ascii-Tabelle: [http://de.wikipedia.org/wiki/ASCII-Tabelle Link]
+
Gesagt getan, schließlich wollte ich meinen Parser auch mal in Aktion sehen ; ) <br/>
 +
Viel Spaß auch allen Anderen beim minimalistischen "HelloWorld!" Schreiben. <br/><br/>
  
−
Jetzt solltet ihr auch in der Lage sein mit eurer eigenen Turingmaschine ein "Hello World"-Programm zu schreiben. Wenn ihr eure Turingmaschine eigentständig erweitern wollt, dann schaut euch diesen Link an: [http://de.wikipedia.org/wiki/Brainfuck Brainfuck]
+
<code><pre>
 +
char[] sourceCode = {'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#', //H
 +
                    '>', '+', '+', '+','+','#',       //e
 +
    '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#',       //l
 +
    '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#',                        //l
 +
    '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+', '#',             //o
 +
    '<','<','<','<','<','<','<','<','<','<',                                                                                       //  Wagenruecklauf zum Testen der < -Methode                                               
 +
    '>', '-', '-', '-', '-', '-', '-', '-', '-', '-','-', '#',               //W
 +
    '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+', '#',                                               //o
 +
    '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+','+', '+', '+', '#',       //r
 +
    '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#',       //l
 +
    '>', '+', '+', '+','#',        //d
 +
    '>', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-',
 +
  '-', '-', '-', '-', '-', '-', '-', '-', '-', '-',   
 +
  '-', '-', '-', '-', '-', '-', '-', '-', '-', '-',   
 +
  '-', '-', '-', '-', '-', '-', '-', '-', '-', '#' //! (wobei hier von H runtergezählt wird, also der ersten Position auf dem Arbeitsband
 +
            }; 
 +
</pre></code>
 +
<br/>
  
−
Hinweis 2: Zum Testen verwendet einfach diese Initialisierung der Variable Source-Code, wenn ihr alles richtig gemacht habt, dann sollten die Buchstaben a, b  und c ausgegeben werden:
+
Und nochmal als formatloser Block zum einfachen Kopieren ; )
−
char[] sourceCode = {'+', '#', '+', '+','#', '+', '+', '+', '#'};
 
  
−
'''2.) Fehler im System'''
 
  
−
Führende PolitikwissenschaftlerInnen haben festgestellt, dass Demokratie einfach nicht funktioniert. Deshalb haben sie sich überlegt, dass es klüger wäre, wenn einfach der/die Älteste entscheidet. Sie haben ein Programm geschrieben, das unter den Parteivorsitzenden der großen Parteien, den/die älteste heraussucht. Leider sind sie keine gelernten Java-Programmierer und haben es nicht geschafft lauffähigen Code zu produzieren. Findest du die Fehler im System?
 
  
−
<nowiki>
+
char[] sourceCode = {'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#','>', '+', '+', '+','+','#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+', '#','<','<','<','<','<','<','<','<','<','<','>', '-', '-', '-', '-', '-', '-', '-', '-', '-','-', '#', '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+', '#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+','+', '+', '+', '#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#','>', '+', '+', '+','#','>', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-','-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-','-', '-', '-', '-', '-', '-', '-', '-', '-', '#' };  
−
public class DemocracyV2 {
 
−
public static void main(String[] args) {
 
−
String[] names = String[5];
 
−
int[] ages = int[5];
 
−
 
−
generateNamesAndAges(names, ages);
 
−
System.out.println(whosTheOldest(names, ages));
 
−
}
 
−
 
−
private static void generateNamesAndAges(String[] names, int[] ages) {
 
−
names[0] = Angela;
 
−
ages[0] =  52;
 
−
 
−
names[1] = Kurt;
 
−
ages[1] = 58;
 
−
 
−
names[2] = Lothar;
 
−
ages[2] = 66;
 
  
−
names[3] = Doppelspitze Claudia und Reinhard;
 
−
ages[3] = 51 + 54;
 
−
 
−
names[4] = Guido;
 
−
ages[4] = 45;
 
−
}
 
  
−
private static void whosTheOldest(String[] names, int[] ages) {
+
----
−
int oldest;
 
−
for(int i; i <= 5; i++) {
 
−
if ( oldest < ages[i] ) {
 
−
int indexOfOldest = i; n
 
−
}
 
−
}
 
−
 
−
return "Oldest and wisest person is " + names[indexOfOldest] + " with an age of " + ages[indexOfOldest]  + ".";
 
−
}
 
−
}
 
−
</nowiki>
 
  
−
Nachdem du die Fehler gefunden hast, wie könntest du sie beseitigen und so die Gesellschaft vor ihrem Untergang bewahren?
+
<!--
−
Wie könnte mit dem Fall umgegangen werden, dass zwei PolitikerInnen gleich alt sind?
+
Fehler in NetBeans:
 +
workingTape[head]=workingTape[head]+1;
 +
funktioniert nicht! man muss explizit casten:
 +
workingTape[head]=(char)(workingTape[head]+1);
 +
Mit javac dagegen funktionierts.
 +
-->
 +
[[Kategorie:Java]]
 +
[[Kategorie:Java_Aufgaben]]

Aktuelle Version vom 7. März 2012, 14:04 Uhr

Einführung

Java ist eine komplexe und mächtige Programmiersprache mit der man viele Informatikprobleme lösen kann. Doch wie weit kann man den Befehlssatz einer Sprache reduzieren, ohne dass diese die Eigenschaft verliert, beliebige mathematische Probleme zu lösen? Diese spezielle Eigenschaft wird Turing-Vollständigkeit genannt. Alle Programmiersprachen sind für gewöhnlich turingvollständig, was bedeutet, dass sie jedes berechenbare Problem lösen können. Zu diesen Problemen zählen zum Beispiel sämtliche mathematische Probleme, aber auch Probleme die eher struktureller Natur sind, also auch das Suchen von Einträgen in einer Kontaktliste (nein, der Weltfrieden ist leider nicht berechenbar).

Brainfuck ist eine Programmiersprache, die ebenfalls turingvollständig ist, allerdings nur aus acht Befehlen besteht. In dieser Aufgabe könnt ihr selbst einen auf einer Turingmaschine basierten Interpreter für eine eigene kleine Sprache schreiben, die man in einen weiteren Schritt Brainfuck-kompatibel machen kann und damit auch turingvollständig.

Aufgabenstellung

In dieser Aufgabe bauen wir uns eine simple Turingmaschine, welche vorgegebenen Programmcode einer eigenen Sprache lesen und auswerten soll. Die Turingmaschine besitzt dabei nur ein Arbeitsband (workingTape) der Länge 10. Es existiert ein Lese/Schreibe-Kopf (head), der über das workingTape gleiten kann, dort Werte ändern und Werte ausgeben soll. Bewegt sich der Kopf über ein Ende des Arbeitsbandes hinaus, so taucht er auf der anderen Seite wieder auf (wenn also z.B der head von Feld 10 auf das 11. Feld bewegt wird, dann soll er wieder auf das 1. zeigen).

Die Maschine selbst wird durch einen einfachen Programmcode gesteuert, der aus 5 Befehlen besteht:

  • > Dieser Befehl bewegt den head ein Feld nach rechts
  • < Dieser Befehl bewegt den head ein Feld nach links
  • + Dieser Befehl erhöht den Wert des aktuellen Feldes um 1
  • - Dieser Befehl verringert den Wert aktuelles Feldes um 1
  • # Dieser Befehl gibt den aktuellen Wert auf der Konsole aus

Der Programmcode der die Turingmaschine steuert, soll in einem Array namens sourceCode stehen, der Code soll Schritt für Schritt durchgegangen und ausgeführt werden. Auf dem Arbeitsband werden Werte vom Typ char gespeichert, die anfangs alle den Wert 'a' haben. Der head zeigt am Anfang auf das erste Feld auf dem workingTape.

Hinweis 1: char-Werte werden intern als Zahlenwerte gespeichert, deshalb könnt ihr ohne Probleme sowas wie char example = (char)('a'+1); schreiben, dies nennt man casten. Wenn ihr wissen wollt, welche Zeichen durch welche Zahlen repräsentiert werden, dann schaut in die ASCII-Tabelle.

Jetzt solltet ihr auch in der Lage sein, mit eurer eigenen Turingmaschine ein "Hello World"-Programm zu schreiben. Wenn ihr eure Turingmaschine eigenständig erweitern wollt, dann schaut euch die Sprache Brainfuck an. Brainfuck ist eine Programmiersprache, welche ähnlich arbeitet wie unsere Turingmaschine in dieser Aufgabe.

Hinweis 2: Zum Testen verwendet einfach diese Initialisierung der Variable Source-Code. Wenn ihr alles richtig gemacht habt, dann sollten die Buchstaben a, b und c ausgegeben werden. Die Schreibweise mit den geschweiften Klammern und den Kommawerten legt automatisch ein Array an und füllt es mit den beschriebenen Werten (Deklaration & Initialisierung in einem Schritt): 

char[] sourceCode = {'#', '+', '#', '+', '#'};

Kommentare

Wenn du Anmerkungen zur Aufgabe hast oder Lob und Kritik loswerden möchtest, ist hier die richtige Stelle dafür. Klicke einfach ganz rechts auf "bearbeiten" und schreibe deinen Kommentar direkt ins Wiki. Keine Scheu, es geht nichts kaputt ;)


Sorry wenn ich das so schreibe, aber das ist die erste Aufgabenstellung wo sich mir der Hintegrund, bzw. der Sinn nicht wirklich erschliesst, wäre jemand der das verstanden hat so freundlich das ganze ein wenig mehr zu erläutern? Das wäre ultranett :>. -mw-


Also zur Erklärung: Ich habe das zu beginn auch nicht so recht verstanden ... frag mal nen Tutor, die erklären das dann nochmal und auch ganz gut ... Für die, die es interessiert ... hier der Code für "Hallo"

char[] sourceCode = {'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#', '>', '#', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#', '#', '+', '+', '+', '#'};

Wer will kann ja noch "World" hinten ran hängen!



Gesagt getan, schließlich wollte ich meinen Parser auch mal in Aktion sehen ; )
Viel Spaß auch allen Anderen beim minimalistischen "HelloWorld!" Schreiben. 

char[] sourceCode = {'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#', //H 
                     '>', '+', '+', '+','+','#',												       //e 
		     '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#',								       //l 
		     '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#',           					               //l 
		     '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+', '#',	       					       //o 
		     '<','<','<','<','<','<','<','<','<','<',	                                                                                       //  Wagenruecklauf zum Testen der < -Methode                                                
		     '>', '-', '-', '-', '-', '-', '-', '-', '-', '-','-', '#',								               //W 
		     '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+', '#',	                                               //o 
		     '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+','+', '+', '+', '#',				       //r 
		     '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#',								       //l 
		     '>', '+', '+', '+','#',   													       //d 
		     '>', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-',																			
			  '-', '-', '-', '-', '-', '-', '-', '-', '-', '-',     
			  '-', '-', '-', '-', '-', '-', '-', '-', '-', '-',     
			  '-', '-', '-', '-', '-', '-', '-', '-', '-', '#'										//! (wobei hier von H runtergezählt wird, also der ersten Position auf dem Arbeitsband
	            };


Und nochmal als formatloser Block zum einfachen Kopieren ; )


char[] sourceCode = {'-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '#','>', '+', '+', '+','+','#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+', '#','<','<','<','<','<','<','<','<','<','<','>', '-', '-', '-', '-', '-', '-', '-', '-', '-','-', '#', '>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+', '#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+','+', '+', '+','+', '+', '+', '#','>', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '+', '#','>', '+', '+', '+','#','>', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-','-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-','-', '-', '-', '-', '-', '-', '-', '-', '-', '#' };


Abgerufen von „https://wiki.freitagsrunde.org/index.php?title=Javakurs/Übungsaufgaben/Brainfuck&oldid=17679“