Gesucht: n
Soweit ist der Algorithmus also klar und im ungünstigsten Fall auf »n+1« Versuche beschränkt. Aber welcher Wert ist für n zu wählen, falls das Haus 100 Stockwerke hat? Die Aufgabe verlangt, die maximal notwendige Anzahl der Versuche zu minimieren, also sind klarerweise kleine Werte für »n« von Vorteil. Allerdings nimmt die Breite der Abschnitte ausgehend von »n« schrittweise um 1 ab und sobald ein Abschnitt die Länge 1 aufweist, ist der Ofen aus, falls dann alle aneinandergelegten Abschnitte noch nicht 100 Stockwerke abdecken.
Folglich muss die Summe aus »n + (n-1) + (n-2) + ... + 1« möglichst genau 100 ergeben. Sie darf leicht darüber liegen, aber nicht darunter. Der deutsche Mathematiker Carl Friedrich Gauß hat für die Summe dieser Zahlenreihe bekanntlich schon im Kindesalter eine Formel gefunden, als der Lehrer die Volksschulklasse dazu aufforderte, die Zahlen von 1 bis 100 von Hand zu addieren, und der geniale Gauß sofort, ohne auch nur eine einzige Addition auszuführen, das Ergebnis ablieferte [2].
Nach Gauß gilt also »n(n+1)/2 >= 100«, was aufgelöst eine quadratische Gleichung ergibt, deren einzige positive Lösung nach der im Gymnasium gelernten binomischen Formel etwa 13,65 ist. Der kleinste akzeptable Wert für n ist demnach 14, die numerische Aufteilung der Abschnitte zeigt Abbildung 3.
|
Abbildung 3: Mit n=14 ergibt sich diese Verteilung der Stockwerke in Abschnitte.
|
In Perl gegossen
Das Listing 1 zeigt eine Implementierung des Algorithmus in Perl. Zeile 9 setzt die Anzahl der Stockwerke (100) in die binomische Formel ein, rundet den ermittelten Fließkommawert mit der Funktion »ceil()« aus dem Posix-Modul auf die nächste ganze Zahl auf und erhält so den Wert 14 in der Variablen »$n«.
Die »while«-Schleife ab Zeile 16 legt einen Array »@stops« an, der als Elemente die Nummern der ersten Stockwerke jedes Abschnitts enthält, also etwa 1, 15, 28, ... 91, 96, 100. Das Stockwerk, aus dem die Bowlingkugeln den Sturz gerade noch überleben, nennt das Skript »Highest OK floor« und nimmt dessen Nummer zu Testzwecken entweder auf der Kommandozeile entgegen (dazu ruft man es also zum Beispiel mit »bball-drop 99« auf) oder es legt den in Zeile 23 voreingestellten Wert 42 fest.
01 #!/usr/local/bin/perl -w
02 use strict;
03 use POSIX qw(ceil);
04 use Log::Log4perl qw(:easy);
05 Log::Log4perl->easy_init($INFO);
06
07 my $total = 100;
08
09 my $n = ceil( (-1 + sqrt(1+4*2*$total))
10 / 2 );
11
12 my $sum = 1;
13 my @stops = ();
14 push @stops, $sum;
15
16 while($sum + $n <= $total) {
17 push @stops, $sum + $n;
18 $sum += $n;
19 $n--;
20 }
21
22 my $last_ok_floor =
23 (defined $ARGV[0] ? $ARGV[0] : 42);
24
25 INFO "Pst, pst: Highest OK floor is ",
26 $last_ok_floor;
27
28 my $tries = 0;
29 my $ok_floor = 1;
30 my $smash_floor = $total + 1;
31
32 for my $stop (@stops) {
33 $tries++;
34 if(!try_floor($stop, $last_ok_floor)) {
35 $smash_floor = $stop;
36 last;
37 }
38 $ok_floor = $stop;
39 }
40
41 for my $try_floor ( $ok_floor+1 ..
42 $smash_floor-1) {
43 $tries++;
44 if(!try_floor($try_floor,
45 $last_ok_floor) ) {
46 $smash_floor = $try_floor;
47 last;
48 }
49 $smash_floor = $try_floor + 1;
50 }
51
52 INFO "Highest OK floor: ", $smash_floor-1,
53 " ($tries tries)";
54
55 ###########################################
56 sub try_floor {
57 ###########################################
58 my($floor, $last_ok_floor) = @_;
59
60 if($floor > $last_ok_floor) {
61 INFO "Floor $floor: Wham, busted!";
62 return 0;
63 }
64
65 INFO "Floor $floor: Okay.";
66 return 1;
67 }
|
Per Log4perl gibt es dann geheimnistuerisch mit "Pst, pst" den vom Algorithmus zu ermittelnden Wert in Zeile 25 aus und fängt dann an, die einzelnen Abschnitte abzuarbeiten. Die For-Schleife ab Zeile 32 fährt jeweils an den Anfang eines Abschnitts im Array »@stop« und ruft die Routine »try_floor()« mit dem aktuell zu testenden und dem geheimen maximal machbaren Stockwerk auf.
Übersteigt die getestete Höhe diese kritische Höhe, gibt »try_floor()« einen falschen Wert zurück, um anzudeuten, dass die gerade geworfene Bowlingkugel nun zerschmettert am Boden liegt.
Findet die »for«-Schleife ab Zeile 32 ein Stockwerk, das die erste Kugel nicht überlebt, bricht sie mit »last« ab und setzt die Variable »$smash_floor« auf das Stockwerk, das den Bruch ausgelöst hat.Anschließend fährt die Schleife ab Zeile 41 zurück zum nächsten Stockwerk des letzten erfolgreichen Wurfs und steigt Stufe um Stufe höher, bis auch die zweite Kugel den Geist aufgibt oder das Ende des Abschnitts erreicht ist. Im ersten Fall bricht auch diese Schleife mit »last« ab und das Ergebnis liegt in »$smash_floor«. Ein um 1 verminderter Wert ergibt das gesuchte höchste Stockwerk, das die Kugeln noch überleben würden.
| Whitepaper |
|---|
|
Open Source Datenintegration in der Praxis: Fallstudien und Anwendungsbeispiele
Über die letzten Jahre hinweg haben sich Open Source Lösungen als fester Bestandteil des gesamten Datenintegrationsmarktes etabliert. Viele Unternehmen haben bereits das Open Source Modell für Ihre Datenintegrationsprojekte aufgegriffen. Das vorliegende White Paper illustriert anhand ausgewählter Fallstudien und Anwendungsbeispiele die Implementierung von Open Source Datenintegration in der Praxis und benennt die daraus resultierenden Vorteile.
Download PDF (Registrierung erforderlich)
|
|
The Role of Open Source in Data Integration
Obwohl in den letzten Jahren viele technische Fortschritte erzielt werden konnten, verfügen die meisten Datenintegrationsprozesse nach wie vor nur über eine sehr begrenzte Automatisierung. Das vorliegende White Paper von dem Industry Analyst Mark Madson wird zunächst ein grundlegendes Verständnis von Daten Integration vermitteln, die Vorzüge von Open Source Lösungen für Daten Integration erläutern und Ihnen professionelle Empfehlungen geben, damit Sie Ihre Integrationsjobs noch einfacher und produktiver gestalten können.
Download PDF (Registrierung erforderlich)
|
Dieser Online-Artikel kann Links enthalten, die auf nicht mehr vorhandene Seiten verweisen. Wir ändern solche "broken links"
nur in wenigen Ausnahmefällen. Der Online-Artikel soll möglichst unverändert der gedrucken Fassung entsprechen.
|
squirrel,
10.02.2010 10:53
;; bowl
(defun floorlist (&key (mxfloor 100))
"build 1st list for iteration"
(let ((steps (ceiling (- (sqrt (+ 1 (* 8 mxfloor))) 1) 2)))
(loop for x from steps downto 1
for y = steps then (+ x y)
while (< y mxfloor) collect y)))
(defun thrower (flist smash &key (ball 2) (ok 0))
"start throwing balls and watch what happens"
(let ((tfl (first flist)) (ret 'bang!))
(unless (or (null flist) (zerop ball))
(when (< tfl smash) (pop flist) (setf ok tfl ret 'ok))
(when (>= tfl smash) (decf ball)
(setf flist (loop for i from (1+ ok) to (1- tfl) collect i)))
(cons (list ret tfl) (thrower flist smash :ball ball
(loop for i from 1 to 101 do
(print i) (princ (thrower (floorlist :mxfloor 100) i)))
Die erste Kugel wird gleich aus dem 14. Stock abgeworfen.
Toralf Förster,
16.11.2009 11:21
$sum += $n;
push @stops, $sum;
die kostbare eingesparte CPU Zeit kann man ja dann an den eigenen BOINC Client verfüttern
R. Schmidt,
07.11.2009 16:57
#! /usr/bin/perl -w
# s. Linux Magazin Nr. 12 2009 S. 116
$n = 13;
for($i = $n + 1, $inc = $n, $k = 1; $i <= 100 && $inc > 0; $i += $inc, $inc -= 1, $k++)
{
print "Kugel: $k: Stock: $i\n";
}
print "\n";
Man möge mich bitte korrigiern, wenns falsch ist.