Verwandte Themen

Frage
von PrettyRANDOM
03.10.2022, 16:07
Informatik "Rätsel"?

Programmiersprache: JavaWie stellt man bei der Datenstruktur Queue Objekte nicht hinten sondern vorne an? Also vom Code her.Kontext/Hintergrund von dieser Frage: Ich habe eine PriorityQueue. Doch dann soll plötzlich ein neues Objekt hinzugefügt werden, welches eine höhere Priorität als alle bereits in der PriorityQueue vorhandenen Objekte hat. (Da das hinzuzufügende Objekt ja die höchste Priorität hätte, müsste es ganz vorne in der PriorityQueue stehen).
Natürlich habe ich mir, bevor ich die Frage hier auf GF stelle, selbst nachgedacht, wie man das Problem lösen könnte. Bis jetzt ist mir aber nur

first = new QueueInhalt(pObject, pPriority);

eingefallen. Ich komme beim setNext(), also wenn der neue, eingefügte, Knoten QueueInhalt seinen Next - Link auf den ursprünglich an derselben Stelle (ganz vorne) gewesenen Knoten QueueInhalt setzt. (Wenn man ein Objekt hinten anstellt, schön nach FIFO halt, hätte ich kein Problem mit dem Setzen der next - links und first - links. Aber vorne anstellen? Keine Ahnung, wie das gehen soll.)
Danke und ein "Hilfreich" schonmal für eure Antworten😀

public void add(ContentTypePerson pObject, int pPriority) {
    QueueInhalt inhaltsobjekt = new QueueInhalt(pObject, pPriority);
    if (first == null) { //Wenn kein Objekt in der Queue vorhanden ist
    first = new QueueInhalt(pObject, pPriority);
    } else if (pPriority > first.getPriority()) {
    first = new QueueInhalt(pObject, pPriority);
//...?    
    }
}
Software, Schule, IT, programmieren, Java, Datenstrukturen, Informatik, Softwareentwicklung, Algorithmen und Datenstrukturen
2 Antworten
Frage
von Michelle910
12.07.2022, 14:27
Informatik Datenstrukturen?

Wir sollen für jedes der Folgenden Computerprogramme eine geeignete Datenstruktur finden und begründen .

Ich weiß nicht ob das so richtig ist,wir bekommen aber leider kein Feedback , vielleicht weil wir eingentlich einen anderen Studiengang haben .Wir hatten auch nur eine Kurze Einführung wo Tupel/Records,(B) Listen/Mengen,Array,Hierarchische StrukturenTree Structure und E-Graphen kurz vorgestellt wurden.Ich habe die Aufgabe gemacht bin mir aber unsicher ob das so stimmt , könnte Bitte jemand drüber gucken und mir sagen ob das so stimmt und gegebenfalls wenn machbar korrigieren?Mit ich gut lernen kann🙈?Ich würde mich freuen wenn mir jemand helfen könnte.

1. Das Spiel Vier Gewinnt

Array oder Listen /Mengen oder reicht schon Tupel/ Record

2. Das Brettspiel Siedler von Catan

array

3. Ein Programm für Familienstammbäume

Hierarchische Strukturen Tree Structure

4. Ein Programm um Bilder zu malen (ähnlich wie Paint)

? Array?

5. Ein Pokerspiel

Array

6. Ein Programm um Rechnungen zu verwalten

List/Menge

7. Ein Programm was hilft einen Bafög-Antrag elektronisch Auszufüllen

Assacoite Array geht nicht weil es sich hier nicht um eine Nummer ziehen geht wie beim Finanzamt richtig?

8. Programm zum Erstellen einer Mind-Map

E -Graph kann man das dafür nutzen?

Oder wird hier list verwendet?

9. Programm für Adressen und Telefonnummern

Hier gehen beides Tupel/Record. Und List Menge richtig?

Studium, IT, Datenstrukturen, Informatik, Algorithmen und Datenstrukturen
1 Antwort
Frage
von EkkoMcfly
21.04.2022, 20:06
Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

Computer, Schule, Mathematik, programmieren, Informatik, Algorithmus, Algorithmen und Datenstrukturen
1 Antwort
Frage
von computerfan001
24.08.2020, 11:04
Umgekehrte Polnische Notation / Postfix-Notation über Stack programmieren, so richtig?

Hallo,

ich soll die umgekehrte polnische Notation / Postfix-Notation in Java mit Hilfe eines Stacks programmieren. Dafür stehen mir nur folgende Informationen zur Verfügung:

public class IntegerStack {
  public boolean emptystack();
  public int head();
  public void push(int i);
  public int pop();
}

Leider zeigt ein Testfall als Fehler Folgendes an:

IntegerStack s = new IntegerStack();
String[] input = {"1", "2", "*", "3", "4", "*", "+"};
Calculator(input, s);
System.out.println(s.compareHistory(new String[] {
  "[1]",
  "[1, 2]",
  "[1]",
  "[]",
  "[2]",
  "[2, 3]",
  "[2, 3, 4]",
  "[2, 3]",
  "[2]",
  "[2, 12]",
  "[2]",
  "[]",
  "[14]",
  "[]" }
));

// erwartet:
true
// erhalten:
wrong history length: target 14 - is 0
false

Ich kann diesen Fehler nicht deuten. Kann mir bitte jemand sagen, was da falsch sein soll? Ich weiß nicht, was ich beheben soll.

Anbei mein Code:

