Differences

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

--- efinf:blc2016:loesungen-2016-12-13 [2016/12/18 10:46]
Ivo Blöchliger [Lösungen Es lebe der König]
+++ efinf:blc2016:loesungen-2016-12-13 [2016/12/21 21:46] (current)
patrick_lehn [Lösungen]
@@ Line 54: / Line 54: @@
   end
 end
+</code>
+=== Luca ===
+<code ruby datensalat.rb>
+def min(*values)
+ values.min
+end
+def max(*values)
+ values.max
+end
+liste = File.open("schrauben.txt", "r"){ |file| file.read.split(" ").each_slice(2).to_a.each{|e| e[1] = e[1].to_i}}
+muttern = Array.new(150, 0)
+schrauben = Array.new(150, 0)
+liste.each{|e| if e[0]=="m" then muttern[e[1]]+=1 elsif e[0]=="s" then schrauben[e[1]]+=1 end}
+for e in 0..149 do
+	minimum = min(muttern[e],schrauben[e])
+	puts "#{e}mm: #{minimum} passende Paare" if minimum != 0
+end
+</code>
+=== Noel ===
+<code php>
+<?php
+/* Sry, wegen PHP...*/
+$m = [];
+$s = [];
+$lines = preg_split('/\n/', trim(file_get_contents('schrauben.txt')));
+foreach($lines as $line) {
+    $v = explode(" ", $line);
+    if($v[0] == "m") {
+        if(isset($m[$v[1]])) {
+            $m[$v[1]] += 1;
+        } else {
+            $m += [$v[1] => 1];
+        }
+    } else {
+        if(isset($s[$v[1]])) {
+            $s[$v[1]] += 1;
+        } else {
+            $s += [$v[1] => 1];
+        }
+    }
+}
+?>
+</code>
+===Patrick===
+<code ruby schrauben.rb>
+liste = File.readlines("schrauben.txt").map{|l| l.split(" ")}.map{|l| [l[0],l[1].to_i]}
+liste.sort!{|a,b|  # a und b stehen für die Arrays # sortiergeschwindigkeit ist O(nlog(n))
+   if a[1]==b[1]   # wenn die Zahlen gleich sind, dann werden die Buchstaben verglichen. PC kennt Reihenfolge der Buchstaben
+      a[0]<=>b[0]  # liefert auch wieder -1 wenn a>b, 0 wenn a=b, 1 wenn a<b
+   else
+      a[1]<=>b[1]  # vergleicht die Zahlen, sortiert sie
+   end
+}
+a=0   # a & g stehen für die Indizes der Unterarrays
+g=1
+schrauben = 0
+muttern = 0
+last_size=liste[a][1]
+puts   #leicht hübschere Ausgabe
+while a!=liste.size
+   if liste[a][1]==last_size   # solange die grösse der Muttern/Schrauben gleich sind...
+      while liste[a]==liste[g]   # solange die Unterarrays gleich sind...
+         g+=1   # ...wächst g
+      end
+         differenz= g-a   # die Buchstaben, die für die Indizes der Unterarrays stehen, werden verglichen
+      if liste[a][0]=="s"
+         schrauben = differenz
+      elsif liste[a][0]=="m"
+         muttern = differenz
+      end
+      a=g   # a wird aktualisiert
+   else
+      if muttern == 0 or schrauben == 0  # damit kein Auswurf entsteht wenn es keine Paare gibt
+         nil
+      elsif muttern > schrauben
+         puts "#{last_size}mm = #{schrauben} Paare"
+      elsif muttern < schrauben
+         puts "#{last_size}mm = #{muttern} Paare"
+      elsif
+         puts "#{last_size}mm = #{muttern} Paare"
+      end
+   last_size=liste[a][1]  # last_size wird aktualisiert, auf eine neue Grösse eingstellt
+   schrauben = 0  # bevor die nächsten Unterarrays verglichen werden, sollen diese wieder auf 0 stehen
+   muttern = 0
+   end
+end
+puts   # leicht hübschere Ausgabe
+# gesamt Aufwand ist O(nlog(n))
 </code>
@@ Line 66: / Line 172: @@
 # No comment
 </code>
 === Mathematiker ===
@@ Line 73: / Line 178: @@
 Der zweite Teil ist interessanter, es läuft auf die Frage hinaus, wieviel mal eine Türe geöffnet und geschlossen wird. Nur wenn diese Anzahl ungerade ist, ist die Türe am Schluss offen. Der Zustand der Türe $n$ wird genau so viel mal geändert, wie die Zahl $n$ Teiler hat (sich selbst ingebegriffen). Wird $m$ in seine Primfaktoren zerlegt geschrieben gilt
 $$n=p_1^{n_1}\cdot p_2^{n_2} \cdot \ldots \cdot p_m^{n_m}$$
-Ein Teiler von $n$ erhält man, indem man von jedem Primfaktor $p_i$ eine beliebige Anzahl zwischen $0$ und $n_i$ wählt. D.h. die Anzahl Teiler ist $(n_1+1)\cdot (n_2+1)\cdot \ldots \cdot (n_m+1)$. Dieses Produkt ist genau dann ungerade, wenn **alle** $n_i$ gerade sind. Sind alle Primfaktoren gerade, ist die Zahl eine Quadratzahl, und damit bleiben 10 Türen offen.
+Ein Teiler von $n$ erhält man, indem man von jedem Primfaktor $p_i$ eine beliebige Anzahl zwischen $0$ und $n_i$ wählt. D.h. die Anzahl Teiler ist $(n_1+1)\cdot (n_2+1)\cdot \ldots \cdot (n_m+1)$. Dieses Produkt ist genau dann ungerade, wenn **alle** $n_i$ gerade sind. Sind alle Exponenten gerade, ist die Zahl eine Quadratzahl, und damit bleiben 10 Türen offen.
 ==== Lösungen "Josephus Problem" ====