Aus Algorithmus Gleichung aufstellen

31.10.2017, 00:04

coldstone

Aus Algorithmus Gleichung aufstellen

HI leute,

wie kann ich aus einem Algorithmus in Pseudocode bestimmen welche funktion g berechnet wird?

code:
1: 2: 3: 4: 5: 6: 7: 8:	for i <-- 1 to n do print i if n = 0 then s <-- n then s <-- n + RekAlg(n-1) return s

RekAlg ist mein rekursiver algorithmus, was ja bedeutet das mein Algorithmus sich selber nochmal aufruft.

31.10.2017, 14:26

coldstone

Auf diesen Beitrag antworten »

code:
1: 2: 3: 4: 5: 6: 7: 8: 9:	for i <-- 1 to n do print i if n = 0 then s <-- n else <-- n + RekAlg(n-1) return s

so sieht der code richtig aus.

31.10.2017, 14:40

HAL 9000

Auf diesen Beitrag antworten »

code:
1: 2:	for i <-- 1 to n do print i

Da werden nur die Zahlen 1,2,...,n ausgegeben. Vermutlich zu Debugging-Zwecken, aber für die eigentliche Funktion an sich überflüssig.

code:
1: 2: 3:	if n = 0 then s <-- n else <-- n + RekAlg(n-1)

Die "then"-Zeile bedeutet $\begin{align*} g(0)=0 \end{align*}$ , die "else"-Zeile hingegen $\begin{align*} g(n) = g(n-1) + n \end{align*}$ . Entflochten heißt das

$\begin{align*} g(n) = g(0) + \sum_{k=1}^n k = \sum_{k=1}^n k \end{align*}$ ,

was man mit dem kleinen Gauß auch noch vereinfachen kann zu einer "summenfreien" expliziten Darstellung.

31.10.2017, 17:00

coldstone

Auf diesen Beitrag antworten »

also erstmal vielen dank für deine erklärung. Den anfang habe ich versanden aber wie ist die gleichung in bezug auf den code zu definieren?

also $\begin{eqnarray*} g(n) \end{eqnarray*}$ ist doch das $\begin{eqnarray*} s \end{eqnarray*}$ was in meinem code als return zurückgegeben wird?
Das $\begin{eqnarray*} g(0) \end{eqnarray*}$ ist dann definiert durch

code:
1: 2:	if n = 0 then s <-- n

da $\begin{eqnarray*} s \end{eqnarray*}$ der Wert $\begin{eqnarray*} n \end{eqnarray*}$ zugewiesen wird, in dem fall natürlich $\begin{eqnarray*} n =0 \end{eqnarray*}$ .
und

code:
1:	else <-- n + RekAlg(n-1)

wird als $\begin{eqnarray*} g(n) = g(n-1) + n \end{eqnarray*}$
definiert, richtig?

dann lautet doch meine gleichung, wie folgt:

$\begin{eqnarray*} g(n) = n + (n-1) +n \end{eqnarray*}$
und n zusammengefasst ---> $\begin{eqnarray*} g(n) = 2n + (n-1) \end{eqnarray*}$
für alle $\begin{eqnarray*} n >= 1 \end{eqnarray*}$ .

Liege ich da richtig? verwirrt

31.10.2017, 17:10

HAL 9000

Auf diesen Beitrag antworten »

Damit bist du offensichtlich der Meinung, dass ich mit $\begin{align*} g(n)=g(n-1)+n \end{align*}$ falsch liege - nun, das ist deine Entscheidung. Augenzwinkern

31.10.2017, 17:23

coldstone

Auf diesen Beitrag antworten »

sorry, ich habe dann da was falsch verstanden. Big Laugh

Dann berechnet der algorithmus folgende funkton $\begin{eqnarray*} g(n) = g(n - 1) + n \end{eqnarray*}$ ?

Ich dachte der part

code:
1: 2: 3: 4:	if n = 0 then s <-- n

muss mit berücksichtigt werden?

Ich habe schwierigkeiten die einzelnen parts im code in der gelichung widerzuspiegeln.

Aber die gelichung gilt ja nur dann wenn $\begin{eqnarray*} n >= 1 \end{eqnarray*}$ ist oder?

31.10.2017, 17:52

HAL 9000

Auf diesen Beitrag antworten »

"Nur " für $\begin{align*} n\geq 1 \end{align*}$ ist ja nicht gerade wenig. Was das im weiteren bedeutet, habe ich oben auch schon geschrieben - vielleicht nimmst du es ja irgendwann zur Kenntnis.

Neue Frage »

Antworten »

Aus Algorithmus Gleichung aufstellen

Verwandte Themen