Sign in Join
Wiki copytemporary

Lucas number/fi: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: Lucas number/fi

OldNewLine
1+Lucasin luvut on numerosarja:
2+
3+``` pascal
4+2, 1, 3, 4, 7, 11, 18, 29, 47, …
5+```
6+
7+Ajatuksena on lisätä kaksi viimeistä numeroa yhteen, jolloin saadaan seuraava arvo.
8+
9+## Luonti
10+
11+### Rekursiivinen toteutus
12+
13+``` pascal
14+type
15+ /// domain for Lucas number function
16+ /// where result fits within a nativeUInt
17+ // You can not name it lucasDomain,
18+ // since the Lucas number function itself
19+ // is defined for all whole numbers
20+ // but the result beyond L(n) exceeds high(nativeUInt).
21+ lucasLeftInverseRange =
22+ {$ifdef CPU64} 0..92 {$else} 0..46 {$endif};
23+
24+{**
25+ calculates Lucas number recursively
26+
27+ \param n the index of the Lucas number to calculate
28+ \return the Lucas number at n,
29+ unless n is out of range, then 0
30+}
31+function lucas(const n: lucasLeftInverseRange): nativeUInt;
32+begin
33+ case n of
34+ // recursive case
35+ 2..high(n):
36+ begin
37+ lucas := lucas(n - 2) + lucas(n - 1);
38+ end;
39+ // base cases
40+ 1:
41+ begin
42+ lucas := 1;
43+ end;
44+ 0:
45+ begin
46+ lucas := 2;
47+ end;
48+ // abort case
49+ otherwise
50+ begin
51+ // neutral element of addition
52+ // indicating n is out of range
53+ // [there is no n satisfying L(n) = 0]
54+ lucas := 0;
55+ end;
56+ end;
57+end;
58+```
59+
60+### Hyödyntäen Fibonacin sarjaa
61+
62+Lucas-numerot voidaan laskea käyttämällä `fibonacci` [[Function/fi|funktiota]] joka oli esillä [[Fibonacci number/fi|Fibonacin luvuissa]].
63+
64+``` pascal
65+{**
66+ calculates Lucas number based on Fibonacci numbers
67+
68+ \param n the index of the Lucas number to calculate
69+ \return the Lucas number at n,
70+ unless n is out of range, then 0
71+}
72+function lucas(const n: lucasLeftInverseRange): nativeUInt;
73+begin
74+ case n of
75+ 1..high(n):
76+ begin
77+ lucas := fibonacci(n - 1) + fibonacci(n + 1);
78+ end;
79+ 0:
80+ begin
81+ // We can not deduce L(0) from Fibonacci
82+ // since that function is not defined for negative n
83+ // [we would call fibonacci(-1) + fibonacci(1)].
84+ lucas := 2;
85+ end;
86+ otherwise
87+ begin
88+ // neutral element of addition
89+ // indicating n is out of range
90+ // [there is no n satisfying L(n) = 0]
91+ lucas := 0;
92+ end;
93+ end;
94+end;
95+```
96+
97+### Iteratiivinen toteutus
98+
99+Tämä on samanlainen kuin Fibonacin iteratiivisen toteutuksen kanssa, mutta erilaisilla lähtöarvoilla. Siksi koodia ei toisteta tässä.
100+
101+## Huomioita
102+
103+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 [[gmp|GNU-monitarkkuuden aritmeettisen kirjaston (GNU multiple precision arithmetic library)]] Lucas-numerotoiminnot käyttävät tätä lähestymistapaa..
104+
105+## Katso myös
106+
107+- [Lucas numbers in “the on-line encyclopedia of integer sequences”](https://oeis.org/A000032)
108+- [Lucas sequence § “Pascal” on RosettaCode.org](https://rosettacode.org/wiki/Lucas_sequence#Pascal)
109+- [[gmp|GNU multiple precision arithmetic library]]'s functions [`mpz_lucnum_ui` and `mpz_lucnum2_ui`](https://gmplib.org/manual/Lucas-Numbers-Algorithm.html#Lucas-Numbers-Algorithm)
110+
111+---
112+*From the Free Pascal wiki, page "Lucas number/fi", as it stood on 2022-08-06 after a change by Kai Burghardt, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).*

Back to history