| Zeige Beiträge 1 bis 8 von 8 Treffern |
|
 Thema: Touringmaschine |
|
|
____________
|"""""""""""""""|
|""""""o""""""""|
|___________|_________|=
^
|
Turingmaschine mit An-Knopf und Stecker, die Palindrome erkennt.
Ich hoffe sehr, dir geholfen zu haben!
|
|
| Thema: Druckauftrag bläht auf |
orkano
| Antworten: |
4 |
| Hits: |
11.150 |
|
|
Kommt auf den Drucker an, wie er damit umgeht (bzw kann auch der Printserver sein). Der eine oder der Andere wird wird wohl aus einem Dokument, welches Graphiken enthält sozusagen ein einziges großes Bild machen, was die gleiche Größe des Auftrages erklären würde.
Wo liegt denn eigentlich das Problem dabei? Sind die 20 Mb zuviel oder wird der Drucker langsam?
|
|
| Thema: QuickSort best/worst |
|
|
Hallo Ihr!
Ich habe einen QuickSort-Algo, der als Pivot immer das erste Element des 8-stelligen Arrays nimmt. Meine Aufgabe ist es nun eine Zahlenfolge aus 8 paarweise verschiedenen Zahlen zu finden, die einmal den best und einmal den worst case für QuickSort darstellt.
Der best case trifft ja genau dann ein, wenn die Wahl des neuen Pivotelements die Mengen genau in 2 Teile teilt.
Nehmen wir an ich hätte ein 8-stelliges Array mit den Zahlen von 1-8 und als Pivot wird immer das erste gewählt. Um jetzt einen best-case zu bekommen müsste also das erste Element im Array gleich der Median des Arrays sein, was also 5 ist.
Soweit so gut, aber jetzt komme ich nicht weiter! Wie muss ich die folgenden Zahlen so ordnen, dass das nächste Pivot immer gleich das "richtige", sprich der Median der Teilmenge, ist?
Danke euch!
EDIT: Zum Worst-Case:
Meiner Ansicht nach hat man den Worst-Case bei einem Szenario mit Pivot als erstem Element bei einem Absteigend vorsortierten Array. Stimmt das?
|
|
| Thema: Asymptotisches Wachstum von versch. Funktionen |
|
|
Vielen Dank soweit, ich hab jetzt folgendes:
37 <= 2/n <= ![[latex] \sqrt{n} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? \sqrt{n} ) <= n(log(logn)) <= n <= n log n <= n(log n²) <= n(log n)² <= n² log(n) <= ![[latex] n^{3/2} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? n^{3/2} ) <= n² <= n³ <= ![[latex] 2^{n/2} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? 2^{n/2} ) <= ![[latex] 2^{n} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? 2^{n} )
Asymptotisch gleich schnell wachsen meiner Meinung nach folgende:
a) n log n, n (log n)², n log (n²), n² log (n)
b) , n², n³
c) ,
Könnt ihr mir sagen, ob das jetzt stimmt bzw wenn nicht wo ich Fehler gemacht habe? Vielen Dank!
|
|
| Thema: Höhe eines Binärbaums rekursiv |
|
|
Hallo Ihr!
Habe folgende Aufgabe: Geben sie einen Pseudocode für eine rekursive Methode an, mit der man die Höhe eines Binärbaums bestimmen kann.
Dazu möchte ich die Teifensuche benutzen, heisst ich nehme den Startknoten, schaue nach, ob der Kinder hat und speichere diese in einem Stack.
Dann rufe ich die Methode rekursiv mit allen Knoten (hier ja max. 2) im Stack auf. Sobald ein Knoten keine Kinder mehr hat, weiss ich, dass hier der Zweig zu Ende ist.
Mein ganzes Problem bei der Sache sind die Verzweigungen des Baumes, durch die ich es nicht hinkriege einen vernünftigen Counter in den Algo zu bekommen, der mir mitzählt, in welcher "Höhe" ich mich gerade befinde. Durch die Verzweigungen zählt der immer zuviel, aber ich weiss nicht, wie ich das ändern kann wegen der Rekursivität! 
Bitte helft mir, wie kann ich das hinkriegen?
Hier mein Algo bis jetzt ohne Counter:
Tiefensuche(knoten n) {
knoten stack s;
if(n.hasChildren()){
s.push(n.getLeftChild());
if(n.hasRightChild()){
s.push(n.getRightChild());
}
}
while( !n.isEmpty()) {
Tiefensuche(s.pop());
}
}
So wird jeder Pfad durchgegangen und wenn der Stack Empty ist, weiss ich, dass ich am Ende bin. Aber wie kanni ch das zählen?
|
|
| Thema: Asymptotisches Wachstum von versch. Funktionen |
|
|
Hallo Ihr!
Ich habe folgende Aufgabe: Ich muss ein paar Funktionen nicht-absteigend nach ihrem asymptotischen Wachstum sortieren und angeben, welche davon asymptotisch gleich schnell wachsen.
Es sind folgende Funktionen:
n; Wurzel(n); n^1,5; n log n; n log(logn); n(log n)²; n log(n²); 2/n; 2^n; 2^(n/2), 37, n² log n, n³
Ich habe sie mal versucht zu sortieren. Bitte helft mir und sagt mir, ob das richtig ist was ich da gemacht habe, danke!
Ausserdem verstehe ich nicht so wirklich welche Gruppen asymptotisch gleich schnell wachsen, bzw was damit gemeint sein könnte...ich vermute dass z.B. n² und n³ asymptotisch gleich schnell wachsen, aber was ist dann z.B. mit n(log(log n)) und n log n...haben die gleiches asymptotisches Wachstum oder wie? Welche der Funtkionen haben gleich schnelles asymptotisches Wachstum? Vielen Dank für eure Hilfe!
37
2/n
n(log(log n))
Wurzel(n)
n log n
n
n(log n)²
n log (n²)
n^1,5
n² log n
n ²
n³
2^n²
2^n
|
|
|
| Zeige Beiträge 1 bis 8 von 8 Treffern |
|
|
|
