Zaunpfahlproblem

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Lattenzaunproblem)
Wechseln zu: Navigation, Suche

Der Begriff Zaunpfahlproblem beschreibt ein Logik­problem der Indexierung. Ein Zaunpfahlproblem tritt immer dort auf, wo Unklarheit herrscht, ob eine Zahlenangabe einen Raum oder einen Punkt darstellt, beziehungsweise ob eine Distanz eines, beide oder keines der Endelemente einschließt. Ein Zaunpfahlfehler[1] (englisch fencepost error)[2] [3] ist ein Spezialfall eines Off-by-one-Errors. Der Begriff Zaunpfahlfehler stammt aus der Informatik, wo man häufig mit dieser Art Fehler zu tun hat. Verwandte Probleme gibt es jedoch bereits seit Jahrtausenden und in allen Lebensbereichen.

Herkunft des Begriffs[Bearbeiten]

Illustration des Zaunpfahlproblems

Der Begriff „Zaunpfahlproblem“ bezieht sich auf das Errichten eines Zaunes. Ein Zaun besteht klassischerweise aus senkrechten Pfählen in festem Abstand. Zwischen ihnen werden die Zaunsegmente angebracht. Man benötigt dabei einen Pfahl mehr als Segmente. Die Länge des Zaunes ist somit nicht der Pfahlabstand mal der Anzahl Pfähle, sondern der Pfahlabstand mal der (Anzahl Pfähle minus Eins). Wenn man zum Beispiel 11 Pfähle im Abstand von 3 m zueinander aufstellt, erhält man einen 30 m langen Zaun.

Distanz vs. Anzahl[Bearbeiten]

Der Kern des Zaunpfahlproblems liegt im Unterschied zwischen Distanzen und Anzahlen. Distanzen entsprechen die Zaunsegmente, Anzahlen entsprechen die Zaunpfähle.

Hat man eine Folge von durchnummerierten Objekten, so beschreibt die Differenz der Zahlwerte zweier Objekte die Anzahl Zwischenräume zwischen diesen, und damit deren Abstand (Distanz). Will man hingegen die Anzahl Objekte einschließlich beider Endpunkte wissen, so muss man zur Differenz 1 addieren. Will man die Anzahl dazwischenliegender Objekte ohne die beiden Endpunkte wissen, so muss man von der Differenz noch 1 subtrahieren.

Betrachtet man zum Beispiel den Bereich, der durch Element 20 bis Element 30 in einer aufsteigenden Folge definiert ist, so ist:

  • der Abstand zwischen den Elementen (die Differenz): 30 − 20 = 10. Dies ist auch die Anzahl Elemente einschließlich 20, aber ohne 30, sowie die Anzahl Elemente einschließlich 30, aber ohne 20.
  • die Anzahl Elemente einschließlich beider Endpunkte („Inklusivzählung“): 30 − 20 + 1 = 11
  • die Anzahl Elemente zwischen den Endpunkten, ohne beide Endpunkte: 30 − 20 − 1 = 9

Aus diesem Grund muss man beim Abmessen von Distanzen mit dem Startpunkt als 0 zu zählen beginnen, weil dadurch der Zahlwert des Endpunkts dem Abstand zum Nullpunkt entspricht. Beim Abzählen von Objekten (z. B. Pfählen) muss man hingegen mit dem Startobjekt als 1 zu zählen beginnen, weil dadurch der Zahlwert des Endobjekts der Anzahl aller gezählter Objekte entspricht. Beide Zählweisen sind korrekt und haben ihre Anwendungen, aber es kann leicht vorkommen, dass sie verwechselt werden.

Informatik[Bearbeiten]

In der Informatik findet der Begriff des Zaunpfahlproblems am häufigsten Verwendung. Diese Zaunpfahlprobleme gehören zwei Hauptgruppen an:

  1. Verwechslung von Distanzen und Anzahlen. 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.
  2. 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 standardmäßig bei 0, denn der Index in einem Array gibt dort eine Distanz (einen Offset) zur Startadresse des Arrays an, und das erste Element beginnt unmittelbar an der Startadresse, hat also den Offset 0. So haben in C oder Java die Elemente eines Arrays der Länge 5 die Indizes 0, 1, 2, 3 und 4. Ein typischer Anfängerfehler ist es, in Schleifen den Index bis zur Länge des Arrays (5) laufen zu lassen – was einen Adressierungsfehler erzeugt – anstatt bis zur Länge des Arrays minus 1.

Verwandte Probleme[Bearbeiten]

Die historische Inklusivzählung[Bearbeiten]

Distanzen und Zeit­rä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 Endelement 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 nach heutiger mathematischer Konvention. 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.

Eines der frühesten Beispiele für einen Zaunpfahlfehler geschah bei der Kalenderreform des Gaius Iulius Caesar. Caesar hatte die Schaltung in jedem vierten Jahr angeordnet, die Priester verstanden dies jedoch nach der Inklusivzählung als eine Schaltung alle drei Jahre.

Von der Inklusivzählung rührt zum Beispiel der Brauch her, zu „in einer Woche“ neben „in sieben Tagen“ auch „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.

Zeitrechnung[Bearbeiten]

Jahr null[Bearbeiten]

Die christliche Zeitrechnung kennt kein Jahr null, sondern geht vom Jahr 1 v. Chr. direkt ins Jahr 1 n. Chr. über. In der astronomischen Zeitrechnung wird dagegen das Jahr 1 v. Chr. als Jahr null gerechnet.

