Median Berechnung mit Teile und Herrsche Rekursiv

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Kroko123

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 13.07.2013, 20:24 Titel: Median Berechnung mit Teile und Herrsche Rekursiv

Hallo liebe Labber,

ich weiß leider mit meiner Median- Berechnung nicht mehr weiter. Ich habe nur ein Pseudo- Code gegeben, der dem Unten aufgeführten Matlab- Code enspricht. Nun passt das aber alles nicht mehr zusammen und ich weiß nicht weiter. Eventuell könnt ihr mir helfen.

Viele Grüße
Marcel

Code:

function Hauptprogramm
clear;clc;

a=(5,1,8,3,9,2)
n=6
k=3

function k_rang(n1,n2,k)
if n1=n2
ergebnis=a(n1);
else
x=a(floor((n1+n2)/2));

%partitionierung
q=n1;
g=n1;
for i=n1:n2
y=a(i);
if y<=x
(i,g) %tausche
g=g+1;
if y<x
(q,g-1) %tausche
q=q+1;
end
end
end

if k<q
ergebnis=k_rang(n1,q-1,k);
else
if k>=g
ergebnis=k_rang(g,n2,k)
else
ergebnis=x;
end
end
end

Funktion ohne Link?

Harald

Forum-Meister


	Beiträge: 24.500

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 13.07.2013, 21:25 Titel:

Hallo,

poste doch bitte den Pseudo-Code dazu.

Probleme, die ich auf den ersten Blick sehe:
- Vektor a falsch definiert (runde Klammern statt eckige)
- Hauptprogramm ruft k_rang nicht auf.
- Vergleich auf Gleichheit benötigt == statt =
- Das Tauschen funktioniert so nicht. Mir ist allerdings nicht klar, was wo getauscht werden soll, daher kann ich auch keinen Korrekturvorschlag machen.

Die Probleme sollten dir auch im MATLAB Editor angezeigt werden, und zwar in Form eines roten Quadrats rechts oben im Editor und roten Balken rechts an der Seite. Jeder rote Balken weist auf einen Fehler hin, jeder orange Balken beinhaltet einen Verbesserungsvorschlag.

Grüße,
Harald

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 13.07.2013, 21:38 Titel:

Nabend Harald,

vielen Dank schoneinmal Smile

Hier der Pseudo-Code:

Code:

FUNCTION k_rang(n1,n2,k)
IF n1=n2 THEN
RETURN a(n1)
ELSE
x := a(floor((n1+n2)/2))
IF k < q THEN
RETURN k_rang(n1,q-1,k)
ELSE
IF k ≥ g THEN
RETURN k_rang(g,n,k)
ELSE
RETURN a(x)
END
END
END
END

Zum Einfügen nach dem Floor:
%Partitionierung
q := n1
g := n1
FOR i := n1:n2 DO
y := a(i)
IF y ≤ x THEN
tausche(i,g)
g := g + 1
IF y < x THEN
tausche(q,g-1)
q := q + 1
END
END
END

und :

%Median-Funktion, benutzt k_rang
FUNCTION median()
RETURN k_rang(1,n,floor((n+1)/2)))
END

Funktion ohne Link?

Eventuell noch wichtig:

Beispiel:
a=(5,1,8,3,9,2); n=6; k=3
1.Minimum: 1, 2.Minimum: 2, 3.Minimum (und Median): 3

n=6 k=[(n+1)/2]=3

Grüße
Marcel

Harald

Forum-Meister


	Beiträge: 24.500

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 13.07.2013, 21:52 Titel:

Hallo,

versuch doch erstmal, die bereits gemachten Vorschläge umzusetzen und die von MATLAB markierten Stellen zu beheben, und poste dann das Ergebnis. Da können wir dann weitermachen.

Ein Hinweis noch: k_rang hat gegenwärtig kein Rückgabeargument (in der function-Zeile, siehe auch der andere Thread).

Grüße,
Harald

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 13.07.2013, 22:06 Titel:

Servus, hier einmal die etwas geänderte Fassung. Wie ich es genau tauschen soll weiß ich leider nicht so genau. Das "sortiert" bereitet mir Kopfzerbrechen.

