WHILE und GOTO Programm

[b1zarRe]

Hi,

ich muss für eine Klausur unter anderem WHILE und GOTO Programm verstehen.
Ich habe mal eine Übung vorbereitet, wo ich 2 * n versuche umzusetzen(unten die Fragen):

++ WHILE ++

x0 := 0;
x1 := 2; // Konstante: 2
x2 := n; // Variable: n

WHILE x1 > 0 DO
    WHILE x2 > 0 DO
        x0 := x0 + 1;
        x2 := x2 - 1;
x1 := x1 - 1;

Fragen:
Dürte ich (theoretisch) auch anstelle x1 > 0 auf x1 = 0 oder < testen? Und auch auf andere Zahlen als 0? Zb.: x1 <= 4 oder x1 > 17 ?

2. Frage: Normalerweise darf man Zuweisungen nur in der Form x0 := variable +(oder -) Konstante machen. Ist damit jegliche beliebige Konstante gemacht? und darf ich ganz oben bei der Deklartion wo ich zb. x2:=n gesetzt habe das überhaupt machen?


++ GOTO ++

M1: x0 := 0;
M2: x1 := 2;
M3: x2 := n;
M4: IF x1 > 0 GOTO M5
M5: IF x2 >0 GOTO M6
M6: x0 := x0 + 1
M7: x2 := x2 - 1
M8: IF x2 >0 GOTO M6
M9: IF x1 > 0 GOTO M5
M10: END

Fragen: Siehe oben... Genau die gleichen Fragen.

Danke euch

 

[SlaterB]

ist GOTO der Name einer Programmiersprache? oder sollte die sonstwie bekannt sein,
wenn ja wieso weißt du nicht was dort erlaubt ist

deine Fragen klingt ohne genauere Rahmenbedingungen (welche Sprache, welche Regeln usw.)
etwa so sinnvolle wie
'darf ich in "sdfjoeoiehjffkssflsfjklj" noch ein Zeichen x einfügen?'

edit:
Mist, gibts ja tatsächlich
GOTO-Programm ? Wikipedia
mal sehen ob mir dazu noch was einfällt, was dir nicht selber auffallen sollte


edit:
den Regeln bei Wiki nach ist offensichtlich schon "while x1 > 0" nicht erlaubt, nur != 0

die Deklaration mit n ist ok, das ist ja nur eine theoretische Sprache, es gibt keine Methodenaufrufe usw.,
n ist der Startwert, insofern für eine bestimmte Betrachtung nicht variabel sondern ein bestimmter Wert, eine Konstante

 

[b1zarRe]

ist GOTO der Name einer Programmiersprache?

edit:
den Regeln bei Wiki nach ist offensichtlich schon "while x1 > 0" nicht erlaubt, nur != 0

Ok, hätte ich noch dazu schreiben könne: GOTO und WHILE Programm sind eine Berechnungs/Theoriesprache (-> Theoretische Informatik), womit man halt unter anderem beweist, dass alle Sachen, die erlaubt sind äquivalent zu einer Turingmaschine sind und somit das in allen anderen Programmiersprachen (Java, C, etc) While und Goto erlaubt sind bzw. turingberechenbar.

Genau das ist mein Problem... überall(auch in unserem Skript) stehen zwar so Sachen, dass man
nur sowas machen darf: x0 := x1 + 3 oder Ähnliches, aber leider nicht, ob alle Abfragen erlaubt sind... deswegen brauche ich eine sichere Antwort. (Werde zur Not auch meinen Professor ansprechen, aber leider ist dieser, Semesterferien, nicht erreichbar).

 

[SlaterB]

was sagst du denn zu meinen Erkenntnissen von denen du eine schon zitierst,
hast du irgendwo ein Programm mit 'while >' gesehen?

bei Sprachen mit Regeln die in 3 Zeilen passen kannst du dir recht sicher sein,
dass es nicht mehr gibt als du in 1-5 Beispielen auch direkt siehst

zumal du die höheren Spielereien nicht brauchst, alles kann auch mit dem restriktisten Vergleich geschafft werden,
bisschen aufwendiger, aber das ist dann ja gerade die Herausforderung,
dafür eben andere Vorteile wie automatische Umformung, Beweisbarkeit und ähnliches

 

