Korrektheit rekursiver Methoden

28.11.2022, 12:24	12345654321	Auf diesen Beitrag antworten »
Korrektheit rekursiver Methoden Meine Frage: Hallo, ich habe eine Frage zu dem Folgenden Problem: Gegeben ist ein Programm 1 Products(n) 2 if n = 1 then 3 return {1} 4 P ? Products(n ? 1) (alle Produkte von Elementen von {1, . . . , n ? 1}) 5 Q ? ? (In Q sammeln wir alle Produkte von Elementen aus {1, . . . , n}, in denen n vorkommt) 6 forall m ? P do 7 Q ? Q ? {m · n} (für jede Zahl in P das Produkt dieser Zahl mit n hinzufügen) 8 return P ? Q Betrachten Sie die in Algorithmus 1 in Pseudocode angegebene rekursive Funktion zur Berechnung aller Produkte von Elementen von {1, . . . , n}: Zeigen Sie mittels vollständiger Induktion, dass für alle n ? N>0 der Aufruf Products(n) die Menge aller Produkte von Zahlen in {1, . . . , n} berechnet. Meine Ideen: Ich hätte versucht mithilfe eines Produktzeichens das Programm zu durchlaufen, jedoch habe ich keine Idee, was ich dahinter schreiben sollte, da a[i] nicht das gewünschte Ergebnis liefert. Vielen Dank bereits für die Hilfe
28.11.2022, 12:52	Ulrich Ruhnau	Auf diesen Beitrag antworten »
RE: Korrektheit rekursiver Methoden Um die Fakultät rekursiv zu berechnen, benötigt man einen viel kürzeren Code. Dieser muss beispielsweise so arbeiten: $\begin{eqnarray} 7! = 7 \cdot 6! \end{eqnarray}$ also allgemein gesprochen $\begin{eqnarray} n!=n\cdot (n-1)! \end{eqnarray}$ Die Aufgabe, $\begin{eqnarray} n! \end{eqnarray}$ zu berechnen wird so durchgereicht an die Aufgabe $\begin{eqnarray} (n-1)! \end{eqnarray}$ auszurechnen. Man muß nur für die richtige Abbruchbedingung sorgen.
28.11.2022, 13:03	HAL 9000	Auf diesen Beitrag antworten »
Alle Produkte von Zahlen in $\begin{eqnarray} \{1,\ldots,n\} \end{eqnarray}$ ist etwas mehr als nur der eine Wert $\begin{eqnarray} n! \end{eqnarray}$ : Ich verstehe das als die Menge aller Werte $\begin{eqnarray} \prod_{k\in A} k \end{eqnarray}$ für beliebige nichtleere Teilmengen $\begin{eqnarray} A \end{eqnarray}$ von $\begin{eqnarray} \{1,\ldots,n\} \end{eqnarray}$ . Aber wie soll man bei den vielen Fragezeichen im obigen Programm erkennen, was 12345654321 wirklich meint? -------------------------------------------------------- Für $\begin{eqnarray} n\leq 5 \end{eqnarray}$ ist $\begin{eqnarray} \operatorname{Products}(n) \end{eqnarray}$ übrigens identisch mit der Menge der positiven Teiler von $\begin{eqnarray} n! \end{eqnarray}$ . Für $\begin{eqnarray} n\geq 6 \end{eqnarray}$ stimmt das indes nicht mehr, so ist beispielsweise 9 zwar ein Teiler von $\begin{eqnarray} 6!=720 \end{eqnarray}$ , aber kein Element von $\begin{eqnarray} \operatorname{Products}(6) \end{eqnarray}$ . D.h., für diese $\begin{eqnarray} n\geq 6 \end{eqnarray}$ ist $\begin{eqnarray} \operatorname{Products}(n) \end{eqnarray}$ allenfalls noch eine echte Teilmenge dieser Teilermenge. Immerhin liefert das eine bessere Abschätzung für $\begin{eqnarray} \left\|\operatorname{Products}(n)\right\| \end{eqnarray}$ nach oben als das triviale $\begin{eqnarray} 2^{n-1} \end{eqnarray}$ : Für $\begin{eqnarray} n=10 \end{eqnarray}$ beispielsweise ist $\begin{eqnarray} d\left(10!\right) = d\left(2^8\cdot 3^4\cdot 5^2\cdot 7\right) = 9\cdot 5\cdot 3\cdot 2 = 270 \end{eqnarray}$ gegenüber $\begin{eqnarray} 2^9=512 \end{eqnarray}$ , und tatsächlich ist $\begin{eqnarray} \left\|\operatorname{Products}(10)\right\| = 238 \end{eqnarray}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »