Zaunpfahlproblem

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.

Problematik

Zaunpfahlprobleme können auftreten, wenn

• es einen Index mehr als Elemente gibt, da die Elemente „zwischen“ den Indizes liegen. 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.

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, da einmal mit 0 und einmal mit 1 zu zählen begonnen wird.

Beispiel:

Index           0   1   2   3   4
Element         1   2   3   4   5

Beispiel

Frage: Wenn man einen 10 m langen geraden Zaun errichten will und die Zaunpfähle 1 m auseinander stehen sollen, wie viele Pfähle braucht man dafür?

Antwort: Viele würden fälschlicherweise 10 durch 1 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.

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:

1. 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.
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 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 Off-by-one-Error 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

Verwandte Probleme

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 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.

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

Jahr null

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

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.

In Italien wird allerdings das Jahrhundert gleichlautend mit der Jahreszahl benannt.

Jahrestage

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

Finden der Mitte

Wird beim Zählen mit 1 begonnen, dann entspricht die Mitte nicht der Hälfte der Anzahl 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 zu „ü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

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?

„Bei drei oder auf drei?“ 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.