[b1zarRe]

Ja, wir hatten in der Übung bei WHILE einmal aufgeschrieben x0 > 0 und bei Goto x = 0,
aber halt nur in der Form:

WHILE x0 > 0 DO S
und IF x = 0 GOTO Mx

Dies sagt aber leider für mich noch nicht 100 Pro aus, ob man zb auch auf x < 0 testen kann,
oder auf x0 >= 0 oder auf x0 > 10 etc. Auch nicht, ob man bei While auf = testen kann, weil
es angeblich in GOTO möglich ist, oder ob man auf = 20 testen kann etc.

 

[Gast2]

Dies sagt aber leider für mich noch nicht 100 Pro aus, ob man zb auch auf x < 0 testen kann,

steht doch bei Wikipedia da:

Es sind nur fünf verschiedene Anweisungen erlaubt

und eine davon lautet

eine bedingte Sprunganweisung, wobei eine Variable auf Gleichheit mit einer Konstanten abgefragt wird,

hand, mogel

 

[b1zarRe]

Hmmm.. und welche Anweisungen sind das?
>
<
>=
<=
=

?

Also wäre x0 <,>,=,>=,<= -12,100,0,20 möglich bei WHILE und GOTO?

EDIT: Leider finde ich das Zitat von dir von Wiki auch nicht??

 

[b1zarRe]

Hmmm.. und welche Anweisungen sind das?
>
<
>=
<=
=

?

Also wäre x0 <,>,=,>=,<= -12,100,0,20 möglich bei WHILE und GOTO?

EDIT: Leider finde ich das Zitat von dir von Wiki auch nicht??

EDIT: Ah, doch gefunden

ps.: Sorry, für doppelpost...

EDIT2: So ganz hilft mir Wiki dennoch nicht, weil da bei WHILE bzw GOTO nur steht, man darf = und != benutzen... jedoch bin ich mir auch sicher, dass bei zb. WHILE auch > getestest werden kann..

 

[Fu3L]

Also vom reinen Wikipediatext her, dürftest du das nicht machen. Die 5 Anweisungen, die Mogel zitiert hat, enthalten auch sowas wie

x0 := 5

und damit nicht etwa 5 Operatoren von der Sorte ==, <, > etc.. Bei While siehts noch fieser aus^^

Allerdings würde mich jetzt interessieren, wie man mit einem dieser WHILE-Programme auf größer oder kleiner testet, versuche mir da aus reinem Interesse schon die ganze Zeit was zusammenzubasteln, komm aber nicht drauf^^

 

[Marcinek]

Naja der Trick ist, dass man prüft

while(i != 0)

und dann das i dekrementiert in der while.


Damit hast du eine while i > 0 simuliert.

Ich würde aber entsprechende Bücher zur Theoretischen Informatik hernehmen und nicht auf wikipedia verlassen.

 

[b1zarRe]

jo danke schonma... werde ich tun... ist mir auch alles noch zu schwammig... nächste woche inner uni 1-2 bücher ausleihen und ggfl. meinen Professor nochmal fragen...

dachte nur hie rhätte vllt. jemand schonmal was damit gemacht..

 

[Fu3L]

while(i != 0)

und dann das i dekrementiert in der while.


Damit hast du eine while i > 0 simuliert.

Vielleicht reicht das ja bei so einer theoretischen Betrachtung, aber für mich hieße das: Wenn i aber kleiner als 0 ist, hab ich ne Endlosschleife.. Ich hab etwas rumgesucht und dabei gelesen, dass auch die Endlosschleife ein Ergebnis darstellt (nämlich es gibt kein Ergebnis). Ich hätte aber nicht gedacht, dass die Endlosschleife auch ein Zwischenergebnis im Programm darstellen darf...
(Ich weiß schon, worauf ich mich nicht im Studium freuen werde^^)

 

[XHelp]

In der reinen Theorie sind nur

WHILE x!=0 DO P END

zulässig.
Wenn du etwas anderes haben willst, musst du erst zeigen, dass es nicht mächtiger ist, als die Sprache, d.h.:
Wenn du z.B.

