Привет, Сергей. Интересная классическая задача, очень важно уметь её решать как рекурсивно, так и итеративно, что собственно ты и показал. Могу добавить только то, что чтобы ускорить рекурсивный вариат можно сохранять в массиве промежуточные значения(мемоизация). Этот вариант называется динамическим программрование назад (или сверху вниз): const res = [0, 1]; function fibonacci(n) { if (!res[n]) { if (n
Да это тоже хороший вариант. Из его плюсов - скорость (хотя итеративный вариант в любом случае выиграет). Из минусов - на нем сложнее изначально объяснить рекурсию (можно еще больше запутать). Но сам принцип мемоизации нужно знать - так как есть задачи, которые решаются именно через рекурсию и их нужно ускорять и кешировать.
второй вариант, мне оказался понятным и удобно читаемый спасибо!) Ну ещё добавил проверку на 0; const n = 9; fibonachi(n); function fibonachi(n) { if (n === 0) { console.log(0) }else{ let a = 1; let b = 1; for (let i = 3; i
Спасибо за разбор. Вот мое решение function fibonacci(n){ let arr = [0,1] for(let i = 0; i < n-2; i++){ let a = arr[i] + arr[i+1]; arr.push(a) } return arr[n-1] } let res = fibonacci(50)
Моё решение и для отрицательных значений: const fibonacci = n => { if (!Number.isInteger(n)) return NaN; if (n === 0) return 0; let prev = 0, curr = 1; if (n > 0) { for(let i = 2; i n; i--) { [curr, prev] = [prev - curr, curr]; } } return curr; }; ...или вот тоже интересный вариант: const fibonacci = n => { if (!Number.isInteger(n)) return NaN; const sign = Math.sign(n); n = Math.abs(n); let even = 0, odd = 1; for (let i = 2; i
Классное видео и классный канал . Начал изучать программирование в 40 с нуля и сейчас подошёл к изучению алгоритмов и их написанию в js. Посоветуйте пожалуйста практикум по самым простым задачам в js( циклы , функции). Спасибо !
Благодарим за подержку! И за идею для видео. :) Если самый начальный уровень, то рекомендуем learn.javascript.ru/ - там есть задачи сразу с решением. Если чуть более продвинутый уровень, то лучше переходить на www.codewars.com/ - там очень много задач, от простых до мегасложных, а на форуме есть разные примеры этих задач. Успехов!
У меня 3 варианта решения: 1) Медленная рекурсия: function fibonacci(n) { return (n < 2) ? n : fibonacci(n - 1) + fibonacci(n - 2); } 2) Итеративный вариант: function fibonacci(n) { let a = 0; let b = 1; for (let i = 1; i < n; i++) { [a, b] = [b, a + b]; } return b; } 3) Быстрая рекурсия: function fibonacci(n, a = 0, b = 1) { return (n === 1) ? b : fibonacci(n - 1, b, a + b); }
Немного не поняла с циклом каким образом если i увеличивается на 1 при повторении цикла то после значения 1 следующие i будет равно 3 ,а это значит 1)3-1=2 2)3-2=1 и их сумма дает 3 таким образом следующие число фибоначчи равно 3 ,а не 2 как это должно быть ,что-то я запуталась
Там не само число вычисляется, а индекс элемента в массиве result[i - 1] - то-есть если сейчас i = 2, значит мы берем result[1] элемент - который у нас уже записан и равен числу 1
а почему на 6:05 получилось так что [a, b] = [b, a + b] разве тут не должно сначала произойти a = b, а потом уже получается что b + b т.к. "a" стала b.
10. Чему равно временная сложность рекурсивного алгоритма вычисления чисел Фибоначчи? 11. Чему равно временная сложность алгоритма вычисления чисел Фибоначчи c использованием переменных? Чему равно временная сложность алгоритма вычисления чисел Фибоначчи c использованием массива? Помогите пожалуйста
Временная сложность обычного рекурсивного алгоритма - экспоненциальная O(2^n). Временная сложность итеративного решения (вероятно который подразумевался под фразой "с использованием пременных") - линейная O(n). Временная сложность рекурсивного алгоритма с мемоизацией с использованием массива - линейная O(n).
с рекурсией чуть комп не завис пришлось перезапуск делать)...раз как то зацикливал систему даже перезапустить не получалось только отключить смог... интересно есть ли какая нибуть команда чтоб сразу отменить зациклившийся цикл???
Последовательность Фибоначчи так же используется в изобразительном искусстве для составления гармоничной композиции картины или фотоснимка - золотое сечение. Этот Фибоначчи явно что то знал :)
Прорешал всеми тремя методами (первоначально решил рекурсией). Заинтересовало сколько времени уходит на решение каждым методом, так как рекурсией число больше 40 вычислять уже долго. В итоге сделал следующее: function fibonachi(num) { if (num
Есть разные мнения что считать первым элементом последовательности. Некоторые считают с 0 а некоторые с 1. Так что тут каждый может подстроиться как ему нужно.
@@vty4261 Ну 1е и 3е решение - как раз пройду проверку на f(0) - а вот второй вариант действительно надо подправить начальные 2 числа и вывод результата чтобы он работал и с f(0) тоже.
А как эту задачу решили бы вы? Напишите ваш вариант в комментариях.
ещё можно мемоизацию добавить
видосы по алгоритмам - супер! большое спасибо!
Привет, Сергей. Интересная классическая задача, очень важно уметь её решать как рекурсивно, так и итеративно, что собственно ты и показал. Могу добавить только то, что чтобы ускорить рекурсивный вариат можно сохранять в массиве промежуточные значения(мемоизация). Этот вариант называется динамическим программрование назад (или сверху вниз):
const res = [0, 1];
function fibonacci(n) {
if (!res[n]) {
if (n
Да это тоже хороший вариант. Из его плюсов - скорость (хотя итеративный вариант в любом случае выиграет). Из минусов - на нем сложнее изначально объяснить рекурсию (можно еще больше запутать). Но сам принцип мемоизации нужно знать - так как есть задачи, которые решаются именно через рекурсию и их нужно ускорять и кешировать.
второй вариант, мне оказался понятным и удобно читаемый спасибо!) Ну ещё добавил проверку на 0;
const n = 9;
fibonachi(n);
function fibonachi(n) {
if (n === 0) {
console.log(0)
}else{
let a = 1;
let b = 1;
for (let i = 3; i
:) Благодарю за решение!
Спасиб)
Спасибо за разбор. Вот мое решение
function fibonacci(n){
let arr = [0,1]
for(let i = 0; i < n-2; i++){
let a = arr[i] + arr[i+1];
arr.push(a)
}
return arr[n-1]
}
let res = fibonacci(50)
Благодарю за решение! 👍
лучший канал! ЛАЙК ПОДПИСКА!
Благодарим за поддержку! Очень вдохновляет! ))
Моё решение и для отрицательных значений:
const fibonacci = n => {
if (!Number.isInteger(n)) return NaN;
if (n === 0) return 0;
let prev = 0, curr = 1;
if (n > 0) {
for(let i = 2; i n; i--) {
[curr, prev] = [prev - curr, curr];
}
}
return curr;
};
...или вот тоже интересный вариант:
const fibonacci = n => {
if (!Number.isInteger(n)) return NaN;
const sign = Math.sign(n);
n = Math.abs(n);
let even = 0, odd = 1;
for (let i = 2; i
Классное видео и классный канал . Начал изучать программирование в 40 с нуля и сейчас подошёл к изучению алгоритмов и их написанию в js. Посоветуйте пожалуйста практикум по самым простым задачам в js( циклы , функции). Спасибо !
Благодарим за подержку! И за идею для видео. :)
Если самый начальный уровень, то рекомендуем learn.javascript.ru/ - там есть задачи сразу с решением.
Если чуть более продвинутый уровень, то лучше переходить на www.codewars.com/ - там очень много задач, от простых до мегасложных, а на форуме есть разные примеры этих задач. Успехов!
@@frontendscience спасибо
Как успехи?
@@программистомв40помер, старпер?
const fibonacci = (num) => Array.from({ length: num - 1 }).reduce(({ first, second }) => ({ first: second, second: first + second }), { first: 0, second: 1 }).second
хороший вариант если не волноваться про память (при создании массива) :)
tool зачетные. Особенно первые два альбома
Ага, я их фанат :)
У меня 3 варианта решения:
1) Медленная рекурсия:
function fibonacci(n) {
return (n < 2) ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
2) Итеративный вариант:
function fibonacci(n) {
let a = 0;
let b = 1;
for (let i = 1; i < n; i++) {
[a, b] = [b, a + b];
}
return b;
}
3) Быстрая рекурсия:
function fibonacci(n, a = 0, b = 1) {
return (n === 1) ? b : fibonacci(n - 1, b, a + b);
}
Отличные варианты
Немного не поняла с циклом каким образом если i увеличивается на 1 при повторении цикла то после значения 1 следующие i будет равно 3 ,а это значит 1)3-1=2 2)3-2=1 и их сумма дает 3 таким образом следующие число фибоначчи равно 3 ,а не 2 как это должно быть ,что-то я запуталась
Там не само число вычисляется, а индекс элемента в массиве result[i - 1] - то-есть если сейчас i = 2, значит мы берем result[1] элемент - который у нас уже записан и равен числу 1
а почему на 6:05 получилось так что [a, b] = [b, a + b] разве тут не должно сначала произойти a = b, а потом уже получается что b + b т.к. "a" стала b.
Уже 3 час ломаю голову почему рекурсивное подсчитывание числа фибоначчи занимает O(2^n) :(
10.
Чему равно временная сложность рекурсивного алгоритма вычисления чисел Фибоначчи?
11.
Чему равно временная сложность алгоритма вычисления чисел Фибоначчи c использованием переменных?
Чему равно временная сложность алгоритма вычисления чисел Фибоначчи c использованием массива? Помогите пожалуйста
Временная сложность обычного рекурсивного алгоритма - экспоненциальная O(2^n).
Временная сложность итеративного решения (вероятно который подразумевался под фразой "с использованием пременных") - линейная O(n).
Временная сложность рекурсивного алгоритма с мемоизацией с использованием массива - линейная O(n).
Front-end Science спасибо бро. С меня лайкос и подписка
с рекурсией чуть комп не завис пришлось перезапуск делать)...раз как то зацикливал систему даже перезапустить не получалось только отключить смог... интересно есть ли какая нибуть команда чтоб сразу отменить зациклившийся цикл???
:) Бывает! Можно убить процесс в таск менеджере или в терминале.
Последовательность Фибоначчи так же используется в изобразительном искусстве для составления гармоничной композиции картины или фотоснимка - золотое сечение. Этот Фибоначчи явно что то знал :)
Это точно! Так и есть
Прорешал всеми тремя методами (первоначально решил рекурсией). Заинтересовало сколько времени уходит на решение каждым методом, так как рекурсией число больше 40 вычислять уже долго.
В итоге сделал следующее:
function fibonachi(num) {
if (num
Спасибо за видео! Но по поводу 10 элемента, он ведь 34, return(num-1) нужно делать
Есть разные мнения что считать первым элементом последовательности. Некоторые считают с 0 а некоторые с 1. Так что тут каждый может подстроиться как ему нужно.
Самое оптимальное решение это с помощью тождества Кнута
console.log(fibonacciShort(0)); // 1
console.log(fibonacciShort(1)); // 1
console.log(fibonacciShort(2)); // 1
console.log(fibonacciShort(3)); // 2
console.log(fibonacciShort(4)); // 3
console.log(fibonacciShort(5)); // 5
Не очень хорошо получается🙃
Не смотрел остальные, но первое решение не пройдет тест на F(0) или F(1)
А почему не пройдет?
@@frontendscience потому что f(0) = 0, а в вашем решении оно будет равно 1
можно конечно добавить простенькую проверку на 1 и 0, но тем не менее
@@vty4261 Ну 1е и 3е решение - как раз пройду проверку на f(0) - а вот второй вариант действительно надо подправить начальные 2 числа и вывод результата чтобы он работал и с f(0) тоже.
@@smashno да, все верно, я неправильно написал, спасибо за поправку
кто не понимает, тот не станет сеньйором?
Как только поймет, сразу станет, ага 😜
я сюда зашел только потому что САМ не могу решить эту задачку
И как? Уже теперь можешь решить? :)
@@frontendscience нет, я реально тупой
//Java - O(1)
public static int fibonacci(int n) {
return (int) (Math.floor(((Math.pow(((1 + Math.sqrt(5)) / 2), n)) - (Math.pow(((1 - Math.sqrt(5)) / 2), n))) / Math.sqrt(5)));
}