0 Daumen
200 Aufrufe

Aufgabe:

Sei \( A \) eine Liste der Länge \( n \) von paarweise verschiedenen Elementen, auf penen eine totale Ordnung („Vergleichsoperation") definiert ist.

(a) Geben Sie einen Algorithmus (in python- oder Pseudocode) an, der (im schlechtesten Fall) mit \( 3\left\lfloor\frac{n}{2}\right\rfloor \) Vergleichen sowohl das Minimum als auch das Maximum von \( A \) bestimmt.
(b) Begründen Sie die Korrektheit des Algorithmus und beweisen Sie, dass die gewünschte obere Schranke von \( 3\left\lfloor\frac{n}{2}\right\rfloor \) Vergleichen gewährleistet ist. Dabei werden nur Vergleiche der Daten (und keine Indexvergleiche) gezählt.


Problem/Ansatz:

Ich weiß nicht ob mir jemand bei dieser Aufgabe helfen kann, weil diese im Python eigentlich geschrieben werden sollte. Aber falls jemand Ahnung hat wie diese aufzuschreiben ist, wáre ich sehr dankbar fúr einen Tipp.

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Aloha :)

Ich kann leider die exakte Python-Syntax nicht, weil wir nicht in Python programmieren. Ich habe dir den Algorithmus daher in Pseudo-Code aufgeschrieben. Du müsstest das dann noch in die Python-Syntax übertragen:


assert( n>=0 && A!=NULL );

i=0; k=n; min=A[0]; max= A[n];

while (i<k) {

    if (A[i]<=A[k]) { klein= A[i] ; gross= A[k]; } else { klein= A[k]; gross= A[i]; }

    if (klein<min) min= klein;

    if (gross>max) max= gross;

    ++i; --k; }


Du erkennst die 3 if-Befehle, in denen die Elemente miteinander verglichen werden. Die Schleife benötigt \(\left\lfloor\frac n2\right\rfloor\) Schritte. Das gibt \(3\left\lfloor\frac n2\right\rfloor\) Vergleiche.

Avatar von 148 k 🚀

omg danke hast mir geholfen

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Antworten
1 Antwort
Gefragt 1 Sep 2020 von Gast
1 Antwort

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community