WHILE x>y DO P END

haben willst, musst du dieses Konstrukt einmalig mit den erlaubten Mitteln nachbauen. Dann kannst du es als Makro benutzen. Das gleiche gilt auch für andere Operatoren.

Allerdings würde mich jetzt interessieren, wie man mit einem dieser WHILE-Programme auf größer oder kleiner testet, versuche mir da aus reinem Interesse schon die ganze Zeit was zusammenzubasteln, komm aber nicht drauf^^

Danz einfach:

Makro: IF a<=b THEN P1 ELSE P2:
Xt := X5 + 0; //X5 ist 0 und ist nur für korrekte Form
X3 = a - b; //das ist eigentlich auch ein Makro
IF X3 = 0 THEN
  Xt := Xt + 1;
  P1
END
IF Xt = 0 THEN
  P2
END

Makro für a-b:
while x2!=0 DO
  x1 = x1 - 1;
  x2 = x2 - 1;
END
x0 = x1;

 

[XHelp]

Zu spät fürs Editieren, deswegen als Doppelpost:

Vielleicht reicht das ja bei so einer theoretischen Betrachtung, aber für mich hieße das: Wenn i aber kleiner als 0 ist, hab ich ne Endlosschleife..

Da gibt es eben einen Trick: es gibt keine negativen Zahlen Es heißt auch "modifizierte Subtraktion", im Grunde kannst du es so umschreiben:

x = max(0,a-b);

, d.h. wenn das Ergebnis negativ sein sollte, dann ist es eben 0

 

[Fu3L]

Ahh, ok, dass es keine negativen Zahlen gibt, vereinfacht es wirklich

 

[b1zarRe]

Ich habe nun meinen Professor gefragt...: Also erlaubt ist:
(while programm)
bedinungen mit variable > 0 (und nichts anderes... also weder if, noch variable == variable2 oder variable == konstante)
weiterhin darf man zuweisungen nur in der form machen: variable1 := variable1 + konstante. * und / oder ähnliches nicht erlaubt. auch sowas ist nicht erlaubt: variable1 := variable1 + variable2, da es immer EINE variable und eine Konstante sein muss. Variable1:=variable2 ist erlaubt.. da <=> Variable1:=variable2 + 0
Negative Zahlen sind auch nicht erlaubt.. sprich 1 - 2 = 0 und nicht -1

Beispielprogramm: http://www7.pic-upload.de/17.08.11/bm1svlnyey5u.jpg (für a + b = c)
Nun wollte ich mal gucken wie ich a / b = c realisieren könnte hänge da aber voll ... jemand eine idee???

 

[XHelp]

a/b=c

c = x + 0
WHILE a>0 DO
  a=a-b
  c = c + 1
END

Musst dir eben noch für

a-b

entweder ein Makro schreiben oder es durch while-form ersetzen.

 

[b1zarRe]

Danke für die Hilfe XHelp, aber so ganz kann das nicht stimmen:

1.) wofür steht das "x" ? -> c := 0; wäre ok gewesen.. denke du meintest mit dem x auch eine auf 0 initialisierte Variable, richtig?

2.) probier deine Methodik mal mit a = 5 und b = 2 aus.. also 5 / 2 müsste c = 2 sein... wenn ich mich gerade nicht verrechnet habe kommt bei dir aber 3 heraus.

Ich hatte mir überlegt das Ganze so auszurechnen:

a / b = c Rest d <=> c * b + d = a
Also sprich: erst eine Modulo Funktion einzubauen welches zb für a = 5 und b = 2 den Rest 1 herausrechnet.. danach a - rest rechnet.. also 5 - 1 = 4. und dann 2 while schleifen wo die 4 dekrementieriert wird bis auf 0 und eine neue variable 2x erhöht wird also auf 2.

Nur is schon irgendwie krass das umzusetzen... oO

 

[XHelp]

1) ja, x ist einfach nur eine dummy-variable
2) Dass 5/2=3 ist, muss nicht in der theoretischer Informatik stimmen
Wenn du es auf 2 haben willst, dann musst du dir ein Makro für

while (a+1-b)>0

schreiben

 

[b1zarRe]

