Verwandte Themen

Jensek81
26.10.2019, 00:48
Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

LG

Jensek81

Computer, Schule, Mathematik, programmieren, rechnen, Array, Informatik, Theoretische Informatik, Algorithmus, stack, Binomialverteilung, Quicksort, Sortieralgorithmus, Algorithmen und Datenstrukturen
1 Antwort
BeastBeat
25.10.2019, 21:56
C++ Der Ausdruck muss einen ganzzahligen Enumerationstyp aufweisen?

Was ist hier das Problem?

/   Programm:       Schiefer Wurf
* Filename:       SchieferWurf.cpp
  Autor:       Kai Lauber
* Version: 1.0
* Datum: 25-OKT-2019
  Entwicklungsablauf:
* (Version, Datum, Autor, Entwicklungsschritt)
 1.0, 25-OKT-2019, Kai Lauber, Entwicklungsbeginn 

  Verwendungszweck:
 ‐ Ausgabe der Koordinatenpunkte (x, y) eines Wurfkörpers 
* Beschreibung:     ← Kurzbeschreibung des Programms
 ‐ Das zu erstellende Modul soll die Koordinatenpunkt (x,y) des Wurfkörpers aus den gegebenen Grössen ermitteln und zurückgeben. 	– Anfangsgeschwindigkeit
 – Abschusswinkel 	– Zeit seit des Abwurfes
 
  Precondition:
* ‐ Keine
  Postcondition:
* ‐ Keine
  Folgende Funktionen werden erzeugt:
* ‐
  Copyright (c) 2019 by Kai Lauber

***/

// Bibliotheksfunktion einbinden #include "stdio.h"


// Hauptprogramm int main() {


int v;
int w;
int t;
double x;
double y;
double g = 9.81;


printf("Geben Sie bitte die Anfangsgeschwindigkeit ein: ");
scanf_s("%d", &amp;v);


printf("Geben Sie bitte die Abschusswinkel ein: ");
scanf_s("%d", &amp;w);


printf("Geben Sie bitte die Zeit seit des Abwurfes ein: ");
scanf_s("%d", &amp;t);


int sin = w - w ^ 3 / 6 + w ^ 5 / 120 - w ^ 7 / 5040;


int cos = 1 - w ^ 2 / 2 + w ^ 4 / 24 - w ^ 6 / 720 + w ^ 8 / 40320;


x = v * t * cos;
y = v * t * sin - g / 2 * t ^ 2;


printf("Die Koordinaten sind x = %f und y = %f", x, y);



}

Computer, programmieren, C (Programmiersprache)
3 Antworten
cameraflash
22.10.2019, 08:56
Was genau bedeutet <identifier> expected?

Hallo, ich bin leider noch ein ziemlicher Anfänger in Java und kann mir bei diesem Problem nicht helfen, obwohl ich schon versucht habe, das Problem im Internet zu finden. Ich hoffe, mir kann jemand helfen.

public class monster extends lebewesen
{
   private int[] posY = new int[8];
   private int[] posX = new int[8];
   protected int centerX;
   protected int centerY;
   protected int a;
   public monster(int x, int y)
   {
       super(x, y);
       centerX = x;
       centerX = y;
       a = 2;
   }
   public void bewegen(){
       Random rn = new Random();
       double z = rn.nextDouble();
       for(int i = 0 ; i < 3 ; i++)
       {
           posX[i] = centerX - 1;
           posY[i] = centerY + 1 - i ;
       }
       posX[4] = centerX;
       posY[4] = centerY - 1;
       posX[5] = centerX + 1;
       posY[4] = centerY - 1;
       posX[6] = centerX + 1;
       posY[6] = centerY;
       posX[7] = centerX+1;
       posY[7] = centerY+1;
       posX[8] = centerX;
       posY[8] = centerY+1;
       if (z<0.5) {
           a = a++;
       } else {
           a = a--;  
       }
       for(int i = 0 ; i < monster.monsterList.size(); i++)
       {
               int x = posX[a];
               int y = posY[a];
               spiel.monsterList.setpos(i).(x, y); | Fehler: <identifier> expected
       }
   }
}
(In der Klasse spiel habe ich noch folgende Zeilen:
public class spiel
{ 
public static LinkedList<monster> monsterList = new LinkedList();
private char pos(int x, int y) {
       if (pos[x][y] == 0) {
           return ' ';
       } else {
           return pos[x][y];
       }
   }
}
)

Danke schon einmal im Voraus!

programmieren, Java, Fehlermeldung
3 Antworten
NIleis
19.10.2019, 19:49
Mit Bildern
Wieso bekommt die Variabel einen anderen Wert?

Wenn ich den C# Code ausführe wird der Wert der Variabel tief auf eingabe+48 gesetzt.

Wie kann ich das verhindern?

private static void tri()
        {
            Console.Write("Bitte geben sie die breite an: ");
            int tief = Console.Read();
            Console.WriteLine(tief);
            int tiefe = tief + 2;
            Console.WriteLine(tiefe +" "+ tief);
            StringBuilder dreieck = new StringBuilder(string.Empty);
            char[] form = new char[tiefe];
            for (int i = 0; i < tiefe; i++)
            {
                form[i] = ' ';
            }
            for (int it = 0; it <= tiefe/2-1; it++)
            {
                    try
                    {
                        form[(tiefe / 2 + 1) - it] = '#';
                        form[(tiefe / 2 + 1) + it] = '#';
                    }
                    catch
                    {
                        //abbrechen
                    }
                  dreieck.AppendFormat(new String(form)+ "\n");
              }
              Console.WriteLine(dreieck);
        }
Bild zum Beitrag
Programm, programmieren, C Sharp, Informatik, Visual Studio
4 Antworten

Meistgelesene Beiträge zum Thema Programmieren
Mehr meistgelesene Fragen zu Programmieren