Differences

This shows you the differences between two versions of the page.

--- efinf:blc2016:loesungen-2016-12-13:schraubensack [2016/12/18 09:04] – created Ivo Blöchliger
+++ efinf:blc2016:loesungen-2016-12-13:schraubensack [2016/12/18 09:14] (current) – [Mit Hash] Ivo Blöchliger
@@ Line 1: / Line 1: @@
+{{backlinks>.}}
+===== Daten =====
+Aufgabenstellung: https://www.programmieraufgaben.ch/aufgabe/schraubensack/uk540btd
+  * Anzahl Zeilen in der Datei: $n$
+  * Kleinster und grösster Druchmesser: $d$ und $D$
+  * Anzahl verschiedene Durchmesser: $a$ (wobei $a<n$).
+==== $O(f(n))$ Notation ====
+Eine Funktion $g(n)$ ist in $O(f(n))$ wenn es ein $n_0$ und $c_0$ gibt, so dass
+$$ g(n) < c_0 f(n) \qquad \forall n>n_0$$
+Umgangssprachlich heisst das, die Funktion $g(n)$ wächst nicht schneller als $f(n)$.
+Beispiel:
+  * Wenn $n$ Personen alle miteinander anstossen, macht es $O(n^2)$ mal "Kling". (Natürlich auch $O(n^3)$, aber nicht $O(n)$)
+==== Sortieren, zählen ====
+Rechenaufwand:
+  * Sortieren $O(n \log(n))$ (naive Sortier-Algorithmen sind $O(n^2)$).
+  * Liste durchgehen $O(n)$
+Insgesamt also $O(n \log(n))$.
+Speicherplatz: $O(n)$ (die ganze Liste)
+==== Durchmesser sequentiell durchgehen, Liste danach absuchen ====
+Rechenaufwand:
+  * (D-d) mal $n$ Einträge absuchen, also $O((D-d)\cdot n)$
+Speicherplat: $O(n)$ (die ganze Liste)
+==== Nur vorhandene Durchmesser durchgehen ====
+Rechenaufwand:
+  * Nächsten Durchmesser finden:
+    * Entweder Liste durchgehen, nächst-grösseren finden, also $O(n)$ pro Schritt.
+    * Oder in der Liste weitersuchen, bis unbekannten Durchmesser gefunden, braucht aber $O(a)$ Speicherplatz. Insgesamt aber nur $O(n)$.
+  * Liste durchgehen, zählen: $O(n)$. Und das ganze $a$ mal.
+Also total $O(a\cdot n \cdot n)$ = $O(n^2 a) \subset O(n^3)$ für die erste Variante.
+Oder $O(a\cdot n + n) = O(a \cdot n) \subset O(n^2)$ für die zweite Variante.
+Speicherplatz: $O(n)$ für beide Varianten (weil $O(n)=O(2n)$).
+==== Mit Hash ====
+Rechenaufwand:
+  * Für jede Zeile, entsprechenden Eintrag finden: Wenn der Hash gut implementiert ist, $O(\log(a))$.
+Also total $O(n \log(a)) \subset O(n \log(n))$.
+Speicherplatz: $O(a)$ (Platz der Datei auf der Platte nicht mitgezählt).
+<code ruby schraubenback-bloechliger-mit-hash.rb>
+#!/usr/bin/ruby
+data = Hash.new
+File.open("schrauben.txt","r"){|f|
+   while(line=f.gets) # Zeile einlesen
+     was = line[0] == "m" ? 0 : 1
+     d = line[2..-1].to_i
+     unless data.has_key?(d)
+        data[d] = [0,0]
+     end
+     data[d][was]+=1
+   end
+}
+# Der folgende Sort ist O(a log(a)), was weniger
+# als O(a log(a)) der obigen Schlaufe ist.
+data.keys.sort.each{|d|
+   puts "#{d}mm: #{data[d].min} passende Paare"
+}
+</code>