134 lines
6.3 KiB
Markdown
134 lines
6.3 KiB
Markdown
---
|
||
id: 598eef80ba501f1268170e1e
|
||
title: Послідовність n-крокових чисел Фібоначчі
|
||
challengeType: 5
|
||
forumTopicId: 302267
|
||
dashedName: fibonacci-n-step-number-sequences
|
||
---
|
||
|
||
# --description--
|
||
|
||
Ця серія чисел є розширенням звичайної [послідовності Фібоначчі](https://rosettacode.org/wiki/Fibonacci sequence "Fibonacci sequence") де:
|
||
|
||
<ol>
|
||
<li>Для $n = 2$ ми маємо послідовність Фібоначчі; з початковими значеннями $[1, 1]$ і $F_k^2 = F_{k-1}^2 + F_{k-2}^2$</li>
|
||
<li>Для $n = 3$ ми маємо послідовність трібоначчі; з початковими значеннями $[1, 2]$ і $F_k^3 = F_{k-1}^3 + F_{k-2}^3 + F_{k-3}^3$</li>
|
||
<li>Для $n = 4$ маємо послідовність тетраначчі; з початковими значеннями $[1, 2, 4]$ та $F_k^4 = F_{k-1}^4 + F_{k-2}^4 + F_{k-3}^4 + F_{k-4}^4$...</li>
|
||
<li>Для загального $n>2$ ми маємо послідовність Фібоначчі $n$-крокову - $F_k^n$; з початковими значеннями з перших $n$ значень $(n-1)$'th $n$-крокової послідовності Фібоначчі $F_k^{n-1}$; і $k$'th значення цієї $n$'ої послідовності - $F_k^n = \sum_{i=1}^{(n)} {F_{k-i}^{(n)}$</li>
|
||
</ol>
|
||
|
||
Для невеликих значень $n$, <ahref="https://en.wikipe[іноді використовують грецькі числівникові префікси](https://en.wikipedia.org/wiki/Number prefix#Greek_series "wp: Number prefix#Greek_series") щоб індивідуально дати назву кожній послідовності.
|
||
|
||
Послідовність $n$- крокових чисел Фібоначчі:
|
||
|
||
| $n$ | Назва послідовності | Значення |
|
||
| --- | ------------------- | ------------------------------------------------------ |
|
||
| 2 | фібоначчі | 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... |
|
||
| 3 | трібоначчі | 1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 ... |
|
||
| 4 | тетрабоначчі | 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872 5536 ... |
|
||
| 5 | пентаначчі | 1 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 ... |
|
||
| 6 | гексаначчі | 1 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 ... |
|
||
| 7 | гептаначчі | 1 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 ... |
|
||
| 8 | октоначчі | 1 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 ... |
|
||
| 9 | нонаначчі | 1 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 ... |
|
||
| 10 | деканаччі | 1 1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 ... |
|
||
|
||
Союзні послідовності можна створити там, де початкові значення змінюються: [Послідовність Люка](https://en.wikipedia.org/wiki/Lucas number "wp: Lucas number") сумує два попередніх значення, так само як серія Фібоначчі для $n= 2$, але використовує рядок $\[2, 1]$ як початкові значення.
|
||
|
||
# --instructions--
|
||
|
||
Напишіть функцію для створення послідовностей $n$-крокових чисел Фібоначчі та послідовностей Люка. Перший параметр буде $n$. Другий параметр - це кількість елементів, які будуть повернені. Третій параметр визначає чи виводити послідовність Фібоначчі чи послідовність Лукаса. Якщо параметр є `"f"`, то поверніть послідовність Фібоначчі і якщо він `"l"`, то поверніть послідовність Лукаса. Послідовності необхідно повернути у вигляді масиву.
|
||
|
||
# --hints--
|
||
|
||
`fib_luc` має бути функцією.
|
||
|
||
```js
|
||
assert(typeof fib_luc === 'function');
|
||
```
|
||
|
||
`fib_luc(2,10,"f")` має повернути `[1,1,2,3,5,8,13,21,34,55]`.
|
||
|
||
```js
|
||
assert.deepEqual(fib_luc(2, 10, 'f'), ans[0]);
|
||
```
|
||
|
||
`fib_luc(3,15,"f")` має повернути `[1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136]`.
|
||
|
||
```js
|
||
assert.deepEqual(fib_luc(3, 15, 'f'), ans[1]);
|
||
```
|
||
|
||
`fib_luc(4,15,"f")` має повернути `[1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536]`.
|
||
|
||
```js
|
||
assert.deepEqual(fib_luc(4, 15, 'f'), ans[2]);
|
||
```
|
||
|
||
`fib_luc(2,10,"l")` має повернути `[ 2, 1, 3, 4, 7, 11, 18, 29, 47, 76]`.
|
||
|
||
```js
|
||
assert.deepEqual(fib_luc(2, 10, 'l'), ans[3]);
|
||
```
|
||
|
||
`fib_luc(3,15,"l")` має повернути `[ 2, 1, 3, 6, 10, 19, 35, 64, 118, 217, 399, 734, 1350, 2483, 4567 ]`.
|
||
|
||
```js
|
||
assert.deepEqual(fib_luc(3, 15, 'l'), ans[4]);
|
||
```
|
||
|
||
`fib_luc(4,15,"l")` має повернути `[ 2, 1, 3, 6, 12, 22, 43, 83, 160, 308, 594, 1145, 2207, 4254, 8200 ]`.
|
||
|
||
```js
|
||
assert.deepEqual(fib_luc(4, 15, 'l'), ans[5]);
|
||
```
|
||
|
||
`fib_luc(5,15,"l")` має повернути `[ 2, 1, 3, 6, 12, 24, 46, 91, 179, 352, 692, 1360, 2674, 5257, 10335 ]`.
|
||
|
||
```js
|
||
assert.deepEqual(fib_luc(5, 15, 'l'), ans[6]);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --after-user-code--
|
||
|
||
```js
|
||
const ans = [[1,1,2,3,5,8,13,21,34,55],
|
||
[1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136],
|
||
[1,1,2,4,8,15,29,56,108,208,401,773,1490,2872,5536],
|
||
[ 2, 1, 3, 4, 7, 11, 18, 29, 47, 76],
|
||
[ 2, 1, 3, 6, 10, 19, 35, 64, 118, 217, 399, 734, 1350, 2483, 4567 ],
|
||
[ 2, 1, 3, 6, 12, 22, 43, 83, 160, 308, 594, 1145, 2207, 4254, 8200 ],
|
||
[ 2, 1, 3, 6, 12, 24, 46, 91, 179, 352, 692, 1360, 2674, 5257, 10335 ]];
|
||
```
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function fib_luc(n, len, w) {
|
||
|
||
}
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
function fib_luc(n, len, w) {
|
||
function nacci(a, n, len) {
|
||
while (a.length < len) {
|
||
let sum = 0;
|
||
for (let i = Math.max(0, a.length - n); i < a.length; i++)
|
||
sum += a[i];
|
||
a.push(sum);
|
||
}
|
||
return a;
|
||
}
|
||
if(w=="f"){
|
||
return nacci(nacci([1,1], n, n), n, len);
|
||
}else{
|
||
return nacci(nacci([2,1], n, n), n, len);
|
||
}
|
||
}
|
||
```
|