Code:

function Hauptprogramm
clear;clc;

a=[5,1,8,3,9,2]
n=6
k=3

sortiert=k_rang(n1,n2,k)

fprintf('DIe Sortierung ergibt: %d',sortiert);

function sortiert=k_rang(n1,n2,k)
if n1==n2
sortiert=a(n1);
else
x=a(floor((n1+n2)/2));

%partitionierung
q=n1;
g=n1;
for i=n1:n2
y=a(i);
if y<=x
(i,g) %tausche
g=g+1;
if y<x
(q,g-1) %tausche
q=q+1;
end
end
end

if k<q
sortiert=k_rang(n1,q-1,k);
else
if k>=g
sortiert=k_rang(g,n2,k)
else
sortiert=x;
end
end
end

Funktion ohne Link?

Zuletzt bearbeitet von Kroko123 am 13.07.2013, 22:14, insgesamt einmal bearbeitet

Harald

Forum-Meister


	Beiträge: 24.500

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 13.07.2013, 22:11 Titel:

Hallo,

was mich an deinem Code sowie dem Pseudo-Code irritiert: nirgends wird gesagt, was a ist. Ich will damit sagen: a wird nicht belegt / definiert.

Meine Vermutung (!) wäre, dass die entsprechenden Elemente in a getauscht werden sollen.

"sortiert" und "ergebnis" dürften dasselbe sein, d.h. du musst dich nur auf einen Variablennamen einigen.

Grüße,
Harald

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 13.07.2013, 22:17 Titel:

Oh, da habe ich dir noch wichtige Dinge verheimlicht:
Das ergebnis und sortieren habe ich bereits oben geändert.

---------------------------------------------------------------
Bestimmung des Medians einer Liste von Daten

Median ist Element in der Mitte nach Sortierung, Index
k= (n+1)/2

bei geradem n der Mittelwert der beiden mittleren Elemente, das wird hier aber ignoriert

aber: Liste ist nicht sortiert, und Sortierung ist zu aufwendig!

erste, ineffiziente Idee (funktioniert für beliebige k):

wiederhole k-mal: bestimme das Minimum der Liste und entferne das Minimum aus der Liste

Minimum-Algorithmus siehe  Selection-Sort

bei der k-ten Wiederholung war es der Median

entspricht Selection-Sort mit Abbruch nach k Durchläufen ( O(n2))

Beispiel:

a=(5,1,8,3,9,2), n=6, k=3

1. Minimum: 1, 2. Minimum: 2, 3. Minimum (und Median): 3

effizientere Idee (funktioniert für beliebige k):

wähle zufälliges Element x der Liste (z.B. das in der Mitte)

partitioniere durch Umstellen die Liste in drei Teile: 1) < x, 2) = x, 3) > x

also a1, ... aq-1, aq, ..., ag-1, ag, ..., an

unterscheide drei Fälle:

k<q wiederhole Verfahren für Bereich 1...q-1 (Rekursion)

k≥g wiederhole Verfahren für Bereich g...n (Rekursion)

q≤k<g x ist die Lösung

1. Fall: a(i) > x
es ist nichts zu tun
2. Fall: a(i) = x
a(i) mit a(g) tauschen, g erhöhen
3. Fall: a(i) < x
a(i) mit a(g) tauschen, g erhöhen, a(q) mit a(g-1) tauschen, q erhöhen

Harald

Forum-Meister


	Beiträge: 24.500

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 14.07.2013, 09:47 Titel:

Hallo,

mir ist nicht klar, welcher Anleitung du nun folgen willst.

Die Elemente k1 und k2 in einem Vektor a vertauschen kann man z.B. so:

Code:

tmp = a(k1);
a(k1) = a(k2);
a(k2) = tmp;

Funktion ohne Link?

Grüße,
Harald

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 14.07.2013, 10:21 Titel:

Moin,

danke.

Ich habe leider nur das gegeben, welches ich oben geschrieben habe Sad

Grüße
Marcel

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 14.07.2013, 23:53 Titel:

