Median von Arraywerten

Flabian

Hallo Leute!

Ich versuche den Median von eingegebenen Arraywerten zu berechnen:

An und für sich wäre das recht einfach.
Ich hab ein Array mit Integerwerten namens "iFeld[]" und dazu noch ein Array mit Boolenwerten namens "bBesetztFeld[]", das anzeigt ob eine Position im Integerarray besetzt ist oder nicht.
Der Median ist,
a) wenn die Anzahl der eingegebenen Zahlen ungerade ist:
Einfach die Anzahl der eigegebenen Zahlen durch zwei, wobei die Nochkomma stellen wegfallen, und dann um eins erhöhen
Beispiel: Anzahl der eingegebenen Zahlen: 9
dann ist der Median die (9/2)+1= 5

oder

b)wenn die Anzahl der eigegebenen Zahlen gerade ist:
Hier liegt Median zwischen den beiden Werten in der Mitte.
Der Median ist also die Hälfte von der Summe der "Anzahl der eigegebenen Zahlen"/2 und ("Anzahl der eigegebenen Zahlen"/2)+1.
Beispiel: Anzahl der eingegebenen Zahlen = 10.
Dann ist der Median die halbe Summe der Werte an den Stellen von (10/2) + (10/2)+1
= also die Summe der Werte an den Stellen 5 und 6 und dann durch 2.

Eigentlich also nicht so schwer.
Aber irgendwie klappt das ganze nicht.
D.h. ab und zu klappt die Umwandlung und ab und an nicht.
Ich konnte leider noch kein Muster feststellen, wann es klappt und wann nicht.

Hier mal der Quellcode der Median Berechnung:

float Median(int iFeld[], int anzahlBelegungen, bool bBesetztFeld[]){

int feldPosition = 0;
int iGefundeneBelegungen = 0;
float fReturnValue;

//Da der Median für ungerade u. gerade Anzahl an Werten unterschiedlich ermittelt wird,
//muss zuerst festgestellt werden, ob die Anzahl der belegten Felder gerade ist oder nicht
if(anzahlBelegungen % 2 != 0){ //Ungerade viel Felder sind belegt
                    //Median = Die Nummer die in folgender Position steht:
                    //die Anzahl der Positionen/2 +1;
                    //z.B. wenn 9 Felder belegt sind, dann ist der Median in Feld 5
         while(iGefundeneBelegungen != (int(anzahlBelegungen/2)+1)){
                if(bBesetztFeld[feldPosition] == true){
                       iGefundeneBelegungen++;//eine bestezte Position gefunden                                             
                       }
                feldPosition++; //gehe zur nächsten Position in der Tabelle
         } 
         feldPosition--; //muss um eines erniedrigt werden, da oben schon um eins weitergegangen wurde
         fReturnValue = float(iFeld[feldPosition]);
         }

else{ //Gerade viele Felder, Achtung! Median = (m1 + m2) /2
     int iHilfsint1, iHilfsint2;

    while(iGefundeneBelegungen < int(anzahlBelegungen/2)+1){                        
       if(bBesetztFeld[feldPosition] == true){
                iGefundeneBelegungen++;
                if(iGefundeneBelegungen == int(anzahlBelegungen/2))
                             iHilfsint1 = iFeld[feldPosition];//ErsterWert   
                feldPosition++; 
                }
                else
                feldPosition++;
                }

      //assert(iGefundeneBelegungen < int(anzahlBelegungen/2)+1);     
      feldPosition--;//muss um eines erniedrigt werden, da oben schon um eins weitergegangen wurde
      iHilfsint2 = iFeld[feldPosition]; //Zweiter Wert
      cout << "Werte der Hilfsint: " << iHilfsint1 << " " << iHilfsint2;
      fReturnValue = float((iHilfsint1+iHilfsint2)/2);
     }

return fReturnValue; 
}

