Antworte auf:  LOOP- / WHILE-Berechenbarkeit von DIV von Mind_Burn
Forum:  Algorithmen / Datenstrukturen, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6407
Herkunft: Milchstraße
 Beitrag No.9, eingetragen 2020-06-09 20:16    [Diesen Beitrag zitieren]

Hallo EinsteinsGewissen,

danke für diese wertvollen Erläuterungen!

Grüße
StrgAltEntf


EinsteinsGewissen
Junior
Dabei seit: 17.01.2014
Mitteilungen: 13
Herkunft: Hannover
 Beitrag No.8, eingetragen 2020-06-09 18:50    [Diesen Beitrag zitieren]

Halli Hallo Leute,

nachdem ich kurz die Forumsregeln nochmal überflogen habe und hier anscheinend das Threadalter keine Einschränkung zum Posten neuer Kommentare bildet, möchte ich meine 2 Cents dazugeben.

An alle Unwissenden ist LOOP erst einmal eine Sprache, die in der theoretischen Informatik dazu verwendet wird, Berechenbarkeit von Problemen durch Turingmaschinen auf simple Schleifen zu erweitern.

LOOP ist daher nur theoretischer/mathematischer Natur und funktioniert folgendermaßen:

1) Es gibt Variablen: \(x_0\), \(x_1\), \(x_2\),...
2) Es gibt Konstanten: 0, 1, 2,...
3) Es gibt die Operationszeichen: + und −
4) Es gibt die Trennsymbole: \(;\) und \(:=\)
5) Es gibt die Schlüsselwörter: LOOP, DO und END

Will man nun z.B. eine Funktion \(f(n_1,...n_k)\) berechnen, so werden per Definition die Variablen \(x_1\) bis \(x_k\) mit den Eingangswerten beschrieben und der Ausgabewert in \(x_0\) geschrieben. Alle anderen Variablen sind gleich 0 vordefiniert.

i) Sind \(x_i\) und \(x_j\) Variablen und \(c\) eine Konstante, so sind \(x_i:=x_j+c\) und \(x_i:=x_j-c\) LOOP-Programme.
ii) Sind \(P_1\) und \(P_2\) LOOP-Programme, so ist \(P_1;P_2\) ein LOOP-Programm.
iii) Ist \(P\) ein LOOP-Programm und \(x_i\) eine Variable, so ist LOOP \(x_i\) DO \(P\) END ein LOOP-Programm.

zu i)
Ist die Differenz negativ, so ist das Ergebnis 0.
zu ii)
Dies ist die normale Hintereinanderausführung (von links nach rechts)
zu iii)
Die Schleife LOOP (das Programm \(P\)) wird so häufig ausgeführt, wie \(x_i\) zu Anfang der Schleife angibt (Neuzuweisungen werden also nicht beachtet).

Damit endet jedes LOOP-Programm nach endlich vielen Schritten.

Nun zur Aufgabe:
In den meisten Skripten wird die Funktion \(x_i:=x_j+x_k\) (Addition zweier Variablen) und \(x_i:=x_j\cdot x_k\) (Multiplikation zweier Variablen) erklärt und zwar als \(x_k\)-mal Addieren von der Konstanten 1 auf \(x_j\) mittels LOOP, oder der \(x_k\)-maligen Ausführung der Addition \(x_i:=x_j+x_k\) mittels LOOP für die Multiplikation.

Wie es in Skripten (leider) gerne auch üblich ist, wird nun die ganzzahlige Division (also \(x_i=\lfloor x_j/x_k\rfloor\)) als "analog" definiert (\(x_i:=x_j\,\mathrm{DIV}\,x_k\)), jedoch nicht ausgeschrieben und erklärt.

Und wie Mind_Burn noch erklärt hat, lässt sich
IF \(x_1=0\) THEN \(P_1\) ELSE \(P_2\) END
durch das LOOP-Programm

\(x_2:=1;\,x_3:=0;\)
LOOP \(x_1\) DO \(x_2:=0;\,x_3:=1\) END\(;\)
LOOP \(x_2\) DO \(P_1\) END\(;\)
LOOP \(x_3\) DO \(P_2\) END\(;\)