Christliches Jahr: 2 v. Chr. 1 v. Chr. 1 n. Chr. 2 n. Chr.
Astronomisches Jahr: -1 0 1 2

Jahrhunderte[Bearbeiten]

Das bekannte Logo des Filmstudios 20th Century Fox. Auch im Englischen bezeichnet 20th century das Jahrhundert von 1901 bis 2000.

Es gab kein „nulltes Jahrhundert“. Das 1. Jahrhundert dauerte vom 1. Januar 1 n. Chr. bis zum 31. Dezember 100 n. Chr. Ein Jahrhundert umfasst immer die hundert Jahre, die mit dem entsprechenden vollen Jahr enden. Entsprechend wird der Zeitraum vom 1. Januar 1901 bis zum 31. Dezember 2000 als das 20. Jahrhundert bezeichnet, und das 21. Jahrhundert begann am 1. Januar 2001.

Im Italienischen werden neben der normalen Bezeichnung der Jahrhunderte („XX secolo“) auch umgangssprachlich die Jahrhunderte so benannt, dass „Novecento“ (wörtlich: neunhundert) den Zeitraum von 1900 bis 1999 bezeichnet. Dies ist jedoch nur für Jahrhunderte ab dem Jahr 1100 möglich. Im Englischen gibt es in ähnlicher Weise die Möglichkeit, mit „1900s“ (gesprochen nineteen-hundreds) den Zeitraum 1900–1999 zu bezeichnen. Bei der letzten Jahrtausendwende feierten auch viele im deutschsprachigen Raum den Jahrtausendwechsel bereits 1999/2000 anstatt 2000/2001.

Jahrestage[Bearbeiten]

Jahrestage (zum Beispiel 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

In einigen Kulturkreisen (z. B. China) ist das hingegen anders: der Tag der Geburt ist der „1. Geburtstag“.

Bei Ereignissen, die regelmäßig einmal jährlich stattfinden, sind eine runde Jubiläumsausgabe und das entsprechend alte Jubiläum des Beginns der Veranstaltungs- oder Ausgabeserie (der ersten Ausgabe) um ein Jahr voneinander entfernt, was oft zu Unklarheiten führt. So wurde 1955 das erste Guinness-Buch der Rekorde ausgegeben, 1956 der erste Eurovision Song Contest abgehalten. Zum 60. Eurovision Song Contest im Jahr 2015 wurde berichtet, das Guinness-Buch der Rekorde feiere ebenfalls seinen 60. Geburtstag, die beiden seien also genau gleich alt.[4]

Finden der Mitte[Bearbeiten]

Wird beim Zählen mit 1 begonnen, dann entspricht die Mitte nicht der Hälfte der Anzahl der Elemente. Zum Beispiel sei eine Skala von 1 bis 10 gegeben. Die 5 liegt hierbei nicht in der Mitte der Skala, sondern darunter. Die tatsächliche Mitte liegt bei 5,5:

1 2 3 4 5 6 7 8 9 10
         ^Mitte

Auch Folgendes mag zunächst unintuitiv erscheinen oder „überraschen“: Von fünf Elementen, nummeriert 1 2 3 4 5, ist das mittlere Element das mit der Nummer 3 – obwohl die Hälfte von 5 bekanntlich 2½ ist.

Bei einer Skala von 0 bis 10 hingegen hat man 11 Indizes und die Mitte liegt bei 5:

0 1 2 3 4 5 6 7 8 9 10
          ^Mitte

Der Grund hierfür ist der gleiche wie beim oben beschriebenen Zaunpfahlproblem. Die obere Skala hat die Indizes 1 bis 10. Diese werden als Punkte betrachtet. Damit beschreibt die Skala jedoch nur eine Länge (Strecke, Distanz zwischen Anfang und Ende) von 9, denn 10 – 1 = 9. Ihre Mitte liegt daher bei der Hälfte von 9, gerechnet ab dem Index 1: 1 + (9 / 2) = 5,5.

Die untere Skala mit den Indizes 0 bis 10 hingegen beschreibt eine Länge von 10 und ihre Mitte liegt bei 0 + (10 / 2) = 5.

Stockwerke[Bearbeiten]

Im deutschen Sprachraum 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.

Bei drei oder auf drei und dann?[Bearbeiten]

„Bei drei oder auf drei und dann?“ ist ein berühmtes Zitat aus der Actionfilm-Reihe Lethal Weapon. 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.

Einzelnachweise[Bearbeiten]

  1.  Jesse Liberty, David Horvath: Jetzt lerne ich C+: das komplette Starterkit für den einfachen Einstieg in die Programmierung ; [Start ohne Vorwissen]. Pearson Deutschland, 2004, ISBN 978-3-8272-6830-3, S. 290 (books.google.com).
  2.  Andrew Koenig: C Traps and Pitfalls. Pearson Education, 1988, ISBN 978-81-7758-139-3, S. Section 3.6 (books.google.com).
  3.  Steve Heller: C++: a Dialogue: Programming with the C++ Standard Library. Prentice Hall Professional, 2003, ISBN 978-0-13-009402-5, S. 353ff (books.google.com).
  4. Eurovision Song Contest hält nun Guinness-Weltrekord. oe3.orf.at, 2015, zuletzt abgerufen 18. Jänner 2016. „Guinness World Records ist die weltweit anerkannte Institution zur Überprüfung und Beglaubigung von Weltrekorden und feiert dieses Jahr, genau wie der Eurovision Song Contest, sein 60. Jubiläum“