Leonardotal
Leonardotal är en heltalsföljd som ges av återkommande:
Edsger W. Dijkstra[1] använde dem som en integrerad del av sin släthetssorterande algoritm,[2]
Beräkning av andra ordningens återkommande förhållande rekursivt och utan memoisation kräver L(n)-beräkningar för den n:te termen i serien.
De första Leonardotalen är:
Relation till Fibonaccital redigera
Leonardotal är relaterade till Fibonaccital av relationen .
Ur denna relation är det enkelt att härleda ett uttryck i sluten form för Leonardotal, analogt med Binets formel för Fibonaccital:
där det gyllene snittet och är rötterna till det kvadratiska polynomet .
Källor redigera
- Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Leonardo number, 22 december 2013.
- ^ EWD797
- ^ Dijkstra, Edsger W. Smoothsort an alternative to sorting in situ (EWD-796a). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. https://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD796a.html
Externa länkar redigera
- "Sloanes A001595 ", Nätuppslagsverket över heltalsföljder (OEIS) (engelska)