Das bringt mich zu der Frage, wie ich a - b = c realisieren kann... Für Werte wie 4-3 = 1 ist das kein Problem:

x1 := a;
x2 := b;

while (x2 > 0) {
    x2 := x2 - 1;
    x1 := x1 - 1;
}

Aber was ist, wenn es sowas zu realisieren gilt: 1-2 = -1 ... Nach unseren Unterlagen, soll falls b > a ist 0 herauskommen... nur ich darf ja nach den Regeln 1 mit 2 vergleichen... woher soll ich wissen, was größer ist... :/

 

[Fu3L]

soll falls b > a ist 0 herauskommen

Wenn eine Substraktion so definiert ist, dass gilt

x = max(x-c, 0)

Dabei sei c eine konstante Zahl

Dann kommt auch bei deiner Schleife für x1 0 raus, wenn x2 größer ist als x1.

 

[XHelp]

Es gibt einfach keine keine negativen Zahlen...

c = a-b

:

b = 5
a = 1
while (b>0) do
  a = a - 1
  b = b - 1
end

a ist dannach 0.

 

[b1zarRe]

Ok, aber wenn man das zb. in Java so eingeben würde, würde ja bei deinem Beispiel -4 herauskommen. Meinst Du also, weil das so definiert ist, muss man das nicht extra noch umsetzen? Bzw. würde das irgendwie überhaupt gehen?!

 

[XHelp]

Wie schon auf der ersten Seite geschrieben: es handelt sich hierbei um eine modifizierte Subtraktion. Wo du was in einer echten Programmiersprache eingibst, hat mit der theoretischen Informatik nichts zu tun und man kann auch keine Argumente ala "aber in Java gehts" bringen

 

[b1zarRe]

Okay, ich verstehe!

Meinst du denn, dass a / b = c oder a^n viel aufwändiger als zb das hier ist: a * b = c sind?

    /** Methode */
    public static int berechne(int a, int b) {   // 3 * 2 = 6
        
        int x0 = 0; // Produkt von a * b
        int x1 = a; // Faktor a
        int x2 = b; // Faktor b
        
        while(x1 > 0) {                          // 3 > 0, 2 > 0,            
            int x3 = x2; // Kopie Faktor b       // 2, NEU initialisierung
            
            while(x3 > 0) {                      // 2 > 0, 1 > 0, 0 > 0(f) 
                x0 = x0 + 1;                     // 1, 2
                x3 = x3 - 1;                     // 1, 0
            }
            x1 = x1 - 1;                         // 2
            }
        return x0;
    }

Dadrauf bin ich noch selbst gekommen... und unser Professor meinte das maximal so etwas in der Klausur vorkommen kann, da zb. besprochene Übungen zu a mod b = c oder a! viel zu aufwändig wären für eine Klausuraufgabe...

 

[XHelp]

Meinst du denn, dass a / b = c oder a^n viel aufwändiger als zb das hier ist: a * b = c sind?

Nö, alles das selbe. Wenn du einmal das Grundprinzip verstanden hast, kannst du das schnell hinzaubern. Vor allem wenn du Makros benutzt. Wenn du in der Aufgabe davor schon

c=a*b

gemacht hast, dann kannst du bei

a^n

eben ganz normal

x=x*a

rechnen und auf die vorherige aufgabe verweisen.

 

[b1zarRe]

echt? komm einfach nicht dahinter wie ich das mit / oder ^n realisieren soll

Problem:
1. Falls a / b das a kleiner ist, dann müsste es auch auf 0 hinauslaufen.... ist das vorher auch schon definiert oder nicht? Denje eher nicht, weil / oder * garnicht definiert sind in solchen Programmen.. aber da komme ich dann nicht weiter wie ich das dann realisieren kann.

oder zu a^n: Klar ist, dass a^n = a * a * a (...) * an ist.. und es eigentlich relativ einfach ist, da ich immer nur zwei zahlen nehmen muss, in das makro von dem a*b überführen muss, irgendwo abspeichern, und dann die nächste zwei zaheln solange ich <= an bin.

also in etwa:

x0 := 0;
x1 := a;
x2 := n;