public int Calculator(String[] input, IntegerStack s) {
  s = new IntegerStack();

  for (int i = 0; i < input.length; i++) {
    switch(input[i]) {
      case "+":
        int x = s.pop();
        int y = s.pop();

      
          s.push(y + x);
        
        break;
      case "-":
        x = s.pop();
        y = s.pop();

       
          s.push(y - x);
        
        break;
      case "/":
        x = s.pop();
        y = s.pop();

      
          s.push(y / x);
       
        break;
      case "*":
        x = s.pop();
        y = s.pop();

        
          s.push(y * x);
        
        break;
      case " ":
        break;
      default:
        if (input[i] != null) {
          s.push(Integer.parseInt(input[i]));
        }
        else {
        }
        ;
      }
    }

    int z = s.pop();
    return z;
  }
Computer, Freizeit, Studium, Schule, Mathematik, programmieren, Java, Informatik, Physik, stack, Algorithmen und Datenstrukturen
3 Antworten
Frage
von 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
Frage
von Jensek81
15.09.2019, 19:59
Mit Bildern
Logarithmenfunktionen nach asymptotischem Wachstum ordnen?

Guten Abend

Ansatz:

Zunächst erst mal alle unnötig kompliziert gegebenen Funktionen so umschreiben, dass sie sich vergleichen lassen

a (n) = 13n³, kann man nicht mehr vereinfachen

b (n) = log_4 n³ ist nichts anderes als 1,5 log_2 n

c (n) = 9 log_3 n hätt ich jetzt auch nicht weiter vereinfachen können

d (n) = log_2 4 n^4/3 ist nichts anderes als log_2 (4) + log2 (n^3/4), also 2 + 3/4 log_2 n

e (n) = n^log_4 n^4 kann man umschreiben zu n^2 log_2 (n).

Ich hätte die Funktionen also sortiert (von langsam nach schnell):

c < d < b < a < e.

Problem: Mein Tutor meinte die richtige Reihenfolge wäre: d < b < c < e < a.

Ich versteh es nicht. c. hat ja log_3 (n) und das ist ja schon mal langsamer als alles mit log_2 (n). Bei d und b bin ich mir unsicher, weil die ja eigentlich asymptotisch gleich schnell wachsen sollten. b wächst vielleicht bissl schneller weil es mit 1,5 multipliziert wird, während d nur mit 3/4 multipliziert wird.

Großes Kopfzerbrechen bereitet mir die Tatsache, dass e langsamer wachen soll als a. Bei e (n) ist doch das "n" im Exponenten. Auch wenn man im TR z.B. für n = 17 die Funktion e (n) eingibt, also 17^log_4 (17)^4 ist das 2.9210^21, also eine tierisch hoche Zahl. Wärend n = 17 in die Funtkion a(n) eingesetzt, lediglich 1317³ = 63869 ergibt, also viel weniger wächst. Auf desmos kann man die Funktionen plotten, und dort ist e (n) [bzw. ich musste es hier f(n) nennen, weil das Programm den Buchstaben "e" direkt als Euler'sche Phi-Funktion interpretiert] auch viel stärker an der y-Achse dran, also müsste es doch eigentlich stärker wachsen, or?

Bild zum Beitrag
Schule, Mathematik, Informatik, Logarithmus, Potenzen, Theoretische Informatik, Wachstum, Algorithmen und Datenstrukturen
2 Antworten
Frage
von Jensek81
09.05.2019, 00:52
Ternärer Baum als Pseudocode?

In dieser Aufgabe betrachten wir gewurzelte ternäre Bäume. Jeder Knoten v kann also ein linkes Kind v.L, ein mittleres Kind v.M und/oder ein rechtes Kind v.R haben. Wir möchten nun herausfinden, wie viele Knoten im Baum sind.Gebe jeweils einen rekursiven Algorithmus in Pseudocode an, der durch den Aufruf count(v0) die Anzahl n der Knoten im Baum mit Wurzel v0 bestimmt. Begründe die Korrektheit der Algorithmen.

a) Gehe für den Entwurf deines Algorithmus zuerst davon aus, dass der Baum vollständig ist, also jeder Knoten entweder genau drei Kinder oder gar kein Kind besitzt und für jedes Blatt der Weg von der Wurzel die gleiche Länge hat. Stelle eine Rekursionsgleichung für die Laufzeit auf und löse diese mithilfe des Master-Theorems. Der Algorithmus soll eine Laufzeit von o(n)haben.

b) Wie verändern sich Algorithmus und Laufzeit, wenn Sie allgemeine ternäre Bäume betrachten?

________________________________________________________

Es geht um Pseudo-Code. In der Vorlesung benutzen wir C (obwohl wir C eigentlich erst nächstes Semester lernen), also wir lassen immer Klammern auf und schließen diese erst in der nächsten oder ubernächsten Zeile und erhöhen Variablen durch i++.

Ich habe mir überlegt, weil das ganze ein ternärer Baum sein soll und die Länge gezählt wird:

var counter = 0
    for b = 0; b ≤ n; b++) {
        for (l = 1, l++) {
             l = l + 1
}
        for (m = m, m++) {
             m = m + 1
}
        for (r = r, r++) {
             r = r + 1
}
        counter = counter + 1
}

wobei b die, ich nenn's jetzt einfach mal "Oberschleife" ,für den Baum an sich ist und l, m und r jeweils Unterschleifen, wobei l = links, m = mitte, r = rechts. Glaube aber, dass ich's mir hiermit zu einfach mache.

Zudem muss das Ganze ja noch als rekursive Funktion geschrieben werden, also der Form T (n) = a * T (n/b) + f(n), wobei b in diesem Fall = 3 ist, weil es ja ein ternärer Baum ist. Aber was ist a? Man könnte ja theoretisch unendlich viele Kinderknoten haben? Oder versteh ich da was falsch?

Schule, Mathematik, Knoten, Baum, Informatik, Pseudocode, Algorithmen und Datenstrukturen
2 Antworten

Meistgelesene Fragen zum Thema Algorithmen und Datenstrukturen
Mehr meistgelesene Fragen zu Algorithmen und Datenstrukturen