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
3type
4 /// domain for Lucas number function
5 /// where result fits within a nativeUInt
6 // You can not name it lucasDomain,
7 // since the Lucas number function itself
8 // is defined for all whole numbers
9 // but the result beyond L(n) exceeds high(nativeUInt).
10 lucasLeftInverseRange =
11 {$ifdef CPU64} 0..92 {$else} 0..46 {$endif};
12
13{**
14 calculates Lucas number recursively
15
16 \param n the index of the Lucas number to calculate
17 \return the Lucas number at n,
18 unless n is out of range, then 0
19}
20function lucas(const n: lucasLeftInverseRange): nativeUInt;
21begin
22 case n of
23 // recursive case
24 2..high(n):
25 begin
26 lucas := lucas(n - 2) + lucas(n - 1);
27 end;
28 // base cases
29 1:
30 begin
31 lucas := 1;
32 end;
33 0:
34 begin
35 lucas := 2;
36 end;
37 // abort case
38 otherwise
39 begin
40 // neutral element of addition
41 // indicating n is out of range
42 // [there is no n satisfying L(n) = 0]
43 lucas := 0;
44 end;
45 end;
46end;
Hyödyntäen Fibonacin sarjaa
Lucas-numerot voidaan laskea käyttämällä fibonacci funktiota joka oli esillä Fibonacin luvuissa.
54{**
55 calculates Lucas number based on Fibonacci numbers
56
57 \param n the index of the Lucas number to calculate
58 \return the Lucas number at n,
59 unless n is out of range, then 0
60}
61function lucas(const n: lucasLeftInverseRange): nativeUInt;
62begin
63 case n of
64 1..high(n):
65 begin
66 lucas := fibonacci(n - 1) + fibonacci(n + 1);
67 end;
68 0:
69 begin
70 // We can not deduce L(0) from Fibonacci
71 // since that function is not defined for negative n
72 // [we would call fibonacci(-1) + fibonacci(1)].
73 lucas := 2;
74 end;
75 otherwise
76 begin
77 // neutral element of addition
78 // indicating n is out of range
79 // [there is no n satisfying L(n) = 0]
80 lucas := 0;
81 end;
82 end;
83end;
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..