definieren, wobei die Hilfsvariablen \(x_2,x_3\) natürlich im Restprogramm nicht erneut verwendet sein dürfen.

Zur Multiplikation analog zu definieren scheint mir die Division aber nicht zu sein, da sie ja nicht analog einfach durch häufiges Subtrahieren zu programmieren ist.

Um die Division nun (mithilfe von Buris Vorschlag) anzugeben:

\(x_i:=x_j\,\mathrm{DIV}\,x_k\):

\(x_l:=x_j+0;\,x_m:=x_k-1;\)
LOOP \(x_j\) DO
    \(x_l=x_l-x_m\);
    IF \(x_l=0\) DO
        \(x_l:=x_l+0\) (also quasi nichts, aber nur "nichts" ist nicht erlaubt)
    ELSE
        \(x_l=x_l-1;\,x_i:=x_i+1\)
    END
END

Der LOOP wird \(x_j\)-mal ausgeführt, womit sichergestellt ist, dass \(x_l\) 0 wird. Nun wird vor jedem Vergleich \(x_k-1\) abgezogen, um den Fall auszuschließen, dass bereits \(x_l<x_k\) gilt. Ist \(x_l\) trotzdem noch nicht 0, wird die fehlende 1 abgezogen und \(x_i\) um 1 erhöht. So sollte es eigentlich klappen, wenn es auch kompliziert ist. Hat jemand noch eine simplere Lösung?

Viele Grüße, EG


PS: Um den Kommilitonen entgegen zu kommen, die nun auch nach einem Programm für \(x_i:=x_j\,\mathrm{MOD}\,x_k\) (normale Modulooperation) suchen (das geht jetzt auch für mich wieder einfach):

\(x_l:=x_j\,\mathrm{DIV}\,x_k;\)
\(x_l:=x_k\cdot x_l;\)
\(x_i:=x_j-x_l\)

Man rechnet den ganzzahligen Quotienten aus, multipliziert den mit dem Nenner und zieht den dann vom Zähler ab. Dadurch erhält man den Rest.


Skeev
Aktiv
Dabei seit: 30.04.2013
Mitteilungen: 162
Herkunft:
 Beitrag No.7, eingetragen 2014-07-10 04:58    [Diesen Beitrag zitieren]

2006-04-20 16:42 - Buri in Beitrag No. 4 schreibt:
  m = 0 ;
  s = x ;
  LOOP x DO
    IF s >= y THEN s = s - y ; m = m + 1;
  END
  // Das Resultat ist m
[ Nachricht wurde editiert von Buri am 20.04.2006 16:44:56 ]
Ich glaube es müsste eher so aussehen:

m = 0 ;
s = x ;
 LOOP x DO
  IF s >= y THEN IF (s - y) > 0 THEN m = m + 1;
END
Sorry, mein Fehler, dass wird ja schon durch die erste If-Anweisung abgefangen upps. Also das Original doch so richtig.


Mind_Burn
Junior
Dabei seit: 20.04.2006
Mitteilungen: 7
Herkunft:
 Beitrag No.6, eingetragen 2006-04-20 17:08    [Diesen Beitrag zitieren]

danke euch für die antworten!

IF-Konstrukte sind so nicht erlaubt, jedoch können sie durch LOOP Beschrieben werden.
Also:
IF x1=0 THEN A ELSE B END

wird durch das LOOP Programm

x2=1; x3=0;
LOOP x1 DO x2=0; x3=1 END;
LOOP x2 DO A END;
LOOP X3 DO B END;

simuliert.

>= geht jedoch nicht, aber ich komm der sache definitv näher :D


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27564
Herkunft: Hessen
 Beitrag No.5, eingetragen 2006-04-20 16:45    [Diesen Beitrag zitieren]

@Buri
Dazu müßte man die erlaubten Befehle kennen


Buri
Senior
Dabei seit: 02.08.2003
Mitteilungen: 46235
Herkunft: Dresden
 Beitrag No.4, eingetragen 2006-04-20 16:42    [Diesen Beitrag zitieren]