WHILE x2 > 0 DO
     x0 := x1;
     x2 := x2 - 1;
     WHILE x2 > 0 DO
          x0 := x0 * a; // das Makro a * b

Aber da happerts dann langsam auch :/

 

[Fu3L]

a^n ist doch nicht schwer?^^

public class WHILE {
	public static void main(String[] args) {
		int x0 = 1;
		int x1 = 5; //a
		int x2 = 3; //n
		while(x2 > 0) {
			x2 = x2 - 1;
			x0 = x0 * x1; //Das a*b Makro
		}
		System.out.println(x0);
	}
}

Zwar Java Syntax, damit mans leichter testen kann, aber nur das Erlaubte verwendet^^

 

[XHelp]

komm einfach nicht dahinter wie ich das mit / oder ^n realisieren soll

Ich habe dir doch schon geschrieben, die c=a/b aussehen kann :bahnhof:

 

[b1zarRe]

Stimmt, danke...
denke mit a-b, a*b, a^n, a/b, a+b bin ich gut gerüstet... schaue mir vielleicht noch fak. und modulo an... denke dann sollte, falls das in der Klausur kommt, gut gelingen.

Danke allen besonders XHelp

 

[b1zarRe]

Ich habe mal versucht a / b = c nochmal umzusetzen(ohne auf die Lösungen hier zu schauen) und kam eigentlich soweit voran: http://www7.pic-upload.de/24.08.11/1iy6tj2glp5h.jpg

Einziges Problem ist dieses IF (x1 >= x2) in der SubMakro da if ja nicht erlaubt ist sowie kein vergleich mit 2 bedinungen... Zur not würde ich das in der Klausur so machen als garnichts hinzuschreiben... aber kann man das überhaupt noch irgendwie anders darstellen?

wie gesagt erlaubt bzw nicht erlaubt:
variable1 > 0 (KEINE anderen bedinungen/abfragen)
bei a - b mit a < b muss 0 herauskommen: keine negativen Zahlen
zuweisungen in der form:
variable1 = variable1 + irgendEinerKonstantenZahl(auch 0)
variable1 = variable1 - irgendEinerKonstantenZahl (auch 0)
also * oder % oder / oder sonstiges nicht erlaubt
variable1 = variable2 +- irgendEinerKonstantenZahl (auch 0)

 

[XHelp]

Das sind doch simplen mathematischen Umformungen...

x1>=x2 <=>
x1-x2>=0 <=>
(x1+1)-x2>0

x1+1 sei mal geschenkt und a-b steht schon auf der ersten Seite, d.h. die musst du einfach nur einsetzen... mehr nicht :bahnhof:

 

[b1zarRe]

Ok, ein Kollege hat mir gerade geholfen:
Vorgehen in Prosa: Man addiert zu a am Anfang + 1 hinzu... berechnet dann mithilfe
2 Schleifen a / b = c zb. 4 / 3 = 2(was ja noch falsch wäre) und zieht dann vom Ergebnis 1 ab.

    private static String div(int x1, int x3) { 
      
        int x2 = x1 + 1;
   
        int x4 = x3;   
        int x5 = 0;      
        
        while (x2 > 0) { 
             while (x3 > 0) { 
                 x3 = x3 - 1;
                 x2 = x2 - 1; 
             }
             x3 = x4;
             x5 = x5+1; 
        }
        x5 = x5 - 1;
        System.out.println(x5);

EDIT:
Habe es nochmal für Fakultät probiert

    /** Berechnet a * b */
    private static int multipliziere(int a, int b) {
        
        int x0 = 0;
        int x1 = a;
        int x2 = b;
        
        while(x1 > 0) {
            int x3 = x2;
            
            while(x3 > 0) {
                x0 = x0 + 1;
                x3 = x3 - 1;
            }
            x1 = x1 - 1;
        }
        return x0;
    }
    
    /** Berechnet a! */
    private static int fakulaet(int a) {
        
        int x0 = 1;
        int x1 = a - 1; 
        int x2 = 1;
        
            while(x1 > 0) {
                x0 = multipliziere(x0, x2 + 1);
                x1 = x1 - 1;
                x2 = x2 + 1;
            }
        
        return x0;
    }