Wäre echt super wenn mir jemand weiterhelfen könnte.
Ech hänge da total fest.:(

hustbaer

Wenn du nen guten Debugger hast dann step doch einfach mal durch bei einer Belegung die du als Fehlerhaft kennst, und schau was schief läuft. Ansonsten poste wenigstens Ausgangsdaten für welche die Funktion falsche Ergebnisse liefert. Das würde sehr helfen. Ein möglichst kleines Set wäre natürlich schön.

DEvent

Wenn ich das richtig verstehe, dann setzt das Array bBesetztFeld fest, ob ein Feld im Array iFeld auch wirklich belegt ist.
(wobei ich das nicht verstehe wozu das gut sein soll, ein Array hat normalerweise die Eigenschaft, das alle Felder Belegte Felder sind).

anzahlBelegungen ist doch nur wieviele Felder, egal ob wirklich belegt oder nicht, in den beiden Arrays bBesetztFeld und iFeld sind.

Also ich nehme an das die beiden Arrays so aussehen:

iFeld=        [2, 3, 5, 0, 6, 8, 100, 12]
bBesetztFeld= [1, 1, 1, 0, 1, 1, 0  , 1 ] // 1=true, 0=false

Dann wäre anzahlBelegungen=8, aber die wirkliche Anzahl wäre 6

Achja, dein Array von Werten ist doch sortiert oder??

Aber du Überprüfst anzahlBelegungen wenn du feststellen willst wie man den Median berechnen muss. Würde es nicht mehr Sinn machen, erst feststellen wieviele Felder wirklich belegt sind (nämlich wieviele "true" es in bBesetztFeld gibt) und diese Anzahl dann als Ausgangspunkt nehmen wie der Median berechnen werden muss.
Also in Code:

int berechneAnzahlBelegtefelder(bool bBesetztFeld[], int anzahlBelegungen)
{
    zähle die Anzahl der "true" in bBesetztFeld;
    return anzahl;
}

float Median(int iFeld[], int anzahlBelegungen, bool bBesetztFeld[])
{
    int anzahlBelegt = berechneAnzahlBelegtefelder(bBesetztFeld, anzahlBelegungen);
    wenn anzahlBelegt ungrade
    {
        berechneUngradenMedian();
    }
    else
    {
        berechneGradenMedian();
    }
}

Ausserdem, wozu eine unnötige Variable einführen?

fReturnValue = float(iFeld[feldPosition]);

ist unnötig, mach einfach

return iFeld[feldPosition];

Dann bricht die Funktion da ab und liefert das Ergebniss. Sonst gewinnt man den Eindruck das noch etwas ganz besonderes mit fReturnValue geschieht.

Achja noch ein Tipp:
Sowas

iGefundeneBelegungen != (int(anzahlBelegungen/2)+1)

ist sehr schwer zu Debbugen. Mach dafür eine Variable, die einen vernünftigen Namen hat. Das Schlüsselwort heist Zerlegung. Zerlege deinen Code möglichst, so das man ihn flüssig lesen kann.

Für Integer-Divison gibt es doch die Funktion div().
http://www.cplusplus.com/ref/cstdlib/div.html

Ausserdem ist es sinnlos nach int zu Casten.

//       int       / int + int
int(anzahlBelegungen/2)+1

sind alles int-Typen, also das Ergebniss ist sowieso ein int. Ein float ist 2.0f, 1.0f, ein double ist 1.0, 2.0

Flabian

Jep, das mit den Integer Array und mit den Boolean Array hast du richtig verstanden.
Und ja, man geht das von aus, dass das Array sortiert ist.

Das ich zwei Arrays habe ist so vorgegeben in der Aufgabenstellung, weis schon das es eigetnlich unnötig ist.

Schief laufen tuts beispielsweise bei:
1, 3, 45, 89, 122

Die richtige Ausgabe wäre "45", er gibt aber 52 aus.

Ich werde jetzt mal den Code vereinfachen und dann wieder posten...

thordk

DEvent schrieb:

Achja, dein Array von Werten ist doch sortiert oder??

die frage ist wichtig. denn für den median MUSS das array sortiert vorliegen. der median ist dazu da, um einen "mittelwert" zu finden, der von großen ausreissern nicht beeinträchtigt wird. dazu sortiert man eine reihe von daten und nimmt einfach den wert in der mitte. wenn die mitte kein element ist (gerade anzahl elemente), dann nimmt man das arithmetische mittel der beiden elemente um die mitte herum.
das war auch alles soweit richtig erklärt/verstanden.

da nicht alle elemente deines arrays berücksichtigt werden sollen, musst du dir natürlich überlegen, wie du das behandeln kannst.

eine einfache variante wäre z.b. das einführen von zwei zählervariablen zLinks und zRechts. zLinks wird mit dem index des ersten besetzten elements belegt, zRechts mit dem letzten belegten (dafür reicht dein array bBesetztFeld).

in jedem iterationsschritt setzt du nun jeweils zLinks auf den nächsten belegten index rechts von zLinks, für zRechts den links nächsten. Das machst du solange, bis entweder zLinks und zRechts identisch sind, oder zRechts kleiner als zLinks wird.
bei ersterem fall hast du es mit einem ungeraden array zu tun und kannst den wert an index zLinks (oder zRechts) zurückgeben.
bei letzterem fall gehst du wieder einen schritt zurück (den schritt zurück kannst du dir sparen, wenn du z.b. erst zLinks mit seinem neuen wert belegst und dann schon mit zRechts vergleichst. bei gleichheit musst du zRechts nicht mehr neu belegen und hast sofort deine beiden indizes) und gibst das arithmetische mittel zwischen element an index zLinks und an index zRechts zurück.

Shinja

vielleicht waers noch gut, alle anzahlBlegungen und bBesetztFeld anzugeben, bei dem Beispiel wos schief laeuft.

Flabian

So, hab den Code jetzt neu geschrieben.
Jetzt ist er deutlich eleganter und einfacher zu lesen, danke dafuer.

Allerdings gibt er jetzt immer "0" aus.

float Median(int iFeld[], int anzahlBelegungen, bool bBesetztFeld[]){                            

int xlinks = 0, zlinks = 0, xrechts = 0, zrechts = 0;                                            
int positionl = 0, positionr = 50;                                                               

while(xlinks != xrechts && xlinks < xrechts){                                                    
        while(bBesetztFeld[positionl] == 0)                                                      
                positionl++;                                                                     
        zlinks = iFeld[positionl];                                                               
        positionl++;                                                                             

        while(bBesetztFeld[positionr] == 0)                                                      
                positionr--;                                                                     
        zrechts = iFeld[positionr];                                                              
        positionr--;                                                                             
        if(zlinks < zrechts){                                                                    
                xlinks = zlinks;                                                                 
                xrechts = zrechts;                                                               
                }                                                                                
        else                                                                                     
        return (xlinks+xrechts)/2;                                                               
        }                                                                                        

assert(xlinks == xrechts);                                                                       
return xlinks;                                                                                   

}

thordk

int xlinks = 0, zlinks = 0, xrechts = 0, zrechts = 0;                                            
int positionl = 0, positionr = 50;                                                              

while(xlinks != xrechts && xlinks < xrechts)
...

xlinks != xrechts wird mit beiden variablen mit dem wert 0 aufgerufen, der vergleich ergibt false und die schleife steigt sofort aus.

Flabian

Ach ja, super, danke!
Das hab ich ganz übersehen.
Jetzt funktioniert der Code ENDLICH!!!
Hier die kompakte und richtige Version für alles dies interessiert:

float Median(int iFeld[], int anzahlBelegungen, bool bBesetztFeld[]){                             

int zlinks = 0, zrechts = 1;                                             
int positionl = 0, positionr = 50;                                                               

while(1){                                                     
        while(bBesetztFeld[positionl] != 1)                                                       
                positionl++;                                                                            
        zlinks = iFeld[positionl];                                                               
        positionl++;                                                                             

        while(bBesetztFeld[positionr] != 1)                                                       
                positionr--;                                                                     
        zrechts = iFeld[positionr];                                                               
        positionr--;                                                                             

        if(zlinks > zrechts){ //gerade
                return (float(zlinks)+zrechts)/2; 
                }    
        if(zlinks == zrechts){//ungerade                                                                         
                return zlinks;  
                }
        }                                                                                         

}

Vielen Dank an alle die geholfen haben!!! Echt super!:)