efinf:blc2016:loesungen-2016-12-13:schraubensack [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
{{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>