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

Katso myös

• Lucas numbers in “the on-line encyclopedia of integer sequences”
• Lucas sequence § “Pascal” on RosettaCode.org
• GNU multiple precision arithmetic library's functions mpz_lucnum_ui and mpz_lucnum2_ui