Hallo zusammen, ein wenig habe ich weitergemacht aber jetzt weiß ich nicht weiter. Hat denn eventuell jemand eine Ahnung? Ich habe ja oben bereits geschrieben, dass Programm soll den Median berechnen. Mehr Infos wie die Obigen habe ich leider auch nicht Sad

Code:

function Hauptprogramm
clear;clc;

a=[5,1,8,3,9,2]
n=6
k=3

sortiert=k_rang(n1,n2,k)

fprintf('DIe Sortierung ergibt: %d',sortiert);

function sortiert=k_rang(n1,n2,k)
if n1==n2
ergebnis=a(n1);
else
x=a(floor((n1+n2)/2));

%partitionierung
q=n1;
g=n1;
for i=n1:n2
y=a(i);
if y<=x
tmp = i;
i = g;
g = tmp;

g=g+1;
if y<x
tmp = q;
q = g-1;
g-1 == tmp;

q=q+1;
end
end
end

if k<q
ergebnis=k_rang(n1,q-1,k);
else
if k>=g
ergebnis=k_rang(g,n2,k)
else
ergebnis=x;
end
end
end

Funktion ohne Link?

Harald

Forum-Meister


	Beiträge: 24.500

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 15.07.2013, 09:07 Titel:

Hallo,

das Problem mit sortiert vs. ergebnis hast du nun wieder eingebaut.

In meinem Vorschlag zum Vertauschen von Elementen eines Vektors a kannst du das a nicht einfach weglassen, höchstens durch eine andere Variable ersetzen.

Im Pseudo-Code wird a verwendet, ohne dass es definiert ist. Das ist m.E. nicht sinnvoll.

Grüße,
Harald

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 15.07.2013, 09:46 Titel:

Hallo Kroko123,

Bemerkung: Ein "clear" am Anfang einer Funktion ist sinnfrei. Es räumt den aktuellen Workspace leer, der aber zu Beginn einer Funktion sowieso leer ist.

Gruß, Jan

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 15.07.2013, 14:05 Titel:

Hallo ihr beiden,

das mit dem clear leuchtet mir ein. Das clc muss ich natürlich stehen lassen Smile

Harald: Das von dir angesprochene habe ich behoben, hatte die alte Datei ausgewählt Rolling Eyes

Das a ist das Beispiel der Reihe, von der der Median bestimmt werden soll.

Viele Grüße
Marcel

Code:

function Hauptprogramm
clc;

a=[5,1,8,3,9,2]
n=6
k=3

sortiert=k_rang(n1,n2,k)

fprintf('DIe Sortierung ergibt: %d',sortiert);

function sortiert=k_rang(n1,n2,k)
if n1==n2
sortiert=a(n1);
else
x=a(floor((n1+n2)/2));

%partitionierung
q=n1;
g=n1;
for i=n1:n2
y=a(i);
if y<=x
tmp = a(i);
a(i) = a(g);
a(g) = tmp;
g=g+1;
if y<x
tmp = a(q);
a(q) = a(g-1);
a(g-1) = tmp;
q=q+1;
end
end
end

if k<q
sortiert=k_rang(n1,q-1,k);
else
if k>=g
sortiert=k_rang(g,n2,k)
else
sortiert=x;
end
end
end

Funktion ohne Link?

Harald

Forum-Meister


	Beiträge: 24.500

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 15.07.2013, 18:27 Titel:

Hallo,

dann muss aber die Variable a mit an die Funktion k_rang übergeben werden, damit sie dort bekannt ist.

Grüße,
Harald

Kroko123

Themenstarter

Forum-Anfänger


	Beiträge: 33

	Anmeldedatum: 10.04.13

	Wohnort: ---

	Version: ---

Verfasst am: 15.07.2013, 19:56 Titel:

Heißt das:

Code:

sortiert=k_rang(n1,n2,k)

Funktion ohne Link?

ersetzen durch

Code:

sortiert=k_rang(n1,n2,k,a)

Funktion ohne Link?

	Gehe zu Seite 1, 2 Weiter
Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.