Array – die neusten Beiträge

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
Benutzer2002410
01.04.2019, 20:24

Python: Wie kann ich feld1 bis feld7 so zusammenfassen, sodass ich das nicht alles einzeln eingeben muss?

Hey, ich möchte feld1 bis feld7 so zusammenfassen, sodass ich das nicht alles einzeln eingeben muss. Dazu finde ich nur leider nichts im Internet.

import tkinter as tk from tkinter import *

modul = tk.Tk()
modul.geometry("900x900")
modul.title("Bunt3x3")
modul.resizable(width=False, height=False)

r = "red"
y = "yellow"
g = "green"
b = "blue"

def change():
  if feld1["bg"] == r:
    feld1.config(bg=g)
    feld3.config(bg=g)
    feld5.config(bg=g)
    feld7.config(bg=g)
    feld2.config(bg=b)
    feld4.config(bg=b)
    feld6.config(bg=b)
    feld8.config(bg=b)

    feldlabel.config(text="Rot & gelb")

  elif feld1["bg"] == g:
    feld1.config(bg=r)
    feld3.config(bg=r)
    feld5.config(bg=r)
    feld7.config(bg=r)
    feld2.config(bg=y)
    feld4.config(bg=y)
    feld6.config(bg=y)
    feld8.config(bg=y)

    feldlabel.config(text="Gruen & blau")

feld1 = tk.Frame(bg=r, width=300, height=300)
feld1.grid(column=1, row=1)
feld3 = tk.Frame(bg=r, width=300, height=300)
feld3.grid(column=3, row=1)
feld5 = tk.Frame(bg=r, width=300, height=300)
feld5.grid(column=1, row=3)
feld7 = tk.Frame(bg=r, width=300, height=300)
feld7.grid(column=3, row=3)
feld2 = tk.Frame(bg=y, width=300, height=300)
feld2.grid(column=2, row=1)
feld4 = tk.Frame(bg=y, width=300, height=300)
feld4.grid(column=1, row=2)
feld6 = tk.Frame(bg=y, width=300, height=300)
feld6.grid(column=3, row=2)
feld8 = tk.Frame(bg=y, width=300, height=300)
feld8.grid(column=2, row=3)

feld = tk.Frame(bg="white", width=300, height=300).grid(column=2, row=2)
feldlabel = tk.Label(text="Gruen & blau", bg="white", fg="black", font=("Arial", 15, "bold"))
feldlabel.grid(column=2, row=2)
feldbutton = tk.Button(text="Farbe aendern!", font=("Arial", 15, "bold"), bg="white", fg="black", command=change).place(x=370, y=470)
modul.mainloop()
programmieren, Array, Informatik, Python, Zusammenfassung, Variablen, list, Tkinter
2 Antworten
Wissensjunkie22
23.03.2017, 12:20

C++ Quersumme errechnen?

Hallo Gutefrage.net Comunity, Ich hab vor einiger Zeit angefangen die Programmiersprache C++ zu lernen. Bisher habe ich viel gelernt. Ich kann Variablen erstellen und initialisieren. Einfache Schleifen mit while, for. Befehle wie cout,cin und if sind auch kein Problem für mich. Sagen wir rinfach ich habe grundfähigkreiten erlernt. Wenn auch nicht alle Grundlegenden Themen behandelt bisher aber schon ein sehr solides Gerüst geschaffen (meiner meinung nach) um weiter diese Programmiersprache vertiefen zu können. Nun zu meiner eigentlichen Frage: Ich stelle mir ein Programm vor (natürlich alles auf der windows konsole) in welches man sein alter eingibt. Das Alter wird in einer integer variable abgespeichert. Danach rechnet das Programm die Quersumme des eingegebenen Alters aus und die quersumme wird als cout ausgegeben. z.B Ich schreibe mein Alter 18 rein. Das Programm errechnet die quersumme (1+8) und schreibt anschließend "9" als ergebnis auf. Zu meinem Problem: Ich kann die integer variable wo das Alter drin steht nicht "zerstückeln" um die beiden ziffern addieren zu können. Ich hab viel gegoogelt und etwas von arrays gelesen. Was arrays sind hab ich grundsätzIch verstanden aber wie ich sie hier anwenden kann? Ich wäre zutiefst froh wenn mir hier ein/e erfahrene/r Programmierer/in einen einfachen Weg aufweisen und somit einem Anfänger helfen könnte. Ich danke fürs durchlesen meiner Frage. Schönen Tag wünsch ich.

