Korrektheit eines Algorithmus beweisen |
| 29.01.2012, 12:57 | Kallinski | Auf diesen Beitrag antworten » |
| Korrektheit eines Algorithmus beweisen Halli Hallo, ich soll in einer Aufgabe die Korrektheit von folgendem Algorithmus beiwesisen: Die Aufgabe genau: Sei X eine endliche Menge der Karidnalität n. Ein Wert x von X heißt Median von X, wenn weniger als n/2 Elemente von X kleiner als x und weniger als n/2 Elemente von X größer als x sind. Folgender Algorithmus dient der Bestimmung des Medians eines Arrays: Funktion Median (X) Eingabe: Array X= [X[0],...,X[n-1]] x <- minus unendlich y <- 0 SOLANGE y < n/2 ---m <- unendlich ---FÜR i=0,...,n-1 TUE ------WENN X[i] > x DANN -----------WENN x[i] = m DANN --------------c <- c+1 -----------WENN X[i] < m DANN --------------m <- X[i] --------------c <- 1 ---x <- m ---y <- y+c ZURÜCK x Ja soweit der Algorithmus. Ich würde mich sehr freuen wenn mir jemand beistehen könnte 
Dies ist leider der letzte Aufgabenzettel den ich abgeben muss und somit ist mein bestehen des Moduls davon abhängig 
Meine Ideen: Ich habe mir bereits artikel über Quicksort, Medians, etc. durchgelgesen und ich verstehe auch ungefähr wie der Algorithmus funktioniert aber ich habe keine Ahnung wie ich beweisen soll, dass er auch richtig funktioniert. Bin für jede Hilfe dankbar. |
||
| 29.01.2012, 13:35 | chrizke | Auf diesen Beitrag antworten » |
Meiner Meinung nach gibt der nämlich immer als Median -unendlich zurück. Und zwar definierst du ja x und m mit -unendlich im ersten schritt. Dann wird geprüft, ob ein Wert aus dem Array größer als x=-inf ist, was natürlich der Fall ist. Dann schaust du, ob dieses x, das ja größer als -inf ist, gleich oder kleiner als -inf ist. Dies ist natürlich nicht der Fall und somit wird in der Schleife rein gar nichts getan. Ich nehme mal an, dass du da was falsch abgeschrieben hast. Halt ich habe mich verlesen. m wird ja nicht minus sondern plus unendlich zugewiesen. Da muss ich nochmal schaun. |
||
| 29.01.2012, 15:04 | Kallinski | Auf diesen Beitrag antworten » |
Hi, hab grade nochmal nachgeschaut, ist alles richtig abgeschrieben. 
Ja ich würde mich freuen wenn du dir das mal anschauen könntest. 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
