Zaunpfahlproblem
aus Wikipedia, der freien Enzyklopädie
 |
Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Bitte entferne zuletzt diese Warnmarkierung. |
Der Begriff Zaunpfahlproblem beschreibt ein Logikproblem der Indexierung und zeichnet sich durch eine Indexverschiebung von genau eins aus. Dieses Problem tritt häufig in der Datenverarbeitung auf.
Inhaltsverzeichnis |
[Bearbeiten] Problematik
Zaunpfahlprobleme können auftreten, wenn
- es einen Index mehr als Elemente gibt. Das liegt daran, dass Anfangs- und Endelement kein Vorgänger- bzw. Nachfolge-Element haben. Das ist das ursprüngliche Zaunpfahlproblem. So hat beispielsweise ein Zentimetermaß zwar die Zentimetermarken (Punkte) 0 und 1, aber nur einen ersten (von 0 bis 1 cm) und keinen nullten Zentimeter. Hier beschreibt die Verbindung von zwei Indizes ein Element, was manchmal zu Schwierigkeiten führen kann.
Beispiel:
Index 0 1 2 3 4 Element 1 2 3 4
- es genauso viele Indizes wie Elemente gibt, diese aber um eins verschoben sind. Dabei wird die Nummerierung anders durchgeführt als dessen Auslesung. In der Datenverarbeitung kommt dieses Problem häufig vor, wenn Computer bei 0 zu zählen beginnen, Anwender aber bei 1.
Beispiel:
Index 0 1 2 3 4 Element 1 2 3 4 5
[Bearbeiten] Beispiel
Frage: Wenn man einen 30 m langen geraden Zaun errichten will und die Zaunpfähle 3 m auseinander stehen sollen, wieviele Pfähle braucht man dafür?
Antwort: Viele würden fälschlicherweise 30 durch 3 teilen und "10 Pfähle" antworten. Richtig ist aber 11, denn wie die nebenstehende Illustration zeigt, brauchen Anfang und Ende des Zauns je einen Pfahl.
[Bearbeiten] Zaunpfahlprobleme in der Informatik
In der Informatik, wo der Begriff des Zaunpfahlproblems am häufigsten Verwendung findet, treten ähnliche Probleme auf. Diese gehören zwei Hauptgruppen an:
- Wie werden Abstände gezählt - inklusive eines oder beider Grenzelemente? Wenn es um den Abstand von Elementen in einer Liste geht, muss sich der Softwareentwickler im Klaren darüber sein, ob eines oder beide Grenzelemente mitgezählt werden oder nicht.
- Zählung ab 0 oder ab 1: Im Alltag beginnen Menschen Aufzählungen meist bei 1, in vielen – vor allem durch C beeinflussten – Programmiersprachen beginnen Aufzählungen hingegen bei 0. So hat beispielsweise in Java ein Array der Größe 5 Elemente mit den Indizes 0, 1, 2, 3 und 4. Ein typischer Anfängerfehler ist es, in einem solchen Array die Elemente 1 bis 5 auszulesen oder einen falschen Vergleichsoperator zu benutzen. Dies kann zu einem Um-eins-daneben-Fehler führen.
Beispiel: Welchen Abstand haben Element 20 und Element 30 in einer Liste?
- Zählung einschließlich beider Grenzwerte ("Inklusivzählung"): 11
- Zählung einschließlich 20, aber ohne 30: 10
- Zählung ohne 20, aber einschließlich 30: 10
- Zählung ohne beide Grenzwerte (die dazwischenliegenden Elemente): 9
[Bearbeiten] Verwandte Probleme
[Bearbeiten] Die historische Inklusivzählung
Abstände, Distanzen und Zeiträume wurden von der Antike bis in nachmittelalterliche Zeit hinein nach der „Inklusivzählung“ gezählt. Bei dieser Zählweise wird sowohl das Anfangs- als auch das Ende-Element einer Folge mitgezählt. Der Startpunkt wird als „1“ definiert und von dort weitergezählt. Der Distanz 0 wird somit der Zahlenwert „1“ zugewiesen, der Distanz 1 der Zahlenwert „2“, usw. Die Werte für Distanzen, Zeiträume usw. sind also bei der Inklusivzählung immer um 1 größer als mathematisch korrekt. Historisch hat die Inklusivzählung ihre Ursache in dem Umstand, dass das Konzept der Zahl Null erst mit der Einführung der arabisch-indischen Zahlen ab dem 13. Jahrhundert in Europa bekannt wurde.
Von der Inklusivzählung rührt z.B. der Brauch her, zu „in einer Woche“ „in acht Tagen“ zu sagen, obwohl jeder weiß, dass eine Woche sieben Tage hat. Der aktuelle Wochentag wird bei der Inklusivzählung mitgezählt:
Wochentag: Montag Dienstag Mittwoch Donnerstag Freitag Samstag Sonntag Montag „Nummer“ des Tages: 1 2 3 4 5 6 7 8
Ein anderes Beispiel für die Inklusivzählung sind die Namen der musikalischen Intervalle:
Distanz zweier Töne: 0 1 2 3 4 5 6 7 Name des Intervalls: Prime Sekunde Terz Quarte Quinte Sexte Septime Oktave Kommt von lat. Zahl: 1 2 3 4 5 6 7 8
Dass der in der Musik übliche Name jedes Intervalls um 1 zu groß ist, sieht man unter anderem bei der Addition von Intervallen. Eine Quarte und eine Quinte ergeben zusammen eine Oktave. Aber 4 + 5 ist nicht 8 – vielmehr ist 3 + 4 = 7.
[Bearbeiten] Zählung von Jahrestagen
Jahrestage (z.B. Geburtstage) feiern die Vollendung und nicht den Beginn der angegebenen Jahre. Ein Mensch, der seinen 18. Geburtstag feiert, beginnt deshalb nicht an diesem Tag sein 18. Lebensjahr – vielmehr hat er schon volle 18 Jahre gelebt und beginnt sein 19. Lebensjahr.
Der Tag der Geburt eines Menschen ist also sozusagen sein "0. Geburtstag", ähnlich wie die Markierung 0 auf einem Zentimetermaß.
Geburtstag: Geburt 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
Lebensjahr: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
[Bearbeiten] Das Wort "bis"
Das Wort "bis" lässt unklar, ob der angegebene Grenzwert eingeschlossen ist oder nicht. Sagt beispielsweise ein Lehrer zu seinen Schülern „Lest bitte das Buch bis Seite 34“, kann es für Außenstehende unklar sein, ob Seite 33 zu Ende gelesen und Seite 34 erreicht werden soll (kleiner-als-Operator; <) oder ob Seite 34 vollendet werden soll (kleiner-gleich-Operator; <=).
Abhilfe schaffen hier die Formulierungen „bis einschließlich“ bzw. „bis ausschließlich“ oder (im bairischen Sprachraum) bei vergleichbaren Wochentagsproblemen die regional übliche Formulierung „mit“ („geschlossen Dienstag mit Donnerstag“).
[Bearbeiten] Stockwerke
In Deutschland ist der 1. Stock das erste aufgestockte Geschoss, im Gegensatz zum Erdgeschoss. In vielen Kulturen hat jedoch das Erdgeschoss die Nummer 1. Auch hier kommt es zum Zaunpfahlproblem: Stockwerk 3 oder drei Treppen hoch? Wenn in Deutschland statt Stockwerken Ebenen durchnummeriert werden, dann wird oft im Erdgeschoss mit dem Zählen bei 1 angefangen.
[Bearbeiten] Finden der Mitte
Problem:
0 1 2 3 4 5 6 7 8 9 10
^Mitte
1 2 3 4 5 6 7 8 9 10
^Mitte
Ziffern beschreiben einerseits ganze Abstände (Ordinalzahlen) und andererseits reelle Zahlen. Die obere Reihe beschreibt die reellen Zahlen und die untere Reihe die ganzen Abstände. Beides kann man nicht als ein und dasselbe bezeichnen. Bei korrekter Zuordnung der Zahlenbedeutung entsteht in keiner der Reihen ein Problem. Das wird in der folgenden Reihe weiter verdeutlicht. In dieser werden die reellen Werte mit | gekennzeichnet und die Zwischenräume stellen ganze Abstände dar.
| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10|
^Mitte
Mit diesem Beispiel wird gezeigt, dass die Mitte zwischen dem Anfang des ersten Abschnitts und dem Ende des zehnten genau bei dem reellen Wert 5 liegt, der sich seinerseits am Ende des 5. Abschnitts befindet. Vor der Mitte sind 5 Abschnitte und nach der Mitte ebenfalls, und das, obwohl die zweite Hälfte mit dem 6. Abschnitt beginnt. Zudem zeigt diese Anordnung sehr schön, warum die Zahl 10 eine gerade Zahl ist, und warum das Ergebnis der Halbierung der 10 eine ganze Zahl ergibt. Das Problem mit dem Finden der Mitte erübrigt sich demnach, wenn einer Zahl eine konkrete Länge zugeordnet wird. Definition: Eine Zahl ist durch Zwei teilbar, wenn die Mitte der Gesamtlänge, die sie definiert, genau auf das Ende eines Abschnitts fällt.
[Bearbeiten] Trivia
"Bei drei oder auf drei?" ist ein berühmtes Zitat aus der Lethal-Weapon-Reihe. Hier ist das Problem, ob man die gemeinsam geplante, überraschende Aktion beginnen soll, nachdem man bis drei gezählt hat oder genau dann, wenn man drei sagt.
