Ganzzahlige Division primitiv-rekursiv

30.04.2007, 13:46

Moeki

Ganzzahlige Division primitiv-rekursiv

Moin.

Ich möchte ohne Verwendung des µ-Operators zeigen, dass die div Funktion (Ganzzahlige Division) primitiv rekursiv ist, indem ich sie aus bereits bekannten primitiv-rekursiven Funktionen aufbaue. Bekannt sind mir dabei Vorgänger-, Substraktion- und Signumfunktion sowie natürlich die Grundfunktionen.

Frage 1: Wie mache ich das? verwirrt

Frage 2: Wie kann man die halboffenen eckigen Klammern in der folgenden Gleichung interpretieren? Beschränkung kann ja damit nicht gemeint sein?

$\begin{eqnarray*} div : \mathbb N ² \rightarrow \mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} div(x,y):= \lfloor x/y \rfloor \end{eqnarray*}$ und $\begin{eqnarray*} y \geq 1 \end{eqnarray*}$ .

Gruß,
Moeki.

30.04.2007, 14:00

Abakus

Auf diesen Beitrag antworten »

RE: Ganzzahlige Division primitiv-rekursiv

Zitat:

Original von Moeki
Frage 2: Wie kann man die halboffenen eckigen Klammern in der folgenden Gleichung interpretieren? Beschränkung kann ja damit nicht gemeint sein?

$\begin{eqnarray*} div : \mathbb N ² \rightarrow \mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} div(x,y):= \lfloor x/y \rfloor \end{eqnarray*}$ und $\begin{eqnarray*} y \geq 1 \end{eqnarray*}$ .

Die Klammern bezeichnen die untere Gaußklammer, also die größte ganze Zahl, die kleiner oder gleich dem eingeklammerten Argument ist.

Bei Frage 1 solltest du zunächst deine Überlegungen darstellen bzw. mal einen Versuch starten.

Grüße Abakus smile

01.05.2007, 13:19

Moeki

Auf diesen Beitrag antworten »

Mir fallen konrekt nur zwei Lösungsalternativen ein: Zum einen fortlaufendes Subtrahieren bis der Rest kleiner ist als der Divident ist oder die Greedy-Variante. Beide kann ich aber net primitiv-rekursiv ausdrücken, weil ich ja dann erst die min bzw. max Funktion herleiten müsste.

Bzw. wie verknüpfe ich die Signum Funktion mit der Kleiner-Gleich bzw. Größer-Gleich Funktion und der Substraktion, so dass die daraus resultierende Funktion primitiv-rekursiv ist.

a / b = c + Rest

Solange der Rest nicht größer ist als c, subtrahiere b von c. c ist dann der größte ganzzahlige quotient.

03.05.2010, 16:16

Theoretiker

Auf diesen Beitrag antworten »

versuche mit solchen allten Tricks wie +/- 0 oder */1.
z.B: a*b=(a-1)*b+b
Überlege wie du das bei der Division ausdrücken könntest Augenzwinkern

Neue Frage »

Antworten »

Ganzzahlige Division primitiv-rekursiv

Verwandte Themen