Lucas number/fi
│
English (en) │
suomi (fi) │
français (fr) │
Lucasin luvut on numerosarja:
2, 1, 3, 4, 7, 11, 18, 29, 47, …
Ajatuksena on lisätä kaksi viimeistä numeroa yhteen, jolloin saadaan seuraava arvo.
Luonti
Rekursiivinen toteutus
type
/// domain for Lucas number function
/// where result fits within a nativeUInt
// You can not name it lucasDomain,
// since the Lucas number function itself
// is defined for all whole numbers
// but the result beyond L(n) exceeds high(nativeUInt).
lucasLeftInverseRange =
{$ifdef CPU64} 0..92 {$else} 0..46 {$endif};
{**
calculates Lucas number recursively
\param n the index of the Lucas number to calculate
\return the Lucas number at n,
unless n is out of range, then 0
}
function lucas(const n: lucasLeftInverseRange): nativeUInt;
begin
case n of
// recursive case
2..high(n):
begin
lucas := lucas(n - 2) + lucas(n - 1);
end;
// base cases
1:
begin
lucas := 1;
end;
0:
begin
lucas := 2;
end;
// abort case
otherwise
begin
// neutral element of addition
// indicating n is out of range
// [there is no n satisfying L(n) = 0]
lucas := 0;
end;
end;
end;
Hyödyntäen Fibonacin sarjaa
Lucas-numerot voidaan laskea käyttämällä fibonacci funktiota joka oli esillä Fibonacin luvuissa.
{**
calculates Lucas number based on Fibonacci numbers
\param n the index of the Lucas number to calculate
\return the Lucas number at n,
unless n is out of range, then 0
}
function lucas(const n: lucasLeftInverseRange): nativeUInt;
begin
case n of
1..high(n):
begin
lucas := fibonacci(n - 1) + fibonacci(n + 1);
end;
0:
begin
// We can not deduce L(0) from Fibonacci
// since that function is not defined for negative n
// [we would call fibonacci(-1) + fibonacci(1)].
lucas := 2;
end;
otherwise
begin
// neutral element of addition
// indicating n is out of range
// [there is no n satisfying L(n) = 0]
lucas := 0;
end;
end;
end;
Iteratiivinen toteutus
Tämä on samanlainen kuin Fibonacin iteratiivisen toteutuksen kanssa, mutta erilaisilla lähtöarvoilla. Siksi koodia ei toisteta tässä.
Huomioita
Lucas-numeroiden laskeminen aina, kun niitä tarvitaan, on aikaa vievä. Vaikka tarvittava koodi ei vie lähes mitään tilaa, hakutaulukko on valintaväline, kun sovellus tarvitsee niitä usein. Koska Lucas-luvut voidaan saada Fibonacci-numeroista, yleensä vain yksi taulukko (Fibonacci-sarja) on kompromissi tehokkuuden ja muistin käytön välillä. Fibonacci-taulukon käyttämiseksi ilman marginaalikäsittelyä se on ainakin laajennettava fibonaksiin [-1]. Esimerkiksi GNU-monitarkkuuden aritmeettisen kirjaston (GNU multiple precision arithmetic library) Lucas-numerotoiminnot käyttävät tätä lähestymistapaa..
