Files

113 lines
3.5 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

---
id: 5a23c84252665b21eecc8028
title: Послідовність Штерна-Броко
challengeType: 5
forumTopicId: 302324
dashedName: stern-brocot-sequence
---
# --description--
Для цього завдання потрібно згенерувати послідовність Штерна-Броко, скориставшись таким самим алгоритмом, як і для генерування [послідовності Фібоначчі](https://rosettacode.org/wiki/Fibonacci sequence).
<ol>
<li>Перший та другий члени послідовності дорівнюють 1:</li>
<ul><li>1, 1</li></ul>
<li>Розпочніть із аналізування другого члена послідовності</li>
<li>Додайте аналізований член послідовності до попереднього, (1+1) = 2 та приєднайте його до кінця послідовності:</li>
<ul><li>1, 1, 2</li></ul>
<li>Приєднайте аналізований член послідовності до кінця даної послідовності:</li>
<ul><li>1, 1, 2, 1</li></ul>
<li>Розглянемо наступний член серії (тобто, третій член - 2)</li>
<li>ДО 3 </li>
<ul>
<li></li>
<li> ── розгорнувши ще один цикл, ми отримуємо: ───</li>
<li></li>
</ul>
<li>Додайте між собою аналізований та попередній члени послідовності, (2 + 1) = 3, та приєднайте цю суму до кінця послідовності:</li>
<ul><li>1, 1, 2, 1, 3</li></ul>
<li>Приєднайте аналізований член до кінця цієї послідовності:</li>
<ul><li>1, 1, 2, 1, 3, 2</li></ul>
<li>Проаналізуйте наступний член серії (тобто четвертий член - 1)</li>
</ol>
# --instructions--
Створіть функцію, яка повертає позицію у послідовності Штерна-Броко, в якій $ n $ зустрічається вперше, де послідовність генерується методом, описаним вище. Зверніть увагу, що ця послідовність використовує індексацію на основі 1.
# --hints--
`sternBrocot` має бути функцією.
```js
assert(typeof sternBrocot == 'function');
```
`sternBrocot(2)` має повертати число.
```js
assert(typeof sternBrocot(2) == 'number');
```
`sternBrocot(2)` має повертати `3`.
```js
assert.equal(sternBrocot(2), 3);
```
`sternBrocot(3)` має повертати `5`.
```js
assert.equal(sternBrocot(3), 5);
```
`sternBrocot(5)` має повертати `11`.
```js
assert.equal(sternBrocot(5), 11);
```
`sternBrocot(7)` має повертати `19`.
```js
assert.equal(sternBrocot(7), 19);
```
`sternBrocot(10)` має повертати `39`.
```js
assert.equal(sternBrocot(10), 39);
```
# --seed--
## --seed-contents--
```js
function sternBrocot(num) {
}
```
# --solutions--
```js
function sternBrocot(num) {
function f(n) {
return n < 2
? n
: n & 1
? f(Math.floor(n / 2)) + f(Math.floor(n / 2 + 1))
: f(Math.floor(n / 2));
}
function gcd(a, b) {
return a ? (a < b ? gcd(b % a, a) : gcd(a % b, b)) : b;
}
var n;
for (n = 1; f(n) != num; n++);
return n;
}
```