為什么很多編程語言要把 0 作為第一個下標索引,而不是直觀的 1 呢?
這個問題 Dijkstra 已經解答過了,沒錯,就是你知道的 Dijkstra,Dijkstra 最短路徑算法,荷蘭語全名是 Edsger Wybe Dijkstra
,于 1972 年獲得了圖靈獎,除了上面說的最短路徑算法,還有眾所周知的信號量和 PV 原語、銀行家算法等也是這位巨佬提出的。
原文在這里:https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html
首先來看個案例
如何用一個不等式(或者說表達式)來表示[2,3,4,5,6,7,8,9,10,11,12]
這個連續的整數序列(一共 11 個數)?
假設i
是一個整數,那么我們能夠迅速地寫出如下四個符合上述連續序列的不等式:
1)2 <= i < 13
(不等式1)
2)1 < i <= 12
(不等式2)
3)2 <= i <= 12
(不等式3)
4)1 < i < 13
(不等式4)
以上四個不等式均滿足要求,那是否有理由選擇其中的一種而不是另一種?
Dijkstra 說有理由的,選 1 和 2,因為這倆不等式有個很突出的優點,就是不等式邊界的差(不等式右邊 - 不等式左邊)正好等于連續序列的長度。
這里可以排除掉 3 和 4,那么 1 和 2 該如何選出最優的表示?
1 和 2 不等式的區別
-
1 不等式左邊(下界)等于序列中的最小值,不等式右邊(上界)大于序列中的最大值
-
2 不等式左邊(下界)小于序列中的最小值,不等式右邊(上界)等于序列中的最大值
對于第 2 個不等式來說,下界小于序列中的最小值,這會出現一個問題,比如我們的連續序列是 [0,1,2,3,4]
那么按照第 2 個不等式的寫法,不等式的左邊就是 -1,-1
是非自然數,而我們需要表示的連續序列是自然數序列,所以第 2 個不等式很不優雅:我們需要用一個 非自然數
來作為 全是自然數的序列
的下界。
因此,綜上所述,不等式 1 是最優雅的選擇。
那么,選出一個看著非常順眼的不等式來表達長度為 N 的連續序列之后,下一個令人煩惱的問題是該為起始元素分配什么下標值?
遵循不等式 1 的規則:
當從下標 1 開始時,下標范圍 1 ≤ i < N+1
當從下標 0 開始時,下標范圍 0 ≤ i < N
哪個更優雅?
Dijkstra 是這樣解釋的:從下標 0 開始能夠給出更好的不等式,因為元素的下標就等于序列中它前面的元素數(或者說 “偏移量”)。