Programm, programmieren, Array, Code, Variablen, Integer
9 Antworten
leckmichmitname
10.12.2015, 21:16

Wie programmiere ich "Schiffe versenken" in Java?

Ich möchte gerne Schiffe versenken in Java programmieren und komme gerade nicht weiter...

Hier mein Beispiel-code: 

import java.util.*;
public class schiffeversenkken {
  
  public static void main(String[] args) {
    Scanner scan = new Scanner (System.in); 
    
    // Hilfsvariablen
    int x = 0 ;
    int y = 0 ;
    int i = 0 ;
    int j = 0 ;
    int s1 = 0 ;
    int s2 = 0 ;
    int s3 = 0 ;
    
    //Spielfeld
    int [][] feld = new int [10][10] ;
    
    // Ausgabe Spielfeld
    
    for(i = 0; i < feld.length; i++){
      for(j = 0; j < feld.length; j++){
        System.out.print(" [ " + feld[i][j] + " ]" + "\t" ) ;
      }
      System.out.println();
    }
    
    // Schiffe platzieren 
    for (s1=0;s1<3 ;s1++ ) {
      System.out.println("x-Koordinate des Schiffes: ");
      x = scan.nextInt() ;
      System.out.println("y-Koordinate des Schiffes: ");
      y = scan.nextInt() ;
      feld [x][y] = 1 ;
    } // end of for
    
    System.out.println("erstes Schiff platziert!");
    System.out.println(" ");
    
    for (s2=0;s2<3 ;s2++ ) {
      System.out.println("x-Koordinate des Schiffes: ");
      x = scan.nextInt() ;
      System.out.println("y-Koordinate des Schiffes: ");
      y = scan.nextInt() ;
      feld [x][y] = 1 ;
    } // end of for
    
    x = 0 ;
    y = 0 ;
    System.out.println("zweites Schiff platziert!");
    System.out.println(" ");
    
    for (s3=0;s3<3 ;s3++ ) {
      System.out.println("x-Koordinate des Schiffes: ");
      x = scan.nextInt() ;
      System.out.println("y-Koordinate des Schiffes: ");
      y = scan.nextInt() ;
      feld [x][y] = 1 ;
    } // end of for
    
    x = 0 ;
    y = 0 ;
    System.out.println("drittes Schiff platziert!");
    System.out.println(" ");
    
    // neues Spielfeld ausgeben
    for(i = 0; i < feld.length; i++){
      for(j = 0; j <feld.length; j++){
        System.out.print("[" + feld[i][j] + "]" + "\t");     
      }
      System.out.println();
      
      
    } // end of main
    
  } // end of class schiffeversenkken
}

Meine Probleme sind jetzt, dass die Schiffe, die ich platziere sehe (Position durch "1" erkennbar, leere Felder gekennzeichnet durch "0" ). Diese möchte ich jedoch verbergen. Ich hab schon drüber nachgedacht es so zu lösen:

Ich vergleiche [x] [y] mit dem Wert "1". Trifft dies zu, lasse ich per System.out.print "feld [x][y] ausgeben (sorry ich kann an dieser Stelle leider keinen Quellcode einfügen :/ )

Das funktioniert leider nicht so, wie ich es mir vorgestellt hab :D

Eine weitere Möglichkeit wäre auch, die Schiffe per Zufall erstellen zu lassen, jedoch weiß ich da auch nicht so genau wie ich das anstellen soll.

Es wäre vermutlich auch mehr als praktisch sämtliche Aktionen in Methoden zu packen, was ich bis jetzt aber noch nicht gemacht habe, da ich relativ unvorbereitet an dieses Pogramm herangetreten bin...

Ich freue mich über schnelle Antworten :)

Schiff, programmieren, Java, get, Array, versenden, Schiffe versenken, Set
2 Antworten

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