2006-04-20 16:33: viertel schreibt:
... Mit einem LOOP mit fester Schleifendurchlaufanzahl wirst Du es nicht hinbekommen.

Hi viertel,
nein, natürlich nicht, aber das ist auch nicht verlangt.
Wichtig ist nur, daß die Durchlaufzahl (anders als bei WHILE) vorher feststeht, bevor in die Schleife (LOOP) eingetreten wird.
Vielleicht geht es so:
  m = 0 ;
  s = x ;
  LOOP x DO
    IF s >= y THEN s = s - y ; m = m + 1;
  END
  // Das Resultat ist m
Ich befürchte indessen, daß man IF-Konstruktionen in der Sprache LOOP nicht benutzen darf, es beschreibt aber genau das, was gerechnet werden muß, also muß man sehen, ob man dieses "IF" durch eine erlaubte Sprachkonstruktion ersetzen kann.
Gruß Buri

-----------------

[ Nachricht wurde editiert von Buri am 20.04.2006 16:44:56 ]


viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27564
Herkunft: Hessen
 Beitrag No.3, eingetragen 2006-04-20 16:33    [Diesen Beitrag zitieren]

Hi Mind_Burn

Willkommen auf dem Planeten

Mit einem LOOP mit fester Schleifendurchlaufanzahl wirst Du es nicht hinbekommen. Der Witz ist doch, daß der Quotient von x und y abhängt.
Was Deine Schleifen machen sollen verstehe ich sowieso nicht. Die Variablen sind vor der ersten Verwendung nicht initialisiert. Ein paar Kommentare oder Anmerkungen wären da ganz nützlich.
Der einzig gangbare Weg, um die Division zu vermeiden, ist die forgestzte Subtraktion und deren Zählung:
q := 0
WHILE x >= y
   x := x-y
   q := q+1
   END
Gruß vom 1/4

-----------------
Bild
[ Nachricht wurde editiert von viertel am 20.04.2006 16:37:57 ]


Mind_Burn
Junior
Dabei seit: 20.04.2006
Mitteilungen: 7
Herkunft:
 Beitrag No.2, eingetragen 2006-04-20 16:28    [Diesen Beitrag zitieren]

hi andreas

Ich schreibe dies in der Programmiersprache LOOP. Diese besteht aus sehr einfachen syntaktischen Komponenten. Eine von LOOP berchnete Funktion ist total. dh im Gegensatz zu den WHILE Programmen kann keine Endlosschleife entstehen, weil ja vorgängig definiert wird, wie oft die Schleife durchlaufen wird
z.B LOOP 5 DO xyz END.
Obwohl sie recht einfach ist können mit LOOP viele mathematische Operationen ausgedrückt werden, zb eben DIV :D
Nur irgendwie krieg ichs einfach nicht hin!


andreas_p
Aktiv
Dabei seit: 25.06.2005
Mitteilungen: 89
Herkunft: Dresden
 Beitrag No.1, eingetragen 2006-04-20 15:54    [Diesen Beitrag zitieren]

hi Mind_Burn

meine erste frage  wäre in welcher sprache du das programm schreibst.

und denn versuch doch mla zu erörtern was der unterschied zwischen LOOP und WHILE ist.

-----------------
DON'T PANIC


Mind_Burn
Junior
Dabei seit: 20.04.2006
Mitteilungen: 7
Herkunft:
 Themenstart: 2006-04-20 15:25    [Diesen Beitrag zitieren]

Hi

Mein Problem ist eigentlich relativ einfach, doch habe ich einen Knoten und komm irgendwie nicht weiter.

Es geht darum ein LOOP Programm zu schreiben welches xDIVy berechnet.
Als WHILE Programm sieht das ganze so aus:

fed-Code einblenden

Irgendwie schaff ich's einfach nicht das als reines LOOP Programm auszudrücken.

Jemand ne Ahnung?

Gruss Mind_Burn

[ Nachricht wurde editiert von Mind_Burn am 20.04.2006 17:16:49 ]


 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]